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]
--
http://mail.python.org/mailman/listinfo/python-list
