🟩➕🟦

Square Sum

Week 36

Submit Answer Submit Code Solution See Hints See Solutions

There are many noteworthy things about the number 36 - like the fact it is highly factorisable and a triangular number. Your friend also claims its a relatively unique number, in that it can be made by adding many different combinations of square numbers together - you want to test your friend's theory to find out just how unique (or not) 36 is in this regard

For example, 36 can be made by summing the following square numbers:

Your program should output all square number combinations that sum to every number from 1 to 100 (in ascending order) - a few rules:

  • We will ignore 0 (i.e. 0 * 0) and 1 (i.e. 1 * 1) as square numbers - since otherwise you can trivially do 1 + 1 + 1...to create all positive integers, infinitely add 0s, add 0 to get a sum of more than 1 term. 4 (i.e. 2 * 2) should hence be the smallest square
  • Each combination should be unique and the terms should be displayed in ascending order - e.g. 4 + 4 + 16 is VALID, but any other order like 4 + 16 + 4 or 16 + 4 + 4 is NOT valid - this prevents having huge numbers of equivalent combinations for larger numbers and the ordered sequence is easier to visualise/understand for any end user
  • A sequence should consist of at least 2 numbers added together - i.e. 9 = 9 (3*3) is invalid, since that sum only consists of one square. In other words, the square number itself should not be valid - e.g. 4 = 4, 9 = 9, 16 = 16 etc
  • If a number has no square sum, then it shouldn't be output - for example, there is no way to make 1, 2, 3, 4, 5, 7, 9...etc by summing two square numbers, hence they shouldn't be output

As a hint, here are the first 3 lines of the valid output - for numbers with multiple solutions (like the 4 solutions for 36 above), the order of those solutions doesn't matter (e.g. you could put the 36 = 9 + 9 + 9 + 9 solution before the 36 = 4 + 4 + 4...+4 solution), since the site will order the lines, remove spaces etc when you click submit)

Paste your answer below:

Hints

Hints will be released at the start of each of the following days - e.g. the start of day 3 is 48 hours after the challenge starts

Release Day Hint
2 There are multiple ways to do this - a recursive approach could be easiest to implement. You might also find it helpful to pre-generate an array of valid squares [4, 9, 16...81] - 100 is not required, since adding even 4 + 100 will be greater than the limit of 100 for this challenge
3 You probably want a loop from 8-100 (you can start from 1 if you want - but we know that 4 + 4 = 8 will be the smallest valid sum), then call some outputSquareSums (which we will create) module for each number
4 The outputSquareSums module could be recursive - you can start with the smallest valid square, then call the function again adding each square that is equal or greater than it (since the terms should be in ascending order) to it - an array/string of numbers in the sum should be passed to each function call and the current total
5 For the base case, if the total equals 100, then you can output this expression as a valid sum
36 2026