Project Euler Problem 725
A number where one digit is the sum of the other digits is called a digit sum number or DS-number for short.
Solution
Answer: 4598797036650685
Using a combinatorial counting approach over digit multisets:
-
A DS-number has total digit sum $2d$, where one digit equals the sum of all others ($d \in {1,\dots,9}$).
-
Since $d \le 9$, the total digit sum is at most $18$, making the number of relevant digit multisets finite and small.
-
For each valid multiset and each length $n \le 2020$, count all permutations with no leading zero and sum their numeric values using symmetry of digit positions.
-
The implementation reproduces the checks:
-
$S(3)=63270$
-
$S(7)=85499991450$
Taking the result modulo $10^{16}$:
Answer: 4598797036650685