math - Python function to decompose a number in all possible sum of squares

Question

I am trying to solve this problem for days now, no strategy came to my mind. We need to decompose a number into all different possible ways it can be summed up from squares of other non repeating numbers.

Example: The number 50 can be decomposed in 3 different ways:

7^2 + 1^2   =   3^2 + 4^2 + 5^2   =   1^2 + 2^2 + 3^2 + 6^2   =   50

We need to know in how many ways can a random number be decomposed.

question from:https://stackoverflow.com/questions/65862330/python-function-to-decompose-a-number-in-all-possible-sum-of-squares

Answer 1

Let nsp( n) be the number of such partitions of n, and nspl( n, k) be the number of such partitions with the least number in it being k Then

nsp( n) = Sum{ k*k <= n | nspl( n, k) }
nspl( n, k) = 1, if n==k*k
              nspl( n-k*k, k+1), otherwise