from itertools import tee, chain, groupby, islice, imap
from heapq import merge

def fibonacci():               # created: 2013-03-12  by: Will Ness   
    def deferred_output():     # for: rosettacode.org/wiki/Hamming_numbers
        for i in output:       #            #Non-sharing_recursive_generator
            yield i
    result, c1, c2 = tee(deferred_output(), 3) # LINEAR !!!!!! ergo, w/SHARING!
    paired = imap(add, c1, islice(c2, 1, None))  # 800 - 0.0 secs !!!!!
    output = chain([0, 1], paired) 
    return result

def add(x, y):
    return x + y

def fibonacci_rec():
    yield 0; yield 1;
    c1, c2 = tee(fibonacci_rec(), 2)  # QUADRATIC !!@#$%@#$!!!!!!
    c2.next()
    for i in imap(add, c1, c2):
        yield i

#for i in islice(fibonacci(), 800, 801):  # rec: 800-0.22 secs !! (400-0.06s)
#    print(i),
#print    
    
# -------------------------------
def hamming_rec():
    last = 1
    yield last

    a,b,c = tee(hamming_rec(), 3)

    for n in merge((2*i for i in a), (3*i for i in b), (5*i for i in c)):
        if n != last:
            yield n
            last = n
            

def hamming():  # by Raymond Hettinger
    # Generate "5-smooth" numbers, also called "Hamming numbers"
    # or "Regular numbers".  See: en.wikipedia.org/wiki/Regular_number
    # Finds solutions to 2**i * 3**j * 5**k  for some integers i, j, and k.
 
    def deferred_output():
        for i in output:
            yield i
 
    result, p2, p3, p5 = tee(deferred_output(), 4)
    m2 = (2*x for x in p2)                          # multiples of 2
    m3 = (3*x for x in p3)                          # multiples of 3
    m5 = (5*x for x in p5)                          # multiples of 5
    merged = merge(m2, m3, m5)
    combined = chain([1], merged)                   # prepend a starting point
    output = (k for k,g in groupby(combined))       # eliminate duplicates
 
    return result
    
            
for i in islice(hamming(), 16000, 16001):  # rec: 2000-0.06s  4000-0.15s
  print(i),                                # rec: 8000-0.39s (linearithmic?)  
                        # rec: 16k: 1.01s ... n^1.37 ... sharing: 0.06s !!!