Project Euler Problem 506

Solution

Answer: 18934502

Let the infinite digit stream be

$$123432123432123432\cdots$$

We partition it into consecutive integers $v_n$ so that the digit sum of $v_n$ equals $n$.

The first terms are:

$$1,2,3,4,32,123,43,2123,432,1234,32123,\dots$$

We want

$$S(n)=\sum_{k=1}^{n} v_k$$

and specifically

$$S(10^{14}) \bmod 123454321.$$

1. Mathematical analysis

Step 1: Observe the periodic structure

The repeating block is

$$123432$$

whose digit sum is

$$1+2+3+4+3+2 = 15.$$

This is the key insight.

Since the repeating block sums to 15, increasing the target digit sum by 15 simply appends one whole cycle of digits.

For example:

$n$	$v_n$
1	1
16	1234321
31	1234321234321

Likewise:

$n$	$v_n$
5	32
20	32123432
35	32123432123432

So for fixed residue $r=n\bmod 15$,

$$n=15q+r$$

the number $v_n$ has the form:

$$v_{15q+r} = \underbrace{C_rC_r\cdots C_r}_{q\text{ copies}},B_r$$

where:

$B_r=v_r$ (the base pattern),
$C_r$ is a 6-digit cyclic block.

For example:

$$B_5=32,\qquad C_5=321234$$

$$v_{20}=32123432.$$

Step 2: Decimal-value formula

If $L_r$ is the digit length of $B_r$, then

$$v_{15q+r} = \left( C_r\sum_{i=0}^{q-1}10^{6i} \right)10^{L_r} + B_r.$$

The geometric part is

$$R_q = \sum_{i=0}^{q-1}10^{6i} = \frac{10^{6q}-1}{10^6-1}.$$

Thus

$$v_{15q+r} = C_r,10^{L_r}R_q+B_r.$$

Step 3: Summing over all $q$

For fixed residue $r$, let

$$m_r = \left\lfloor\frac{N-r}{15}\right\rfloor+1$$

be the number of terms.

Then

$$S_r = \sum_{q=0}^{m_r-1} v_{15q+r}.$$

Substitute the formula:

$$S_r = m_rB_r + C_r10^{L_r} \sum_{q=0}^{m_r-1}R_q.$$

Now

$$\sum_{q=0}^{m-1}R_q = \frac{ \sum_{q=0}^{m-1}10^{6q}-m }{ 10^6-1 }$$

and

$$\sum_{q=0}^{m-1}10^{6q} = \frac{10^{6m}-1}{10^6-1}.$$

Everything can be computed modulo

$$M=123454321$$

using modular inverses.

Because

$$\gcd(999999,M)=1,$$

division modulo $M$ is valid.

2. Python implementation

MOD = 123454321
BASE = 10**6
D = BASE - 1  # 999999

# First 15 base values v_r
B = [
    None,
    "1", "2", "3", "4", "32",
    "123", "43", "2123", "432",
    "1234", "32123", "43212",
    "34321", "23432", "123432"
]

# Corresponding repeating 6-digit blocks
C = [
    None,
    "123432", "234321", "343212", "432123",
    "321234", "123432", "432123", "212343",
    "432123", "123432", "321234", "432123",
    "343212", "234321", "123432"
]

def solve(N):
    inv_D = pow(D, -1, MOD)
    inv_geom = pow(BASE - 1, -1, MOD)

    total = 0

    for r in range(1, 16):
        if r > N:
            break

        # number of q-values
        m = (N - r) // 15 + 1

        b = int(B[r])
        c = int(C[r])
        L = len(B[r])

        # geometric sum:
        # sum_{q=0}^{m-1} 10^(6q)
        geom = (
            (pow(BASE, m, MOD) - 1)
            * inv_geom
        ) % MOD

        # sum of R_q
        sum_R = ((geom - m) % MOD) * inv_D % MOD

        contribution = (
            (m % MOD) * (b % MOD)
            + c * pow(10, L, MOD) * sum_R
        ) % MOD

        total = (total + contribution) % MOD

    return total

# Checks
print(solve(11))    # 36120
print(solve(1000))  # 18232686

# Final answer
print(solve(10**14))

3. Code walkthrough

B[r] stores the base pattern $v_r$.
C[r] stores the repeating 6-digit cycle for residue $r$.
For each residue class $r=1,\dots,15$:
count how many terms appear up to $N$,
compute the geometric series modulo $M$,
compute the total contribution of that residue class,
add it to the answer.

Verification

The program reproduces the examples:

$$S(11)=36120$$

and

$$S(1000)\bmod 123454321=18232686.$$

Both match the problem statement exactly.

4. Final verification

The computation is:

logarithmic in $N$ (only modular exponentiation),
uses exact modular arithmetic,
matches all provided examples,
avoids handling gigantic integers directly.

Therefore the result is reliable.

Answer: 18934502