Hamming numbers: Difference between revisions

Line 597:

===Alternate version using "Cyclic Iterators"===

The original author is Raymond Hettinger and the code was first published [http://code.activestate.com/recipes/576961/ here] under the MIT license.

The original author is Raymond Hettinger and the code was first published [http://code.activestate.com/recipes/576961/ here] under the MIT license. This implementation is quite memory efficient.

⚫

This ~~implementation~~ is the fastest of the Python implementations ~~and~~ is ~~quite~~ ~~memory~~ ~~efficient~~.

<lang python>from itertools import tee, chain, groupby

from heapq import merge

Line 627:

Line 625:

Results are the same as before.

===Alternate version from the Java version===

⚫

This is the fastest of the Python implementations, it uses a lot of memory.

<lang python>import psyco

def hamming(limit):

h = [1] * limit

x2, x3, x5 = 2, 3, 5

i = j = k = 0

for n in xrange(1, limit):

h[n] = min(x2, x3, x5)

if x2 == h[n]:

i += 1

x2 = 2 * h[i]

if x3 == h[n]:

j += 1

x3 = 3 * h[j]

if x5 == h[n]:

k += 1

x5 = 5 * h[k]

return h[-1]

psyco.bind(hamming)

print [hamming(i) for i in xrange(1, 21)]

print hamming(1691)

print hamming(1000000)</lang>

=={{header|R}}==

Recursively find the Hamming numbers below <math>2^{31}</math>. Works for larger limits, however to find the <math>1000000^{th}</math> value, one needs guess the correct limit