not homework... something i find an interesting problem

[MRAB]

bearophileHUGS at lycos.com wrote:
> MRAB:
>> I think I might have cracked it:
>> ...
>>      print n, sums
> 
> Nice.
> If you don't want to use dynamic programming, then add a @memoize
> decoration before the function, using for example my one:
> http://code.activestate.com/recipes/466320/
> 
> And you will see an interesting speed increase, even if you don't use
> Psyco ;-)
> 
I discovered I hadn't got it quite right (it still missed some). Here's
the fixed code:

import math

def sumsq(n, depth=0):
     if n == 0:
         return [[]]
     root = int(math.sqrt(n))
     square = root ** 2
     sums = [[square] + s for s in sumsq(n - square, depth + 1)]
     while root > 0:
         square = root ** 2
         if square * len(sums[0]) < n:
             break
         more_sums = [[square] + s for s in sumsq(n - square, depth + 1)]
         if len(more_sums[0]) == len(sums[0]):
             sums.extend(more_sums)
         elif len(more_sums[0]) < len(sums[0]):
             sums = more_sums
         root -= 1
     sums = set(tuple(sorted(s, reverse=True)) for s in sums)
     sums = [list(s) for s in sorted(sums, reverse=True)]
     return sums

for n in range(1, 150):
     print n, sumsq(n)