Detailed mathematical approach

Problem Summary

Let \(p(n)\) denote the number of ways to write \(n\) as a sum of powers of \(2\), with unlimited repetition allowed. Problem 890 asks for

$p\left(7^{777}\right)\pmod{10^9+7}.$

The classical generating function is

$\prod_{j\ge 0}\frac{1}{1-x^{2^j}}=\sum_{n\ge 0}p(n)x^n.$

Because \(7^{777}\) is enormous, the implementation cannot iterate up to \(n\). Instead, it reads the binary digits of \(n\) and counts valid carry patterns. That turns the problem into a digit DP whose size depends on the bit-length of \(n\), not on \(n\) itself.

Mathematical Approach

The key observation is that a binary partition can be read bit by bit. At each bit position we only need to know how many lower-power terms have paired up and carried into the next position.

Step 1: Encode a Partition as a Carry Process

Write

$n=\sum_{k=0}^{L-1} b_k2^k,\qquad b_k\in\{0,1\}.$

If a partition uses \(x_k\) copies of \(2^k\), then after combining pairs of \(2^k\)-terms into \(2^{k+1}\)-terms we get the balance equation

$x_k+c_k=b_k+2c_{k+1},$

where \(c_k\) is the carry entering bit \(k\), and \(c_{k+1}\) is the carry leaving it. For fixed \(c_k\) and \(c_{k+1}\), there is exactly one possible value of \(x_k\), namely

$x_k=b_k+2c_{k+1}-c_k.$

This value is valid if and only if it is nonnegative, so

$c_k\le 2c_{k+1}+b_k.$

Now define \(F_k(c)\) to be the number of ways to satisfy the lowest \(k\) bits of \(n\) and end with carry \(c\) into bit \(k\). Then for \(k\ge 1\),

$F_{k+1}(u)=\sum_{c=0}^{2u+b_k}F_k(c).$

After the least significant bit there is always exactly one choice once the outgoing carry is fixed, so

$F_1(c)=1\qquad(c\ge 0).$

This is also why the least significant bit does not need a special case later: both \(p(2m)\) and \(p(2m+1)\) start from the same initial carry polynomial.

Step 2: Expand Each Carry Function in the Binomial Basis

The recurrence is a prefix sum evaluated at \(2u+b_k\), so starting from the constant function \(F_1(c)=1\), each step raises the degree by at most one. Therefore \(F_k(c)\) is always a polynomial of degree at most \(k-1\).

The implementation stores this polynomial in the basis

$\binom{c}{0},\binom{c}{1},\binom{c}{2},\dots$

so that

$F_k(c)=\sum_{j=0}^{k-1}A_{k,j}\binom{c}{j}.$

This basis is ideal because of the hockey-stick identity

$\sum_{c=0}^{M}\binom{c}{j}=\binom{M+1}{j+1}.$

Substituting the binomial expansion into the recurrence gives

$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+b_k+1}{j+1}.$

So the whole problem becomes: given the coefficient vector \((A_{k,0},\dots,A_{k,k-1})\), compute the next coefficient vector efficiently.

Step 3: Derive the Transition for a 0 Bit

If the current bit is \(b_k=0\), then

$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+1}{j+1}.$

Using Pascal's identity,

$\binom{2u+1}{j+1}=\binom{2u}{j+1}+\binom{2u}{j}.$

Hence if we define an intermediate coefficient list by

$B_r=A_{k,r}+A_{k,r-1},$

with the convention that terms outside the valid range are \(0\), then

$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u}{r}.$

We now need to re-expand \(\binom{2u}{r}\) in the basis \(\binom{u}{j}\). Start from

$\sum_{r\ge 0}\binom{2u}{r}t^r=(1+t)^{2u}=((1+t)^2)^u=(1+2t+t^2)^u.$

Expanding again,

$ (1+2t+t^2)^u=\sum_{j\ge 0}\binom{u}{j}(2t+t^2)^j=\sum_{j\ge 0}\binom{u}{j}\sum_{m=0}^{j}\binom{j}{m}2^{j-m}t^{j+m}. $

Therefore the coefficient of \(\binom{u}{j}\) inside \(\binom{2u}{j+m}\) is

$w_j(m)=\binom{j}{m}2^{j-m}.$

So the next coefficient vector is

$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w_j(m).$

In the finite arrays used by the implementation, the sum stops at

$m_{\max}=\min(j,\;k-j).$

Step 4: Derive the Transition for a 1 Bit

If the current bit is \(b_k=1\), then

$F_{k+1}(u)=\sum_{j=0}^{k-1}A_{k,j}\binom{2u+2}{j+1}.$

Applying Pascal once more gives

$\binom{2u+2}{j+1}=\binom{2u+1}{j+1}+\binom{2u+1}{j},$

so the same intermediate coefficients \(B_r\) appear and

$F_{k+1}(u)=\sum_{r=0}^{k}B_r\binom{2u+1}{r}.$

Now use

$\binom{2u+1}{r}=\binom{2u}{r}+\binom{2u}{r-1}.$

This means the kernel for bit \(1\) is just the sum of two neighboring bit-\(0\) kernels:

$w^{(1)}_j(m)=w_j(m)+w_j(m-1),$

where \(w_j(m)=0\) whenever \(m<0\) or \(m>j\). Thus

$A_{k+1,j}=\sum_{m\ge 0} B_{j+m}\,w^{(1)}_j(m).$

In the finite implementation, the upper limit is

$m_{\max}=\min(j+1,\;k-j).$

Step 5: Extract the Final Answer

After all \(L\) bits have been processed, there can be no carry beyond the most significant bit. Therefore the desired count is

$p(n)=F_L(0).$

In the binomial basis, this is especially simple:

$F_L(0)=\sum_{j=0}^{L-1}A_{L,j}\binom{0}{j}=A_{L,0},$

because \(\binom{0}{0}=1\) and \(\binom{0}{j}=0\) for every \(j>0\). That is why the implementation returns the first coefficient of the last state vector.

Worked Example: \(n=7\)

Take \(n=7=111_2\). We begin with

$F_1(c)=1.$

The second bit is \(1\), so

$F_2(u)=\sum_{c=0}^{2u+1}1=2u+2.$

In binomial form,

$F_2(u)=2\binom{u}{0}+2\binom{u}{1}.$

The third bit is again \(1\), therefore

$F_3(u)=\sum_{c=0}^{2u+1}(2c+2)=(2u+2)(2u+3)=4u^2+10u+6.$

Convert this polynomial back to the binomial basis:

$F_3(u)=6\binom{u}{0}+14\binom{u}{1}+8\binom{u}{2}.$

Hence

$p(7)=F_3(0)=6,$

which matches the known value and the implementation checkpoint.

How the Code Works

The C++, Python, and Java implementations all target the same digit-DP formula. The C++ and Java implementations first convert \(n\) to binary, least significant bit first. They then precompute powers of \(2\) modulo \(10^9+7\), Pascal coefficients modulo \(10^9+7\), and two lower-triangular transition tables corresponding to the formulas for a current bit of \(0\) and \(1\).

The running state is the coefficient list of \(F_k(c)\) in the basis \(\binom{c}{j}\). For each new bit, the implementation first applies the Pascal update \(B_r=A_r+A_{r-1}\), then performs the appropriate convolution against the precomputed kernel. The C++ implementation can split the outer coefficient range across several threads, while the Java implementation performs the same arithmetic serially.

The Python implementation is a thin execution bridge: it compiles and runs the C++ solver when necessary, then parses the numeric output. In every language, the published answer is the first coefficient after the most significant bit has been processed.

Complexity Analysis

Let \(L=\lfloor\log_2 n\rfloor+1\). Precomputing powers of \(2\), Pascal coefficients, and the two triangular transition tables costs \(O(L^2)\) time and \(O(L^2)\) memory. At stage \(k\), the convolution examines \(\Theta(k^2)\) coefficient pairs, so the full dynamic program costs

$\sum_{k=1}^{L-1}\Theta(k^2)=\Theta(L^3)$

time. The optional threading in the C++ implementation improves wall-clock time but does not change the asymptotic bound.

Footnotes and References

1. Project Euler Problem 890: https://projecteuler.net/problem=890
2. OEIS A000123, binary partitions: https://oeis.org/A000123
3. Generating function: Wikipedia — Generating function
4. Binomial coefficient: Wikipedia — Binomial coefficient
5. Pascal's triangle: Wikipedia — Pascal's triangle