# Project Euler 719 - Number Splitting

Note: I am quite happy with my solution and understanding of the problem however my code took a good 15 mins to run

# Thought Process

This problem was not very easy in my opinion, it took me a long time to get a code which worked at decent speed, however there are a few speed ups which can help

1. All n are perfect squares so we only need to check 10^6 numbers and square them

2. The hardest part of this problem is to find all the partitions of a number, however this can be made easy by thinking of partitions as the length of a number

• For example the Partitions of the number 4 including permutations are

1. 4 = [4]

2. 3 + 1, 1 + 3 = [3, 1], [1, 3]

3. 2 + 2 = [2, 2]

4. 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2 = [2, 1, 1], [1, 2, 1], [1, 1, 2]

5. 1 + 1 + 1 + 1 = [1, 1, 1, 1]

• Lets take the number 6724 in the example, because it is length 4 we can now represent all of the valid permutations extremely easily given the permutations of 4

1. [6724]

2. [672, 4], [6, 724]

3. [67, 24]

4. [67, 2 ,4], [6, 72, 4], [6, 7, 24]

5. [6, 7, 2, 4]

3. A mathematical 4.5x speedup happens because we are looking for all x such that sqrt(x) = sum of the digits of x, this means we can use a modulo 9 trick

# Interactive Code

Enter a number (yourinput)

Code will output sum of all S numbers less than yourinput