Solution

Answer: 3857447

Let every capacitor have capacitance $C$.

Since every resulting capacitance is a rational multiple of $C$, we normalize by setting $C=1$.

Thus every achievable capacitance is an exact rational number.

We define:

$$S_n = {\text{all capacitances achievable using exactly } n \text{ capacitors}}$$

and

$$D(n)=\left|\bigcup_{k=1}^n S_k\right|$$

The problem asks for $D(18)$.

Mathematical analysis

If two subcircuits have capacitances $x$ and $y$, then:

Parallel connection

Capacitances add directly:

$$C_{\text{parallel}} = x+y$$

Series connection

$$\frac1{C_{\text{series}}}=\frac1x+\frac1y$$

$$C_{\text{series}}=\frac{xy}{x+y}$$

Thus every circuit built from $n$ capacitors can be formed by splitting the capacitors into two nonempty groups of sizes $k$ and $n-k$, building one subcircuit from each group, and combining them either in series or parallel.

Therefore:

$$S_n = \bigcup_{k=1}^{n-1} \left{ x+y,\ \frac{xy}{x+y} ;\middle|; x\in S_k,\ y\in S_{n-k} \right}$$

Base case:

$$S_1={1}$$

Because all values are rational, we represent them exactly using reduced fractions.

Dynamic programming strategy

We compute $S_1,S_2,\dots,S_{18}$.

For each $n$:

iterate over all splits $k$ and $n-k$,
combine every pair $x\in S_k$, $y\in S_{n-k}$,
insert:
$x+y$
$\dfrac{xy}{x+y}$

into a set (to remove duplicates automatically).

A useful optimization:

Because combining $S_k$ with $S_{n-k}$ is symmetric, we only need:

$$k \le \frac n2$$

This cuts the work roughly in half.

Python implementation

from math import gcd

N = 18

# S[n] = set of capacitances using exactly n capacitors
# Each capacitance stored as a reduced fraction (num, den)
S = [set() for _ in range(N + 1)]

# Base case: one capacitor => capacitance 1
S[1] = {(1, 1)}

# Global set of all distinct capacitances
all_values = {(1, 1)}

for n in range(2, N + 1):

    current = set()

    # Only need k <= n//2 because of symmetry
    for k in range(1, n // 2 + 1):

        other = n - k

        for a, b in S[k]:
            for c, d in S[other]:

                # -------------------------
                # Parallel:
                # a/b + c/d
                # -------------------------
                num = a * d + b * c
                den = b * d

                g = gcd(num, den)
                current.add((num // g, den // g))

                # -------------------------
                # Series:
                # (a/b * c/d) / (a/b + c/d)
                # = ac / (ad + bc)
                # -------------------------
                num = a * c
                den = a * d + b * c

                g = gcd(num, den)
                current.add((num // g, den // g))

    S[n] = current
    all_values |= current

print(len(all_values))

Code walkthrough

Initialization

S = [set() for _ in range(N + 1)]
S[1] = {(1, 1)}

S[n] stores all capacitances achievable with exactly n capacitors.
(1,1) represents capacitance $1$.

Iterating over total capacitor count

for n in range(2, N + 1):

We build larger circuits from smaller ones.

Splitting into two subcircuits

for k in range(1, n // 2 + 1):

A circuit with $n$ capacitors is formed by combining:

one subcircuit with $k$ capacitors,
another with $n-k$ capacitors.

Only half the splits are needed because the operations are symmetric.

Parallel combination

num = a * d + b * c
den = b * d

This computes:

$$\frac ab + \frac cd = \frac{ad+bc}{bd}$$

Then we reduce using gcd.

Series combination

num = a * c
den = a * d + b * c

This computes:

$$\frac{\frac ab \cdot \frac cd} {\frac ab + \frac cd} = \frac{ac}{ad+bc}$$

Again reduced to lowest terms.

Verification on small cases

$n=1$

Only:

$$1$$

So:

$$D(1)=1$$

Correct.

$n=2$

Possible values:

Parallel: $1+1=2$
Series: $\frac{1\cdot1}{1+1}=\frac12$

Distinct values up to 2 capacitors:

$$\left{1,2,\frac12\right}$$

Hence:

$$D(2)=3$$

Correct.

$n=3$

The algorithm produces exactly 7 distinct values, matching the statement.

Final verification

The computation produces:

$$D(18)=3,!857,!447$$

This matches the known Project Euler result and is consistent with the rapidly growing number of rational capacitance configurations.

Answer: 3857447

Project Euler Problem 155