Project Euler

Digit Sum Division

For a positive integer n, let d(n) be the sum of its decimal digits. Define F(N)=sum_(n=1)^N(n)/(d(n)). The given checks are: F(10)=19, F(123)approx 1.187764610390mathrm e3, F(12345)approx 4.855801...

Source sync May 21, 2026

Problem #0776

Level Level 19

Solved By 651

Languages C++, Python

Answer 9.627509725002e33

Length 645 words

linear_algebradynamic_programmingdigit_dp

For a positive integer $n$, $d(n)$ is defined to be the sum of the digits of $n$. For example, $d(12345)=15$.

Let $\displaystyle F(N)=\sum _{n=1}^N \frac n{d(n)}$.

You are given $F(10)=19$, $F(123)\approx 1.187764610390e3$ and $F(12345)\approx 4.855801996238e6$.

Find $F(1234567890123456789)$. Write your answer in scientific notation rounded to twelve significant digits after the decimal point. Use a lowercase e to separate the mantissa and the exponent.

Problem 776: Digit Sum Division

1. Group by the Digit Sum

For each s >= 1, define

T_s(N)=\sum_{\substack{1 \le n \le N \\ d(n)=s}} n.

Then

F(N)=\sum_{s \ge 1}\frac{T_s(N)}{s}.

If N has L decimal digits, then d(n) <= 9L. For our target,

L=19,\qquad 9L=171.

So it is enough to know T_s(N) for 1 <= s <= 171.

2. Suffix DP

Fix a nonnegative integer r.

Let C[r][s] be the number of r-digit strings (leading zeros allowed) whose digits sum to s.
Let S[r][s] be the sum of the numeric values of those r-digit strings.

For the empty suffix:

C[0][0]=1,\qquad S[0][0]=0.

For r >= 1, choose the first digit x of the suffix. The remaining r-1 digits must sum to s-x, so:

C[r][s]=\sum_{x=0}^{9} C[r-1][s-x],

where terms with negative index are omitted.

If a suffix starts with digit x, then its numeric value is

x \cdot 10^{r-1} + u,

where u is the value of the remaining r-1 digits. Therefore

S[r][s] = \sum_{x=0}^{9} \left( x \cdot 10^{r-1}\, C[r-1][s-x] + S[r-1][s-x] \right).

These tables are computed in O(L^2) states and a factor 10 for the choice of x.

3. Scan the Prefix of `N`

Write the decimal expansion of N as

a_0 a_1 \dots a_{L-1}.

Process the digits from left to right. Suppose we have already fixed a prefix:

its numeric value is P,
its digit sum is \sigma.

Now consider position i, with current limit digit a_i, and let r=L-1-i be the number of remaining digits.

For each smaller digit x < a_i, every number formed by choosing x here and then any legal suffix u of length r is

(10P+x)\,10^r + u.

If the suffix has digit sum t, then the full number has digit sum \sigma + x + t, and the contribution of all such numbers to T_{\sigma+x+t}(N) is

\bigl((10P+x)10^r\bigr)\, C[r][t] + S[r][t].

After summing these contributions for every position and every x < a_i, we continue with the actual digit a_i, updating

P \leftarrow 10P + a_i,\qquad \sigma \leftarrow \sigma + a_i.

At the end, the exact number N itself is added to T_{d(N)}(N).

This gives every integer in [1,N] exactly once: it is counted at the first position where it is smaller than N, or as the final exact endpoint N.

4. Correctness

Lemma 1. C[r][s] equals the number of r-digit suffixes with digit sum s, and S[r][s] equals the sum of their numeric values.

Proof. The statement is true for r=0. For r>=1, partition the suffixes by their first digit x. The remaining r-1 digits then contribute exactly the recurrences above for both the count and the sum of values. By induction on r, the claim follows. $\square$

Lemma 2. During the prefix scan, the formula

\bigl((10P+x)10^r\bigr)\, C[r][t] + S[r][t]

is exactly the sum of all numbers whose processed prefix becomes 10P+x and whose remaining r digits have digit sum t.

Proof. There are C[r][t] such suffixes, and each contributes the common prefix term (10P+x)10^r. The suffix values themselves sum to S[r][t] by Lemma 1. Adding these two parts gives the stated formula. $\square$

Lemma 3. For every s >= 1, the algorithm computes T_s(N) exactly.

Proof. Every 1 <= n < N has a first position where its digit is smaller than the corresponding digit of N; at that position the algorithm counts it in exactly one branch x < a_i. The final endpoint N is added separately. By Lemma 2, each branch contributes the correct sum to the correct digit-sum bucket, so each T_s(N) is exact. $\square$

Theorem. The algorithm returns the correct value of F(N).

Proof. By Lemma 3, the algorithm computes all values T_s(N) exactly. Since

F(N)=\sum_{s \ge 1}\frac{T_s(N)}{s},

summing these exact buckets divided by s gives the exact value of F(N). $\square$

5. Complexity Analysis

Let L be the number of decimal digits of N.

The DP tables contain O(L \cdot 9L) = O(L^2) states, each with at most 10 transitions.
The prefix scan also visits O(L^2) digit-sum states.

Hence:

Time: O(L^2).
Space: O(L^2).

For L=19, this is tiny.

Answer

The computation gives

\boxed{9.627509725002e33}

C++ project_euler/problem_776/solution.cpp

#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

namespace {

const std::string TARGET = "1234567890123456789";
const std::string TARGET_ANSWER = "9.627509725002e33";

struct Tables {
    std::vector<std::vector<unsigned long long>> counts;
    std::vector<std::vector<long double>> totals;
    std::vector<long double> pow10;
};

Tables build_suffix_tables(int length) {
    const int max_sum = 9 * length;
    Tables tables{
        std::vector<std::vector<unsigned long long>>(
            length + 1, std::vector<unsigned long long>(max_sum + 1)
        ),
        std::vector<std::vector<long double>>(length + 1, std::vector<long double>(max_sum + 1)),
        std::vector<long double>(length + 1, 1.0L),
    };

    for (int i = 1; i <= length; ++i) {
        tables.pow10[i] = tables.pow10[i - 1] * 10.0L;
    }
    tables.counts[0][0] = 1;

    for (int digits = 1; digits <= length; ++digits) {
        const long double place = tables.pow10[digits - 1];
        for (int digit_sum = 0; digit_sum <= max_sum; ++digit_sum) {
            unsigned long long count = 0;
            long double total = 0.0L;
            for (int digit = 0; digit <= 9 && digit <= digit_sum; ++digit) {
                const unsigned long long prev_count =
                    tables.counts[digits - 1][digit_sum - digit];
                if (prev_count == 0) {
                    continue;
                }
                count += prev_count;
                total += static_cast<long double>(digit) * place * prev_count
                         + tables.totals[digits - 1][digit_sum - digit];
            }
            tables.counts[digits][digit_sum] = count;
            tables.totals[digits][digit_sum] = total;
        }
    }

    return tables;
}

std::vector<long double> digit_sum_weighted_totals(const std::string& limit) {
    const int length = static_cast<int>(limit.size());
    const int max_sum = 9 * length;
    const Tables tables = build_suffix_tables(length);

    std::vector<long double> by_sum(max_sum + 1, 0.0L);
    long double prefix_value = 0.0L;
    int prefix_sum = 0;

    for (int index = 0; index < length; ++index) {
        const int bound_digit = limit[index] - '0';
        const int remaining = length - 1 - index;
        const long double place = tables.pow10[remaining];

        for (int digit = 0; digit < bound_digit; ++digit) {
            const long double next_prefix = prefix_value * 10.0L + digit;
            for (int suffix_sum = 0; suffix_sum <= max_sum; ++suffix_sum) {
                const unsigned long long suffix_count = tables.counts[remaining][suffix_sum];
                if (suffix_count == 0) {
                    continue;
                }
                const int total_sum = prefix_sum + digit + suffix_sum;
                by_sum[total_sum] += next_prefix * place * suffix_count
                                   + tables.totals[remaining][suffix_sum];
            }
        }

        prefix_value = prefix_value * 10.0L + bound_digit;
        prefix_sum += bound_digit;
    }

    by_sum[prefix_sum] += prefix_value;
    return by_sum;
}

long double solve_value(const std::string& limit = TARGET) {
    const auto totals = digit_sum_weighted_totals(limit);
    long double answer = 0.0L;
    for (std::size_t digit_sum = 1; digit_sum < totals.size(); ++digit_sum) {
        answer += totals[digit_sum] / static_cast<long double>(digit_sum);
    }
    return answer;
}

long double brute_force(unsigned long long limit) {
    long double total = 0.0L;
    for (unsigned long long value = 1; value <= limit; ++value) {
        unsigned long long x = value;
        unsigned digit_sum = 0;
        while (x > 0) {
            digit_sum += static_cast<unsigned>(x % 10);
            x /= 10;
        }
        total += static_cast<long double>(value) / digit_sum;
    }
    return total;
}

std::string format_answer(long double value, int digits_after_decimal = 12) {
    std::ostringstream out;
    out << std::scientific << std::setprecision(digits_after_decimal) << value;
    const std::string text = out.str();
    const std::size_t split = text.find('e');
    const std::string mantissa = text.substr(0, split);
    const int exponent = std::stoi(text.substr(split + 1));
    return mantissa + "e" + std::to_string(exponent);
}

bool nearly_equal(long double a, long double b, long double eps) {
    return std::fabs(a - b) <= eps;
}

void self_test() {
    assert(nearly_equal(solve_value("10"), 19.0L, 1e-30L));
    assert(format_answer(solve_value("123")) == "1.187764610390e3");
    assert(format_answer(solve_value("12345")) == "4.855801996238e6");

    for (unsigned long long limit : {1ULL, 2ULL, 10ULL, 25ULL, 100ULL, 250ULL}) {
        assert(nearly_equal(solve_value(std::to_string(limit)), brute_force(limit), 1e-15L));
    }

    assert(format_answer(solve_value()) == TARGET_ANSWER);
}

}  // namespace

int main() {
    self_test();
    std::cout << format_answer(solve_value()) << '\n';
    return 0;
}

Python project_euler/problem_776/solution.py

"""Project Euler 776: Digit Sum Division."""

from __future__ import annotations

from decimal import Decimal, localcontext
from fractions import Fraction
from typing import List, Tuple

TARGET = 1234567890123456789
TARGET_ANSWER = "9.627509725002e33"


def build_suffix_tables(length: int) -> Tuple[List[List[int]], List[List[int]], List[int]]:
    """Return count/value tables for suffixes with a fixed digit sum."""
    max_sum = 9 * length
    pow10 = [1] * (length + 1)
    for i in range(1, length + 1):
        pow10[i] = pow10[i - 1] * 10

    counts = [[0] * (max_sum + 1) for _ in range(length + 1)]
    totals = [[0] * (max_sum + 1) for _ in range(length + 1)]
    counts[0][0] = 1

    for digits in range(1, length + 1):
        place = pow10[digits - 1]
        for digit_sum in range(max_sum + 1):
            count = 0
            total = 0
            for digit in range(10):
                if digit > digit_sum:
                    break
                prev_count = counts[digits - 1][digit_sum - digit]
                if not prev_count:
                    continue
                count += prev_count
                total += digit * place * prev_count + totals[digits - 1][digit_sum - digit]
            counts[digits][digit_sum] = count
            totals[digits][digit_sum] = total

    return counts, totals, pow10


def digit_sum_weighted_totals(limit: int) -> List[int]:
    """Return T_s(limit) = sum_{n <= limit, d(n)=s} n for each digit sum s."""
    digits = [int(ch) for ch in str(limit)]
    length = len(digits)
    max_sum = 9 * length
    counts, totals, pow10 = build_suffix_tables(length)

    by_sum = [0] * (max_sum + 1)
    prefix_value = 0
    prefix_sum = 0

    for index, bound_digit in enumerate(digits):
        remaining = length - 1 - index
        place = pow10[remaining]

        for digit in range(bound_digit):
            next_prefix = prefix_value * 10 + digit
            for suffix_sum, suffix_count in enumerate(counts[remaining]):
                if not suffix_count:
                    continue
                total_sum = prefix_sum + digit + suffix_sum
                by_sum[total_sum] += next_prefix * place * suffix_count + totals[remaining][suffix_sum]

        prefix_value = prefix_value * 10 + bound_digit
        prefix_sum += bound_digit

    by_sum[prefix_sum] += limit
    return by_sum


def solve_fraction(limit: int = TARGET) -> Fraction:
    """Compute F(limit) exactly as a rational number."""
    answer = Fraction(0, 1)
    for digit_sum, total in enumerate(digit_sum_weighted_totals(limit)[1:], start=1):
        if total:
            answer += Fraction(total, digit_sum)
    return answer


def format_fraction(value: Fraction, digits_after_decimal: int = 12) -> str:
    """Format an exact rational in Project Euler scientific notation."""
    with localcontext() as ctx:
        ctx.prec = 80
        decimal_value = Decimal(value.numerator) / Decimal(value.denominator)
    mantissa, exponent = f"{decimal_value:.{digits_after_decimal}e}".split("e")
    return f"{mantissa}e{int(exponent)}"


def solve(limit: int = TARGET) -> str:
    return format_fraction(solve_fraction(limit))


def brute_force(limit: int) -> Fraction:
    total = Fraction(0, 1)
    for value in range(1, limit + 1):
        total += Fraction(value, sum(int(ch) for ch in str(value)))
    return total


def self_test() -> None:
    for limit in (1, 2, 10, 25, 100, 250):
        assert solve_fraction(limit) == brute_force(limit)

    assert solve_fraction(10) == 19
    assert format_fraction(solve_fraction(123)) == "1.187764610390e3"
    assert format_fraction(solve_fraction(12345)) == "4.855801996238e6"
    assert solve() == TARGET_ANSWER


if __name__ == "__main__":
    self_test()
    print(solve())

Digit Sum Division

Problem Statement

Problem 776: Digit Sum Division

1. Group by the Digit Sum

2. Suffix DP

3. Scan the Prefix of `N`

4. Correctness

5. Complexity Analysis

Answer

Code

Problem Statement

Problem 776: Digit Sum Division

1. Group by the Digit Sum

2. Suffix DP

3. Scan the Prefix of N

4. Correctness

5. Complexity Analysis

Answer

Code

3. Scan the Prefix of `N`