Problem 155: Counting Capacitor Circuits

View on Project Euler

Project Euler Problem 155 Solution

EulerSolve provides an optimized solution for Project Euler Problem 155, Counting Capacitor Circuits, with C++, Python, Java, and a step-by-step mathematical explanation.

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}\)....

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

Problem 155 source code

C++

#include <algorithm>
#include <climits>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    int max_n = 18;
    bool run_checkpoints = true;
};

struct Fraction {
    u64 num = 0;
    u64 den = 1;

    bool operator<(const Fraction& other) const {
        if (num != other.num) {
            return num < other.num;
        }
        return den < other.den;
    }

    bool operator==(const Fraction& other) const {
        return num == other.num && den == other.den;
    }
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--max-n=", options.max_n)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.max_n >= 1;
}

Fraction make_fraction(u64 num, u64 den) {
    const u64 g = std::gcd(num, den);
    return {num / g, den / g};
}

Fraction parallel_combine(const Fraction& a, const Fraction& b) {
    const u128 num = static_cast<u128>(a.num) * b.den + static_cast<u128>(b.num) * a.den;
    const u128 den = static_cast<u128>(a.den) * b.den;
    return make_fraction(static_cast<u64>(num), static_cast<u64>(den));
}

u64 distinct_up_to(const int max_n) {
    std::vector<std::vector<Fraction>> ways(static_cast<std::size_t>(max_n + 1));
    std::vector<Fraction> all;
    all.reserve(4'000'000);

    ways[1] = {{1, 1}};
    all.push_back({1, 1});

    for (int n = 2; n <= max_n; ++n) {
        std::vector<Fraction> cur;
        std::size_t estimate = 0;
        for (int a = 1; a <= n / 2; ++a) {
            const int b = n - a;
            const auto& left = ways[static_cast<std::size_t>(a)];
            const auto& right = ways[static_cast<std::size_t>(b)];
            const std::size_t combos = left.size() * right.size();
            const std::size_t term_count = 2ULL * combos;
            if (estimate <= std::numeric_limits<std::size_t>::max() - term_count) {
                estimate += term_count;
            } else {
                estimate = std::numeric_limits<std::size_t>::max();
            }
        }
        cur.reserve(std::min<std::size_t>(estimate, 16'000'000));

        for (int a = 1; a <= n / 2; ++a) {
            const int b = n - a;
            const auto& left = ways[static_cast<std::size_t>(a)];
            const auto& right = ways[static_cast<std::size_t>(b)];

            for (std::size_t i = 0; i < left.size(); ++i) {
                const std::size_t j_start = (a == b) ? i : 0;
                for (std::size_t j = j_start; j < right.size(); ++j) {
                    const Fraction p = parallel_combine(left[i], right[j]);
                    cur.push_back(p);
                    if (p.num != p.den) {
                        cur.push_back({p.den, p.num});
                    }
                }
            }
        }

        std::sort(cur.begin(), cur.end());
        cur.erase(std::unique(cur.begin(), cur.end()), cur.end());

        ways[static_cast<std::size_t>(n)] = std::move(cur);
        all.insert(all.end(), ways[static_cast<std::size_t>(n)].begin(), ways[static_cast<std::size_t>(n)].end());
    }

    std::sort(all.begin(), all.end());
    all.erase(std::unique(all.begin(), all.end()), all.end());
    return static_cast<u64>(all.size());
}

bool run_checkpoints() {
    if (distinct_up_to(3) != 7ULL) {
        std::cerr << "Checkpoint failed for D(3)" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << distinct_up_to(options.max_n) << '\n';
    return 0;
}

Python

from math import gcd

def solve():
    max_n = 18

    def make_fraction(num, den):
        g = gcd(num, den)
        return (num // g, den // g)

    def parallel_combine(a, b):
        num = a[0] * b[1] + b[0] * a[1]
        den = a[1] * b[1]
        return make_fraction(num, den)

    ways = [[] for _ in range(max_n + 1)]
    ways[1] = [(1, 1)]
    all_fracs = set()
    all_fracs.add((1, 1))

    for n in range(2, max_n + 1):
        cur = set()
        for a in range(1, n // 2 + 1):
            b = n - a
            for fi in ways[a]:
                j_start = 0
                for idx, fj in enumerate(ways[b]):
                    if a == b and idx < ways[a].index(fi):
                        continue
                    p = parallel_combine(fi, fj)
                    cur.add(p)
                    if p[0] != p[1]:
                        cur.add((p[1], p[0]))
        ways[n] = sorted(cur)
        all_fracs.update(cur)

    return str(len(all_fracs))

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler155 {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static long pack(long n, long d) {
        long g = gcd(n, d);
        return ((n / g) << 32) | (d / g);
    }

    static long parPack(long a, long b) {
        long an = a >>> 32, ad = a & 0xFFFFFFFFL;
        long bn = b >>> 32, bd = b & 0xFFFFFFFFL;
        long num = an * bd + bn * ad, den = ad * bd;
        long g = gcd(num, den);
        return ((num / g) << 32) | (den / g);
    }

    public static String solve() {
        int maxN = 18;
        List<Set<Long>> ways = new ArrayList<>();
        for (int i = 0; i <= maxN; i++)
            ways.add(new HashSet<>());
        long one = pack(1, 1);
        ways.get(1).add(one);
        Set<Long> all = new HashSet<>();
        all.add(one);
        for (int n = 2; n <= maxN; n++) {
            Set<Long> cur = new HashSet<>();
            for (int a = 1; a <= n / 2; a++) {
                int b = n - a;
                for (long fi : ways.get(a)) {
                    for (long fj : ways.get(b)) {
                        long p = parPack(fi, fj);
                        cur.add(p);
                        long pn = p >>> 32, pd = p & 0xFFFFFFFFL;
                        if (pn != pd)
                            cur.add(pack(pd, pn));
                    }
                }
            }
            ways.set(n, cur);
            all.addAll(cur);
        }
        return String.valueOf(all.size());
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}