439,957 Members | 2,038 Online Need help? Post your question and get tips & solutions from a community of 439,957 IT Pros & Developers. It's quick & easy.

# This is very simple question

 P: n/a 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 Jul 18 '05 #1
16 Replies

 P: n/a 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 Jul 18 '05 #2

 P: n/a 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 Jul 18 '05 #3

 P: n/a 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] Jul 18 '05 #4

 P: n/a 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 Jul 18 '05 #5

 P: n/a 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] Jul 18 '05 #6

 P: n/a 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 :-) Jul 18 '05 #7

 P: n/a 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] Jul 18 '05 #8

 P: n/a 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] Jul 18 '05 #9

 P: n/a ek****@yahoo.com (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. Jul 18 '05 #10

 P: n/a "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] The code is buggy, it won't work for odd numbers... func(5)  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 Jul 18 '05 #11

 P: n/a In article <40***********************@news.easynet.fr>, Nicolas Lehuen wrote: Jul 18 '05 #13

 P: n/a > > 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 Jul 18 '05 #14 