15
\$\begingroup\$

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\$:
    1. Resistors in series: 3 Ohms
    2. Resistors in series, then parallel: 3/2 Ohms
    3. Resistors in series within parallel: 2/3 Ohms
    4. Resistors in parallel: 1/3 Ohms
\$\endgroup\$
12
  • 4
    \$\begingroup\$ 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)\$. \$\endgroup\$ – xnor Nov 3 '20 at 0:55
  • 7
    \$\begingroup\$ 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\$. \$\endgroup\$ – xnor Nov 3 '20 at 1:05
  • 2
    \$\begingroup\$ Wondering if there's a Mathematica builtin for this. \$\endgroup\$ – Razetime Nov 3 '20 at 3:37
  • 1
    \$\begingroup\$ @user—I've updated the prompt to allow the use of floats. \$\endgroup\$ – Peter Kagey Nov 3 '20 at 19:15
  • 2
    \$\begingroup\$ 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.) \$\endgroup\$ – Bubbler Nov 3 '20 at 23:48
9
\$\begingroup\$

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)])
\$\endgroup\$

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.