# Find the smallest regular number that is not less than N (Python)

This is from an answer to my own StackOverflow question on how to efficiently find a regular number that is greater than or equal to a given value.

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)


from itertools import ifilter, takewhile
from Queue import PriorityQueue

def nextPowerOf2(n):


Python convention says that function should be named with_underscores

    p = max(1, n)
while p != (p & -p):


Parens not needed.

        p += p & -p
return p


I suspect that isn't the most efficient way to implement this function. See here for some profiling done on various implementations. http://www.willmcgugan.com/blog/tech/2007/7/1/profiling-bit-twiddling-in-python/

# Generate multiples of powers of 3, 5
def oddRegulars():
q = PriorityQueue()


So this is a synchronized class, intended to be used for threading purposes. Since you aren't using it that way, you are paying for locking you aren't using.

    q.put(1)
prev = None
while not q.empty():


Given that the queue will never be empty in this algorithm, why are you checking for it?

        n = q.get()
if n != prev:
prev = n


The prev stuff bothers me. Its ugly code that seems to distract from your algorithm. It also means that you are generating duplicates of the same number. I.e. it would be better to avoid generating the duplicates at all.

            yield n
if n % 3 == 0:
q.put(n // 3 * 5)
q.put(n * 3)


So why don't you just push n * 3 and n * 5 onto your queue?

# Generate regular numbers with the same number of bits as n
def regularsCloseTo(n):
p = nextPowerOf2(n)
numBits = len(bin(n))


These two things are basically the same thing. p = 2**(numBits+1). You should be able to calculate one from the other rather then going through the work over again.

    for i in takewhile(lambda x: x <= p, oddRegulars()):
yield i << max(0, numBits - len(bin(i)))


I'd have a comment here because its tricky to figure out what you are doing.

def nextRegular(n):
bigEnough = ifilter(lambda x: x >= n, regularsCloseTo(n))
return min(bigEnough)


I'd combine those two lines.

Is there a convention for indicating what version of the language you are targeting (like > require in perl?) This program only works in 2.6.

Honestly, much programs just fail when trying to use something not supported in the current version of python.

I know it is possible to implement lazy lists in Python but they are not in 2.6 are they?

Lazy lists? You might be referring to generators. But they are supported in 2.6, and you used one in your code.

• The point of the bit twiddling was to calculate exactly the right power of 2 to multiply by to get the regular number in the right range. This could be applied to your version, if you turn those nested loops inside-out, the inner loop could be replaced by a bit count + shift. And no I was referring to lazy lists: svn.python.org/projects/python/tags/r267/Lib/test/… – finnw Feb 13 '12 at 16:57
• @finnw, oh I figured out what you were doing with the bit twiddles. It just took me a while, hence my suggestion for a comment. Certainly you can further improve my version, I've left that as an exercise for the reader. – Winston Ewert Feb 13 '12 at 17:00
• @finnw, I don't think that any version of python includes lazy lists. You can implement lazy lists, which is what is done in what you linked. But as far as I know they've never been added to the standard library. – Winston Ewert Feb 13 '12 at 17:03
• Note that this doesn't fulfill the original requirements of "greater than or equal to". The original question wants p(18) = 18, but this returns 24 – endolith Oct 2 '13 at 23:51
• @endolith, removed apparently bad algorithm. – Winston Ewert Oct 6 '13 at 2:06