not homework... something i find an interesting problem

[Trip Technician]

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]

 

[Dave Angel]

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.

 

[Trip Technician]

Thank you Dave. This does it but slowly. takes every subset of the
list a of squares, and then gets a 'partition' that will work, many
are very inefficient (with lots of 1s).

any hints about how to speed up ?


def subset(x):
for z in range(1,2**len(x)):
q=bin(z)
subs=[]
for dig in range(len(q)):
if q[dig]=='1':
subs.append(x[dig])
yield subs

def bin(x):
q=""
while x>=1:
q+=str(x%2)
x//=2
return q



def squ(z,b):
if z==0:
return 0
for x in b:
if z>=x:
return x,squ(z-x,b)


def flatten(lst):
for elem in lst:
if type(elem) in (tuple, list):
for i in flatten(elem):
yield i
else:
yield elem



sizelim=150

a=[x**2 for x in range(int(sizelim**0.5),1,-1)]

q,r=[],[]

for aa in range(sizelim):
r.append([])


for xx in range(1,sizelim):
for z in subset(a):
q=[]
z.append(1)
for rr in flatten(squ(xx,z)):
if rr !=0:
q.append(rr)
item=[len(q),q]
if item not in r[xx]:
r[xx].append(item)
r[xx].sort()

for eee in r:
if eee:
print r.index(eee),eee[0:3]

 

[MRAB]

Thank you Dave. This does it but slowly. takes every subset of the
list a of squares, and then gets a 'partition' that will work, many
are very inefficient (with lots of 1s).

any hints about how to speed up ?


def subset(x):
for z in range(1,2**len(x)):
q=bin(z)
subs=[]
for dig in range(len(q)):
if q[dig]=='1':
subs.append(x[dig])
yield subs

def bin(x):
q=""
while x>=1:
q+=str(x%2)
x//=2
return q



def squ(z,b):
if z==0:
return 0
for x in b:
if z>=x:
return x,squ(z-x,b)


def flatten(lst):
for elem in lst:
if type(elem) in (tuple, list):
for i in flatten(elem):
yield i
else:
yield elem



sizelim=150

a=[x**2 for x in range(int(sizelim**0.5),1,-1)]

q,r=[],[]

for aa in range(sizelim):
r.append([])


for xx in range(1,sizelim):
for z in subset(a):
q=[]
z.append(1)
for rr in flatten(squ(xx,z)):
if rr !=0:
q.append(rr)
item=[len(q),q]
if item not in r[xx]:
r[xx].append(item)
r[xx].sort()

for eee in r:
if eee:
print r.index(eee),eee[0:3]

Even this code doesn't find them all! For 135 it finds [49, 49, 36, 1],
[81, 25, 25, 4] and [81, 36, 9, 9], but not [121, 9, 4, 1].

 

[Trip Technician]

Thank you Dave. This does it but slowly. takes every subset of the
list a ofsquares, and then gets a 'partition' that will work, many
are very inefficient (with lots of 1s).

any hints about how to speed up ?

def subset(x):
    for z in range(1,2**len(x)):
        q=bin(z)
        subs=[]
        for dig in range(len(q)):
            if q[dig]=='1':
                subs.append(x[dig])
        yield subs

def bin(x):
  q=""
  while x>=1:
    q+=str(x%2)
    x//=2
  return q

def squ(z,b):
    if z==0:
        return 0
    for x in b:
        if z>=x:
            return x,squ(z-x,b)

def flatten(lst):
    for elem in lst:
        if type(elem) in (tuple, list):
            for i in flatten(elem):
                yield i
        else:
            yield elem

sizelim=150

a=[x**2 for x in range(int(sizelim**0.5),1,-1)]

q,r=[],[]

for aa in range(sizelim):
    r.append([])

for xx in range(1,sizelim):
    for z in subset(a):
        q=[]
        z.append(1)
        for rr in flatten(squ(xx,z)):
            if rr !=0:
                q.append(rr)
        item=[len(q),q]
        if item not in r[xx]:
            r[xx].append(item)
            r[xx].sort()

for eee in r:
    if eee:
            print r.index(eee),eee[0:3]

Even this code doesn't find them all! For 135 it finds [49, 49, 36, 1],
[81, 25, 25, 4] and [81, 36, 9, 9], but not [121, 9, 4, 1].- Hide quoted text -

- Show quoted text -

blowed if i know why that is !

 

[MRAB]

Thank you Dave. This does it but slowly. takes every subset of the
list a ofsquares, and then gets a 'partition' that will work, many
are very inefficient (with lots of 1s).
any hints about how to speed up ?
def subset(x):
for z in range(1,2**len(x)):
q=bin(z)
subs=[]
for dig in range(len(q)):
if q[dig]=='1':
subs.append(x[dig])
yield subs
def bin(x):
q=""
while x>=1:
q+=str(x%2)
x//=2
return q
def squ(z,b):
if z==0:
return 0
for x in b:
if z>=x:
return x,squ(z-x,b)
def flatten(lst):
for elem in lst:
if type(elem) in (tuple, list):
for i in flatten(elem):
yield i
else:
yield elem
sizelim=150
a=[x**2 for x in range(int(sizelim**0.5),1,-1)]
q,r=[],[]
for aa in range(sizelim):
r.append([])
for xx in range(1,sizelim):
for z in subset(a):
q=[]
z.append(1)
for rr in flatten(squ(xx,z)):
if rr !=0:
q.append(rr)
item=[len(q),q]
if item not in r[xx]:
r[xx].append(item)
r[xx].sort()
for eee in r:
if eee:
print r.index(eee),eee[0:3]

Even this code doesn't find them all! For 135 it finds [49, 49, 36, 1],
[81, 25, 25, 4] and [81, 36, 9, 9], but not [121, 9, 4, 1].- Hide quoted text -

- Show quoted text -

blowed if i know why that is !

I think I might have cracked it:

import math

def sumsq(n):
if n == 0:
return [[]]
root = int(math.sqrt(n))
square = root ** 2
sums = [[square] + s for s in sumsq(n - square)]
while root > 1:
root -= 1
square = root ** 2
if square < n // len(sums[0]):
break
more_sums = [[square] + s for s in sumsq(n - square)]
if len(more_sums[0]) == len(sums[0]):
sums.extend(more_sums)
return sums

for n in range(1, 150):
# Find all the possible sums.
sums = sumsq(n)
# Create a set of the unique combinations.
sums = set(tuple(sorted(s, reverse=True)) for s in sums)
# Convert back to a list of lists.
sums = [list(s) for s in sorted(sums, reverse=True)]
print n, sums

 

[bearophileHUGS]

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

Bye,
bearophile

 

[MRAB]

MRAB:

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)