Project Euler Problem 676

Solution

Answer: 3562668074339584

A digit sum in base $2^k$ can be rewritten in terms of binary blocks. If we write the binary expansion of $n$ in chunks of $k$ bits, then

$$d(n,2^k)$$

is just the sum of the chunk values.

The key observation is that for $l<k$, if $g=\gcd(k,l)$, we can regroup binary digits into blocks of size $g$. Then both digit sums become additive automata over a common radix $2^g$. This turns the condition

$$d(n,2^k)=d(n,2^l)$$

into a finite-state digit DP problem: scanning the digits of $n$ in a common base $2^{\mathrm{lcm}(k,l)}$, we only need to track the difference of the two digit sums. Since $k,l\le 6$, the state space is tiny.

For each pair $(2^k,2^l)$ with

$$3\le k\le 6,\qquad 1\le l\le k-2,$$

one computes

$$M(10^{16},2^k,2^l)$$

using a memoized digit DP that simultaneously accumulates:

the count of valid numbers,
the sum of valid numbers,
the current digit-sum difference.

The recurrence is standard digit-DP:

process digits of $10^{16}$ in the common radix,
maintain a tight flag,
update the difference

$$\Delta \leftarrow \Delta + d(\text{block},2^k) - d(\text{block},2^l),$$

at the end accept iff $\Delta=0$.

The implementation reproduces the examples:

$M(10,8,2)=18$,
$M(100,8,2)=292$,
$M(10^6,8,2)=19173952$,

matching the statement.

Summing over all required pairs and taking the last $16$ digits gives:

Answer: 3562668074339584