I originally implemented this in C# but translated it to Python because I guessed (correctly) that it would be shorter and would eliminate a third-party library dependency.
I am a Python newbie though - This is the longest Python program I have ever written. So I would like to know:
- Is there a convention for indicating what version of the language you are targeting (like
require <version>in perl?) This program only works in 2.6.
- Instead of the priority queue, is there a better way to generate the odd regular numbers? I know it is possible to implement lazy lists in Python but they are not in 2.6 are they?
- Any other idioms/naming conventions I am missing?
from itertools import ifilter, takewhile from Queue import PriorityQueue def nextPowerOf2(n): p = max(1, n) while p != (p & -p): p += p & -p return p # Generate multiples of powers of 3, 5 def oddRegulars(): q = PriorityQueue() q.put(1) prev = None while not q.empty(): n = q.get() if n != prev: prev = n yield n if n % 3 == 0: q.put(n // 3 * 5) q.put(n * 3) # Generate regular numbers with the same number of bits as n def regularsCloseTo(n): p = nextPowerOf2(n) numBits = len(bin(n)) for i in takewhile(lambda x: x <= p, oddRegulars()): yield i << max(0, numBits - len(bin(i))) def nextRegular(n): bigEnough = ifilter(lambda x: x >= n, regularsCloseTo(n)) return min(bigEnough)