# not homework... something i find an interesting problem

MRAB google at mrabarnett.plus.com
Tue Apr 21 22:31:55 CEST 2009

```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)

```