Detailed mathematical approach

Problem Summary

For a positive integer \(n\), let \(F(n)=f(n)\) be the sum of all positive decimal integers that contain no zero digit and whose digit sum is exactly \(n\). Let \(A(n)\) denote how many such integers exist.

The problem asks for

$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$

A direct enumeration is impossible because \(13^{17}\) is enormous, so the implementation turns the digit-building process into a fixed linear recurrence and then evaluates that recurrence with matrix exponentiation.

Mathematical Approach

Step 1: Count the admissible numbers

Every valid number with digit sum \(n\) ends in exactly one digit \(d\in\{1,\dots,9\}\). After removing that last digit, the remaining prefix must still avoid zeros and must have digit sum \(n-d\). Therefore

$A(n)=\sum_{d=1}^{9} A(n-d).$

To make the recurrence uniform, we use the standard empty-prefix convention

$A(0)=1,\qquad A(n)=0 \text{ for } n\lt 0.$

The value \(A(0)=1\) does not represent a positive integer. It represents the single empty prefix that allows one-digit numbers to be generated correctly.

Step 2: Sum the values of the numbers

Now let \(F(n)\) be the sum of all valid integers with digit sum \(n\). Fix the last digit \(d\). If a prefix value is \(x\), appending \(d\) on the right creates the new number \(10x+d\). Summing over all prefixes of digit sum \(n-d\) gives the contribution \(10F(n-d)+d\,A(n-d)\).

Adding the contributions of the nine possible last digits gives the coupled recurrence

$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$

with initial conditions

$F(0)=0,\qquad F(n)=0 \text{ for } n\lt 0.$

This pair of recurrences is exactly what the C++, Python, and Java solutions implement.

Step 3: Small example at \(n=5\)

The valid numbers are \(5\); \(14,23,32,41\); \(113,122,131,212,221,311\); \(1112,1121,1211,2111\); and \(11111\). There are \(16\) such numbers, so \(A(5)=16\), and their total is

$F(5)=17891.$

The C++ program uses this identity as a checkpoint before it starts the large matrix-power computations.

Step 4: Turn the recurrence into an 18-dimensional linear system

Both recurrences only look back nine steps, so one state vector stores everything needed for the next update:

$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$

From the formulas above we obtain

$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$

$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$

All other coordinates of \(v_{n+1}\) are simple shifts of the previous window. Hence there exists a fixed \(18\times18\) matrix \(T\) such that

$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$

with initial state

$v_0=(1,0,\dots,0,0,\dots,0)^T.$

The required value \(F(n)\) is the 10th component of \(v_n\), which is why the implementations read state index \(9\).

Step 5: Use binary exponentiation for the indices \(13^k\)

The target indices are \(13,13^2,\dots,13^{17}\), so iterating the recurrence step by step is still infeasible. Instead the code precomputes

$T^{2^0},T^{2^1},T^{2^2},\dots$

by repeated squaring modulo \(10^9\). For each exponent \(n\), the binary expansion of \(n\) tells us which precomputed powers must be applied to \(v_0\). Because the recurrence is linear, reducing every intermediate result modulo \(10^9\) is mathematically valid.

How the Code Works

build_transition() constructs the sparse \(18\times18\) matrix described above. The first row contains nine ones for the count recurrence, the next eight rows shift the count window, the 10th row contains coefficients \(1,2,\dots,9\) for the count block and nine copies of \(10\) for the value-sum block, and the last eight rows shift the value-sum window.

The C++ version precomputes 64 matrix powers because \(13^{17}\) fits within 64 bits, then f_of_n() applies only the powers corresponding to set bits of \(n\). The Python and Java versions use the same transition and the same binary-exponentiation idea.

Complexity Analysis

Let \(m\) be the largest queried index. Precomputing the matrix powers costs \(O(18^3\log m)\) time and \(O(18^2\log m)\) memory. After that, one evaluation of \(F(n)\) costs only \(O(18^2\log n)\) time because the query phase multiplies matrices by a vector, not by another matrix. For this problem there are only 17 queries, so the total runtime is dominated by a small constant number of \(18\times18\) operations.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=377
2. Matrix exponentiation for linear recurrences: cp-algorithms
3. Generating functions and coefficient extraction: Wikipedia — Generating function
4. Digit sums and compositions into parts \(1\) through \(9\): Wikipedia — Composition