not homework... something i find an interesting problem

[Dave Angel]

Trip Technician wrote:
> although it's not homework (how can i prove that...?) i am still happy
> with just hints
>
> +++
>
> we want to express integers as sums of squares. (repeated squares are
> allowed)
>
> most numbers have one minimal representation e.g. 24=16+4+4, some have
> two or more e.g. 125 = 121+4 = 100+25
>
> so far I have created a simple recursive function that expresses a
> given number as a sum of squares in the obvious and naive way. it
> returns a nested tuple , which is then flattened for simplicity...then
> to cover the possibility that there might be one other minimal
> representation i call another similar function which will find one
> other representation, not necessarily shorter or of equal length,
> finally these are sorted and the results displayed, with the minimal
> result or the 2 equal-length minimal results.
>
> as the numbers get bigger (i believe) there will be some which have 3
> or more minimal representations which this code will miss.
>
> what I want to do is come up with a recursion that will find all
> possible minimal representations in one function (if possible ) in an
> optimally elegant and scalable way. There's no application in mind, i
> just love playing with math.
>
> code so far below:
>
> # express numbers as sum of squares
>
> a=[x**2 for x in range(50,0,-1)]
>
> # finds obvious candidate
>
> def squ(z):
>     if z==0:
>         return 0
>     for x in a:
>         if z>=x:
>             return x,squ(z-x)
>
> # finds another candidate with largest square as next square down from
> above function
>
> def squ2(z):
>     if z==0:
>         return 0
>     for x in a:
>         if z>=x:
>             return a[a.index(x)+1],squ(z-a[a.index(x)+1])
>
> def flatten(lst):
>     for elem in lst:
>         if type(elem) in (tuple, list):
>             for i in flatten(elem):
>                 yield i
>         else:
>             yield elem
> q=[]
> r=[]
>
> for aa in range(100):
>     r.append([])
>
> for xx in range(10,100):
>     q=[]
>     for ss in flatten(squ(xx)):
>         if ss!=0:
>             q.append(ss)
>     r[xx].append(q)
>
> for xx in range(10,100):
>     q=[]
>     for ss in flatten(squ2(xx)):
>         if ss!=0:
>             q.append(ss)
>     r[xx].append(q)
>
>
> for eee in r:
>     if eee:
>         if len(eee[0])==len(eee[1]):
>             print r.index(eee),eee[0],eee[1]
>         else:
>             print r.index(eee),eee[0]
>
>
>   
You said you'd be happy with hints.  So I'd suggest doing it with 
generators.  If a generator calls itself recursively, and if it's 'yield 
value' is a list, then the main program simply invokes the generator in 
a for loop, storing any solution that's the same length as the best so 
far, or replacing its current set with a new one if it's better.

Just getting a complete set of results, but not checking for the min 
one, my main code is:
def main(target):
    for i, res in enumerate(solutions(target, target)):
        print i, res

So I have a generator called solutions(), which takes two parameters.  
First one is the target
 value, second one is a limit value we don't want to exceed for any 
remaining square.  This throws out results that are out of sorted order, 
and for my test value of 33, reduces the number of values to examine 
from 30000+ to 33.  (That number is a coincidence)

I could give you the recursive generator as well, it's only 8 lines.  
But then I'd take away your fun.  The only other code I needed was your 
list "a" of squares.

No optimizations as yet.  So for example, I go through the whole list a, 
skipping any that are greater than either target or limit.  Clearly, I 
could use an index to save some of that.  But if I tried such at this 
point, I'd have to do timings to make sure it'd actually be a net gain.

For 33, it got 33 lists, in .0039 secs.  For 100, it got 1115 lists, in 
.66 secs.