Project Euler Problem 776

Project Euler Problem 776

Solution

Answer: 9.627509725002e33

Using a digit DP decomposition,

$$F(N)=\sum_{n=1}^{N}\frac{n}{d(n)} =\sum_{s=1}^{171}\frac{1}{s} \left(\sum_{\substack{1\le n\le N\ d(n)=s}} n\right)$$

for $N=1234567890123456789$.

The computation is done efficiently by digit DP over the decimal expansion of $N$, tracking:

• position in the number,
• remaining digit sum,
• tight bound status,

and for each state accumulating:

• the count of valid numbers,
• the sum of those numbers.

This reproduces the given checks:

• $F(10)=19$
• $F(123)\approx 1.187764610390\times 10^3$
• $F(12345)\approx 4.855801996238\times 10^6$

For

$$N=1234567890123456789$$

the value is

$$F(N)\approx 9.627509725001875958\ldots \times 10^{33}$$

Rounded to twelve digits after the decimal point:

Answer: 9.627509725002e33