Detailed mathematical approach

Problem Summary

We must evaluate

$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$

where \(s(n)\) is the sum of the decimal digits of \(n\). The target bound is a 19-digit number, so iterating over every \(n\le N\) is infeasible. The crucial observation is that the denominator depends only on the digit sum, so the whole sum can be reorganized by digit-sum classes and computed with digit dynamic programming.

Mathematical Approach

Let \(L\) be the number of decimal digits of \(N\). Any \(L\)-digit decimal string has digit sum between \(0\) and \(9L\), so there are only \(9L+1\) relevant classes. The implementation uses that small state space to aggregate many numbers at once.

Step 1: Group the sum by digit sum

Define

$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$

Then the original expression becomes

$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$

So we do not need to handle each value \(n/s(n)\) separately. It is enough to know, for each possible digit sum \(\sigma\), the total of all numbers up to \(N\) whose digit sum is exactly \(\sigma\).

Step 2: Scan the decimal expansion from left to right

Write the bound as decimal digits \(d_1d_2\dots d_L\). We process these digits from left to right and allow leading zeros, so every integer \(0\le n\le N\) is represented exactly once as an \(L\)-digit string.

After processing the first \(k\) positions, for every digit sum \(\sigma\) we store four quantities:

$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$

The \(C\) values count how many prefixes lie in that state, and the \(S\) values store the sum of the numeric values of those prefixes. The superscript \(\mathrm{eq}\) means the processed prefix is exactly equal to the first \(k\) digits of \(N\); the superscript \(\mathrm{lt}\) means it is already smaller, so the remaining digits are unrestricted.

Initially only the empty prefix exists:

$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$

and every other state is zero.

Step 3: Update both the count and the numeric total

Suppose a state currently contains \(C\) prefixes with digit sum \(\sigma\) and total numeric sum \(S\). Appending a digit \(d\) transforms every old value \(x\) into \(10x+d\). Therefore the new digit sum is \(\sigma+d\), the number of resulting prefixes is still \(C\), and their total numeric sum is

$\sum (10x+d)=10S+dC.$

So one transition contributes

$\Delta C=C,\qquad \Delta S=10S+dC.$

If the current state is exact, then appending the current limit digit stays in the exact family, while appending a smaller digit moves to the smaller family. If the current state is already smaller, then any digit \(0,\dots,9\) remains in the smaller family.

A tiny example shows why the formula is correct. If a state contains the prefixes \(1\) and \(4\), then \(C=2\) and \(S=5\). Appending digit \(7\) produces \(17\) and \(47\), whose total is \(64\). The formula gives the same result immediately:

$10S+dC=10\cdot 5+7\cdot 2=64.$

Step 4: Recover the final sum from the last layer

After all \(L\) digits are processed, the total numeric sum of all values in \(0\le n\le N\) with digit sum \(\sigma\) is

$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$

Leading zeros automatically include shorter numbers. The class \(\sigma=0\) contains only the number \(0\), and it must be excluded because the denominator would be zero. Hence

$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$

Worked Example: \(N=10\)

Using two-digit strings, the integers from \(0\) to \(10\) are \(00,01,\dots,09,10\). Group the positive ones by digit sum:

$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$

$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$

Therefore

$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$

This matches the checkpoint used by the implementations and shows exactly why grouping by digit sum is sufficient.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They convert the bound to a decimal string, compute \(L\) and the maximum digit sum \(9L\), and maintain two rolling tables indexed by digit sum: one for prefixes still equal to the bound and one for prefixes already below it.

Each table entry stores two exact quantities: how many prefixes are represented there, and the sum of those prefix values as integers. At every decimal position, the implementation creates fresh tables, loops over the reachable digit sums, and applies the append-a-digit rule \(10S+dC\) to build the next layer.

After the last digit, the implementation combines the exact-prefix and smaller-prefix totals for every positive digit sum \(\sigma\), divides by \(\sigma\), and accumulates the final decimal answer. Exact integer accumulation is essential because the intermediate class sums grow far beyond machine-word size, while high-precision decimal arithmetic is used only for the final divisions and output formatting.

Complexity Analysis

There are \(L\) digit positions, \(9L+1\) possible digit sums, and at most \(10\) candidate digits per transition. Therefore the running time is

$O(L\cdot 9L\cdot 10)=O(L^2).$

The rolling tables use \(O(9L)=O(L)\) memory. Since \(L=\Theta(\log_{10} N)\), this is \(O((\log N)^2)\) time and \(O(\log N)\) memory as a function of the size of the bound.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=776
2. Digital sum: Wikipedia — Digital sum
3. Dynamic programming: Wikipedia — Dynamic programming
4. Positional notation: Wikipedia — Positional notation
5. Arbitrary-precision arithmetic: Wikipedia — Arbitrary-precision arithmetic