# Total resistance from unit resistors

This problem is based on, A337517, the most recent OEIS sequence with the keyword "nice".

$$\a(n)\$$ is the number of distinct resistances that can be produced from a circuit with exactly $$\n\$$ unit resistors.

The sequence begins 1, 2, 4, 9, 23, 57, 151, 427, 1263, 3823, 11724, 36048, 110953, 342079.

The goal of this challenge is to write a program that takes a positive integer n and outputs the possible resistances that can be formed with $$\n\$$ unit resistors, written as fractions (or floats, ordered pairs representing fractions, or in another essentially similar format) as in the following:

f(3) = [3/1, 3/2, 2/3, 1/3]
= [(3,1), (3,2), (2,3), (1,3)]
= [[3,1], [3,2], [2,3], [1,3]]


This is a challenge, so shortest code wins. Your program needs to be able to handle inputs up to $$\n = 6\$$ on TIO.

### Examples

• With $$\n = 1\$$ resistor, the only possibility is a circuit with $$\1 \Omega\$$ total resistance.
• With $$\n = 2\$$ resistors, there are only $$\a(2) = 2\$$ possibilities:
1. Resistors in sequence resulting in $$\2 \Omega\$$ total resistance.
2. Resistors in parallel resulting in $$\\frac 12 \Omega\$$ total resistance.
• With $$\n = 3\$$ resistors, there are $$\a(3) = 4\$$ possibilities with resistances $$\3 \Omega, \frac 32 \Omega, \frac 23 \Omega\$$, and $$\\frac 13 \Omega\$$:
• I think it's worth pointing out that not all circuits can be formed by recursively taking components in parallel or series. I think this means we can't necessarily obtain the resistances using $n-1$ applications of $s(a,b)=a+b$ and $p(a,b)=ab/(a+b)$.
– xnor
Commented Nov 3, 2020 at 0:55
• I see the series/parallel circuit vs general circuit distinction is discussed on the OEIS page, comparing to other OEIS sequences for limited circuits. The table shows that $n=6$ suffices to distinguishes circuits without only series and parallel subcomponents, which give only 53 of the 57 possible values. But adding bridges gives matching values until $n=8$, so answers testing only up to $n=6$ should be careful that they indeed compute the full set of resistances for all $n$.
– xnor
Commented Nov 3, 2020 at 1:05
• Wondering if there's a Mathematica builtin for this. Commented Nov 3, 2020 at 3:37
• @user—I've updated the prompt to allow the use of floats. Commented Nov 3, 2020 at 19:15
• In order to be at least theoretically correct, one should implement generating arbitrary graph circuits and computing their total resistances by Kirchhoff's laws, as illustrated in this pdf. (And it contains a full-page worth of Mathematica code.) Commented Nov 3, 2020 at 23:48

# Python 2, 734 bytes

import fractions as F,itertools as I
r=range
s=set
P=lambda G,p=[0]:[x for a,b in G if(p[-1]==a)*(1-(b in p))for x in(P(G,p+[b])if b-1else[p+[b]])]
def R(G):
G+=tuple((b,a)for a,b in G);B=s(b for a,b in G);n=1+max(B)
if s(G)-s(x for p in P(G)for e in zip(p,p[1:])for x in[e,e[::-1]])or len(B)-n:return 0
M=[[0]*(n+1)for _ in B];M[0][0],M[0][n],M[1][1]=[F.Fraction(1)]*3
for a,b in G:M[a][a]+=a>1;M[a][b]-=a>1
for i in r(n):
for j in r(i,n):
if M[j][i]:break
M[i],M[j]=M[j],M[i];M[i]=[x/M[i][i]for x in M[i]]
for j in r(n):M[j]=[a-(j!=i)*b*M[j][i]for a,b in zip(M[j],M[i])]
return 1/sum(M[a][n]-M[b][n]for a,b in G if a==0)
f=lambda n:s(map(R,I.combinations_with_replacement([(a,b)for a in r(n)for b in r(a,n+1)],n)))-s([0])


Try it online!

I probably missed a bunch of golfing opportunities, but it's under 1000 bytes at least! I could have used SymPy for row reduction but went for a pure python answer instead.

Graphs are represented as lists of edges.

P generates all paths from vertex 0 to 1, used to determine if any resistors are unused (if they don't appear in any path).

R accepts a graph and returns the resistance between vertex 0 and 1, or 0 if the graph is invalid (it has unused edges/resistors or unused vertices). It does this by solving a system of linear equations of the voltages at each vertex.

f enumerates all graphs and generates the distinct resistances as a set. 0 from invalid graphs is removed.

Here are the results for 1 to 6 (as output by the footer in TIO):

f(1) = set([Fraction(1, 1)])
f(2) = set([Fraction(1, 2), Fraction(2, 1)])
f(3) = set([Fraction(3, 2), Fraction(3, 1), Fraction(1, 3), Fraction(2, 3)])
f(4) = set([Fraction(1, 4), Fraction(3, 4), Fraction(4, 1), Fraction(5, 2), Fraction(1, 1), Fraction(4, 3), Fraction(2, 5), Fraction(3, 5), Fraction(5, 3)])
f(5) = set([Fraction(3, 8), Fraction(7, 4), Fraction(4, 7), Fraction(5, 1), Fraction(5, 8), Fraction(7, 3), Fraction(5, 6), Fraction(2, 1), Fraction(3, 7), Fraction(8, 5), Fraction(1, 2), Fraction(6, 7), Fraction(7, 6), Fraction(1, 5), Fraction(1, 1), Fraction(5, 4), Fraction(4, 5), Fraction(7, 5), Fraction(6, 5), Fraction(7, 2), Fraction(2, 7), Fraction(8, 3), Fraction(5, 7)])
f(6) = set([Fraction(1, 2), Fraction(5, 9), Fraction(2, 1), Fraction(1, 3), Fraction(8, 13), Fraction(6, 1), Fraction(1, 1), Fraction(7, 12), Fraction(3, 11), Fraction(13, 5), Fraction(12, 5), Fraction(3, 1), Fraction(1, 6), Fraction(7, 11), Fraction(10, 3), Fraction(3, 4), Fraction(11, 13), Fraction(11, 10), Fraction(4, 9), Fraction(2, 9), Fraction(11, 5), Fraction(10, 7), Fraction(3, 10), Fraction(5, 6), Fraction(3, 2), Fraction(13, 7), Fraction(13, 11), Fraction(7, 10), Fraction(7, 9), Fraction(13, 8), Fraction(10, 9), Fraction(5, 4), Fraction(11, 8), Fraction(5, 11), Fraction(4, 5), Fraction(8, 11), Fraction(6, 11), Fraction(5, 13), Fraction(9, 10), Fraction(2, 3), Fraction(11, 4), Fraction(6, 5), Fraction(9, 4), Fraction(11, 7), Fraction(7, 13), Fraction(13, 6), Fraction(11, 3), Fraction(4, 3), Fraction(6, 13), Fraction(12, 7), Fraction(9, 5), Fraction(10, 11), Fraction(9, 7), Fraction(9, 2), Fraction(5, 12), Fraction(11, 6), Fraction(4, 11)])