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

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.

This means that for each partition of the numbers 1 to 9 we can count how many 1 to n digit numbers there are using those digits. Note that we are really counting the 1 to n digit numbers, not just the n digit numbers since in our example, a 0 at the front is perfectly valid and the resulting DS-numbers are 4 digits.

But this doesn't solve the problem since we are looking for the sum of DS-numbers not how many there are, the idea is as follows:

Interactive Code

Input an integer (yourinput)

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