Project Euler 719 - Number Splitting

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

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