Digit constraints

This is a nice application of dynamic programming. Note that if we have a satisfying number $x$ of $n$ digits, we can extend it to $n+1$ digits easily: just consider the last two digits $a,b$ of $x$ , and append a digit $c$ where $a+b+c \le 7$ . All the previous digits are not affected by the addition of $c$ ; if they satisfy the condition (sum of three consecutive digits is at most 7), they will also satisfy it now. Thus we can do dynamic programming. We will keep track of three states: number of digits, second-last digit, and last digit. We abbreviate this as dp[n, a, b] . This counts the number of satisfying integers that has $n$ digits, whose last two digits are $a,b$ (where $a$ is the tens and $b$ is the units digit).

As the base cases, any two digit number $\overline{ab}$ with $a \neq 0$ satisfies the condition vacuously , just because there is no string of three consecutive digits. Thus dp[2, a, b] is equal to 1 for all $a \neq 0$ .

For the actual dynamic programming work, we simply translate the above observation into code. Suppose we have three digits $a,b,c$ where $a+b+c \le 7$ . Then every number of $n-1$ digits that ends with $a,b$ can be extended into a number of $n$ digits that ends with $b,c$ . In other words, we can add dp[n-1, a, b] to dp[n, b, c] . There's trivially no overlap, because different $a,b,c$ give different numbers. Now we just iterate that over all $a,b,c$ to fill our dynamic programming state of $n$ digits, and then iterate that over $n$ so we obtain the numbers for 77 digits.

Finally, once it's done, we simply add up everything together: we sum dp[77, a, b] over all $a,b$ to give the answer.

Python 3 code follows. This explains why I select to choose commas instead of a more common multi-dimensional array dp[n][a][b] , because it's easier to initialize a dict type whose keys are tuples (n, a, b) , instead of a layered list type with a layer for n , a layer for a , and a layer for b .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

dp = dict()
for n in range(2, 78):
    for a in range(8):
        for b in range(8):
            dp[n, a, b] = 0

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

for n in range(3, 78):
    for a in range(8):
        for b in range(8):
            if a+b > 7: continue
            for c in range(8-a-b):
                dp[n, b, c] += dp[n-1, a, b]

print(sum(dp[77, a, b] for a in range(8) for b in range(8)) % 1000)
>>> prints 718

(The actual number before modulo is 13080748169314291086539372946324303289341309985718.)

Now that you've done this, try Project Euler 164 .

Below is the solution that applies pure backtracking in Python 3. It also uses memoization to improve performance. The program finishes execution in a blink of an eye due to search optimizations.

from functools import lru_cache

NUM_DIGITS = 77
LIMIT = 7
MODULO = 1_000

@lru_cache(maxsize=128)
def count_integers(index = 0, prev_digit = 0, current_digit = 0):
    prefix_sum = prev_digit + current_digit
    if prefix_sum > LIMIT:
        return 0

    num_candidate_digits = 8 - prefix_sum    
    if index == NUM_DIGITS - 1:
        return num_candidate_digits

    count = 0
    for next_digit in range(num_candidate_digits):
        # We should start with a number whose most significant digit is one.
        if index == 0 and next_digit == 0:
            continue

        count += count_integers(index + 1, current_digit, next_digit)
    return count % MODULO

print(count_integers())