# This is very simple question

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

1. ### EricGuest

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

2. ### Fredrik LundhGuest

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

3. ### Brian QuinlanGuest

> 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
4. ### wes westonGuest

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
5. ### Noah from IT Goes ClickGuest

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

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
6. ### Gyro FunchGuest

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
7. ### Cameron LairdGuest

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:

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

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

Cameron Laird <>

Cameron Laird, Apr 21, 2004
8. ### wes westonGuest

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
9. ### wes westonGuest

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
10. ### A. Lloyd FlanaganGuest

(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
11. ### Rob RenaudGuest

"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
12. ### Nicolas LehuenGuest

"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
>
>
> The real exercise is to convert this to a readable one-liner,
> at least for the binary case.
> --
>
> Cameron Laird <>

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
13. ### Cameron LairdGuest

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

Cameron Laird, Apr 22, 2004
14. ### Nicolas LehuenGuest

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

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
15. ### Peter AbelGuest

(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
>
>
> 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.
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
16. ### Daniel 'Dang' GriffithGuest

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

>
>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
17. ### Al SchapiraGuest

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]