Detailed mathematical approach

Problem Summary

Fix integers \(k\) and \(\ell\) with \(3 \le k \le 6\) and \(1 \le \ell \le k-2\). Write a positive integer \(x\) in binary as

$x=\sum_{p\ge 0} b_p 2^p,\qquad b_p\in\{0,1\}.$

For each period \(r\), define the weighted binary digit sum

$B_r(x)=\sum_{p\ge 0} b_p\,2^{p \bmod r}.$

For a fixed pair \((k,\ell)\), the quantity of interest is

$S_{k,\ell}(n)=\sum_{1\le x\le n,\ B_k(x)=B_\ell(x)} x \pmod{10^{16}}.$

The full Project Euler task asks for the sum of \(S_{k,\ell}(10^{16})\) over all admissible pairs \((k,\ell)\). Direct enumeration is impossible, so the solution turns the digit condition into a bounded-state dynamic program over the bits of \(n\).

Mathematical Approach

The central trick is to replace the equality of two weighted digit sums by a single signed balance equation. Once that balance is tracked while scanning the binary digits of \(n\), the algorithm can count all admissible numbers and add their values without listing them individually.

Step 1: Rewrite the matching condition as a signed sum

For each bit position \(p\), define

$\delta_p=2^{p \bmod k}-2^{p \bmod \ell}.$

Then the difference between the two weighted sums is

$B_k(x)-B_\ell(x)=\sum_{p\ge 0} b_p\,\delta_p.$

Therefore the matching condition is equivalent to

$\sum_{p\ge 0} b_p\,\delta_p=0.$

Each bit set to \(1\) contributes a fixed signed amount to a running balance, while each bit set to \(0\) contributes nothing. The coefficient pattern is periodic because it depends only on \(p \bmod k\) and \(p \bmod \ell\), but the program only needs the finitely many positions that appear below the highest bit of \(n\).

Step 2: Bound the range of reachable balances

Let

$L=\lfloor\log_2 n\rfloor+1$

be the number of relevant bit positions when \(n>0\). Over these positions, define the safe bound

$A=\sum_{p=0}^{L-1} |\delta_p|.$

No partial or final balance can ever leave the interval

$-A\le d\le A.$

This observation turns the problem into a finite-state DP. Instead of storing balances in a dictionary, the implementation shifts the interval by an offset and uses ordinary arrays of width

$2A+1.$

That is why the method stays compact even though the original condition is phrased over all integers \(x\le n\).

Step 3: Use prefix-constrained binary digit DP

Process the bits of \(n\) from the most significant bit down to the least significant bit. After deciding the higher bits, a DP state records

$\text{state}=(d,e),$

where \(d\) is the current balance and \(e\in\{0,1\}\) is a prefix-equality flag. The value \(e=1\) means the chosen prefix is still exactly equal to the prefix of \(n\); the value \(e=0\) means the constructed number is already smaller, so the remaining bits may be chosen freely.

If the current bit of \(n\) is \(n_p\in\{0,1\}\) and we choose the new bit \(u\in\{0,1\}\), then in the equal-prefix layer we must respect \(u\le n_p\). The balance update is

$d'=d+u\,\delta_p.$

The new flag becomes

$e'=\begin{cases} 1,& e=1\ \text{and}\ u=n_p,\\ 0,& \text{otherwise}. \end{cases}$

This is the standard digit-DP tightness idea, specialized to binary digits and to the balance defined above.

Step 4: Carry both counts and value sums

For every reachable state, the DP stores two quantities modulo \(10^{16}\):

$C(d,e)=\text{number of represented prefixes},\qquad V(d,e)=\text{sum of their numeric values}.$

When the next bit \(u\) is appended at position \(p\), every represented number gains \(u\,2^p\). Therefore the transition rules are

$C'(d',e')\equiv C'(d',e')+C(d,e)\pmod{10^{16}},$

$V'(d',e')\equiv V'(d',e')+V(d,e)+u\,2^p\,C(d,e)\pmod{10^{16}}.$

The second formula is what makes the solution efficient: a single transition adds the contribution of an entire family of numbers at once, rather than adding admissible integers one by one.

Step 5: Read the answer from balance \(0\)

After all \(L\) bits are processed, the condition \(B_k(x)=B_\ell(x)\) is satisfied exactly when the final balance is zero. Hence

$S_{k,\ell}(n)=V_{\mathrm{final}}(0,0)+V_{\mathrm{final}}(0,1)\pmod{10^{16}}.$

The state for \(x=0\) is harmless: it also ends with balance \(0\), but it contributes value \(0\), so the sum over positive integers is unchanged.

Worked Example: \(n=10\), \(k=3\), \(\ell=1\)

Because \(10=1010_2\), the relevant positions are \(p=0,1,2,3\). Since \(p \bmod 1=0\) always, the coefficients are

$\delta_0=2^0-2^0=0,\qquad \delta_1=2^1-2^0=1,\qquad \delta_2=2^2-2^0=3,\qquad \delta_3=2^0-2^0=0.$

So bits at positions \(0\) and \(3\) do not affect the balance, while bits at positions \(1\) and \(2\) add \(1\) and \(3\). Among the integers \(1\le x\le 10\), the only values with total balance \(0\) are

$1=0001_2,\qquad 8=1000_2,\qquad 9=1001_2.$

Their sum is

$1+8+9=18,$

which matches the first checkpoint used by the C++, Python, and Java implementations. Those implementations also verify the larger checkpoints \(292\) for \(n=100\) and \(19{,}173{,}952\) for \(n=10^6\) when \((k,\ell)=(3,1)\).

How the Code Works

The implementations begin with the trivial case \(n=0\), for which the required sum is \(0\). Otherwise they compute the bit length of \(n\), generate the coefficient list \(\delta_0,\dots,\delta_{L-1}\), and add their absolute values to determine the balance range.

Next they maintain four rolling arrays: counts and value sums for the smaller-prefix layer, and counts and value sums for the equal-prefix layer. For each bit position, fresh arrays are created for the next layer, the allowable bit choices are applied, and all arithmetic is reduced modulo \(10^{16}\).

The C++ implementation uses 128-bit intermediate multiplication to keep modular products safe, the Python implementation relies on arbitrary-precision integers, and the Java implementation uses repeated doubling so multiplication cannot overflow a signed 64-bit value. After evaluating one pair \((k,\ell)\), the implementation adds that contribution to the running total over all required pairs and prints the final result as a 16-digit decimal string.

Complexity Analysis

For fixed \(n\), \(k\), and \(\ell\), let

$L=\lfloor\log_2 n\rfloor+1,\qquad A=\sum_{p=0}^{L-1} |\delta_p|.$

The DP uses two prefix layers and \(2A+1\) balance states. Therefore the running time is

$O\bigl(L(2A+1)\bigr)=O(LA),$

and the memory usage with rolling arrays is

$O(2A+1)=O(A).$

In the actual problem there are only ten admissible pairs \((k,\ell)\), and the bit length of \(10^{16}\) is small, so this bounded-state DP is easily fast enough in all three languages.

Footnotes and References

1. Problem page: Project Euler 676
2. Binary number: Wikipedia - Binary number
3. Dynamic programming: Wikipedia - Dynamic programming
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Digit DP overview: GeeksforGeeks - Digit DP Introduction