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

Mathematical Foundation

Theorem 1 (Recurrence). Let $f(\ell, a, b)$ denote the number of $\ell$-digit suffixes (allowing leading zeros) such that the first two digits are $a$ and $b$, and every three consecutive digits sum to at most 9. Then:

Proof. For $\ell = 2$, the suffix is exactly the two digits $a, b$ and there are no three-consecutive-digit windows, so $f(2, a, b) = 1$.

For $\ell \geq 3$, the suffix is $a, b, d, \ldots$ where $d$ is the third digit. The constraint on the first window requires $a + b + d \leq 9$, i.e., $d \leq 9 - a - b$. Since $a + b \leq 9$ (otherwise no valid suffix exists at all, and the sum is empty), we have $d \in \{0, 1, \ldots, 9 - a - b\}$. Choosing $d$ and continuing from the pair $(b, d)$ with $\ell - 1$ remaining digits gives the recurrence. $\square$

Theorem 2 (Answer formula). The number of 20-digit numbers with no three consecutive digits summing above 9 is:

Proof. The first digit $a$ ranges over $\{1, \ldots, 9\}$ (no leading zeros). The second digit $b$ must satisfy $a + b \leq 9$ (otherwise the pair $(a, b)$ cannot begin any valid triple), so $b \in \{0, \ldots, 9 - a\}$. The remaining 18 digits are counted by $f(20, a, b)$. $\square$

Lemma 1 (State space size). The number of valid states $(a, b)$ with $0 \leq a, b \leq 9$ and $a + b \leq 9$ is exactly $\binom{11}{2} = 55$.

Proof. We count pairs $(a, b)$ with $a + b \leq 9$:

$\square$

Lemma 2 (Matrix exponentiation alternative). Define the $55 \times 55$ transition matrix $M$ where rows and columns are indexed by valid states $(a,b)$, and $M_{(a,b),(b,d)} = 1$ if $a + b + d \leq 9$ (i.e., $d \leq 9 - a - b$), and 0 otherwise. Then $f(\ell, a, b) = \sum_{(c,e)} (M^{\ell-2})_{(a,b),(c,e)}$. This allows computation in $O(55^3 \log \ell)$ time.

Proof. Each multiplication by $M$ extends the suffix by one digit. After $\ell - 2$ multiplications, we sum over all terminal states. $\square$

Editorial

Count 20-digit numbers where no three consecutive digits sum > 9. Dynamic programming with state = (last two digits). We use dynamic programming with a rolling array. We then state: (last_two_digits) = (a, b) with a + b <= 9. Finally, initialize for length 2.

Pseudocode

DP with rolling array
State: (last_two_digits) = (a, b) with a + b <= 9
Initialize for length 2
Extend from length 2 to length 20
Sum over starting digits a >= 1

Complexity Analysis

• Time: $O(L \cdot S \cdot D)$ where $L = 20$ (digit positions), $S = 55$ (states), and $D \leq 10$ (digit choices per state). This gives $O(20 \cdot 55 \cdot 10) = O(11{,}000)$.
• Space: $O(S) = O(55)$ with a rolling array (two layers of DP).

Answer

#include <bits/stdc++.h>
using namespace std;

// Problem 164: No three consecutive digits sum > 9
// DP with state (last two digits)

int main() {
    const int DIGITS = 20;

    // dp[a][b] = count of valid numbers ending in digits a, b
    long long dp[10][10] = {};

    // First digit: 1-9, second digit: 0 to 9-first
    for (int a = 1; a <= 9; a++)
        for (int b = 0; b <= 9 - a; b++)
            dp[a][b] = 1;

    // Process digits 3 through 20
    for (int pos = 3; pos <= DIGITS; pos++) {
        long long ndp[10][10] = {};
        for (int a = 0; a <= 9; a++) {
            for (int b = 0; b <= 9 - a; b++) {
                if (dp[a][b] == 0) continue;
                int maxc = 9 - a - b;
                for (int c = 0; c <= maxc; c++) {
                    ndp[b][c] += dp[a][b];
                }
            }
        }
        memcpy(dp, ndp, sizeof(dp));
    }

    long long ans = 0;
    for (int a = 0; a <= 9; a++)
        for (int b = 0; b <= 9; b++)
            ans += dp[a][b];

    cout << ans << endl;
    return 0;
}

"""
Problem 164: Numbers for Which No Three Consecutive Digits Have a Sum Greater Than 9

Count 20-digit numbers where no three consecutive digits sum > 9.
Dynamic programming with state = (last two digits).
"""

def solve():
    DIGITS = 20

    # dp[a][b] = count of valid numbers ending in digits a, b
    dp = [[0]*10 for _ in range(10)]

    # Initialize: first two digits
    for a in range(1, 10):  # no leading zero
        for b in range(0, 10 - a):
            dp[a][b] = 1

    # Fill digits 3 through 20
    for pos in range(3, DIGITS + 1):
        ndp = [[0]*10 for _ in range(10)]
        for a in range(10):
            for b in range(10 - a):
                if dp[a][b] == 0:
                    continue
                for c in range(10 - a - b):
                    ndp[b][c] += dp[a][b]
        dp = ndp

    ans = sum(dp[a][b] for a in range(10) for b in range(10))
    print(ans)

solve()