How many resistors are needed?

I was able to find a bound for the number of resistors required.

Given a resistance $\frac{a}{b}$, at least $n$ resistors are required where $\phi_{n+2}$ is the first Fibonacci number greater than or equal to $a+b$.

Here's my thinking process and proof:

Naturally I started out by listing things to see if I could find a pattern.

\begin{align*} n&=1 &&1/1\\ n&=2 &&1+1=2/1\\ & &&1\oplus1 = 1/2\\ n&=3 &&1+(1+1)=3/1\\ & &&1+(1\oplus1) = 3/2\\ & &&1\oplus(1+1) = 2/3\\ & &&1\oplus(1\oplus1) = 1/3\\ n&=4 &&1+(1+(1+1)) = 4/1\\ & &&1+(1+(1\oplus1)) = 5/2\\ & &&1+(1\oplus(1+1)) = 5/3\\ \end{align*}

At this point I got bored, but I noticed a curious pattern: Let $R_n$ be the set of possible resistances for $n$ resistors. Let $M_n = \max\{a+b: a/b \in R_n\}$ It appears to be the case that the $n$th Fibonacci number, $\phi_n$, is equal to $M_{n-2}$. Define Max($R_n$) to be the subset of $R_n$ such that $a/b \in \mathrm{Max}(R_n)$ if $a+b = M_n$. Then the maximal resistances for $n$ resistors are any resistances in Max($R_n$). It can also be observed that Max($R_n$) always seems to have two elements, and these are of the form $\frac{\phi_{n+1}}{\phi_{n}}$ and $\frac{\phi_{n}}{\phi_{n+1}}$. (Note that the first "pattern" is a direct consequence of this.)

In other words, (if this is true), given a resistance $a/b$, at least $n$ resistors are required where $\phi_{n+2}$ is the first Fibonacci number greater than or equal to $a+b$.

Claim: Given $n$ resistors, the only two maximal resistances are of the form $\frac{\phi_{n+1}}{\phi_{n}}$ and $\frac{\phi_{n}}{\phi_{n+1}}$.

Proof

Note that from here on I will use $v(R) = a+b$, where $R = a/b$.

Base case: trivial.

Inductive step: Let $k\in \mathbb{N}$. Suppose the only maximal resistances for 1 through $k$ resistors have been of the form $\frac{\phi_{k+1}}{\phi_{k}}$ and $\frac{\phi_{k}}{\phi_{k+1}}$. It follows that for $k+1$ resistors, $R = \frac{\phi_{k+2}}{\phi_{k+1}}$ can be obtained, as $\frac{\phi_{k+2}}{\phi_{k+1}} = 1\oplus\frac{\phi_{k}}{\phi_{k+1}}$. Similarly the reciprocal can be obtained. Now it must be shown that $\frac{\phi_{k+2}}{\phi_{k+1}}$ and $\frac{\phi_{k+1}}{\phi_{k+2}}$ are maximal.

Suppose $R_k = a/b$ is a resistance such that $a+b+n = \phi_k+\phi_{k+1}, n > 0$. If $b\leq \phi_{k+1}$ and $a\leq \phi_{k+1}$ then $1+a/b = (b+a)/b = (\phi_{k+2}-n)/b$, so $v(1+a/b) < v(\frac{\phi_{k+2}}{\phi_{k+1}})$. Similarly, $1\oplus a/b = a/(b+a) = a/(\phi_{k+2}-n)$ and we get $v(1\oplus a/b) < v(\frac{\phi_{k+2}}{\phi_{k+1}})$. Now suppose $a > \phi_{k+1}$ or $b > \phi_{k+1}$. This is actually impossible, as $b = \alpha + \beta$ and $a = \eta + \mu$ for some $\alpha/\beta$ and $\eta/\mu$ resistances for $k-1$ resistors. However, by the inductive hypothesis, this sum is capped at $\phi_{k+1}$. There is a second way that a resistance $R_{k+1}$ can form: Rather than adding a resistance of 1 to $R_k$, this is adding two resistances $R_{m}$ and $R_{n}$ so that $m+n=k+1$. Using similar reasoning to the special case above and the fact that $\phi_s\phi_t < \phi_{s+t}$, one can prove that $v(R_{m}+R_{n}) < v(\frac{\phi_{k+2}}{\phi_{k+1}})$. It follows that for $k+1$ resistors, there are exactly two maximal resistances, given by $\frac{\phi_{k+2}}{\phi_{k+1}}$ and $\frac{\phi_{k+1}}{\phi_{k+2}}$.

Since the other day I've played with resistors, and made a program similar to Martin's to enumerate all possibilities that ensure the minimum number of resistors.

You can download the result file there $\to$ All rationnals for $n\le 12$

Also from this list, I've drawn a picture of the rationnals that share the same $n$. It is quite impressive the see how the bubble expands, but the border of this bubble seems to have an asymptotic behaviour already.

As you can see it is hollow, because many rationnals are not reached for such a low $n$, eventually all the white is to be filled with a superior rank color.

For a better rendering you can download directly the XPM file.

Some convenient notational framework
For the formal handling I' propose a slightly different notation:

1. two resistors with $r_1$ and $r_2$ Ohm in serie : $ r_1 \oplus r_2$
2. two resistors with $r_1$ and $r_2$ Ohm parallel : $ r_1 || r_2$

For convenience (reduction of parentheses) we assume that "$||$" binds stronger than "$ \oplus $"

3. two or more equal resistors in serie : $ \,^n r $
4. two or more equal resistors parallel : $ \,_n r $

where if the iteration-number $n=1$ we have $ \,^1 r= \,_1 r = r$ . We let the notation $ \,^n r$ and $ \,_n r$ bind stronger than $||$ and $\oplus$. Of course numerically $\,^n r $ with a resistor of $r=1 \; \Omega$ evaluates to $ n \cdot r = n \; \Omega $, $\, _n r$ evaluates to $1/n \cdot r = 1/n \;\Omega$ .

Some basic algebraic rules on equal resistors are

5. $ \,^m r \oplus \,^n r = \,^{n+m} r $ and
6. $ \, _m r|| \, _n r = \,_{n+m} r $ ,
7. $ \,_m ( \,^n r) = \,^n ( \,_m r) = \,_m ^n r \quad $ where also $\,_1 ^n r = \, ^nr \quad $ and $\,_n ^1 r = \, _nr \quad $ and finally
8. $ \,_n ^m r || \,_p ^q r = \,_{qn+pm} ^{m q} r \qquad $ and $ \qquad \,_n ^m r \oplus \,_p ^q r = \,_{n p} ^{mp + qn} r $
9. For some partial construct $ \, ^a_b r $, the upper bound for the needed resistors is $a \cdot b$ and for concatenation of such constructs their sum. By expansion of $ \, ^a_b r $ into concatenated subconstructs that number can in most cases be reduced; a standard (=safe) algorithm is that of representation of $\frac ab $ by its continued fraction; for sometimes even better solutions see some examples below.

A nice conjugay: $ \,^m r || \,^n r = {1 \over \, _m r \oplus \, _n r} $

Some examples show possible improvement over continued-fraction solutions
Three examples:

1. Let $x=5/6 = {2 + 3\over 2 \cdot 3}$ and of course we have always $r=1 \text{ Ohm} $ . The continued fraction (="Euclidean"?) gives $\text{contfrac}(x) = [0,1,5]$ so we have $x = 1/(1 + 1/5) $ and thus $$x = r || \, ^5 r $$ and we need $6$ resistors, which is not optimal.
   A better configuration is by $ 5/6 = 1/2 + 1/3 = \,_ 2 r \oplus \, _3 r$ so we need $5$ resistors. $$ $$

2. Let $x=8/15 = {3+5\over 3 \cdot 5}$ and again $r=1 \text{Ohm} $ The continued fraction gives $\text{contfrac}(x) = [0,1,1,7]$ so we have $x = 1/(1 + 1/(1+1/7)) $ and thus $$x = r||(r \oplus \, _7r ) $$ and we need $9$ resistors, which is not optimal.
   A better configuration is by $ 8/15 = 1/3 + 1/5 = \,_3 r \oplus \, _5 r $ so we need $8$ resistors.
   $$ $$

3. Let $x=103/165 = {3 \cdot 5 + 5\cdot 11 + 11 \cdot 3\over 3 \cdot 5 \cdot 11} $
   The continued fraction gives $\text{contfrac}(x) = [0, 1, 1, 1, 1, 1, 20]$ so we have $x = 1/(1 + 1/(1+ 1/(1+1/(1+1/20)))) $ and thus $$x = r || ( r \oplus ( r || ( r \oplus r || \,^{20} r )))$$ and we need $25$ resistors , which is not optimal.
   A better configuration is by $ x = 1/3 + 1/5 + 1/11 = \,_3 r \oplus \, _5 r \oplus \, _{11} r$ so we need only $19$ resistors. update: I get by $$ x= \, _3 r \oplus \, _3 r || ( \,^2 r \oplus \, _3 r || \, ^2 r ) $$ an even better solution with only $13$ resistors... Hmmm. It is the following sum of two shorter and much smoother continued fractions: $$ x = \frac13 + {1 \over 3 + {1\over 2+ {1\over 3+\frac12} } } = [0;3] + [0;3,2,3,2] $$

1. Let $$R_1 = [r] $$ be the 1-element vector of possible configurations with one resistor.
2. Then let $$R_2 = [\,^2 r, \, _2 r] $$ be the two-element vector of possible configurations of two resistors.
   We can understand that result as concatenation of the vectorproduct $ R_1 \times_\oplus R_1 $ one time with the operation $ \oplus$ and one time $ R_1 \times_{||} R_1 $ with the operation $||$ . So full expanded we have $$ R_2 = [ r \oplus r , r || r ]$$ with the already given two resulting elements.

This latter definition lets us generalize to get a full tree:

3. Let analoguously $$\hat R_3 = [R_2 \times_\oplus R_1 , R_2 \times_{||} R_1] $$ Then let us assume that this is sorted and that doublet elements are removed to occur only once such that effectively $$ \begin{array}{rl}R_3 &= [\,^2 r \oplus r, \, _2 r \oplus r, \, ^2 r || r, \, _2 r||r ] \quad \text{or}\\ R_3 &= [\,^3 r, \, ^3_2 r, \, ^2_3 r, \, ^1_3 r ] = [\frac31, \frac32 , \frac23 , \frac13 ] \end{array} $$

The key to the full tree is now, that for $R_4$ all possbible combinations must be collected, which means

4. $$ \begin{array} {rl} \hat R_4 &= [ & R_3 \times_\oplus R_1 , R_3 \times_{||} R_1 , \\ & & R_2 \times_\oplus R_2 , R_2 \times_{||} R_2 ] \\ \end{array}$$
   and $R_4$ is then the sorted and shortened version of $\hat R_4$ with the elements $$ R_4 = [4, \frac52, \frac53, \frac43, 1, \frac34, \frac35, \frac25, \frac14] $$ The difference to earlier answers (with a sketch of the partial tree, for instance by @zwim) is that there we have only $$ \begin{array} {rl} \hat R_4 &= [ & R_3 \times_\oplus R_1 , R_3 \times_{||} R_1 ] \\ \end{array}$$ and so the second part ($R_2 \times R_2$)is missing there.

5. Of course $$ \begin{array} {rl} \hat R_5 &= [ & R_4 \times_\oplus R_1 , R_4 \times_{||} R_1 , \\ & & R_3 \times_\oplus R_2 , R_3 \times_{||} R_2 ] \\ \hat R_6 &= [ & R_5 \times_\oplus R_1 , R_5 \times_{||} R_1 , \\ & & R_4 \times_\oplus R_2 , R_4 \times_{||} R_2 ] \\ & & R_3 \times_\oplus R_3 , R_3 \times_{||} R_3 ] \\ \end{array}$$ and so on ....

I save myself the draw of the (complicated) tree of partial constructions, someone else might do that. But it is to be noted that in this full tree various results occur multiple and we can search for the earliest occurence / the occurence with least number of required resistors. Note, that for instance in $R_4$ we find the element $1r$ which has there the configuration $ (r \oplus r) || (r \oplus r) = \,^2 r || \,^2 r$ having 4 resistors, but of course that element occurs already in $R_1$ and has its earliest occurence there.

I don't see, how one could formalize that earliest occurence in the tree /that "least number of resistors needed for some result" furtherly...

[appendix] After we remove from $R_m$ all that which occur in earlier $R_k, k \lt m$ to get $T_m$ we get the set of cardinalities $ [@T_1,@T2,@T_3,...] = [ 1, 2, 4, 8, 20, 42, 102, 250, 610, 1486, 3710, 9228, 23050, 57718,...] $ which has already been found by @martin and also is as sequence in OEIS: see "A051389 Rational resistances requiring at least n 1-ohm resistors in series or parallel (2006)" which provides also links to more related information (a recent update was from 20 Mar, just a couple of days ago).

An ordered list for all reachable fractional resistance-values by that vectors $T_k$ (which have duplicates with higher number of resistors removed) shows the following picture (ironically I've written "transistors" instead of "resistors", but that's caused by my old-time education in electronics...)

Just an observation:

For fractions $<1$ this differs from the Euclidean algorithm initially for $(n-1)/n$:

Euclidean:

ea[frac_] := Tr@ContinuedFraction[1/y[{frac}]];

OP:

x[z_List] := Total@z;
y[z_List] := (Times @@ z)/Total[Times @@@ Subsets[z, {Length@z - 1}]];
fun[n_] := ToExpression /@ StringReplace[
ToString /@ Groupings[Array[1 &, n], 2], {"{" -> "g[", 
 "}" -> "]"}];
replaceHeads[expr_, h_, new_] := ReplacePart[expr, Thread[Position[expr, h] -> new]];
foo[n_] := Sort@DeleteDuplicates[ToExpression@
   StringReplace[ToString[#], {"[" -> "@{", "]" -> "}"}] & /@ 
   Flatten[Table[replaceHeads[#, g, t] & /@ fun@n, {t, Tuples[{x, y}, {n - 1}]}]]];
h1[frac_] := (n = 1; While[True, If[MemberQ[foo[n], frac], Break[]]; n++]; n);
i1[n_] := h1[#/n] & /@ Range[n - 1];

test:

m = 9;
ea /@ Range@m // Grid
i1 /@ Range@m // Grid

$\begin{array}{cccccccc} \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 2 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 3 & 3 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 4 & 2 & 4 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 5 & 4 & 4 & 5 & \text{} & \text{} & \text{} & \text{} \\ 6 & 3 & 2 & 3 & 6 & \text{} & \text{} & \text{} \\ 7 & 5 & 5 & 5 & 5 & 7 & \text{} & \text{} \\ 8 & 4 & 5 & 2 & 5 & 4 & 8 & \text{} \\ 9 & 6 & 3 & 6 & 6 & 3 & 6 & 9 \\ \end{array}$

OEIS A049834

$\begin{array}{cccccccc} \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 2 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 3 & 3 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 4 & 2 & 4 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 5 & 4 & 4 & 5 & \text{} & \text{} & \text{} & \text{} \\ 6 & 3 & 2 & 3 & \color{red}5 & \text{} & \text{} & \text{} \\ 7 & 5 & 5 & 5 & 5 & \color{red}5 & \text{} & \text{} \\ 8 & 4 & 5 & 2 & 5 & 4 & \color{red}7 & \text{} \\ 9 & 6 & 3 & 6 & 6 & 3 & 6 & \color{red}7\\ \end{array}$

where the above corresponds with the minimal number of resistors needed for the following fractions:

$ \begin{array}{cccccccc} \frac{1}{2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \frac{1}{3} & \frac{2}{3} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \frac{1}{4} & \frac{1}{2} & \frac{3}{4} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \frac{1}{5} & \frac{2}{5} & \frac{3}{5} & \frac{4}{5} & \text{} & \text{} & \text{} & \text{} \\ \frac{1}{6} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{5}{6} & \text{} & \text{} & \text{} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{7} & \frac{4}{7} & \frac{5}{7} & \frac{6}{7} & \text{} & \text{} \\ \frac{1}{8} & \frac{1}{4} & \frac{3}{8} & \frac{1}{2} & \frac{5}{8} & \frac{3}{4} & \frac{7}{8} & \text{} \\ \frac{1}{9} & \frac{2}{9} & \frac{1}{3} & \frac{4}{9} & \frac{5}{9} & \frac{2}{3} & \frac{7}{9} & \frac{8}{9} \\ \end{array} $

Table of differences

Table of differences between Euclidean Algorithm and OP:

for corresponding fractions up to $49/50$. Note the repeating pattern in each column. This does not hold further down the table however where it starts to exhibit minor changes. The asterists use $>12$ resistors. It is likely the left hand "clump" of asterisks are all $0$ (ie, equivalent to the EA).

Here is a file showing all possible fractions $<1$ generated by up to $12$ resistors, with an example for each one. The notation used is $x(1,1)$ for series and $y(1,1)$ for parallel. Corresponding Mathematica functions for x and y can be found above.

Case for (n-1)/n

$(n-1)/n$ clearly differs the most from EA. From the data gathered, the minimal number of resistors needed for $(n-1)/n\approx \frac{5}{2}\log (n)$:

examples of f((n-1)/n) using minimal # resistors

$ 1 \oplus 1 \\ (1+1)\oplus 1 \\ ((1+1)+1)\oplus 1 \\ (((1+1)+1)+1)\oplus 1 \\ ((1 \oplus 1)\oplus 1)+(1\oplus 1) \\ (1+1)\oplus ((1 \oplus 1)+1) \\ (((1 \oplus 1)+1)\oplus(1\oplus 1))+ (1 \oplus 1) $

$(n-1)/n$ differs considerably from Euclidean algorithm as $n$ get larger. eg $26/27$ can be made with only $8$ resistors: $(1+1)\oplus (((1+1)\oplus((1\oplus 1)+1))+1)$

Since this method was suggested in the comments, I'm going to present it, but this is a restriction on the OP problem, in that we consider only adding a resistor either in serie, either in parallel to an existing circuit built in the same way. Thus it is far from representing all possibilities.

If there $n$ resistors then there are $2^n$ arrangements of resistors, basically they are given by the binary developpement where for instance $+$ is associated to $1$ and $\oplus$ to $0$.

It behaves as an arithmetic stack.

Example let's look at shayne2020 listing for $n=3$.

$\begin{array}{c|c|c|c|} \mathbb Q & \text{circuit} & \text{arithm stack} & \text{binary} \\ \hline 1/3 & (1\oplus 1)\oplus 1 & +\oplus\oplus 111 & 100\\ 3/2 & (1\oplus 1)+1 & +\oplus+111 & 101\\ 2/3 & (1+1)\oplus 1 & ++\oplus111 & 110\\ 3/1 & (1+1)+1 & +++111 & 111\\ \end{array}$

This correspond to the well known bijection from $\mathbb N\to\mathbb Q^+$ which has a representation as the Stern-Brocot tree : Stern-Brocot Tree

The tree also has this interesting property : Fractions on a Binary Tree II

It is not too difficult to prove that our resistors verify these properties.

Remember on the left branch of a subtree we process a $0$ in the binary developpement so this correspond to $\oplus$ operation. While on the right branch of the tree, we process a $1$, this is the $+$ operation.

Let's start from a fraction $a/b$ :

• on left branch of the tree we have $\frac ab\oplus 1=\frac{1}{\frac ba+1}=\frac{1}{\frac{a+b}{a}}=\frac{a}{a+b}$
• on right branch of the tree we have $\frac ab+1=\frac{a+b}{b}$

Note also that the bijection can be explicited :

$\begin{cases} \displaystyle g(x)=\frac{1}{1+2\lfloor x\rfloor-x} \\ \\ f(n)=\underbrace{g \circ g \circ g\ \circ...\circ\;g\;}_{\text{n times}}(0)=g^{(\circ^n)}(0) \end{cases}$

The case of more complex circuits (i.e. other parenthesizations, and there are Catalan numbers many of them) still need to be adressed. And from Martin's results it seems they lead to shorter circuits.

So even if this idea seems nice because it offers a constructive way to reach every rational resistor, it does not realizes the minimum in term of needed resistors.