Detailed mathematical approach

Problem Summary

The problem asks for the number of ways to write \(10^{25}\) as a sum of powers of 2 when each power may be used at most twice. Equivalently, we want the number of digit strings \((c_0,c_1,c_2,\dots)\) with

$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$

This is a bounded binary expansion problem, often called a hyperbinary representation problem. Ordinary binary expansion is unique because the digits are restricted to \(\{0,1\}\); here the digit 2 is also allowed, so uniqueness disappears and the task becomes a counting question.

Mathematical Approach

Let \(F(n)\) denote the number of admissible representations of a nonnegative integer \(n\) in the form

$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$

The implementations solve the problem entirely through a parity-based recurrence. The important point is that after the lowest coefficient is fixed, the rest of the expression has exactly the same shape as the original problem.

A Hyperbinary View of the Sum

Every valid representation is determined by choosing how many copies of \(1,2,4,8,\dots\) appear, with each count limited to 0, 1, or 2. Since only finitely many powers can contribute to a fixed \(n\), this is a finite combinatorial object even though the summation index is written as \(i\ge 0\).

The crucial invariant is that if we peel off the contribution of \(2^0\), then every remaining term is divisible by 2. Dividing by 2 simply shifts the coefficient sequence one position to the right, and the new coefficients are still in the same set \(\{0,1,2\}\). That self-similarity is exactly what makes the recurrence so short.

The Coefficient of \(2^0\) Controls the Split

The parity of \(n\) is determined entirely by the coefficient \(c_0\), because all higher powers of 2 are even.

If \(n\) is odd, then \(c_0\) must be 1. There is no other possibility: \(c_0=0\) or \(c_0=2\) would make the whole sum even. So every odd representation has the form

$n=1+2\sum_{i\ge 0} d_i2^i,$

where \(d_i=c_{i+1}\in\{0,1,2\}\). After subtracting 1 and dividing by 2, we obtain a bijection with representations of \((n-1)/2\). Therefore, for odd \(n\),

$F(n)=F\left(\frac{n-1}{2}\right).$

If \(n\) is even, then \(c_0\) cannot be 1. The only legal choices are \(c_0=0\) and \(c_0=2\), and they lead to two disjoint families of representations.

Why Halving Preserves the Problem

When \(n\) is even and \(c_0=0\), the representation looks like

$n=2\sum_{i\ge 0} d_i2^i,$

so dividing by 2 gives a valid representation of \(n/2\). Conversely, any representation of \(n/2\) can be doubled to recover a representation of \(n\) with \(c_0=0\).

When \(n\) is even and \(c_0=2\), the representation looks like

$n=2+2\sum_{i\ge 0} d_i2^i,$

so after subtracting 2 and dividing by 2 we obtain a valid representation of \(n/2-1\). Again this is a bijection: every representation of \(n/2-1\) lifts uniquely to a representation of \(n\) with two copies of \(2^0\).

Because these two families are exhaustive and disjoint, even inputs satisfy

$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$

Boundary Cases and the Final Recurrence

The empty sum gives the unique representation of 0, so

$F(0)=1.$

It is also convenient to define

$F(-1)=0,$

so that the even case remains valid all the way down to \(n=0\) without extra branching. The complete recurrence is therefore

$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $

This formula is the whole mathematics used by the implementations. There is no search over partitions and no explicit generation of representations of \(10^{25}\).

Worked Example: \(F(10)=5\)

The recurrence immediately gives

$F(10)=F(5)+F(4).$

Since \(5\) is odd, \(F(5)=F(2)\). Since \(2\) is even, \(F(2)=F(1)+F(0)=1+1=2\). Also,

$F(4)=F(2)+F(1)=2+1=3.$

Hence \(F(10)=2+3=5\).

The five actual representations are

$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$

This example also illustrates the recurrence structurally. The two representations of 5, namely \(5=4+1\) and \(5=2+2+1\), become the two representations of 10 with \(c_0=0\) after doubling. The three representations of 4, namely \(4=4\), \(4=2+2\), and \(4=2+1+1\), become the three representations of 10 with \(c_0=2\) after doubling and then adding two copies of 1.

How the Code Works

Memoized Evaluation of the Recurrence

The C++, Python, and Java implementations all store previously computed values of \(F(n)\) in a memo table. Each call first checks whether the current argument has already been solved. If so, the stored value is reused immediately. Otherwise, the implementation inspects the parity of \(n\): odd inputs make one recursive call, and even inputs make two recursive calls. After the value is computed once, it is inserted into the memo table.

The initial memo table contains the two boundary values \(F(0)=1\) and \(F(-1)=0\). That choice keeps the recursive logic uniform and prevents awkward special cases near the bottom of the recursion tree.

Handling a Very Large Target Cleanly

The target input is \(10^{25}\), which is far beyond ordinary 32-bit arithmetic. The implementations therefore use arbitrary-precision integer support where the language needs it, while Python relies on its built-in big integers. The arithmetic performed on this large input is still very mild: parity tests, subtraction by 1 or 2, and right shifts by one bit.

The C++ implementation also includes small checkpoint evaluations, such as \(F(10)=5\) and \(F(5)=2\), before processing the full target. Those checks verify that the recurrence and the memoization logic agree with known small cases.

Complexity Analysis

Every recursive step removes the lowest binary digit of the current argument, because the next state is either \((n-1)/2\), \(n/2\), or \(n/2-1\). As a result, the depth of the recursion is proportional to the number of bits of \(n\).

With memoization, each distinct state is evaluated only once, and the reachable state graph remains very small compared with \(n\) itself. In practice the running time is proportional to the number of memoized states, which grows on the order of the bit-length of the input, so the algorithm is effectively \(O(\log n)\) states and \(O(\log n)\) memory. The important qualitative fact is that the implementation scales with the number of binary digits of \(n\), not with the enormous magnitude of \(10^{25}\).

Footnotes and References

1. Project Euler, Problem 169: https://projecteuler.net/problem=169
2. Binary number: Wikipedia - Binary number
3. Recurrence relation: Wikipedia - Recurrence relation
4. Memoization: Wikipedia - Memoization
5. Partition (number theory): Wikipedia - Partition (number theory)