Project Euler Problem 164

Solution

Answer: 378158756814587

We want to count 20-digit integers such that:

• the first digit is nonzero,
• and for every three consecutive digits, their sum is at most 9.

Let the digits be

$$d_1 d_2 \cdots d_{20},$$

with $d_1 \neq 0$, and for every $i$,

$$d_i + d_{i+1} + d_{i+2} \le 9.$$

This is a classic finite-state dynamic programming problem.

---

Mathematical analysis

The condition only depends on the previous two digits.

If we already know the last two digits $(a,b)$, then the next digit $c$ is allowed iff

$$a+b+c \le 9.$$

Thus:

$$c \in {0,1,\dots,9-a-b}.$$

So the entire process can be modeled as transitions between states consisting of the last two digits.

---

Defining the DP

Let

$$DP(k,a,b)$$

be the number of valid $k$-digit sequences ending in digits $a,b$, satisfying the condition for all triples.

The transition is:

$$DP(k+1,b,c) += DP(k,a,b)$$

for every $c$ such that

$$a+b+c \le 9.$$

---

Initialization

For a 2-digit prefix:

• first digit $a \in {1,\dots,9}$,
• second digit $b \in {0,\dots,9}$.

No triple exists yet, so every such pair is initially valid.

Thus:

$$DP(2,a,b)=1.$$

---

State count

The state space is tiny:

• $a,b \in {0,\dots,9}$,
• only $100$ states.

For each state, at most $10$ transitions exist.

So computation is trivial.

---

Python implementation

from collections import defaultdict

# dp[(a,b)] = number of valid sequences ending with digits a,b
dp = defaultdict(int)

# Initialize all valid 2-digit beginnings
for a in range(1, 10):      # first digit cannot be zero
    for b in range(10):
        dp[(a, b)] = 1

# Extend sequences until length 20
for length in range(2, 20):
    new_dp = defaultdict(int)

    for (a, b), count in dp.items():

        # Next digit c must satisfy a+b+c <= 9
        max_c = 9 - a - b

        for c in range(max_c + 1):
            new_dp[(b, c)] += count

    dp = new_dp

# Total number of valid 20-digit numbers
answer = sum(dp.values())

print(answer)

---

Code walkthrough

Initialization

dp = defaultdict(int)

We store counts keyed by the final two digits.

---

for a in range(1, 10):
    for b in range(10):
        dp[(a, b)] = 1

Every 2-digit number with nonzero first digit is initially valid.

There are:

$$9 \times 10 = 90$$

such states.

---

Main transition loop

for length in range(2, 20):

If we currently have sequences of length length, we extend them by one digit until we reach length 20.

---

for (a, b), count in dp.items():

Suppose the current sequence ends with digits $a,b$.

---

max_c = 9 - a - b

The next digit $c$ must satisfy

$$a+b+c \le 9.$$

---

for c in range(max_c + 1):

Enumerate every legal next digit.

---

new_dp[(b, c)] += count

The new sequence ends in digits $b,c$.

---

Final summation

answer = sum(dp.values())

After reaching length 20, sum all valid ending states.

---

Small sanity checks

For 3-digit numbers:

We count triples $(a,b,c)$ with:

• $a \ge 1$,
• $a+b+c \le 9$.

For each $a$,

$$#(b,c)=\sum_{s=0}^{9-a}(s+1).$$

This gives:

$$45+36+28+21+15+10+6+3+1 = 165.$$

The DP reproduces this correctly.

---

Final verification

The answer should be:

• much smaller than $9 \times 10^{19}$ (all 20-digit numbers),
• but still very large because many constrained sequences exist.

The dynamic programming is exact and exhaustive, with no overcounting.

Running the code yields:

$$378158756814587$$

---

Answer: 378158756814587