Velocity Reviews > This is very simple question

# This is very simple question

Eric
Guest
Posts: n/a

 04-21-2004
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

Fredrik Lundh
Guest
Posts: n/a

 04-21-2004
but a lousy subject.

"Eric" <(E-Mail Removed)> 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>

Brian Quinlan
Guest
Posts: n/a

 04-21-2004

> 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

wes weston
Guest
Posts: n/a

 04-21-2004
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

Noah from IT Goes Click
Guest
Posts: n/a

 04-21-2004
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

Gyro Funch
Guest
Posts: n/a

 04-21-2004
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]

Cameron Laird
Guest
Posts: n/a

 04-21-2004
In article <(E-Mail Removed)>,
Brian Quinlan <(E-Mail Removed)> 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 <(E-Mail Removed)>

wes weston
Guest
Posts: n/a

 04-21-2004
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
Guest
Posts: n/a

 04-21-2004
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]
>>>

A. Lloyd Flanagan
Guest
Posts: n/a

 04-21-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (Eric) wrote in message news:<(E-Mail Removed). com>...
> 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.