Detailed mathematical approach

Problem Summary

The problem asks for the number of 20-digit decimal numbers with no leading zero such that every block of three consecutive digits has sum at most 9. If the digits are \(d_1,d_2,\dots,d_{20}\), the condition is

$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$

A brute-force search would have to inspect \(9\cdot 10^{19}\) candidates, which is hopeless. The crucial fact is that the legality of the next digit depends only on the previous two digits, so the whole problem collapses to a finite-state dynamic program.

Mathematical Approach

The condition is a sliding window of width 3, so the right viewpoint is to keep track of the last two digits of a valid prefix and forget everything earlier.

The right state space: the last two digits

Suppose two valid prefixes end in the same ordered pair \((a,b)\). Any future continuation will be legal for one prefix exactly when it is legal for the other, because every new test only inspects the new triple formed with those two final digits. That means the complete history can be compressed to the suffix \((a,b)\).

This gives a directed graph on the 100 ordered digit pairs \((a,b)\) with \(0\le a,b\le 9\). There is an edge

$(a,b)\to(b,c)$

exactly when

$a+b+c\le 9.$

So a valid 20-digit number is nothing more than a valid 2-digit start, with first digit nonzero, followed by an 18-step walk in this graph.

State definition and the initial layer

Let \(A_n(a,b)\) be the number of valid \(n\)-digit prefixes whose last two digits are \(a\) and \(b\). For \(n=2\), nothing has been checked yet except the leading-zero rule, so

$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{otherwise.} \end{cases}$

This base layer contains the 90 possible two-digit starts \(10,11,\dots,99\). Some of those pairs will die immediately when we try to append a third digit, but they are still legitimate length-2 prefixes.

The recurrence and the reachable-state invariant

From a state \((a,b)\), the next digit \(c\) is allowed exactly when the new triple has acceptable sum, namely \(a+b+c\le 9\). Therefore, for \(n\ge 2\),

$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{whenever } b+c\le 9,$

and \(A_{n+1}(b,c)=0\) if \(b+c>9\).

This formula reveals a useful invariant. Once the number has length at least 3, every reachable suffix \((a,b)\) satisfies \(a+b\le 9\), because it must have appeared inside some valid triple. So the active state space shrinks from 100 table cells to only

$\sum_{a=0}^{9}(10-a)=55$

reachable pairs after the first true transition.

Worked example: the three-digit checkpoint

The smallest nontrivial case is \(n=3\). For a fixed first digit \(a\) and second digit \(b\), the third digit can be any value in \(\{0,1,\dots,9-a-b\}\), so there are \(10-a-b\) choices whenever \(a+b\le 9\).

Hence

$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$

where \(N_n\) denotes the total number of valid \(n\)-digit numbers. For example, if a valid prefix currently ends in \((3,1)\), then the next digit can only be \(0,1,2,3,4,5\); choosing 6 or more would make the sum of the last three digits exceed 9. This is exactly the rule applied at every later position as well.

Extracting the 20-digit total

After iterating the recurrence until length 20, every valid 20-digit number appears in exactly one final state. Therefore

$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$

That is the whole solution. The original question about 20-digit numbers with a local three-digit restriction becomes a repeated update on a fixed \(10\times 10\) table.

How the Code Works

The C++, Python, and Java implementations all store a \(10\times 10\) table indexed by the last two digits. The entry in row \(a\), column \(b\) is the number of currently known valid prefixes that end in \((a,b)\).

They initialize that table by assigning one count to every two-digit starting prefix whose first digit is 1 through 9 and whose second digit is 0 through 9. Then they sweep positions 3 through 20. For each populated state \((a,b)\), they test every candidate next digit \(c\in\{0,\dots,9\}\); if \(a+b+c\le 9\), the current count is added to the next-layer entry for \((b,c)\). After finishing one position, the old table is discarded and the new one becomes the current state.

At the end, the implementations sum all entries of the last table. A checkpointed version also verifies the small cases \(N_3=165\) and \(N_4=990\), which are consistent with the same recurrence. The fully general form of the algorithm also has the trivial edge cases \(N_1=9\) and \(N_2=90\).

Complexity Analysis

There are at most 100 pair states and, from each state, at most 10 candidate next digits. For a target length \(L\), the running time is therefore

$O(L\cdot 100\cdot 10)=O(L).$

In this problem \(L=20\), so the actual workload is tiny. The memory usage is \(O(100)\), because only the current \(10\times 10\) table and the next one are needed. Mathematically only 55 states remain reachable after the first extension, although the code keeps the full 100-cell grid for simplicity.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=164
2. Dynamic programming: Wikipedia - Dynamic programming
3. Finite-state machine: Wikipedia - Finite-state machine
4. Transfer-matrix method: Wikipedia - Transfer-matrix method
5. Introduction to dynamic programming: CP-Algorithms - Introduction to Dynamic Programming