Problem 155: Counting Capacitor Circuits

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

Identical capacitors of capacitance $C$ may be connected in series or in parallel to form sub-units, which may again be connected in series or in parallel with capacitors or other sub-units, up to a final circuit. In parallel, capacitances $C_1,C_2,\dots$ give the total $C_1+C_2+\cdots$; in series, the total $C_T$ satisfies $1/C_T=1/C_1+1/C_2+\cdots$. ^[2] $D(n)$ is the number of distinct total capacitances obtainable with up to $n$ capacitors. The statement gives $D(1)=1$, $D(2)=3$ and $D(3)=7$, the seven totals of up to three capacitors of 60 µF, and asks for $D(18)$. ^[1]

The whole solution in one sentence: taking one capacitor as the unit, we build the fractional values of all circuits with $k=1,2,\dots,18$ capacitors from the stored values of smaller circuits, using only sums and reciprocals because exchanging series and parallel turns a value $x$ into $1/x$, and count the distinct values.

Mathematical Approach

We turn capacitances into fractions, build each set of values from sums alone, and then study overlaps, exact arithmetic and the size of the numbers.

1. Capacitances become fractions

Two sub-units with capacitances $x$ and $y$ give $x+y$ in parallel and

$$S(x,y)=\frac{1}{1/x+1/y}=\frac{xy}{x+y}$$

in series. Multiplying both inputs by $c\gt0$ multiplies both results by $c$, so a circuit of capacitors $C$ has $C$ times the value of the same circuit of capacitors $1$, and $D(n)$ does not depend on $C$. From now on every capacitor has the value $1$, and all values are positive rational numbers. The seven totals of the statement are $20$, $30$, $40$, $60$, $90$, $120$ and $180$ µF, that is, $\tfrac13$, $\tfrac12$, $\tfrac23$, $1$, $\tfrac32$, $2$ and $3$ times 60 µF.

2. The last connection of a circuit

Let $E_k$ be the set of values of the circuits with exactly $k$ capacitors, so $E_1=\{1\}$. For $k\ge2$, the last connection joins two or more sub-units, all in series or all in parallel, where a single capacitor also counts as a sub-unit. Joining three or more at once gives the same value as joining them two at a time, because $C_1+C_2+C_3=(C_1+C_2)+C_3$, and in series the reciprocals add in the same way. So $E_k$ consists of the values $x+y$ and $S(x,y)$ with $x\in E_a$, $y\in E_{k-a}$ and $1\le a\le k-1$; both rules are symmetric, so $a\le k/2$ suffices. The value of a joined circuit depends only on the values of its two parts, so each $E_k$ can be stored as a set of numbers, and computing $E_1,E_2,\dots$ in turn from the stored smaller sets is dynamic programming: each subproblem is solved once and its result reused. ^[9] Up to $n$ capacitors means any number from $1$ to $n$, so

$$D(n)=\bigl|E_1\cup E_2\cup\dots\cup E_n\bigr|.$$

3. One, two and three capacitors

Two capacitors give $1+1=2$ and $S(1,1)=\tfrac12$, so $E_2=\{2,\tfrac12\}$. Three capacitors split as $1+2$: a single capacitor joined with $2$ gives $3$ and $S(1,2)=\tfrac23$, and joined with $\tfrac12$ it gives $\tfrac32$ and $S(1,\tfrac12)=\tfrac13$. Together with $E_1$ and $E_2$ these are the seven values of Section 1, which confirms $D(1)=1$, $D(2)=3$ and $D(3)=7$. Each set contains the reciprocals of its values: $\tfrac32$, one capacitor in parallel with a series pair, becomes $\tfrac23$, one capacitor in series with a parallel pair, when series and parallel are exchanged.

4. Exchanging series and parallel

Claim. If $x\in E_k$, then $1/x\in E_k$.

Proof. By induction on $k$; for $k=1$, $1/1=1$. For $k\ge2$, Section 2 writes $x=y+z$ or $x=S(y,z)$ with $y\in E_a$ and $z\in E_{k-a}$, and by the induction hypothesis $1/y\in E_a$ and $1/z\in E_{k-a}$. If $x=y+z$, then $1/x=S(1/y,1/z)$, because $S(u,v)=1/(1/u+1/v)$; if $x=S(y,z)$, then $1/x=1/y+1/z$. Either way $1/x$ joins a value of $E_a$ with a value of $E_{k-a}$, so $1/x\in E_k$.

Resistances add in series, so resistors obey the same rules with series and parallel exchanged: in units of one element, the resistance of a circuit equals the capacitance of the exchanged circuit. Exchanging twice restores a circuit, so $k$ equal resistors give exactly the values $E_k$, and results on resistor networks apply here; Khan calls the claim the reciprocal theorem. ^[6]

5. Sums are enough

For $x\in E_a$ and $y\in E_{k-a}$, Section 4 shows that $S(x,y)=1/(1/x+1/y)$ is the reciprocal of a sum of a value of $E_a$ and a value of $E_{k-a}$; conversely, $1/(x+y)=S(1/x,1/y)$ is a series value. So the series values are exactly the reciprocals of the sums. If $P_k$ is the set of sums $x+y$ with $x\in E_a$, $y\in E_{k-a}$ and $1\le a\le k/2$, then

$$E_k=P_k\cup\{\,1/s\ :\ s\in P_k\,\}.$$

The programs therefore need only additions and reciprocals. For the split $a=k/2$, the pairs $(x,y)$ and $(y,x)$ give the same sum, so unordered pairs suffice.

6. Worked example: four capacitors

The split $a=1$ adds $1$ to the values of $E_3$ and gives $4$, $\tfrac52$, $\tfrac53$ and $\tfrac43$. The split $a=2$ gives $2+2=4$, $2+\tfrac12=\tfrac52$ and $\tfrac12+\tfrac12=1$. Adding the reciprocals,

$$E_4=\Bigl\{\tfrac14,\tfrac25,\tfrac35,\tfrac34,1,\tfrac43,\tfrac53,\tfrac52,4\Bigr\}.$$

The construction produced $13$ candidates, the seven sums and the reciprocals of the six sums other than $1$, but only $9$ distinct values: $4$, $\tfrac52$ and their reciprocals come once from each split. A repeat may be one circuit grouped in two ways, as both routes to $4$ put all four capacitors in parallel, and different circuits may share a value, as two series pairs in parallel and two parallel pairs in series both give $1$. Only the value $1$ occurred before, in $E_1$, so $D(4)=7+8=15$. Continuing in the same way gives, for $k=1,\dots,10$:

the sizes $|E_k|$: $1, 2, 4, 9, 22, 53, 131, 337, 869, 2213$;
the counts $D(k)$: $1, 3, 7, 15, 35, 77, 179, 429, 1039, 2525$.

The sizes form the sequence A048211 of the OEIS, the number of values of exactly $k$ equal resistors, which by Section 4 equals $|E_k|$. ^[5] Each additional capacitor multiplies the size by about $2.5$; from $k=16$ to $k=17$ the factor is $2.53$.

7. The sets overlap

The sets are not nested: $\tfrac23$ lies in $E_3$ but not in $E_4$ or $E_5$, and $1$ lies in $E_1$ and $E_4$ but not in $E_2$, $E_3$ or $E_5$. So $D(4)=15$ is not the sum $1+2+4+9=16$ of the sizes. The sub-unit of Section 6 with value $1$, two series pairs connected in parallel, can replace any single capacitor of a circuit without changing any value, and it uses three more capacitors. Hence $E_k\subseteq E_{k+3}$ for every $k\ge1$. For $n\ge3$, every $k\le n$ is congruent modulo $3$ to one of $n-2$, $n-1$ and $n$, and is not larger than that number, so

$$D(n)=\bigl|E_{n-2}\cup E_{n-1}\cup E_n\bigr|.$$

Khan proves the same inclusion and draws the same conclusion. ^[6] The overlaps are large; for example, $727$ of the $2213$ values of $E_{10}$ also occur with fewer capacitors. The programs do not use this shortcut; they keep the union of all sets, which gives the same count.

8. Exact fractions in lowest terms

Every positive rational number has exactly one representation $p/q$ with positive integers $p$, $q$ and $\gcd(p,q)=1$, obtained from any such representation by dividing numerator and denominator by their greatest common divisor. ^[3] So two values are equal exactly when their reduced pairs $(p,q)$ are equal. For $x=p/q$ and $y=r/s$ in lowest terms,

$$x+y=\frac{ps+rq}{qs},$$

whose numerator and denominator are then both divided by $g=\gcd(ps+rq,\,qs)$, which the Euclidean algorithm computes. ^[4] For example, $\tfrac12+\tfrac12=\tfrac44$ has $g=4$, while $2+\tfrac12=\tfrac{2\cdot2+1\cdot1}{1\cdot2}=\tfrac52$ is already reduced. The reciprocal $q/p$ of a reduced fraction is reduced as well.

Floating-point numbers would fail, because rounding depends on the order of the operations. Two single capacitors and a series chain of three, all in parallel, have the value $\tfrac73$, reached as $2+\tfrac13$ and as $1+\tfrac43$ with $\tfrac43=1+\tfrac13$; in double precision these give $2.3333333333333335$ and $2.333333333333333$, and a floating-point version of the method finds $24$ values for five capacitors instead of $22$.

9. How large the numbers get

Every reduced value $p/q$ in $E_k$ has $p\le2^{k-1}$ and $q\le2^{k-1}$. This holds for $k=1$. For $k\ge2$, by Section 5 every value is a sum of some $p/q\in E_a$ and $r/s\in E_b$ with $a+b=k$, or the reciprocal of such a sum; if the claim holds for both parts, then $ps+rq\le2\cdot2^{a-1}\cdot2^{b-1}$${}=2^{k-1}$ and $qs\le2^{k-2}$, and reducing or taking the reciprocal makes nothing larger. For $k\le18$ no number, even before reduction, exceeds $2^{17}=131072$.

The true maximum is smaller. With the Fibonacci numbers $F_1=F_2=1$ and $F_{j+1}=F_j+F_{j-1}$, the numerators and denominators in $E_k$ are at most $F_{k+1}$, and the bound is reached by the ladder that adds one capacitor at a time, alternately in parallel and in series: $1$, $2$, $\tfrac23$, $\tfrac53$, $\tfrac58$, $\tfrac{13}8$, and so on. ^[5] ^[6] For every $k\le18$ the computation confirms that the largest numerator is $F_{k+1}$; no number exceeds $F_{19}=4181$.

How the Code Works

The C++ program ^[7] stores a value as a Fraction with unsigned 64-bit fields num and den in lowest terms. Its operator< compares numerators, then denominators; this is not the numerical order, but any fixed order makes equal pairs adjacent after sorting. make_fraction divides by std::gcd, and parallel_combine forms $ps+rq$ and $qs$ with unsigned 128-bit products, converts them back to 64 bits and reduces, which by Section 9 loses nothing.

distinct_up_to(max_n) keeps $E_k$ in ways[k] as a sorted vector without repetitions and collects all values in all. For each $n\ge2$ it estimates the number of candidates as twice the sum of $|E_a|\cdot|E_{n-a}|$ over $a\le n/2$ and reserves room for at most $16\,000\,000$ of them. For every split $a\le n/2$ with $b=n-a$ it combines each left[i] of ways[a] with each right[j] of ways[b], where j starts at i when $a=b$ (Section 5). It appends each sum p and, unless p.num == p.den, which means $p=1$, its reciprocal {p.den, p.num}. Then std::sort, std::unique and erase remove repetitions, the sort first because std::unique only removes adjacent copies. ^[8] The set is moved into ways[n] and appended to all, which is sorted and deduplicated once more at the end; its size is printed. Unless --skip-checkpoints is given, run_checkpoints first verifies $D(3)=7$; --max-n=K changes the default $18$.

The Python program uses tuples and math.gcd. It collects each new set in a Python set cur, stores it as the sorted list ways[n] and adds it to the set all_fracs. For $a=b$ it visits all ordered pairs and skips the mirrored ones by comparing the position idx of fj with ways[a].index(fi). The list has no repetitions, so the sums are those of C++, but index is a linear search inside the inner loop, scanning $m^2(m+1)/2$ positions for $m=|E_{n/2}|$: about $3.3\cdot10^8$ for $n=18$, where $m=869$, and about $2$ of the $16$ seconds in our runs. Python integers cannot overflow.

The Java program packs a reduced fraction into one long, the numerator in the upper and the denominator in the lower $32$ bits, which Section 9 makes safe. pack reduces with its own Euclidean gcd; parPack unpacks two values, adds them with 64-bit products and packs the reduced sum. The sets are HashSet<Long> objects, which drop repetitions on insertion, so Java does not skip mirrored pairs for $a=b$. The reciprocal goes through pack(pd, pn), which computes a greatest common divisor again, always $1$.

Complexity and Verification

The pair loops dominate the work. With mirrored pairs skipped, as in C++ and Python, the program combines $12\,733\,513$ pairs for $n\le18$, $7\,968\,532$ of them for the last set; Java combines $13\,177\,442$ and $8\,345\,678$. Each pair costs three multiplications, an addition and one reduction by a greatest common divisor, and Java reduces every reciprocal other than $1$ a second time. No number exceeds $4181$, so by Lamé's theorem the Euclidean algorithm needs at most $20$ division steps. ^[4] Java's own gcd, which is this algorithm, needs at most $17$ for the sums and $18$ for the reciprocals; C++ and Python call library routines. For the last set the C++ program sorts $c=15\,936\,686$ candidates in $O(c\log c)$ time and at the end sorts all values once more; Python and Java pay an expected constant time per hash-set insertion, and Python also sorts each new set.

The cost grows exponentially with $n$, like the sets of Section 6: the pairs of the last set grow by a factor of about $2.7$, from $2\,987\,853$ for $n=17$. By Section 9, $E_k$ contains only fractions whose numerator and denominator are at most $F_{k+1}$, and the number of such fractions grows like $2.618^k$, the square of the golden ratio; Khan derives this bound and estimates the actual growth as $2.55^k$. ^[6] The method suits $n=18$, but not much larger $n$.

Memory grows in the same way, because all sets are kept. In C++ each set even keeps its candidate buffer, since erase does not release capacity and the vector is moved into ways[n]. For the last set the estimate $16\,691\,356$, which counts mirrored pairs too, exceeds the cap, so room for $16\,000\,000$ fractions of $16$ bytes, $256$ MB, is reserved; all buffers together take about $411$ MB, plus the vector all. On a desktop computer (Clang with -O2, OpenJDK 17, CPython 3.11) the C++ program peaked at about $0.55$ GB of resident memory and took about $2$ seconds, Python $1.3$ GB and $16$ seconds, and Java $2$ GB and $8$ seconds, as every fraction there is a separate object.

The C++ program checks $D(3)=7$, and all three programs print the same value. Further checks, not part of the published solutions: both rules of Section 2 applied without the reciprocal shortcut give the same sets $E_k$ for $k\le15$, each closed under reciprocals; joining any number of sub-units at once gives the same sets for $k\le10$; the sizes $|E_k|$ agree with OEIS A048211 for $k\le17$; the C++ program with --max-n=K agrees with a separately written implementation for $K\le18$; and the three-set formula of Section 7 matches the full union for $3\le n\le18$.

Footnotes and References

The references below supply the background facts used above; the reduction to sums and reciprocals, the worked example, the bound $2^{k-1}$ and the operation counts are derived or computed in this article.

Project Euler 155 — Counting Capacitor Circuits. Identical capacitors of value C are combined in series or in parallel into sub-units up to a final circuit; D(n) counts the distinct total capacitances with up to n capacitors, D(1) = 1, D(2) = 3, D(3) = 7, and the task asks for D(18).
Wikipedia — Series and parallel circuits. The total capacitance of capacitors in parallel is the sum of their capacitances; in series it is the reciprocal of the sum of the reciprocals of their capacitances.
Wikipedia — Irreducible fraction. Every rational number can be represented as an irreducible fraction with positive denominator in exactly one way, obtained by dividing numerator and denominator by their greatest common divisor.
Wikipedia — Euclidean algorithm. It computes greatest common divisors and reduces fractions; by Lamé's theorem it never needs more steps than five times the number of decimal digits of the smaller integer.
OEIS A048211 — Distinct resistances of n equal resistors in series and parallel. It counts the values of exactly n resistors and notes that their numerators and denominators never exceed the (n + 1)st Fibonacci number.
Sameen Ahmed Khan — The bounds of the set of equivalent resistances of n equal resistors combined in series and in parallel (arXiv:1004.3346). Its reciprocal theorem: exchanging all series and parallel connections turns a/b into b/a; its second theorem bounds a and b by Fib(n + 1), reached by adding resistors incrementally. Appendix E proves that the set for m resistors lies in the set for m + 3, so only the last three sets are needed for up to n; the paper bounds the growth by about 2.618ⁿ and quotes 2.55ⁿ from data.
C++ — Euler155.cpp. The linked immutable revision contains parallel_combine, distinct_up_to and run_checkpoints. It is the implementation record for this article.
cppreference — std::unique. It keeps the first element of every group of consecutive equivalent elements without shortening the container, so erase follows; sorting first makes all equal values consecutive.
Wikipedia — Dynamic programming. It breaks a complicated problem down into simpler sub-problems in a recursive manner and solves each sub-problem only once, storing the solutions in a table.

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());
    }
}