Project Euler/171

Problem Statement

Link: https://projecteuler.net/problem=171

For a positive integer n, let f(n) be the sum of the squares of the digits (in base 10) of n, e.g.

f(3) = 3² = 9

f(25) = 2² + 5² = 4 + 25 = 29

f(442) = 4² + 4² + 2² = 16 + 16 + 4 = 36

Find the last nine digits of the sum of all n, 0 < n < 10²⁰, such that f(n) is a perfect square.

Solution: https://git.charlesreid1.com/cs/euler/src/branch/main/scratch/Round7_170-180/Problem171.py

Explanation

This problem asks for the sum (modulo 10⁹) of all numbers up to 10²⁰ − 1 whose sum of squared digits is a perfect square.

Approach

Numbers with the same digits (in any order) share the same digit-square sum, so they can be grouped and counted combinatorially rather than enumerated individually.

For a given multiset of digits with counts d[0]…d[9] and total count N = Σ d[i]:

• The digit-square sum is S = Σ d[i] × i².
• If S is a perfect square, the contribution from all permutations of this digit multiset is computed using the formula for the sum of all multiset permutations:

$ \text{result} = \frac{N!}{d[0]! \; d[1]! \; \dots \; d[9]!} \times \frac{0 \cdot d[0] + 1 \cdot d[1] + \dots + 9 \cdot d[9]}{N} \times \frac{10^N - 1}{9} $

Only the last 9 digits are required, so the repunit factor (10^N − 1)/9 can be truncated modulo 10⁹ when N > 9, and intermediate results are reduced modulo 10⁹.

A recursive search builds digit multisets in non-decreasing digit order (to avoid duplicates), with a maximum of 20 digits. When the multiset is complete, the formula above is evaluated.