Problem 169: Exploring the Number of Different Ways a Number Can Be Expressed as a Sum of Powers of 2

Project Euler Problem 169 Solution

EulerSolve provides an optimized solution for Project Euler Problem 169, Exploring the Number of Different Ways a Number Can Be Expressed as a Sum of Powers of 2, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

Detailed mathematical approach

Problem Summary

Every positive integer is a sum of powers of $2$, the numbers $1,2,4,8,\dots$. Here each power may be used at most twice, and two sums that differ only in the order of their terms count as the same sum. Let $f(n)$ be the number of such sums with total $n$, and $f(0)=1$, which counts the empty sum. The statement lists the five sums $1+1+8$, $1+1+4+4$, $1+1+2+2+4$, $2+4+4$ and $2+8$, so that $f(10)=5$, and asks for $f(10^{25})$. ^[1]

If $c_i$ is the number of times the power $2^i$ is used, a sum is the same thing as a string of digits with

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

This is a binary representation in which the digit $2$ is allowed as well, a hyperbinary representation, so $f(n)$ is the number of hyperbinary representations of $n$. ^[2]

The whole solution in one sentence: a sum for an odd $n$ uses the power $1$ exactly once and a sum for an even $n$ uses it zero or two times; removing these ones and halving all other terms leaves the same question for one or two numbers about half as large; and a table of the counts already found limits the work to at most two numbers per binary digit of $n$, only $165$ numbers for $10^{25}$.

Mathematical Approach

We count small cases by hand, find and prove a halving rule, and then show why the rule is cheap to evaluate and why the counts stay small enough for $64$-bit integers.

1. Small cases by hand

The sum $1+1+1$ uses the power $1$ three times, so $3$ has the single sum $1+2$ and $f(3)=1$. The number $4$ has the sums $4$, $2+2$ and $1+1+2$, so $f(4)=3$; $5$ has $1+4$ and $1+2+2$; and $8$ has $8$, $4+4$, $2+2+4$ and $1+1+2+4$. Listing all sums for $n=0,1,\dots,20$ gives the values

$1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5,$
$2, 5, 3, 4, 1, 5, 4, 7, 3, 8.$

Two patterns stand out. Odd numbers copy a smaller value: $f(5)=f(2)=2$, $f(7)=f(3)=1$ and $f(9)=f(4)=3$. Even numbers add two neighbouring values: $f(8)=f(4)+f(3)=3+1$ and $f(10)=f(5)+f(4)=2+3$. Sections 2 and 3 explain both patterns.

2. Sums as digit strings

Write the digits $c_i$ like a binary numeral, the highest place first and $c_0$ last. Only powers $2^i\le n$ can occur, so only finitely many digits are nonzero; as in a numeral, leading zeros are not written, and the empty string stands for the empty sum of $0$. The five sums of $10$ become

$$1010,\quad 1002,\quad 210,\quad 202,\quad 122;$$

for example, $122$ stands for $1\cdot4+2\cdot2+2\cdot1$, the sum $4+2+2+1+1$. With the digits $0$ and $1$ alone this is the ordinary binary representation, which exists and is unique, so $f(n)\ge1$. The digit $2$ creates the other possibilities, because two copies of $2^i$ can replace one copy of $2^{i+1}$: in this way $1010$ turns into $1002$ and into $210$.

3. The last digit is decided by parity

Every power $2^i$ with $i\ge1$ is even, so $n$ and its last digit $c_0$ have the same parity. Deleting the last digit of a string means subtracting $c_0$ and halving, because $(n-c_0)/2=\sum_{i\ge0}c_{i+1}2^i$, and appending a digit undoes this.

If $n=2k+1$ is odd, then $c_0=1$. Deleting it gives a representation of $k$, and appending $1$ to any representation of $k$ gives one of $n$.
If $n=2k$ with $k\ge1$ is even, then $c_0$ is $0$ or $2$. The strings ending in $0$ correspond in the same way to the representations of $k$, and those ending in $2$ to the representations of $(2k-2)/2=k-1$.

These correspondences are one-to-one, and strings with different last digits are different strings, so

$$\begin{aligned}f(2k+1)&=f(k)&&(k\ge0),\\f(2k)&=f(k)+f(k-1)&&(k\ge1).\end{aligned}$$

The arguments on the right are smaller than the one on the left, so together with $f(0)=1$ these rules determine every $f(n)$. It is natural to set $f(-1)=0$, since no string has a negative value; then the even rule also holds for $k=0$, as $1=1+0$, although there it cannot compute $f(0)$, which appears on both sides. Two quick consequences: $f(2^k-1)=f(2^{k-1}-1)$, and so on down to $f(0)=1$, so $2^k-1$ has only its binary representation; and $f(2^k)=f(2^{k-1})+1$, so $f(2^k)=k+1$.

4. Worked example: $f(10)$

The rules give $f(10)=f(5)+f(4)$, $f(5)=f(2)$, $f(4)=f(2)+f(1)$, $f(2)=f(1)+f(0)$ and $f(1)=f(0)$. Working upwards from $f(0)=1$, we get $f(1)=1$, $f(2)=2$, $f(4)=3$, $f(5)=2$ and finally $f(10)=2+3=5$, as in the statement.

The proof of Section 3 also shows which strings are counted where. The two representations $101$ and $21$ of $5$, that is $4+1$ and $2+2+1$, get a $0$ appended and become $1010$ and $210$, the sums $8+2$ and $4+4+2$. The three representations $100$, $20$ and $12$ of $4$ get a $2$ appended and become $1002$, $202$ and $122$, the sums $8+1+1$, $4+4+1+1$ and $4+2+2+1+1$. Together these are exactly the five sums of the statement.

5. The same rule from a generating function

A generating function stores a sequence as the coefficients of a power series; multiplying power series adds exponents, so a product counts combinations. ^[3] For the powers $1$ and $2$ alone, the product $(1+x+x^2)(1+x^2+x^4)$ has the coefficient $2$ at $x^2$, from $x^2\cdot1$, the sum $1+1$, and from $1\cdot x^2$, the sum $2$. In general, choosing the digit $c_i$ means choosing one of the terms $1$, $x^{2^i}$ and $x^{2\cdot2^i}$, so

$$\begin{aligned}G(x)&=\sum_{n\ge0}f(n)\,x^n\\&=\prod_{i\ge0}\bigl(1+x^{2^i}+x^{2^{i+1}}\bigr).\end{aligned}$$

This is a formal power series: the coefficient of $x^n$ involves only the finitely many factors with $2^i\le n$, since every other factor can only contribute its term $1$. Replacing $x$ by $x^2$ moves every factor one place along, so $G(x)=(1+x+x^2)\,G(x^2)$. As $G(x^2)$ has only even powers of $x$, the coefficient of $x^{2k+1}$ comes from the term $x$ alone and equals $f(k)$, while the coefficient of $x^{2k}$ is $f(k)+f(k-1)$: the rules of Section 3 once more.

6. Two numbers for each binary digit

Evaluated naively, the even rule calls itself twice, and every representation of $n$ ends in its own call of $f(0)$, which contributes $1$ to the total; so this plain recursion makes more than $f(n)$ calls, already $5330$ for $n=10^6$. Memoization stores every computed value in a table, the memo, and answers repeated calls from it. ^[4] From $x$ the rules call $\lfloor x/2\rfloor$ and $\lfloor (x-1)/2\rfloor$, which are equal for odd $x$ and are $x/2$ and $x/2-1$ for even $x$.

Claim. After $k$ halvings the argument is $q_k$ or $q_k-1$, where $q_k=\lfloor n/2^k\rfloor$ is $n$ with its last $k$ binary digits removed.

Proof. For $k=0$ the argument is $n=q_0$. If $x$ is $q_k$ or $q_k-1$, both new arguments lie between $\lfloor (q_k-2)/2\rfloor=q_{k+1}-1$ and $\lfloor q_k/2\rfloor=q_{k+1}$, because $\lfloor y/2\rfloor$ never decreases when $y$ grows, and removing one more binary digit from $q_k$ gives $q_{k+1}$. $\square$

For $n=10=1010_2$ the arguments are $10$; then $5$ and $4$; then $2$ and $1$; then $1$ and $0$. The memo computes $f(10)$, $f(5)$, $f(4)$, $f(2)$ and $f(1)$, and four of the nine calls are answered from it. A call on $x/2-1$ happens only for an even $x\ge2$, since $f(0)$ is answered at once, so no argument is ever negative. As $2^{83}\lt10^{25}\lt2^{84}$, the levels $k=0,\dots,83$ have $q_k\ge1$ and $q_{84}=0$; level $0$ holds $n$ alone, so fewer than $2\cdot84=168$ values are computed. In fact the recursion computes $165$ values in $249$ calls, at most $85$ calls deep, and for $n=10^6$ it needs $58$ calls instead of $5330$.

7. The same values from the leading digit

By Section 6 each level needs at most $f(q)$ and $f(q-1)$ for one number $q$, so this pair can also be carried along the binary digits of $n$ from the front, without recursion. Appending a binary digit to $q$ gives $2q$ or $2q+1$, and by Section 3

$$\begin{aligned}(f(2q),f(2q-1))&=(f(q)+f(q-1),\,f(q-1)),\\(f(2q+1),f(2q))&=(f(q),\,f(q)+f(q-1)).\end{aligned}$$

Starting from $(f(0),f(-1))=(1,0)$, the binary digits $1,0,1,0$ of $10$ give the pairs $(1,1)$, $(2,1)$, $(2,3)$ and $(5,3)$, so $f(10)=5$ and $f(9)=3$; here $f(-1)=0$ is really used, in the first step. The published programs evaluate the same rules recursively with a memo instead of carrying the pair.

8. How large $f(n)$ can be

The C++ and Java programs store the counts in $64$-bit integers, so we need a bound. It involves the Fibonacci numbers $F_1=F_2=1$, $F_{j+1}=F_j+F_{j-1}$, ^[5] and the list of Section 1 already shows them: its largest values below $2$, $4$, $8$ and $16$ are $1$, $2$, $3$ and $5$.

Claim. If $0\le n\lt2^L$, then $f(n)\le F_{L+1}$.

Proof. By induction on $L$. For $L=1$ and $L=2$ the values $1,1$ and $1,1,2,1$ respect the bounds $F_2=1$ and $F_3=2$. Let $L\ge3$ and $n\lt2^L$. If $n=0$, then $f(n)=1$. If $n$ is odd, $f(n)=f((n-1)/2)\le F_L$. If $n=2k$ with $k\ge1$, then $f(n)=f(k)+f(k-1)$, and both $k$ and $k-1$ are below $2^{L-1}$, so each term is at most $F_L$. One of $k$ and $k-1$ is odd, say $2i+1$, and $2i+1\lt2^{L-1}$ gives $i\lt2^{L-2}$, so that term equals $f(i)\le F_{L-1}$. Hence $f(n)\le F_L+F_{L-1}=F_{L+1}$. $\square$

The bound is sharp. For $L\ge2$ take the $L$-digit binary pattern $1010\ldots10$ if $L$ is even and $1010\ldots100$ if $L$ is odd, such as $10=1010_2$ and $20=10100_2$. Along the alternating digits $1,0,1,0,\dots$ each step of Section 7 replaces one entry of the pair by the sum of both, alternately the second and the first, so after $j$ digits the pair holds $F_{j+1}$ and $F_j$, as in the example for $10$. For even $L$ the count of the pattern is the first entry, $F_{L+1}$, and for odd $L$ the final extra $0$ gives $F_L+F_{L-1}=F_{L+1}$. A computer search shows for every $L\le22$ that no smaller number reaches this value; the On-Line Encyclopedia of Integer Sequences records the same maxima. ^[2] Since $10^{25}\lt2^{84}$, every value in the computation is at most

$$F_{85}=259695496911122585\lt2.6\cdot10^{17},$$

far below $2^{63}\approx9.2\cdot10^{18}$. The counts therefore fit into signed and unsigned $64$-bit integers, while the argument $10^{25}$ itself exceeds $2^{64}\approx1.8\cdot10^{19}$, so the programs hold it in arbitrary-precision integers.

9. Stern's diatomic sequence and the rationals

The values $f(n)$ are a famous sequence shifted by one place. Stern's diatomic sequence is defined by $s(0)=0$, $s(1)=1$, $s(2m)=s(m)$ and $s(2m+1)=s(m)+s(m+1)$. With $f(n)=s(n+1)$ these rules become those of Section 3, and $f(0)=s(1)=1$: ^[2]

$$\begin{aligned}f(2k+1)&=s(2k+2)=s(k+1)=f(k),\\f(2k)&=s(2k+1)=s(k)+s(k+1)\\&=f(k-1)+f(k).\end{aligned}$$

The quotients $f(n)/f(n+1)$, beginning with $1/1$, $1/2$, $2/1$, $1/3$, $3/2$, $2/3$, $3/1$, $1/4$, contain every positive rational number exactly once, in lowest terms: they are the fractions of the Calkin–Wilf tree, read level by level. ^[6]

How the Code Works

The C++ program ^[7] keeps its settings in Options: the argument $n$, by default $10^{25}$, built from a decimal string as a cpp_int, the arbitrary-precision integer of Boost.Multiprecision, ^[8] and the flag run_checkpoints. main first calls parse_arguments, which accepts --skip-checkpoints and --n= followed by decimal digits, checked by parse_cpp_int_after_prefix; any other argument gives exit code $1$. Boost reads a string with a leading zero as an octal number, so --n=010 computes $f(8)=4$ and --n=09 ends with an uncaught std::runtime_error. Unless switched off, run_checkpoints then requires $f(10)=5$ and $f(5)=2$, with exit code $2$ on a failure, and main prints solve(options.n).

solve creates the memo, a std::map<cpp_int, u64> holding $f(0)=1$ and $f(-1)=0$, and calls f. This function returns a stored value if there is one and otherwise applies Section 3 with the parity test (n & 1) != 0: an odd argument gives f((n - 1) >> 1), an even one f(half) + f(half - 1) with half = n >> 1, and the result is stored before it is returned. Since $0$ is in the memo, the branch for n == 0 never runs, and by Section 6 the entry for $-1$ is never read; both are safeguards. The counts are of type u64, unsigned $64$-bit integers, and by Section 8 they are exact for every $n\lt2^{92}$, since $F_{93}\lt2^{64}$. Larger inputs can wrap around modulo $2^{64}$: ^[9] for the $28$-digit number $n=(2^{94}-4)/3$, with the binary digits $1010\ldots100$, the true value, $F_{94}$ by Section 8, exceeds $2^{64}$, and the program prints its remainder.

The Python program fixes $n$ at 10**25 and has no options or checkpoints. Its function solve keeps the memo in the dictionary {0: 1, -1: 0} and defines f inside itself with the same look-up and the same odd and even cases. Python's integers have unlimited precision, ^[10] and at most $85$ nested calls stay far below the default recursion limit of $1000$. The Java program keeps the memo in a static HashMap<BigInteger, Long>. Its f tests the sign with signum(), in branches for zero and negative arguments that are again only safeguards, the parity with testBit(0), and halves with shiftRight(1); main stores the two base values and prints f(BigInteger.TEN.pow(25)). The counts are of type long, a signed $64$-bit integer, which suffices because $F_{85}\lt2^{63}$.

Complexity and Verification

Let $b$ be the number of binary digits of $n$, so $b=84$ for $10^{25}$. By Section 6 fewer than $2b$ values are computed, each making at most two further calls, so there are $O(b)$ calls, at most $b+1$ deep. Each call does a few shifts, additions, subtractions and comparisons on integers of at most $b$ bits and at most two operations, look-ups or an insertion, on a memo of fewer than $2b+2$ entries. Such an operation costs $O(\log b)$ comparisons in the C++ std::map ^[9] and, with the usual expected constant number of probes, one hash computation in Python and Java. The time is therefore $O(b^2\log b)$ bit operations in C++ and expected $O(b^2)$ in Python and Java, polynomial in the number of digits of $n$, and the memory holds $O(b)$ numbers of $O(b)$ bits. For $10^{25}$ the main evaluation makes $249$ calls, and the C++ checkpoints add two small ones; in a test run each program took less than $0.03$ seconds, about as long as an empty program in the same language.

The C++ program checks $f(10)=5$ and $f(5)=2$ before its main run. For this article all three programs were run; they print the same number, which the method of Section 7 confirms. A direct count of all digit strings for every $n\lt600$ and an independent dynamic programming count over the powers $1,2,4,\dots$ for every $n\le5000$ agree with Section 3. The identity $f(n)=s(n+1)$ holds for every $n\lt200000$, the claim of Section 6 for every $n\le20000$ and $2000$ random $200$-bit numbers, and Section 7 matches the recursion for every $n\lt100000$ and $300$ random $300$-bit numbers. The first $65535$ fractions $f(n)/f(n+1)$ are distinct and in lowest terms and include all $95$ reduced fractions $p/q$ with $p+q\le17$. The C++ program prints the exact value $F_{93}$ for $n=(2^{93}-2)/3$, whose $92$ binary digits are $1010\ldots10$, and wraps around for the $28$-digit example. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The halving rule, the bound on the number of memo entries and the Fibonacci bound are derived explicitly in this article.

Project Euler 169 — Sums of Powers of Two. The official statement defines f(0) = 1 and f(n) as the number of different ways to express n as a sum of integer powers of 2 using each power no more than twice, shows f(10) = 5 and asks for f(10²⁵).
OEIS A002487 — Stern's diatomic series. The entry defines a(0) = 0, a(1) = 1, a(2n) = a(n) and a(2n + 1) = a(n) + a(n + 1), states that a(n + 1) is the number of hyperbinary representations of n, the ways of writing n as a sum of powers of 2 with each power used at most twice, and notes that the largest term between a(2ᵏ) and a(2ᵏ⁺¹) is the Fibonacci number F(k + 2).
Wikipedia — Generating function. The ordinary generating function of a sequence is the power series with the terms of the sequence as coefficients, and multiplying two of them gives the Cauchy product, the convolution of the sequences.
Wikipedia — Memoization. Memoization speeds up a program by storing the results of calls to pure functions and reusing them when the same inputs occur again.
Wikipedia — Fibonacci sequence. Each Fibonacci number is the sum of the two preceding ones, starting from F₁ = F₂ = 1.
Wikipedia — Calkin–Wilf tree. The tree, named after Neil Calkin and Herbert Wilf, who considered it in their 2000 paper Recounting the rationals, contains every positive rational number exactly once, and in breadth-first order its rationals are fusc(n)/fusc(n + 1), with Stern's diatomic sequence fusc; fusc(n + 1) counts the ways of writing n as a sum of powers of two in which each power occurs at most twice.
C++ — Euler169.cpp. The linked immutable C++ revision contains parse_arguments, f, solve and run_checkpoints. It is the implementation record for this article.
Boost.Multiprecision — cpp_int, an arbitrary-precision integer type. By the page on conversions, integer types detect the prefixes 0x and 0 when they read a string, and invalid input results in a std::runtime_error.
cppreference — Arithmetic operators. Unsigned integer arithmetic is performed modulo 2ⁿ for a type of n bits. The page on std::map gives search and insertion logarithmic complexity.
Python — numeric types: integers have unlimited precision. Java — BigInteger: immutable arbitrary-precision integers, with the methods signum, testBit and shiftRight.

Problem 169 source code

C++

#include <boost/multiprecision/cpp_int.hpp>

#include <cstdint>
#include <iostream>
#include <map>
#include <string>

namespace {

using boost::multiprecision::cpp_int;
using u64 = std::uint64_t;

struct Options {
    cpp_int n = cpp_int("10000000000000000000000000");
    bool run_checkpoints = true;
};

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

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

    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
    }

    value = cpp_int(tail);
    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_cpp_int_after_prefix(arg, "--n=", options.n)) {
            continue;
        }

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

    return options.n >= 0;
}

u64 f(const cpp_int& n, std::map<cpp_int, u64>& memo) {
    auto it = memo.find(n);
    if (it != memo.end()) {
        return it->second;
    }

    u64 ans = 0;
    if (n == 0) {
        ans = 1;
    } else if ((n & 1) != 0) {
        ans = f((n - 1) >> 1, memo);
    } else {
        const cpp_int half = n >> 1;
        ans = f(half, memo) + f(half - 1, memo);
    }

    memo[n] = ans;
    return ans;
}

u64 solve(const cpp_int& n) {
    std::map<cpp_int, u64> memo;
    memo[cpp_int(0)] = 1;
    memo[cpp_int(-1)] = 0;
    return f(n, memo);
}

bool run_checkpoints() {
    if (solve(cpp_int(10)) != 5ULL) {
        std::cerr << "Checkpoint failed for f(10)" << '\n';
        return false;
    }
    if (solve(cpp_int(5)) != 2ULL) {
        std::cerr << "Checkpoint failed for f(5)" << '\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 << solve(options.n) << '\n';
    return 0;
}

Python

# Problem 169: Exploring the number of different ways a number can be expressed
# as a sum of powers of 2, each power used at most twice.

def solve():
    n = 10**25
    memo = {0: 1, -1: 0}
    def f(n):
        if n in memo: return memo[n]
        if n & 1:
            ans = f((n - 1) >> 1)
        else:
            half = n >> 1
            ans = f(half) + f(half - 1)
        memo[n] = ans
        return ans
    print(f(n))

solve()

Java

import java.math.BigInteger;
import java.util.*;

public class Euler169 {
    static Map<BigInteger, Long> memo = new HashMap<>();

    static long f(BigInteger n) {
        if (memo.containsKey(n))
            return memo.get(n);
        long ans;
        if (n.signum() == 0)
            ans = 1;
        else if (n.signum() < 0)
            ans = 0;
        else if (n.testBit(0))
            ans = f(n.subtract(BigInteger.ONE).shiftRight(1));
        else {
            BigInteger half = n.shiftRight(1);
            ans = f(half) + f(half.subtract(BigInteger.ONE));
        }
        memo.put(n, ans);
        return ans;
    }

    public static void main(String[] args) {
        memo.put(BigInteger.ZERO, 1L);
        memo.put(BigInteger.ONE.negate(), 0L);
        System.out.println(f(BigInteger.TEN.pow(25)));
    }
}