Detailed mathematical approach

Problem Summary

The problem asks for \(D(18)\), the number of distinct equivalent capacitances that can be built from at most 18 identical capacitors using only series and parallel connections. Because every capacitor has the same base capacitance \(C\), the absolute unit is irrelevant for counting: dividing every circuit value by \(C\) turns the problem into one about unit capacitors of value \(1\).

So the real task is not to count circuit shapes, but to count distinct rational numbers obtainable from repeated series/parallel composition. Different wiring trees can lead to the same final value, so exact deduplication is the central issue.

Mathematical Approach

The implementations solve the problem with dynamic programming over the number of capacitors, while storing each capacitance exactly as a reduced fraction.

Normalizing the capacitance scale

If two subcircuits have normalized capacitances \(x\) and \(y\), then the two physical combination rules are

$P(x,y)=x+y \qquad \text{(parallel)},$

$S(x,y)=\frac{xy}{x+y} \qquad \text{(series)}.$

Starting from the single value \(1\), these rules always produce positive rational numbers. That is why the implementations never use floating-point arithmetic: every reachable capacitance can be stored exactly as a reduced fraction \(\frac{p}{q}\).

The exact-\(n\) state space

Let \(E_n\) be the set of normalized capacitances obtainable with exactly \(n\) capacitors, and let

$U_n=\bigcup_{k=1}^{n} E_k,\qquad D(n)=|U_n|.$

The base case is immediate:

$E_1=\{1\}.$

Now consider any circuit that uses exactly \(n\ge 2\) capacitors. Its topmost connection is either series or parallel, so it splits the circuit into two smaller subcircuits using \(a\) and \(b\) capacitors with

$a+b=n,\qquad a\ge 1,\ b\ge 1.$

Therefore every value in \(E_n\) must arise by combining some \(x\in E_a\) and \(y\in E_b\). This gives a complete recursive description of the search space.

Reciprocal duality removes the need for a second recurrence

The key invariant used by all three implementations is reciprocal closure. For unit capacitors, exchanging series and parallel everywhere in a circuit changes its value from \(x\) to \(\frac1x\). So if a value belongs to \(E_n\), its reciprocal also belongs to \(E_n\).

This means the algorithm does not need to generate \(P(x,y)\) and \(S(x,y)\) separately. It is enough to generate the parallel sum

$p=x+y$

and also insert its reciprocal \(\frac1p\). Why does that cover the series case? Because if \(x\in E_a\) and \(y\in E_b\), then by reciprocal closure \(\frac1x\in E_a\) and \(\frac1y\in E_b\) as well, and

$\frac{1}{\frac1x+\frac1y}=\frac{xy}{x+y}=S(x,y).$

So the implemented recurrence can be written as

$E_n=\operatorname{red}\!\left(\bigcup_{a+b=n}\left\{x+y,\ \frac1{x+y}: x\in E_a,\ y\in E_b\right\}\right),$

where \(\operatorname{red}\) means reducing every fraction to lowest terms and deleting duplicates.

Worked example: building \(D(3)\)

The first layers already show all of the important ideas.

With one capacitor,

$E_1=\{1\}.$

For \(n=2\), the only split is \(1+1\). Combining \(1\) with \(1\) gives

$1+1=2,\qquad \frac1{1+1}=\frac12,$

so

$E_2=\left\{2,\frac12\right\}.$

For \(n=3\), the only relevant split is \(1+2\). Combining \(1\) with the two values in \(E_2\) gives

$1+2=3,\qquad \frac13,$

$1+\frac12=\frac32,\qquad \frac{2}{3}.$

Hence

$E_3=\left\{3,\frac32,\frac23,\frac13\right\}.$

Taking the union up to 3 capacitors,

$U_3=\left\{1,2,\frac12,3,\frac32,\frac23,\frac13\right\},$

so

$D(3)=7.$

This small case is exactly the same recurrence that is used all the way up to \(n=18\).

How the Code Works

Exact arithmetic with reduced fractions

The C++, Python, and Java implementations represent every capacitance as a numerator-denominator pair in lowest terms. If \(x=\frac{u}{v}\) and \(y=\frac{r}{s}\), then the parallel combination is

$x+y=\frac{us+rv}{vs},$

after which the result is reduced by dividing both numerator and denominator by their greatest common divisor. This canonical representation guarantees that equal capacitances compare equal even when they come from different circuit trees.

Layer-by-layer construction

The implementation builds \(E_1,E_2,\dots,E_{18}\) in order. For a fixed \(n\), it enumerates splits \(a+b=n\) only with \(a\le b\), because swapping the left and right subcircuits does not create a new capacitance. For each pair of exact layers, it combines every value from the first with every value from the second, inserts \(x+y\), and also inserts its reciprocal unless the value is \(1\) and would duplicate itself.

When the split is symmetric, \(a=b\), there is an additional mirror symmetry inside that layer pair. One implementation skips those mirrored pairs during generation; the others let the set-based deduplication remove them later. The mathematical result is the same in every language.

Counting values with at most \(n\) capacitors

After generating all candidates for exactly \(n\) capacitors, the implementation removes duplicates inside that layer and then merges the layer into a global union. The final answer is not \(|E_{18}|\), but

$D(18)=\left|\bigcup_{k=1}^{18}E_k\right|,$

because the problem asks for all distinct capacitances obtainable with up to 18 capacitors.

Complexity Analysis

Let \(m_n=|E_n|\). For a fixed \(n\), the dominant work is the number of cross-layer pairs examined:

$T_n=\sum_{a=1}^{\lfloor n/2\rfloor} m_a\,m_{n-a}.$

Each such pair produces one reduced sum and, in general, one reciprocal. After that, duplicates must be removed. In the sort-based version this costs \(O(T_n\log T_n)\) for the layer; in the hash-set versions insertion is expected near-linear in the number of generated candidates, with the same mathematical set size at the end.

Total memory is \(O\!\left(\sum_{k=1}^{18} m_k\right)\), because all exact layers must remain available for later splits, and the global union must also be stored. The growth is combinatorial, but for \(n=18\) the recurrence is still practical precisely because the code exploits symmetry, reciprocal closure, and exact deduplication.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=155
2. Capacitance: Wikipedia - Capacitance
3. Series and parallel circuits: Wikipedia - Series and parallel circuits
4. Rational number: Wikipedia - Rational number
5. Greatest common divisor: Wikipedia - Greatest common divisor