Project Euler 725 - Digit Sum Numbers

Official link: https://projecteuler.net/problem=725

Thought Process

I found this problem tricky, but in the end there is a nice solution.

Firstly notice that if x is a DS-number then there is a digit, i, such that sod(x) - i = i where sod(x) = sum of of digits of x. Equivalently, this is sod(x) = 2i, which leads us to https://oeis.org/A064544

My idea was the following:

Use the partition of a digit k to find all possible DS-numbers. For example, the partitions of 4 are

1. (1, 1, 1, 1)

2. (2, 1, 1)

3. (2, 2)

4. (3, 1)

5. (4, )

This means that if we have an n-digit number, x, where the sod(x) = 2*4, then we know what the rest of the digits in x must be based on the partition!

I have implemented a partition function before, but it needed some tweaking to generate the partitions instead of count how many there are.

Lets walk through the case of n = 5 with our partitions of 4. For any of our given partition's of 4 we want to count how many DS-numbers there are of each partition, take partition (2, 1, 1) for example. The numbers we use to create our DS-numbers are therefore (0, 1, 1, 2, 4), how many of these are there?

Well 5! possibilities, but we divide by the count, di!, of each digit, (where di  is the count of digit i in the partition), hence in total we have 5!/2!

In general we have the following formula.

Interactive Code

Input an integer (yourinput)

Code will output S(yourinput) (mod 10^(16))