A *[Hamming number][1]* is a positive integer of the form 2*i*3*j*5*k*, for some non-negative integers *i*, *j*, and *k*.

Write a function that computes the *n*th smallest Hamming number. 

Specifically:

  - The first smallest Hamming number is 1 = 2^(0)3^(0)5^(0)
  - The second smallest Hamming number is 2 = 2^(1)3^(0)5^(0)
  - The third smallest Hamming number is 3 = 2^(0)3^(1)5^(0)
  - The fourth smallest Hamming number is 4 = 2^(2)3^(0)5^(0)
  - The fifth smallest Hamming number is 5 = 2^(0)3^(0)5^(1)

The 20 smallest Hamming numbers are given in example test fixture.

Your code should be able to compute all of the smallest 5,000 (Clojure: 2000, NASM: 13282) Hamming numbers without timing out.

[1]:https://en.wikipedia.org/wiki/Regular_number

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:
def hamming(n):
	

Solutions:
def hamming(n):
	bases = [2, 3, 5]
	expos = [0, 0, 0]
	hamms = [1]
	for _ in range(1, n):
		next_hamms = [bases[i] * hamms[expos[i]] for i in range(3)]
		next_hamm = min(next_hamms)
		hamms.append(next_hamm)
		for i in range(3):
			expos[i] += int(next_hamms[i] == next_hamm)
	return hamms[-1]


def hamming(n):
	num = [1]
	(i, j, k) = (0, 0, 0)
	if n == 1:
		return 1
	else:
		for e in range(1, n):
			x = min(2 * num[i], 3 * num[j], 5 * num[k])
			num.append(x)
			if 2 * num[i] <= x:
				i += 1
			if 3 * num[j] <= x:
				j += 1
			if 5 * num[k] <= x:
				k += 1
	return num[len(num) - 1]


def hamming(n):
	bag = {1}
	for _ in range(n - 1):
		head = min(bag)
		bag.remove(head)
		bag |= {head * 2, head * 3, head * 5}
	return min(bag)


class _CacheEntry(object):
	__slots__ = ['is_optimal', 'linked_to', 'idx', 'seq']

	def __init__(self, is_optimal=None, linked_to=None, idx=None, seq=None):
		self.is_optimal = is_optimal
		self.linked_to = linked_to
		self.idx = idx
		self.seq = seq
_FACTORS_CACHE = {}

def factorizable(n, factors, sort_factors=True):
	if not factors:
		return False
	if sort_factors:
		factors = sorted(set(factors))
	fs = [n]
	while fs:
		sub = []
		for n in fs:
			for f in factors:
				if n == f:
					return True
				elif f <= n:
					if n % f == 0:
						sub.append(n / f)
				else:
					break
		fs = sub
	return False

def normalized_factors(factors, caching=True):
	if caching and factors in _FACTORS_CACHE:
		entry = _FACTORS_CACHE[factors]
		if entry.is_optimal:
			return factors
		else:
			return entry.linked_to
	fs = sorted(set(factors))
	i = 1
	for _ in range(1, len(fs)):
		if factorizable(fs[i], fs[0:i], False):
			del fs[i]
		else:
			i += 1
	t = tuple(fs)
	if caching and t != factors:
		_FACTORS_CACHE[factors] = _CacheEntry(is_optimal=False, linked_to=t)
	return t

def normalized_factors_f(factors):
	fs = sorted(set(factors))
	return (e[1] for e in filter(lambda t: not factorizable(t[1], fs[0:t[0]], False), enumerate(fs)))

def factored(n, factors, caching=True):
	factors = normalized_factors(factors, caching)
	cached = False
	if caching and factors in _FACTORS_CACHE:
		e = _FACTORS_CACHE[factors]
		if n <= len(e.seq):
			return e.seq[n - 1]
		cached = True
	fn = len(factors)
	next_nums = list(factors)
	if cached:
		for i in range(fn):
			next_nums[i] = e.seq[e.idx[i]] * factors[i]
	else:
		e = _CacheEntry(is_optimal=True, idx=[0] * fn, seq=[1])
	for _ in range(len(e.seq), n):
		next_n = min(next_nums)
		e.seq.append(next_n)
		for i in range(fn):
			if next_n == next_nums[i]:
				e.idx[i] += 1
				next_nums[i] = e.seq[e.idx[i]] * factors[i]
	if caching and (not cached):
		_FACTORS_CACHE[factors] = e
	return e.seq[-1]

def hamming(n):
	return factored(n, (2, 3, 5))


h = sorted((2 ** i * 3 ** j * 5 ** k for i in range(35) for j in range(25) for k in range(15)))

def hamming(n):
	return h[n - 1]


from heapq import *
(H, Q) = ([1], [(2, 2, 1), (3, 3, 1), (5, 5, 1)])

def hamming(n):
	while len(H) <= n:
		(v, root, i) = heappop(Q)
		if H[-1] != v:
			H.append(v)
		heappush(Q, (H[i] * root, root, i + 1))
	return H[n - 1]


import itertools
H = sorted([2 ** i * 3 ** j * 5 ** k for (i, j, k) in itertools.product(xrange(50), xrange(50), xrange(50))])
hamming = lambda n, H=H: H[n - 1]


def hamming(n):
	(h, i, j, k) = ([1] * n, 0, 0, 0)
	for nn in range(1, n):
		h[nn] = min(2 * h[i], 3 * h[j], 5 * h[k])
		i += 2 * h[i] == h[nn]
		j += 3 * h[j] == h[nn]
		k += 5 * h[k] == h[nn]
	return h[-1]


nums = set()
for i in range(35):
	for j in range(25):
		for k in range(15):
			nums.add(2 ** i * 3 ** j * 5 ** k)
nums = [None] + sorted(nums)

def hamming(n):
	return nums[n]