45
$\begingroup$

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:

enter image description here

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]).$$

$\endgroup$
  • 7
    $\begingroup$ The Calkin-Wilf tree may be relevant -- its basic operations correspond to "put one in series withe everything so far" and "put one in parallel with everything so far". $\endgroup$ – Henning Makholm Feb 25 '17 at 12:39
  • 5
    $\begingroup$ It is, of course, not true that combinations of (in series) or (in parallel) are the only ways of to constructing a given fraction resistance R. A general network of resistors doesn't have to be in that way. $\endgroup$ – Han de Bruijn Mar 21 '17 at 10:33
  • $\begingroup$ "Euclidean algorithm" is basically this: If the goal $x$ is larger than 1 ohm, connect 1 ohm in series and find the representation of $x-1$. If $x<1$, connect 1 ohm in parallel and find the representation of $1/ (\frac {1}{x}-1)$. You proved the strategy when $x<1$ might be wrong. But is there ever a case that the strategy when $x>1$ might be ever wrong? $\endgroup$ – didgogns Mar 23 '17 at 16:26
  • $\begingroup$ OMG. Just take the reciprocal of 5/6. $\endgroup$ – LRDPRDX Mar 23 '17 at 16:31
  • $\begingroup$ the minimum for a given resistance ($R$) will be the same for the corresponding conductance ($G=1/R$) $\endgroup$ – G Cab Mar 23 '17 at 23:03
9
+50
$\begingroup$

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}}$.

$\endgroup$
  • $\begingroup$ Firstly, there are some typos in your text. Secondly, why did you write this $$ $\endgroup$ – LRDPRDX Mar 28 '17 at 3:48
  • $\begingroup$ Secondly, according to your direction of reasoning, you should say that ''In other words, ..., at most $n$ resistors ...'' instead of ''...at least''. $\endgroup$ – LRDPRDX Mar 28 '17 at 4:26
  • $\begingroup$ Thirdly, it seems like you will get the bounty because I have to give it someone. $\endgroup$ – LRDPRDX Mar 28 '17 at 4:29
  • $\begingroup$ Rather than answering the question I've just created a lower bound, but I'm interested in this too! Once your bounty ends I'll add a bounty as well. $\endgroup$ – Harambe Mar 28 '17 at 4:36
  • $\begingroup$ I do not understand the implication from the 1st part of your answer begin with ''Let $M_n :=$" to the part begin with ''In other words...". Please, explain. $\endgroup$ – LRDPRDX Mar 28 '17 at 4:47
6
$\begingroup$

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.

enter image description here


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

$\endgroup$
5
$\begingroup$

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 $"

  1. two or more equal resistors in serie : $ \,^n r $
  2. 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

  1. $ \,^m r \oplus \,^n r = \,^{n+m} r $ and
  2. $ \, _m r|| \, _n r = \,_{n+m} r $ ,
  3. $ \,_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
  4. $ \,_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 $
  5. 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] $$


Method for creation of the full tree of resistors-configurations
One remark on the example-trees in the other answers.

  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:

  1. 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

  1. $$ \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.

  2. 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...)
picture

$\endgroup$
  • $\begingroup$ nice - I think half the problem is that we are all working with different notations - your 13 resistor setup for me is $a(b(1, b(1, 1)), b(b(1, b(1, 1)), a(a(1, 1), b(b(1, b(1, 1)), a(1, 1)))))$ where $a(x,y)=x+y$ and $b(x,y)=xy/(x+y)$. $\endgroup$ – martin Mar 28 '17 at 14:39
  • $\begingroup$ when you say the above method, do you mean the factoring one? How did you get the 13 resistor one BTW? $\endgroup$ – martin Mar 28 '17 at 14:49
  • $\begingroup$ @martin : I've just tried... I looked, whether the value x minus the leading $1/3$ would have a nicer decomposition. So I just found empirically that the continued fraction of $1/5 + 1/11$ has a set of very nice small coefficients. $\endgroup$ – Gottfried Helms Mar 28 '17 at 15:06
  • $\begingroup$ yes - I meant the "factoring method", better named the "construction-by-primefactors" method or the like. $\endgroup$ – Gottfried Helms Mar 28 '17 at 15:08
  • 1
    $\begingroup$ your answer still gives a very good lower bound. Consider the fraction $385774678978047295113064712800727674369526436922217581784412894295689697835549/198962376391690981640415251545285153602734402721821058212203976095413910572270$, EA gives $91803$ resistors, where your method gives $3831$. $\endgroup$ – martin Mar 28 '17 at 15:15
3
$\begingroup$

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:

enter image description here

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)$:

enter image description here

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)$

$\endgroup$
  • $\begingroup$ This seems really interesting, but can you explain a little more what you are doing. To what do the tables above correspond ? $\endgroup$ – zwim Mar 28 '17 at 10:35
  • 1
    $\begingroup$ @zwim - updated now $\endgroup$ – martin Mar 28 '17 at 10:47
  • $\begingroup$ What about $n=103/165$ by Euclidean and by using your tables? I get 25 resistors by EA and 19 resistors by optimal configuration... $\endgroup$ – Gottfried Helms Mar 28 '17 at 11:57
  • $\begingroup$ @GottfriedHelms I can't compute that high with current algorithm! I am basically calculating exhaustively for each number of resistors - giving 0,2,8,40,224,1344,8448,54912,366080,2489344… number of possible permutations. $\endgroup$ – martin Mar 28 '17 at 12:03
  • 1
    $\begingroup$ I factor $165 = 3 \cdot 5 \cdot 11$ and find that also $103 = 3 \cdot 5 + 3 \cdot 11 + 5 \cdot 11$ so I get $103/165 = 1/3 + 1/5 + 1/11$. (Actually I'd constructed the example this way: taking some primefactors but making sure that there does not occur cancelling in the sum-formula for the reciprocals) $\endgroup$ – Gottfried Helms Mar 28 '17 at 12:13
2
$\begingroup$

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

Stern Brocot tree

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ I've given an example how to complete your graphical tree in my answer above. It is near the end with the example of the 4'th row defined by $R_4$ $\endgroup$ – Gottfried Helms Mar 29 '17 at 4:18
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I mentioned the Euclidean algorithm in the description which is closely related to CF and an example when it falls. $\endgroup$ – LRDPRDX Feb 25 '17 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.