project_euler.problem_092.sol1

Project Euler Problem 092: https://projecteuler.net/problem=92 Square digit chains A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. For example, 44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89. How many starting numbers below ten million will arrive at 89?

References:

Functions

solution(→ int)

Returns how many starting numbers below number will arrive at 89

Module Contents

project_euler.problem_092.sol1.solution(number: int = 10000000) → int

Returns how many starting numbers below number will arrive at 89 in the digit-square chain.

Uses digit DP so the count is computed in O(k * d_max * 10) time — roughly 40 000 operations for number = 10^7 — instead of iterating all number values explicitly.

Key observations: 1. For any n < number, digit_square_sum(n) ≤ num_digits * 81,

so chain endpoints can be precomputed for that small range only.

  1. A digit DP over the decimal digits of (number - 1) counts how many integers in [0, number-1] have each possible digit-square sum, grouping by whether the prefix is still bounded (“tight”) or free. Integers whose digit-square sum equals 0 are exactly 0 itself.

>>> solution(100)
80

>>> solution(10_000_000)
8581146