This is very simple question

Discussion in 'Python' started by Eric, Apr 21, 2004.

  1. Eric

    Eric Guest

    I would want to obtain a list of factors (multiples of 2) given a
    prime number in python.

    For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]

    I would appreciate a fuction which would do this.

    Eric
     
    Eric, Apr 21, 2004
    #1
    1. Advertising

  2. but a lousy subject.

    "Eric" <> wrote;

    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]


    >>> 8*4*1

    32

    > I would appreciate a fuction which would do this.


    def func(x): return [2**i for i in range(3,0,-1) if x & 2**i]

    </F>
     
    Fredrik Lundh, Apr 21, 2004
    #2
    1. Advertising


  3. > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.


    If we told you it wouldn't be fair to the other students in your class :)

    Cheers,
    Brian
     
    Brian Quinlan, Apr 21, 2004
    #3
  4. Eric

    wes weston Guest

    Eric wrote:
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric


    Eric,
    Is the last test 17 vs 15?
    With not much checking:
    >>>

    13 [8, 4, 1]
    5 [4, 1]
    7 [4, 2, 1]
    17 [16, 1]
    >>>


    #------------------------------------------------------------------


    import math

    #For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    #For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 17=[16,1]

    def LargestPrimeLessThanOrEqualTo(n):
    i = 0
    while 1:
    x = int(math.pow(2,i))
    if x == n:
    return x
    if x > n:
    return prevx
    prevx = x
    i += 1

    def foo(x):
    list = []
    temp = x
    while(temp > 0):
    z = LargestPrimeLessThanOrEqualTo(temp)
    temp -= z
    list.append(z)
    return list

    for x in [13,5,7,17]:
    print x,foo(x)

    wes
     
    wes weston, Apr 21, 2004
    #4
  5. I'm not sure those are factors? But then again I never was good at math

    for say 13 you could just count up by two and then find the largest
    number you can make of the twos and then move down until you find the
    next one and then add 1 say you start with 13=[2,2,2,2,2,2,1] ?

    then you know you have [12,1] 12 is a multiple of 2 or do you want
    powers? if you want powers you could make the nessisary logic adjustments

    Why exactly do you want this anyways?



    Eric wrote:
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric
     
    Noah from IT Goes Click, Apr 21, 2004
    #5
  6. Eric

    Gyro Funch Guest

    Eric wrote:
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric



    Below is an ugly and inefficient implementation.

    -g


    def i2b(i):
    s = ''
    while i:
    s = (i & 1 and '1' or '0') + s

    i >>= 1

    return s or '0'


    def find_factors(val):

    bstr = i2b(val)
    facs = [int(j)*2**i for (i,j) in enumerate(bstr[::-1]) if
    int(j) != 0]
    facs.reverse()
    return facs

    if __name__ == '__main__':
    print find_factors(13) == [8,4,1]

    print find_factors(5) == [4,1]

    print find_factors(7) == [4,2,1]

    print find_factors(15) == [8,4,2,1]
     
    Gyro Funch, Apr 21, 2004
    #6
  7. In article <>,
    Brian Quinlan <> wrote:
    >
    >> I would want to obtain a list of factors (multiples of 2) given a
    >> prime number in python.
    >>
    >> For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >>
    >> I would appreciate a fuction which would do this.

    >
    >If we told you it wouldn't be fair to the other students in your class :)

    .
    .
    .
    I'm surprised only one of the responses I've seen so far has
    objected to what sure seems like an inappropriate response to
    classwork. I'm astonished that no one is reading this question
    as I do. I leave as an exercise for readers this generalization
    of what *I* think is going on:

    def positional_addends(positive_integer, base = 2):
    result = []
    current = 1
    while positive_integer:
    remainder = positive_integer % (base * current)
    if remainder:
    result.append(remainder)
    positive_integer -= remainder
    current *= base
    result.reverse()
    return result

    print positional_addends(13)
    print positional_addends(5)
    print positional_addends(7)
    print positional_addends(15)
    print positional_addends(78904, 10)

    The real exercise is to convert this to a readable one-liner,
    at least for the binary case.
    --

    Cameron Laird <>
    Business: http://www.Phaseit.net
     
    Cameron Laird, Apr 21, 2004
    #7
  8. Eric

    wes weston Guest

    Eric wrote:
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric


    Eric,
    To be less illustrative and somewhat more efficient.
    wes

    import math

    def ListOfPowersLessThan(n):
    list = []
    i = 0
    while True:
    x = int(math.pow(2,i))
    if x <= n:
    list.append(x)
    else:
    break
    i += 1
    return list

    TEST = [13,5,7,15,17,33]
    powers = ListOfPowersLessThan( max(TEST) )
    powers.reverse()

    for x in TEST:
    sum = 0
    list = []
    for s in powers:
    if (sum + s) <= x:
    sum += s
    list.append(s)
    if sum >= x:
    break
    print x,list

    >>>

    13 [8, 4, 1]
    5 [4, 1]
    7 [4, 2, 1]
    15 [8, 4, 2, 1]
    17 [16, 1]
    33 [32, 1]
    >>>
     
    wes weston, Apr 21, 2004
    #8
  9. Eric

    wes weston Guest

    Eric wrote:
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric


    import math

    def foo(n):
    list = []
    while n > 0:
    x = int(math.log(n,2))
    pow = int(math.pow(2,x))
    list.append(pow)
    n -= pow
    return list

    for x in [13,5,7,15,17,33]:
    print x, foo(x)


    >>>

    13 [8, 4, 1]
    5 [4, 1]
    7 [4, 2, 1]
    15 [8, 4, 2, 1]
    17 [16, 1]
    33 [32, 1]
    >>>
     
    wes weston, Apr 21, 2004
    #9
  10. (Eric) wrote in message news:<>...
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric


    Minor quibble: you don't mean factors. The only factors of a prime
    number are the number itself and one; that's the definition of a prime
    number.

    Now, do you want a list of all powers of 2 less than a prime number,
    OR do you want a list of powers of 2 such that the sum of the numbers
    is the given prime number? For Mersienne primes, which are of the
    form (2**n-1) the answer is the same either way. All your examples
    are Mersienne primes.
    But look at 11:
    11 = 8 + 2 + 1, not 8 + 4 + 2 + 1

    Of course, any odd number can be expressed as 2 + 2 + ... + 1, so what
    you would really want is the shortest list of powers of 2 that add up
    to the prime.
     
    A. Lloyd Flanagan, Apr 21, 2004
    #10
  11. Eric

    Rob Renaud Guest

    "Fredrik Lundh" <> wrote in message news:<>...
    > but a lousy subject.
    >
    > "Eric" <> wrote;
    >
    > > I would want to obtain a list of factors (multiples of 2) given a
    > > prime number in python.
    > >
    > > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]

    >
    > >>> 8*4*1

    > 32
    >
    > > I would appreciate a fuction which would do this.

    >
    > def func(x): return [2**i for i in range(3,0,-1) if x & 2**i]
    >
    > </F>


    The code is buggy, it won't work for odd numbers...

    >>> func(5)

    [4]

    >>> def func(x): return [2**i for i in range(3,-1,-1) if x & 2**i]

    ....
    >>> func(5)

    [4, 1]

    But this still leaves us with numbers which are too big.

    >>> func(243)

    [2, 1]

    So this should take care of it...

    >>> def func(x): return [2**i for i in

    range(int(math.log(x)/math.log(2)),-1,-1) if x & 2**i]

    >>> func(323421234)

    [268435456, 33554432, 16777216, 4194304, 262144, 131072, 65536, 1024,
    32, 16, 2]
    >>> sum(func(323421234))

    323421234
     
    Rob Renaud, Apr 22, 2004
    #11
  12. "Cameron Laird" <> a écrit dans le message de news:...
    > In article <>,
    > Brian Quinlan <> wrote:
    > >
    > >> I would want to obtain a list of factors (multiples of 2) given a
    > >> prime number in python.
    > >>
    > >> For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    > >>
    > >> I would appreciate a fuction which would do this.

    > >
    > >If we told you it wouldn't be fair to the other students in your class :)

    > .
    > .
    > .
    > I'm surprised only one of the responses I've seen so far has
    > objected to what sure seems like an inappropriate response to
    > classwork. I'm astonished that no one is reading this question
    > as I do. I leave as an exercise for readers this generalization
    > of what *I* think is going on:
    >
    > def positional_addends(positive_integer, base = 2):
    > result = []
    > current = 1
    > while positive_integer:
    > remainder = positive_integer % (base * current)
    > if remainder:
    > result.append(remainder)
    > positive_integer -= remainder
    > current *= base
    > result.reverse()
    > return result
    >
    > print positional_addends(13)
    > print positional_addends(5)
    > print positional_addends(7)
    > print positional_addends(15)
    > print positional_addends(78904, 10)
    >
    > The real exercise is to convert this to a readable one-liner,
    > at least for the binary case.
    > --
    >
    > Cameron Laird <>
    > Business: http://www.Phaseit.net


    You can also use divmod :

    def decompose(i,base=2):
    result=[]
    factor=1
    while i>0:
    i,r=divmod(i,base)
    if r:
    result.append(r*factor) # or result.extend([factor]*r), depending on style
    factor*=base
    return result.reverse() # if you really want it reversed

    Regards,
    Nicolas
     
    Nicolas Lehuen, Apr 22, 2004
    #12
  13. In article <4087a0f6$0$25552$>,
    Nicolas Lehuen <> wrote:
    .
    .
    .
    >You can also use divmod :
    >
    >def decompose(i,base=2):
    > result=[]
    > factor=1
    > while i>0:
    > i,r=divmod(i,base)
    > if r:
    > result.append(r*factor) # or result.extend([factor]*r),
    >depending on style
    > factor*=base
    > return result.reverse() # if you really want it reversed

    .
    .
    .
    I agree that divmod() improves the algorithm, and thank
    you for pointing that out.

    I'm reasonably certain that the return value of reverse()
    is not what you believe it to be.
    --

    Cameron Laird <>
    Business: http://www.Phaseit.net
     
    Cameron Laird, Apr 22, 2004
    #13
  14. > > return result.reverse() # if you really want it reversed
    >
    > I agree that divmod() improves the algorithm, and thank
    > you for pointing that out.
    >
    > I'm reasonably certain that the return value of reverse()
    > is not what you believe it to be.
    > --
    >
    > Cameron Laird <>
    > Business: http://www.Phaseit.net


    Ooops indeed, reverse() always returns None, because the reverse is made in place. I did test the program without the reverse, so I missed this mistake. Thanks !

    BTW, I've been bitten by this behaviour a lot since I've switched to Python a year ago (coming from C++ and Java)... I would feel much better if reverse(), sort() and so on returned the list itself ; but then maybe other people would think the reversing/sorting etc. would not be done in place...

    Regards,
    Nicolas
     
    Nicolas Lehuen, Apr 22, 2004
    #14
  15. Eric

    Peter Abel Guest

    (Cameron Laird) wrote in message news:<>...
    > In article <>,
    > Brian Quinlan <> wrote:
    > >
    > >> I would want to obtain a list of factors (multiples of 2) given a
    > >> prime number in python.
    > >>
    > >> For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    > >>
    > >> I would appreciate a fuction which would do this.

    > >
    > >If we told you it wouldn't be fair to the other students in your class :)

    > .
    > .
    > .
    > I'm surprised only one of the responses I've seen so far has
    > objected to what sure seems like an inappropriate response to
    > classwork. I'm astonished that no one is reading this question
    > as I do. I leave as an exercise for readers this generalization
    > of what *I* think is going on:
    >
    > def positional_addends(positive_integer, base = 2):
    > result = []
    > current = 1
    > while positive_integer:
    > remainder = positive_integer % (base * current)
    > if remainder:
    > result.append(remainder)
    > positive_integer -= remainder
    > current *= base
    > result.reverse()
    > return result
    >
    > print positional_addends(13)
    > print positional_addends(5)
    > print positional_addends(7)
    > print positional_addends(15)
    > print positional_addends(78904, 10)
    >
    > The real exercise is to convert this to a readable one-liner,
    > at least for the binary case.


    I'm not quite sure, if I understood, what you mean.
    One-liners ... OK.
    Readable ??? Mmmhm ??
    i2b=lambda num,s=[],i=1:num and i2b(num>>1,(num &1) and [(num &1)*i]+s
    or s,i<<1) or s

    >>> i2b(13)

    [8, 4, 1]
    >>> i2b(15)

    [8, 4, 2, 1]

    Let's test it in general:
    >>> sum=lambda l:reduce(lambda x,y:x+y,l,0)
    >>> sum([8, 4, 2, 1])

    15
    >>> for i in range(1,100000):

    .... if sum(i2b(i))!=i:
    .... print 'i=%d: sum(i2b(i))=%d' % (i,sum(i2b(i)))
    .... break
    .... else:
    .... print 'OK'
    ....
    OK
    >>>


    Regards
    Peter
     
    Peter Abel, Apr 22, 2004
    #15
  16. On Thu, 22 Apr 2004 16:53:55 +0200, "Nicolas Lehuen"
    <> wrote:

    >> > return result.reverse() # if you really want it reversed

    >>
    >> I agree that divmod() improves the algorithm, and thank
    >> you for pointing that out.
    >>
    >> I'm reasonably certain that the return value of reverse()
    >> is not what you believe it to be.
    >> --
    >>
    >> Cameron Laird <>
    >> Business: http://www.Phaseit.net

    >
    >Ooops indeed, reverse() always returns None, because the reverse is made in place. I did test the program without the reverse, so I missed this mistake. Thanks !
    >
    >BTW, I've been bitten by this behaviour a lot since I've switched to Python a year ago (coming from C++ and Java)... I would feel much better if reverse(), sort() and so on returned the list itself ; but then maybe other people would think the reversing/sorting etc. would not be done in place...
    >
    >Regards,
    >Nicolas

    You probably already do this, but in case someone else wants an easy
    workaround:

    def reversed(lst):
    lst2 = lst[:]
    lst2.reverse()
    return lst2

    def sorted(lst):
    lst2 = lst[:]
    lst2.sort()
    return lst2

    Then you can do things like:
    mylst = reversed(mylst)

    Which is not as pretty as
    mylst = mylist.reversed()

    But it is less punctuation! ;-)

    There's been talk about adding this type of method to the builtin list
    object.
    --dang
     
    Daniel 'Dang' Griffith, Apr 22, 2004
    #16
  17. Eric

    Al Schapira Guest

    Eric wrote:
    > I would want to obtain a list of factors (multiples of 2) given a
    > prime number in python.
    >
    > For example 13=[8,4,1], 5=[4,1], 7=[4,2,1], 15=[8,4,2,1]
    >
    > I would appreciate a fuction which would do this.
    >
    > Eric


    What you seem to want are the powers of 2 that add up to the given
    number. These are the powers of two that correspond to 1's in the binary
    representation of the given number (integer).

    $ cat foo.py
    powerlist = [1 << (30-i) for i in range(31)] # [... 32, 16, 8, 4, 2, 1]

    for x in [13,5,7,15,17,33]:
    print x, [x & i for i in powerlist if x & i]

    $ python < foo.py
    13 [8, 4, 1]
    5 [4, 1]
    7 [4, 2, 1]
    15 [8, 4, 2, 1]
    17 [16, 1]
    33 [32, 1]

    Is this horse dead yet?

    -Al Schapira,
     
    Al Schapira, Jun 7, 2004
    #17
    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. Raymond Arthur St. Marie II of III

    very Very VERY dumb Question About The new Set( ) 's

    Raymond Arthur St. Marie II of III, Jul 23, 2003, in forum: Python
    Replies:
    4
    Views:
    486
    Raymond Hettinger
    Jul 27, 2003
  2. shanx__=|;-

    very very very long integer

    shanx__=|;-, Oct 16, 2004, in forum: C Programming
    Replies:
    19
    Views:
    1,641
    Merrill & Michele
    Oct 19, 2004
  3. Abhishek Jha

    very very very long integer

    Abhishek Jha, Oct 16, 2004, in forum: C Programming
    Replies:
    4
    Views:
    431
    jacob navia
    Oct 17, 2004
  4. Peter

    Very very very basic question

    Peter, Feb 8, 2005, in forum: C Programming
    Replies:
    14
    Views:
    521
    Dave Thompson
    Feb 14, 2005
  5. olivier.melcher

    Help running a very very very simple code

    olivier.melcher, May 12, 2008, in forum: Java
    Replies:
    8
    Views:
    2,310
Loading...

Share This Page