Problem Summary

An infinite digit stream repeats

$$1,2,3,4,3,2,1,2,3,4,3,2,\dots$$

The stream is continuous: after \(v_n\) is built, the next term starts exactly where the previous one stopped. For each positive integer \(n\), \(v_n\) is the decimal integer obtained by concatenating successive digits until their digit-sum is exactly \(n\). The first terms are

$$v_1=1,\quad v_2=2,\quad v_3=3,\quad v_4=4,\quad v_5=32,\quad v_6=123,\dots$$

The goal is to compute

$$S(N)=\sum_{n=1}^{N} v_n \pmod{123454321}$$

for an enormous value of \(N\). A direct simulation would require producing every term one after another, so the solution must exploit the periodicity of the digit stream and the arithmetic structure of the digit sums.

Mathematical Approach

The decisive observation is that the sequence does not need to be handled term by term forever. Once the terms are grouped by their residue class modulo \(15\), each group follows a simple affine recurrence.

Step 1: Track the Starting Position of Each Term

After the first \(m\) terms have been completed, the total digit-sum consumed from the stream is

$$A_m=1+2+\cdots+m=\frac{m(m+1)}{2}.$$

One complete clock cycle uses the six digits \(1,2,3,4,3,2\), whose sum is

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

The partial sums inside one cycle are \(0,1,3,6,10,13,15\), and these are all distinct modulo \(15\). Therefore the position inside the six-digit cycle is determined by the consumed digit-sum modulo \(15\).

The term \(v_n\) starts after the first \(n-1\) terms, so its starting position depends on \(A_{n-1}\). Now

$$A_{n+14}-A_{n-1}=\frac{(n+14)(n+15)-(n-1)n}{2}=15(n+7),$$

which is divisible by \(15\). Hence \(v_n\) and \(v_{n+15}\) always start at the same point of the repeating digit stream. This is why the natural classification is by \(n \bmod 15\).

Step 2: Terms in the Same Residue Class Differ by One Six-Digit Block

Fix a residue \(r \in \{1,\dots,15\}\) and write

$$n=r+15k.$$

The terms \(v_r,v_{r+15},v_{r+30},\dots\) all start at the same stream position. Their target digit-sums differ by \(15\), and the next complete cycle from any fixed position contains exactly six digits whose sum is \(15\). Therefore, once \(v_{r+15k}\) has been read, the term \(v_{r+15(k+1)}\) is obtained by appending one more six-digit rotation of the clock sequence.

If \(B=10^6\), appending six decimal digits multiplies the previous number by \(B\). So there exist constants \(b_r\) and \(a_r\), depending only on the residue class \(r\), such that

$$b_r=v_r,$$

$$v_{r+15(k+1)}=B\,v_{r+15k}+a_r.$$

The quantity \(a_r\) is the six-digit block appended in that residue class.

Step 3: Solve the Affine Recurrence

The recurrence

$$x_{k+1}=B\,x_k+a_r,\qquad x_0=b_r$$

has the closed form

$$x_k=b_r B^k+a_r\sum_{j=0}^{k-1}B^j.$$

Therefore

$$v_{r+15k}=b_r B^k+a_r\frac{B^k-1}{B-1}.$$

This formula is exact over the integers and is the core reason the huge input becomes manageable.

Step 4: Sum One Residue Class at a Time

For a fixed residue \(r\), the number of indices of the form \(r+15k\) that do not exceed \(N\) is

$$K_r=\left\lfloor\frac{N-r}{15}\right\rfloor+1 \qquad (N \ge r).$$

Define the two standard sums

$$P(K)=\sum_{k=0}^{K-1} B^k=\frac{B^K-1}{B-1},$$

$$Q(K)=\sum_{k=0}^{K-1}\frac{B^k-1}{B-1}=\frac{P(K)-K}{B-1}.$$

Then the total contribution of residue class \(r\) is

$$\sum_{k=0}^{K_r-1} v_{r+15k}=b_r P(K_r)+a_r Q(K_r).$$

Summing over all possible residues gives

$$S(N)=\sum_{r=1}^{\min(15,N)}\left(b_r P(K_r)+a_r Q(K_r)\right)\pmod{123454321}.$$

Step 5: Modular Form of the Formula

The implementation works modulo

$$M=123454321.$$

Since

$$\gcd(B-1,M)=\gcd(999999,123454321)=1,$$

the factor \(B-1\) has a modular inverse modulo \(M\). Thus the divisions in \(P(K)\) and \(Q(K)\) are carried out safely as multiplications by \((B-1)^{-1} \pmod{M}\), while \(B^K \pmod{M}\) is obtained by fast exponentiation.

Worked Example: The Residue Class \(r=5\)

The exact terms in this class begin as

$$v_5=32,\qquad v_{20}=32123432,\qquad v_{35}=32123432123432.$$

Therefore

$$a_5=v_{20}-10^6 v_5=32123432-32000000=123432.$$

The closed form becomes

$$v_{5+15k}=32 \cdot 10^{6k}+123432\frac{10^{6k}-1}{10^6-1}.$$

For \(k=2\), this gives

$$32 \cdot 10^{12}+123432(10^6+1)=32123432123432,$$

which matches the third exact term. As a small full-sequence checkpoint, the first eleven terms satisfy

$$S(11)=36120.$$

How the Code Works

The C++, Python, and Java implementations first generate the first \(45\) terms exactly. That is enough to obtain three terms from each residue class modulo \(15\): \(v_r\), \(v_{r+15}\), and \(v_{r+30}\).

From these values, the implementation extracts the initial value \(b_r=v_r\) and the appended six-digit block

$$a_r=v_{r+15}-10^6 v_r.$$

It then checks that the same block also satisfies

$$v_{r+30}=10^6 v_{r+15}+a_r,$$

so the affine law is verified before the large-\(N\) computation begins.

After that, the program uses fast modular exponentiation to evaluate \(B^{K_r} \pmod{M}\), computes the modular inverse of \(B-1\), forms \(P(K_r)\) and \(Q(K_r)\) modulo \(M\), and accumulates the \(15\) residue-class contributions. The exact prefix generation is only a fixed-size calibration step; the enormous target \(N\) is handled entirely by closed forms.

Complexity Analysis

Generating the first \(45\) exact terms is constant work. The main computation processes only \(15\) residue classes, and each class requires a constant number of modular operations plus one modular exponentiation \(B^{K_r}\). Therefore the total running time is

$$O(\log N),$$

and the memory usage is

$$O(1).$$

Footnotes and References

1. Problem page: https://projecteuler.net/problem=506
2. Geometric series: Wikipedia — Geometric series
3. Recurrence relation: Wikipedia — Recurrence relation
4. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
5. Triangular number: Wikipedia — Triangular number