How many resistors are needed? I was told about the following problem. Suppose you have infinite number of resistors with only value 1$\Omega$. Question is 


  What minimal number of 1$\Omega$-resistors is needed to construct given fraction resistance $R$, i.e. $R\in \mathbb{Q}_+$.


Note that you can connect two resistors ($R_1$ and $R_2$) in two ways: parallel and series. The resulting resistance ($R_p$ and $R_s$ respectively) in those cases are:
$$R_s = R_1 + R_2$$
$$R_p = R_1 \oplus R_2 = \frac{1}{\frac{1}{R_1}+\frac{1}{R_2}},$$
where we introduced $\oplus$-operation in order to simplify notes. NOTE: only schemes which are able to be written in the form:
$$(... 1 + (1\oplus 1) ... )$$
are allowed. For example, this is not allowed:



If you know how to formulate this rule better, please, say.



For example, you can use the Euclidean algorithm. 
$$\frac56 = \frac{1}{\frac65}=\frac{1}{1+\frac15} = 1 \oplus 5,$$
so you needed 6 resistors because
$$5 = \sum_{k=1}^{5}1$$
But it was not the minimum number of resistors because, for example,
$$\frac56 = \frac12 + \frac13 = (1\oplus 1)+(1\oplus 1\oplus 1),$$
where it is enough to use only 5 resistors.



I think that Euclidean algorithm often solves the problem. More over, it is needed to consider only one "half of $\mathbb{Q}_+$", for the other half it is enough to replace +'s by $\oplus$'s and vice-versa.



The one who told me about this problem adhered to the following notations.
$$[1,1]\quad \text{for}\quad 1\oplus 1.$$
$$(1,1)\quad \text{for}\quad 1 + 1,$$
so our previous example looks like
$$[1,(1,1,1,1,1)]\quad \text{and}\quad ([1,1,1],[1,1]).$$
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&amp;=1 &amp;&amp;1/1\\
n&amp;=2 &amp;&amp;1+1=2/1\\
&amp; &amp;&amp;1\oplus1 = 1/2\\
n&amp;=3 &amp;&amp;1+(1+1)=3/1\\
&amp; &amp;&amp;1+(1\oplus1) = 3/2\\
&amp; &amp;&amp;1\oplus(1+1) = 2/3\\
&amp; &amp;&amp;1\oplus(1\oplus1) = 1/3\\
n&amp;=4 &amp;&amp;1+(1+(1+1)) = 4/1\\
&amp; &amp;&amp;1+(1+(1\oplus1)) = 5/2\\
&amp; &amp;&amp;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 &gt; 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) &lt; 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) &lt; v(\frac{\phi_{k+2}}{\phi_{k+1}})$. Now suppose $a &gt; \phi_{k+1}$ or $b &gt; \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 &lt; \phi_{s+t}$, one can prove that $v(R_{m}+R_{n}) &lt; 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}}$.
I like the use of the "bracket - parenthesis" notation, but I will add following feature, namely to write $[3]$ for $[1,1,1]$ and $(5)$ for  $(1,1,1,1,1)$ likewise. I'd like to draw the attention of how continued fractions can be of use. Suppose we were to build a resistance of $\frac{5}{7} \Omega$. Brute force shows you that you can build this resistance as $([7][7][7][7][7])$, using $35$ resistors. If we write $\frac{5}{7}$ as a continued fraction we obtain: 
$$
5/7 = 0+\frac{1}{1+\frac{1}{2+\frac{1}{2}}}
$$ Which shows that the resistance can be built as $[1,((2),[2])]$ using only $5$ resistances. It is not sure this method is really optimal, and probably poses the same logistic problem as the travelling salesman problem.