Classical FP problem in python : Hamming problem

[Jeff Epler]

Your formulation in Python is recursive (hamming calls hamming()) and I
think that's why your program gives up fairly early.

Instead, use itertools.tee() [new in Python 2.4, or search the internet
for an implementation that works in 2.3] to give a copy of the output
sequence to each "multiply by N" function as well as one to be the
return value.

Here's my implementation, which matched your list early on but
effortlessly reached larger values.  One large value it printed was
6412351813189632 (a Python long) which indeed has only the distinct
prime factors 2 and 3. (2**43 * 3**6)

Jeff

from itertools import tee
import sys

def imerge(xs, ys):
    x = xs.next()
    y = ys.next()
    while True:
        if x == y:
            yield x
            x = xs.next()
            y = ys.next()
        elif x < y:
            yield x
            x = xs.next()
        else:
            yield y
            y = ys.next()

def hamming():
    def _hamming(j, k):
        yield 1
        hamming = generators[j]
        for i in hamming:
            yield i * k
    generators = []
    generator = imerge(imerge(_hamming(0, 2), _hamming(1, 3)), _hamming(2, 5))
    generators[:] = tee(generator, 4)
    return generators[3]

for i in hamming():
    print i,
    sys.stdout.flush()
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20050123/055dcaa5/attachment.sig>