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

Mathematical Development

Definition. $f(n) = |\{(c_0, c_1, c_2, \ldots) : c_i \in \{0, 1, 2\}, \, \sum_{i \geq 0} c_i \cdot 2^i = n\}|$.

Theorem 1 (Recurrence for $f$). For all $n \geq 0$:

Proof. Consider the coefficient $c_0$ (the number of times $2^0 = 1$ is used).

Case $n$ odd: We need $c_0$ odd, so $c_0 = 1$. Then $\sum_{i \geq 1} c_i \cdot 2^i = n - 1$. Dividing by 2: $\sum_{i \geq 1} c_i \cdot 2^{i-1} = (n-1)/2 = \lfloor n/2 \rfloor$. Relabeling $c_i' = c_{i+1}$ gives a representation of $\lfloor n/2 \rfloor$ with each $c_i' \in \{0, 1, 2\}$. This is a bijection, so $f(n) = f(\lfloor n/2 \rfloor)$.

Case $n$ even: We need $c_0$ even, so $c_0 \in \{0, 2\}$.

• If $c_0 = 0$: the remaining sum is $n$, so $\sum_{i \geq 1} c_i \cdot 2^i = n$, giving $\sum_{i \geq 0} c_{i+1} \cdot 2^i = n/2$. This contributes $f(n/2)$ representations.
• If $c_0 = 2$: the remaining sum is $n - 2$, so $\sum_{i \geq 1} c_i \cdot 2^i = n - 2$, giving $\sum_{i \geq 0} c_{i+1} \cdot 2^i = (n-2)/2 = n/2 - 1$. This contributes $f(n/2 - 1)$ representations (valid since $n \geq 2$ ensures $n/2 - 1 \geq 0$).

Total: $f(n) = f(n/2) + f(n/2 - 1)$. $\square$

Theorem 2 (Subproblem count). The memoized computation of $f(n)$ encounters at most $O(\log^2 n)$ distinct subproblems.

Proof. At recursion depth $d$, the argument has the form $\lfloor n / 2^d \rfloor - j$ for some integer $j$ with $0 \leq j \leq d$. This is because each “even” branch produces two subproblems at argument $\lfloor n/2^{d+1} \rfloor \cdot \text{(something)} - j'$, and the offset $j$ increases by at most 1 per even step. At depth $d$, there are at most $d + 1$ possible values of $j$, giving at most $\sum_{d=0}^{\lfloor \log_2 n \rfloor} (d + 1) = O(\log^2 n)$ distinct subproblems. $\square$

Lemma 1 (Base cases). $f(0) = 1$ (the empty sum) and $f(1) = 1$ (only $c_0 = 1$, all others 0).

Proof. $f(0)$: the unique representation is $c_i = 0$ for all $i$. $f(1)$: $c_0 = 1$ is forced (only way to get an odd sum); then the remaining sum is 0, which has a unique representation. $\square$

Lemma 2 (Correctness for $n = 10^{25}$). The recursion terminates since each step replaces $n$ by $\lfloor n/2 \rfloor$ or $\lfloor n/2 \rfloor - 1$, strictly decreasing $n$ until reaching the base cases. The recursion depth is $\lceil \log_2(10^{25}) \rceil = 84$.

Proof. $\log_2(10^{25}) = 25 \log_2 10 \approx 25 \times 3.3219 = 83.05$, so the recursion depth is 84. $\square$

Editorial

The recurrence already does all the heavy lifting. Looking at the coefficient of $2^0$ splits the problem into one smaller subproblem when $n$ is odd and two smaller subproblems when $n$ is even. Because every recursive call roughly halves the argument, the state graph stays tiny even for $10^{25}$.

The implementation is therefore just memoized recursion. Each distinct value of $n$ is solved once, cached, and reused whenever it reappears from a different branch. That turns what looks like an exponential expansion into a small DAG of overlapping subproblems, making the exact count for $10^{25}$ straightforward to obtain.

Pseudocode

Define a memoized function `f(n)`.

If `n` is zero, return 1.
If `n` is already cached, return the cached value.

If `n` is odd:
    the coefficient of 1 is forced to be 1,
    so return `f(n // 2)`.

If `n` is even:
    either use zero copies of 1 or two copies of 1,
    so return `f(n // 2) + f(n // 2 - 1)`.

Store the result in the cache and return it.
Evaluate the function at $10^{25}$.

Complexity Analysis

• Time: $O(\log^2 n)$ subproblems, each requiring $O(1)$ work (plus big-integer arithmetic for the values, which are $O(\log n)$ bits). Total: $O(\log^2 n \cdot M(\log n))$ where $M$ is multiplication cost, but since the values of $f$ are polynomially bounded in $n$, $O(\log^3 n)$ suffices.
• Space: $O(\log^2 n)$ for the memoization table.

For $n = 10^{25}$: depth $\approx 84$, subproblems $\leq 84^2 / 2 \approx 3{,}528$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 169: Number of ways to express n as sum of powers of 2,
 * each used at most twice. Find f(10^25).
 *
 * Recurrence:
 *   f(0) = 1
 *   f(n) = f(n/2)             if n is odd
 *   f(n) = f(n/2) + f(n/2-1)  if n is even
 *
 * We use Python-style big integers via strings or __int128.
 * Since 10^25 fits in unsigned 128-bit, we use __int128.
 */

typedef __int128 lll;

map<lll, long long> memo;

long long f(lll n) {
    if (n == 0) return 1;
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;

    long long result;
    if (n % 2 == 1) {
        result = f(n / 2);
    } else {
        result = f(n / 2) + f(n / 2 - 1);
    }
    memo[n] = result;
    return result;
}

int main(){
    // 10^25
    lll n = 1;
    for (int i = 0; i < 25; i++) n *= 10;

    cout << (long long)f(n) << endl;
    return 0;
}

"""
Problem 169: Number of ways to express n as sum of powers of 2,
each power used at most twice. Find f(10^25).

Recurrence:
  f(0) = 1
  f(n) = f(n//2)              if n is odd
  f(n) = f(n//2) + f(n//2-1)  if n is even
"""

import sys
sys.setrecursionlimit(10000)

memo = {}

def f(n):
    if n == 0:
        return 1
    if n in memo:
        return memo[n]
    if n % 2 == 1:
        result = f(n // 2)
    else:
        result = f(n // 2) + f(n // 2 - 1)
    memo[n] = result
    return result

print(f(10**25))