not homework... something i find an interesting problem

Discussion in 'Python' started by Trip Technician, Apr 18, 2009.

  1. 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]
     
    Trip Technician, Apr 18, 2009
    #1
    1. Advertising

  2. Trip Technician

    Dave Angel Guest

    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.
     
    Dave Angel, Apr 19, 2009
    #2
    1. Advertising

  3. 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]
     
    Trip Technician, Apr 21, 2009
    #3
  4. Trip Technician

    MRAB Guest

    Trip Technician wrote:
    > 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].
     
    MRAB, Apr 21, 2009
    #4
  5. On 21 Apr, 14:46, MRAB <> wrote:
    > Trip Technician wrote:
    > > 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 !
     
    Trip Technician, Apr 21, 2009
    #5
  6. Trip Technician

    MRAB Guest

    Trip Technician wrote:
    > On 21 Apr, 14:46, MRAB <> wrote:
    >> Trip Technician wrote:
    >>> 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
     
    MRAB, Apr 21, 2009
    #6
  7. Trip Technician

    Guest

    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
     
    , Apr 21, 2009
    #7
  8. Trip Technician

    MRAB Guest

    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)
     
    MRAB, Apr 21, 2009
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Charles
    Replies:
    5
    Views:
    528
    Charles
    Jul 28, 2003
  2. Mensanator
    Replies:
    7
    Views:
    342
    Terry Reedy
    Sep 22, 2008
  3. David Segall
    Replies:
    9
    Views:
    924
    Neredbojias
    Feb 22, 2010
  4. preet
    Replies:
    1
    Views:
    129
  5. Replies:
    4
    Views:
    225
    Tad McClellan
    Jun 1, 2007
Loading...

Share This Page