project_euler.problem_164.sol1

Project Euler Problem 164: https://projecteuler.net/problem=164

Three Consecutive Digital Sum Limit

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?

Brute-force recursive solution with caching of intermediate results.

Functions

solution(→ int)	Solves the problem for n_digits number of digits.
solve(→ int)	Solve for remaining 'digit' digits, with previous 'prev1' digit, and

Module Contents

project_euler.problem_164.sol1.solution(n_digits: int = 20) → int

Solves the problem for n_digits number of digits.

>>> solution(2)
45
>>> solution(10)
21838806

project_euler.problem_164.sol1.solve(digit: int, prev1: int, prev2: int, sum_max: int, first: bool, cache: dict[str, int]) → int

Solve for remaining ‘digit’ digits, with previous ‘prev1’ digit, and previous-previous ‘prev2’ digit, total sum of ‘sum_max’. Pass around ‘cache’ to store/reuse intermediate results.

>>> solve(digit=1, prev1=0, prev2=0, sum_max=9, first=True, cache={})
9
>>> solve(digit=1, prev1=0, prev2=0, sum_max=9, first=False, cache={})
10