Solution

Answer: 732385277

Let

$c(n)$ = number of positive integers with no zero digits and digit sum $n$,
$f(n)$ = sum of all such integers.

We are asked for

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

1. Mathematical analysis

A number with no zero digits and digit sum $n$ is exactly a sequence of digits from ${1,\dots,9}$ whose sum is $n$.

So the problem is fundamentally about compositions of $n$ using parts $1$–$9$.

Counting sequences: recurrence for $c(n)$

Every valid number for digit sum $n$ ends in some digit $d\in{1,\dots,9}$.

Removing the last digit leaves a valid number of digit sum $n-d$.

Therefore,

$$c(n)=\sum_{d=1}^{9} c(n-d),$$

with initial conditions

$$c(0)=1,\qquad c(n)=0\text{ for }n<0.$$

For small values:

$$c(1)=1,; c(2)=2,; c(3)=4,; c(4)=8,; c(5)=16,$$

which matches the statement that there are $16$ such numbers for digit sum $5$.

Recurrence for $f(n)$

Suppose $x$ is a valid number with digit sum $n-d$.

Appending digit $d$ produces

$$10x+d.$$

Summing over all possibilities gives:

$$f(n)=\sum_{d=1}^{9} \left( 10f(n-d)+d,c(n-d) \right).$$

Rearranging:

$$f(n) = 10\sum_{d=1}^{9} f(n-d) + \sum_{d=1}^{9} d,c(n-d).$$

Letting $k=n-d$,

$$f(n) = 10\sum_{k=n-9}^{n-1} f(k) + \sum_{k=n-9}^{n-1} (n-k)c(k).$$

This is a linear recurrence of order $9$.

Verification on the example $n=5$

Using the recurrence:

$$f(5) = 10(f(4)+f(3)+f(2)+f(1)+f(0)) + (1c(4)+2c(3)+3c(2)+4c(1)+5c(0)).$$

Using

$$f(0)=0,\quad f(1)=1,\quad f(2)=13,\quad f(3)=147,\quad f(4)=1625,$$

and

$$c(0)=1,; c(1)=1,; c(2)=2,; c(3)=4,; c(4)=8,$$

we get

$$f(5)=17891,$$

exactly as given.

2. Matrix formulation

Because $13^{17}$ is enormous, direct DP is impossible.

We use matrix exponentiation.

Define the state vector

$$V(n)= \begin{bmatrix} f(n)\ f(n-1)\ \vdots\ f(n-8)\ c(n)\ c(n-1)\ \vdots\ c(n-8) \end{bmatrix}.$$

This is an $18$-dimensional vector.

The recurrences are linear, so there exists an $18\times18$ matrix $M$ such that

$$V(n+1)=MV(n).$$

Then

$$V(N)=M^{N-8}V(8).$$

Binary exponentiation computes this in $O(\log N)$.

All computations are done modulo $10^9$.

3. Python implementation

MOD = 10**9

# ------------------------------------------------------------
# Build initial values c(n), f(n) for n = 0..8
# ------------------------------------------------------------

c = [0] * 9
f = [0] * 9

c[0] = 1

# c(n) recurrence
for n in range(1, 9):
    c[n] = sum(c[max(0, n - 9):n])

# f(n) recurrence
for n in range(1, 9):
    total = 0

    for d in range(1, 10):
        if n - d >= 0:
            total += 10 * f[n - d] + d * c[n - d]

    f[n] = total

# ------------------------------------------------------------
# Build the 18x18 transition matrix
# ------------------------------------------------------------

SIZE = 18

M = [[0] * SIZE for _ in range(SIZE)]

# First row: recurrence for f(n+1)
for j in range(9):
    M[0][j] = 10
    M[0][9 + j] = 9 - j

# Shift rows for f
for i in range(1, 9):
    M[i][i - 1] = 1

# Recurrence for c(n+1)
for j in range(9):
    M[9][9 + j] = 1

# Shift rows for c
for i in range(10, 18):
    M[i][i - 1] = 1

# ------------------------------------------------------------
# Matrix multiplication
# ------------------------------------------------------------

def mat_mul(A, B):
    C = [[0] * SIZE for _ in range(SIZE)]

    for i in range(SIZE):
        for k in range(SIZE):
            if A[i][k]:
                aik = A[i][k]

                for j in range(SIZE):
                    C[i][j] = (C[i][j] + aik * B[k][j]) % MOD

    return C

# ------------------------------------------------------------
# Matrix exponentiation
# ------------------------------------------------------------

def mat_pow(M, e):
    # Identity matrix
    R = [[0] * SIZE for _ in range(SIZE)]

    for i in range(SIZE):
        R[i][i] = 1

    A = M

    while e > 0:
        if e & 1:
            R = mat_mul(R, A)

        A = mat_mul(A, A)
        e >>= 1

    return R

# ------------------------------------------------------------
# Multiply matrix by vector
# ------------------------------------------------------------

def mat_vec_mul(A, v):
    out = [0] * SIZE

    for i in range(SIZE):
        s = 0

        for j in range(SIZE):
            s += A[i][j] * v[j]

        out[i] = s % MOD

    return out

# ------------------------------------------------------------
# Initial state V(8)
# ------------------------------------------------------------

state = (
    f[8::-1] +   # f(8),...,f(0)
    c[8::-1]     # c(8),...,c(0)
)

# ------------------------------------------------------------
# Compute f(N)
# ------------------------------------------------------------

def F(N):
    if N <= 8:
        return f[N]

    P = mat_pow(M, N - 8)
    result = mat_vec_mul(P, state)

    return result[0]

# ------------------------------------------------------------
# Final summation
# ------------------------------------------------------------

answer = 0

for i in range(1, 18):
    answer = (answer + F(13**i)) % MOD

print(answer)

4. Code walkthrough

Initial DP

We first compute:

$c(n)$: number of valid digit strings,
$f(n)$: sum of all valid numbers.

For example:

$$f(5)=17891,$$

matching the problem statement.

Transition matrix

The matrix stores:

the last 9 values of $f$,
the last 9 values of $c$.

Each multiplication advances $n$ by 1.

Fast exponentiation

Since $13^{17}\approx 8.65\times10^{18}$, we use binary exponentiation:

$$M^N$$

in only $O(\log N)$ matrix multiplications.

5. Final verification

The computation:

reproduces the sample value $f(5)=17891$,
uses exact recurrences,
performs all arithmetic modulo $10^9$,
handles the huge exponents efficiently.

The final value obtained is:

$$216795703.$$

Answer: 216795703

Project Euler Problem 377