Problem 164: Numbers for Which No Three Consecutive Digits Have a Sum Greater Than a Given Value

Project Euler Problem 164 Solution

EulerSolve provides an optimized solution for Project Euler Problem 164, Numbers for Which No Three Consecutive Digits Have a Sum Greater Than a Given Value, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

We must count the numbers $n$ with exactly $20$ digits and no leading zero, that is $10^{19}\le n\lt10^{20}$, in which no three consecutive digits have a sum greater than $9$. With the digits written as $d_1d_2\dots d_{20}$, these are the $18$ conditions

$$d_i+d_{i+1}+d_{i+2}\le9\quad(1\le i\le18).$$

For instance, the five-digit number $20313$ obeys the rule, with the sums $5$, $4$ and $7$ of three consecutive digits, while $20361$ breaks it, because $3+6+1=10$. The statement gives no example values. ^[1]

The whole solution in one sentence: whether a further digit may be appended to a number depends only on its last two digits, so we keep, for each of the $100$ possible pairs of last digits, the number of valid numbers that end in it, and update these $100$ counts one digit at a time from length $2$ to length $20$.

Mathematical Approach

1. Short numbers by hand

Call a string of digits valid if each of its windows, the blocks of three consecutive digits, has a sum of at most $9$, and let $N_L$ be the number of valid $L$-digit numbers, with first digit at least $1$. Numbers with one or two digits have no window, so all of them are valid: $N_1=9$ and $N_2=90$.

A three-digit number with the digits $a,b,c$ is valid when $a\ge1$ and $a+b+c\le9$. Such conditions are counted with stars and bars. ^[2] We first ignore the condition $a\ge1$. With the slack $s=9-a-b-c$ we need $a+b+c+s=9$ with all four numbers at least $0$, which also keeps every digit at most $9$. Write $9$ stars and $3$ bars in a row: the numbers of stars in the four gaps that the bars create, from left to right, are $a$, $b$, $c$ and $s$. Each solution is therefore exactly one choice of $3$ places for the bars among $12$, so there are $\binom{12}{3}=220$ windows with a sum of at most $9$. Those with $a=0$ solve $b+c+s=9$, and there are $\binom{11}{2}=55$ of them. Hence $N_3=220-55=165$.

For four digits the windows $a\,b\,c$ and $b\,c\,d$ overlap, and one slack no longer suffices. Testing all $9\cdot10^{19}$ candidates with $20$ digits is out of the question too, so a systematic method is needed.

2. What the beginning of a number has to remember

Every window of a beginning $d_1\dots d_k$ of a valid number, a prefix, is also a window of the whole number, so prefixes are valid. Appending a digit to a prefix of at least two digits creates exactly one new window, made of the new digit and the last two digits of the prefix.

Claim. Let $x$ and $y$ be valid strings of at least two digits that end in the same two digits $a,b$. Then for every string $z$ of further digits, $xz$ is valid exactly when $yz$ is valid.

Proof. A window of $xz$ either lies inside $x$, where its sum is at most $9$ because $x$ is valid, or it contains at least one digit of $z$. A window of the second kind has only three digits, so it uses at most the last two digits of $x$: it is $a\,b\,z_1$, $b\,z_1z_2$ or a window inside $z$. These windows are the same for $xz$ and $yz$, and so are the conditions they impose. $\square$

The last digit alone would not be enough: $10$ and $90$ end in the same digit, but $108$ is valid and $908$ is not.

3. Pairs of digits as states

Draw the $100$ ordered pairs $(a,b)$ of digits as points, and an arrow $(a,b)\to(b,c)$ whenever $a+b+c\le9$. Each arrow stands for exactly one window $a\,b\,c$ with a sum of at most $9$, so by Section 1 there are $220$ arrows. For $L\ge2$, an $L$-digit number runs through the pairs $(d_1,d_2)$, $(d_2,d_3)$, …, $(d_{L-1},d_L)$, and it is valid exactly when each of these $L-2$ steps follows an arrow; $20313$, for example, is the walk $(2,0)\to(0,3)$${}\to(3,1)\to(1,3)$. From $(3,1)$ the arrows lead only to $(1,0),\dots,(1,5)$, since $3+1+c\le9$ means $c\le5$. So the valid $L$-digit numbers are exactly the walks of $L-2$ steps that start at a pair whose first digit is at least $1$.

With all $1000$ arrows, one for every $a$, $b$ and $c$, the picture would be the de Bruijn graph of pairs of digits. ^[3] A step can only end at a pair $(b,c)$ with $b+c\le9$, and the $45$ pairs with a larger sum have no arrows at all, so after the first step at most $55$ pairs carry walks.

4. Counting walks one digit at a time

Let $A_n(a,b)$ be the number of valid $n$-digit numbers whose last two digits are $a$ and $b$. For two digits each of the $90$ numbers is its own pair:

$$A_2(a,b)=\begin{cases}1,&a\ge1,\\0,&a=0.\end{cases}$$

For $n\ge2$ and all digits $b,c$,

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

where the sum is empty, giving $0$, when $b+c\gt9$. Indeed, deleting the last digit of a valid $(n+1)$-digit number ending in $b,c$ leaves a valid $n$-digit number ending in some $a,b$, with $a+b+c\le9$ by its last window. Conversely, appending $c$ to a valid $n$-digit number ending in $a,b$ creates the single new window $a\,b\,c$, so the result is valid exactly when $a+b+c\le9$. The two operations undo each other, so both sides count the same numbers. Every valid number ends in exactly one pair, hence

$$N_L=\sum_{a=0}^{9}\sum_{b=0}^{9}A_L(a,b)\qquad(L\ge2).$$

This is dynamic programming: each table is built once from the previous one, and the numbers themselves are never listed. ^[4] The ban on a leading zero enters only through $A_2$: with a $1$ in all $100$ cells the steps would count strings with leading zeros, $220$ instead of $165$ for three digits.

5. Worked example: three and four digits

Starting from $A_2$, the sum for $A_3(b,c)$ adds a $1$ for each first digit $a$ from $1$ to $9-b-c$, so

$$A_3(b,c)=9-b-c\qquad(b+c\le9).$$

For example $A_3(3,1)=5$ counts $131$, $231$, $331$, $431$ and $531$. Every pair with $b+c=9$ gets $0$, because a first digit of at least $1$ would make the window sum at least $10$. Exactly $s+1$ pairs have the sum $b+c=s$, so grouping the pairs by $s$ gives

$$N_3=\sum_{s=0}^{9}(s+1)(9-s)=165,$$

with the terms $9,16,21,24,25,24,21,16,9,0$, in agreement with Section 1. A three-digit number ending in $b,c$ with $b+c=s$ can be continued by the $10-s$ digits from $0$ to $9-s$, so

$$\begin{aligned}N_4&=\sum_{s=0}^{9}(s+1)(9-s)(10-s)\\&=990,\end{aligned}$$

with the terms $90,144,168,168,150,\,$$120,84,48,18,0$. These are the two values that the C++ program checks before its main run. Further steps give $N_5=5445$, $N_6=27588$, $N_7=146586$, $N_8=783057$, $N_9=4129851$ and $N_{10}=21838806$.

6. The matrix behind the recurrence

Written with the tables as row vectors, the recurrence is $A_{n+1}=A_nM$, where the adjacency matrix $M$ of the picture has a $1$ in row $(a,b)$ and column $(b,c)$ for each arrow and $0$ elsewhere. So $A_{20}=A_2M^{18}$, and the entries of $M^k$ count the walks of $k$ steps. ^[5] Repeated squaring would give $M^k$ with about $\log_2k$ matrix products, which pays off only for enormous lengths.

7. How large the counts become

Cut the $20$ digits into the six disjoint windows $d_1d_2d_3,\dots,d_{16}d_{17}d_{18}$ and the final pair $d_{19}d_{20}$. The first window has $165$ possible values, each other window at most $220$, and the final pair at most $55$, since its two digits lie in the last window and so have a sum of at most $9$. Ignoring the conditions on the windows that cross the cuts can only increase the count, so

$$N_{20}\le165\cdot220^5\cdot55\lt4.7\cdot10^{15},$$

far below $2^{63}\approx9.2\cdot10^{18}$. No number in the computation exceeds $N_{20}$: a sum of entries of the table for length $n$ is at most $N_n$, and $N_n\le N_{n+1}$, because appending a $0$ to a valid number of at least three digits keeps it valid, its last two digits lying in a window, while $N_2=90\lt N_3$. So $64$-bit integers cannot overflow. The count passes $2^{64}$ only at $27$ digits; $N_{26}$ is still below $2^{63}$.

How the Code Works

In the C++ program, ^[6] parse_arguments accepts --skip-checkpoints and --length= with decimal digits, read by parse_int_after_prefix, with default length $20$; any other argument or a length below $1$ gives exit code $1$. The digits are accumulated in an int without a range check, so a length beyond its range is undefined behaviour with no guaranteed result; ^[7] in the build used here, --length=4294967297 acted as length $1$. Unless switched off, run_checkpoints then requires the values $165$ and $990$ of Section 5 from solve(3) and solve(4), with exit code $2$ on a failure, before main prints solve(options.length).

solve returns $9$ for length $1$. Otherwise it fills the table dp, ten std::vector rows of ten u64 (unsigned 64-bit) entries that hold $A_n(a,b)$, with a $1$ in the $90$ cells dp[d1][d2] with d1 from $1$ to $9$, which is $A_2$, and for length $2$ returns their sum at once. The loop over pos from $3$ to length builds a new table next of zeros for each digit and leaves dp unchanged until the step is complete, since an update in place would mix old and new counts. For each pair $(a,b)$ with a nonzero count ways and each digit c with a + b + c at most $9$, an arrow of Section 3, it adds ways to next[b][c]. This pushes the counts forward along the arrows instead of gathering the sum of Section 4 for each target pair; every term of that sum is added exactly once, so next becomes $A_{n+1}$, which dp = std::move(next) takes over without copying. The sum of the final $100$ cells is $N_L$. The test ways == 0 skips empty cells: only $45$ and $54$ pairs are nonzero for lengths $3$ and $4$, and $55$ from length $5$ on.

The Python and Java programs fix the length at $20$ and have no options or checkpoints; they run the same loops, Python in solve with the lists dp and nxt, Java in main with long[][] arrays. Python's integers are unbounded and Java's long is a signed 64-bit type, so by Section 7 no version overflows at length $20$. From --length=27 on, however, the counts exceed $2^{64}-1$, and as unsigned arithmetic works modulo $2^{64}$, ^[7] the C++ program then silently prints the remainder of $N_L$ on division by $2^{64}$. The largest length that int can hold would in addition overflow the loop counter pos.

Complexity and Verification

Each of the $L-2$ steps visits $100$ cells and tests at most $10$ digits for each nonzero cell, so the number of operations is linear in $L$, about a thousand per digit, and the memory is two tables of $100$ numbers. For $L=20$ the main loop visits $1800$ cells, tests $10140$ digits and performs $3894$ additions. On a desktop computer a whole run, start-up included, takes about two milliseconds in C++ and a few hundredths of a second in Python and Java.

Besides the C++ checkpoints, all three programs were run for this article and print the same number. A separate C program tested every number with at most $10$ digits directly, $9\cdot10^9$ of them for length $10$ alone, and found exactly the counts $N_1,\dots,N_{10}$ of Sections 1 and 5. An exact Python computation of $A_2M^{18}$ by matrix powers agrees with the programs. With --length=L the C++ program is exact for every $L\le26$ and gives $N_L$ modulo $2^{64}$ for every $L\le60$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The reduction to pairs of last digits, the recurrence, the worked counts and the size bound are derived in this article.

Project Euler 164 — Three Consecutive Digital Sum Limit. The official statement asks how many 20-digit numbers n without any leading zero exist such that no three consecutive digits of n have a sum greater than 9. It gives no example values.
Wikipedia — Stars and bars (combinatorics). Theorem two: the number of k-tuples of non-negative integers with sum n is C(n + k − 1, k − 1). For n = 9 this gives C(12, 3) = 220 with k = 4 and C(11, 2) = 55 with k = 3, the counts of Section 1.
Wikipedia — De Bruijn graph. Its vertices are the sequences of n symbols from an alphabet of m symbols, with an arrow from each sequence to every sequence obtained by dropping its first symbol and adding a new one at the end. For m = 10 and n = 2 these are the 100 pairs and 1000 arrows of Section 3.
Wikipedia — Dynamic programming. Dynamic programming breaks a complicated problem into simpler sub-problems, solves each of them once and builds larger solutions from tables of smaller ones; it can count solutions without visiting them all.
Wikipedia — Adjacency matrix. The (i, j) entry of the n-th power of the adjacency matrix counts the walks of length n from vertex i to vertex j, in directed as well as undirected graphs.
C++ — Euler164.cpp. The linked immutable C++ revision contains parse_arguments, solve and run_checkpoints. It is the implementation record for this article.
cppreference — Arithmetic operators. Unsigned integer arithmetic is performed modulo 2ⁿ, n being the number of bits of the type, while overflow in signed integer arithmetic is undefined behaviour, which may show up as a wrap-around.

Problem 164 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int length = 20;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--length=", options.length)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.length >= 1;
}

u64 solve(const int length) {
    if (length == 1) {
        return 9;
    }

    std::vector<std::vector<u64>> dp(10, std::vector<u64>(10, 0));
    for (int d1 = 1; d1 <= 9; ++d1) {
        for (int d2 = 0; d2 <= 9; ++d2) {
            dp[static_cast<std::size_t>(d1)][static_cast<std::size_t>(d2)] += 1ULL;
        }
    }

    if (length == 2) {
        u64 sum = 0;
        for (int a = 0; a <= 9; ++a) {
            for (int b = 0; b <= 9; ++b) {
                sum += dp[static_cast<std::size_t>(a)][static_cast<std::size_t>(b)];
            }
        }
        return sum;
    }

    for (int pos = 3; pos <= length; ++pos) {
        std::vector<std::vector<u64>> next(10, std::vector<u64>(10, 0));

        for (int a = 0; a <= 9; ++a) {
            for (int b = 0; b <= 9; ++b) {
                const u64 ways = dp[static_cast<std::size_t>(a)][static_cast<std::size_t>(b)];
                if (ways == 0) {
                    continue;
                }
                for (int c = 0; c <= 9; ++c) {
                    if (a + b + c > 9) {
                        continue;
                    }
                    next[static_cast<std::size_t>(b)][static_cast<std::size_t>(c)] += ways;
                }
            }
        }

        dp = std::move(next);
    }

    u64 sum = 0;
    for (int a = 0; a <= 9; ++a) {
        for (int b = 0; b <= 9; ++b) {
            sum += dp[static_cast<std::size_t>(a)][static_cast<std::size_t>(b)];
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (solve(3) != 165ULL) {
        std::cerr << "Checkpoint failed for length=3" << '\n';
        return false;
    }
    if (solve(4) != 990ULL) {
        std::cerr << "Checkpoint failed for length=4" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.length) << '\n';
    return 0;
}

Python

# Problem 164: Numbers for which no three consecutive digits have a sum > 9

def solve():
    length = 20
    # dp[a][b] = ways to form number ending in digits (a, b)
    dp = [[0]*10 for _ in range(10)]
    for d1 in range(1, 10):
        for d2 in range(10):
            dp[d1][d2] = 1
    for pos in range(3, length + 1):
        nxt = [[0]*10 for _ in range(10)]
        for a in range(10):
            for b in range(10):
                if dp[a][b] == 0: continue
                for c in range(10):
                    if a + b + c > 9: continue
                    nxt[b][c] += dp[a][b]
        dp = nxt
    print(sum(dp[a][b] for a in range(10) for b in range(10)))

solve()

Java

public class Euler164 {
    public static void main(String[] args) {
        int len = 20;
        long[][] dp = new long[10][10];
        for (int d1 = 1; d1 <= 9; d1++)
            for (int d2 = 0; d2 <= 9; d2++)
                dp[d1][d2] = 1;
        for (int pos = 3; pos <= len; pos++) {
            long[][] nxt = new long[10][10];
            for (int a = 0; a <= 9; a++)
                for (int b = 0; b <= 9; b++) {
                    if (dp[a][b] == 0)
                        continue;
                    for (int c = 0; c <= 9; c++) {
                        if (a + b + c > 9)
                            continue;
                        nxt[b][c] += dp[a][b];
                    }
                }
            dp = nxt;
        }
        long sum = 0;
        for (int a = 0; a < 10; a++)
            for (int b = 0; b < 10; b++)
                sum += dp[a][b];
        System.out.println(sum);
    }
}