find all multiplicands and multipliers for a number

[Paul Rubin]

Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
>     primes = sieve [2..]
>     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
> In her paper http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf, Melissa
> O'Neill calls this the "Sleight on Eratosthenes".

Oh cool, I wrote very similar Haskell code and converted it to Python.
I probably saw it before though, so it looks like a case of
not-exactly-independent re-invention.

> def turner():
>     nums = itertools.count(2)
>     while True:
>         prime = next(nums)
>         yield prime
>         nums = filter(lambda v, p=prime: (v % p) != 0, nums)

This is nice, though it will still hit the nesting limit about equally
soon, because of the nested filters.  I like the faster versions in the
O'Neill paper.

> On my computer, your recursive version is about 35% slower than the
> iterative version over the first 499 primes.

Interesting.  I wonder why it's slower.

A Hamming (or "5-smooth") number is a number with no prime factors
larger than 5.  So 20 (= 2*2*5) is a Hamming number but 21 (= 3*7) is
not.  The first few of them are:
  [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]

Here's an ugly computation of the millionth Hamming number, converted
from Haskell code that you've probably seen.  I'd be interested in
seeing a cleaner implementation.  

================================================================
import itertools, time

def merge(a0,b0):
    def advance(m): m[0] = next(m[1])
    a = [next(a0), a0]
    b = [next(b0), b0]
    while True:
        if a[0] == b[0]:
            yield a[0]
            advance(a)
            advance(b)
        elif a[0] < b[0]:
            yield a[0]
            advance(a)
        else:
            yield b[0]
            advance(b)

def hamming(n):
    hh = [1]
    def hmap(k):
        for i in itertools.count():
            yield k * hh[i]

    m = merge(hmap(2),merge(hmap(3), hmap(5)))
    for i in xrange(n):
        hh.append(next(m))
    return hh[-1]

# this takes about 2.4 seconds on my i5 laptop with python 2.7,
# about 2.8 sec with python 3.3.2

t0=time.time()
print (hamming(10**6-1))
print (time.time()-t0)
================================================================