Finds the n-th golomb number

golomb.py

import bisect
import timeit

#Finds the Nth golumb number from the
#sequence x(n) using a binary search
def findNthGolumb(n, x, upto) :
	pos = bisect.bisect(x, n, 1, upto)
	return pos - 1

#Creates the sequence x(n) where x(n) is k
#if the first appearance of n in the golumb
#sequence is at position k (1-based)
def golumb(n) :
	x = [0]*700000
	x[1], x[2] = 1, 2
	cur, start = 2, 3

	while x[start - 1] < n :
	 	times = findNthGolumb(cur, x, start)
	 	while times :
	 		x[start] = x[start - 1] + cur
	 		start += 1
	 		times -= 1
	 	cur += 1

	return findNthGolumb(n, x, start)

print timeit.Timer("print golumb(2000000000)", 'from __main__ import golumb').timeit(number=1)