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 !!!
ZnJvbSBpdGVydG9vbHMgaW1wb3J0IHRlZSwgY2hhaW4sIGdyb3VwYnksIGlzbGljZSwgaW1hcApmcm9tIGhlYXBxIGltcG9ydCBtZXJnZQoKZGVmIGZpYm9uYWNjaSgpOiAgICAgICAgICAgICAgICMgY3JlYXRlZDogMjAxMy0wMy0xMiAgYnk6IFdpbGwgTmVzcyAgIAogICAgZGVmIGRlZmVycmVkX291dHB1dCgpOiAgICAgIyBmb3I6IHJvc2V0dGFjb2RlLm9yZy93aWtpL0hhbW1pbmdfbnVtYmVycwogICAgICAgIGZvciBpIGluIG91dHB1dDogICAgICAgIyAgICAgICAgICAgICNOb24tc2hhcmluZ19yZWN1cnNpdmVfZ2VuZXJhdG9yCiAgICAgICAgICAgIHlpZWxkIGkKICAgIHJlc3VsdCwgYzEsIGMyID0gdGVlKGRlZmVycmVkX291dHB1dCgpLCAzKSAjIExJTkVBUiAhISEhISEgZXJnbywgdy9TSEFSSU5HIQogICAgcGFpcmVkID0gaW1hcChhZGQsIGMxLCBpc2xpY2UoYzIsIDEsIE5vbmUpKSAgIyA4MDAgLSAwLjAgc2VjcyAhISEhIQogICAgb3V0cHV0ID0gY2hhaW4oWzAsIDFdLCBwYWlyZWQpIAogICAgcmV0dXJuIHJlc3VsdAoKZGVmIGFkZCh4LCB5KToKICAgIHJldHVybiB4ICsgeQoKZGVmIGZpYm9uYWNjaV9yZWMoKToKICAgIHlpZWxkIDA7IHlpZWxkIDE7CiAgICBjMSwgYzIgPSB0ZWUoZmlib25hY2NpX3JlYygpLCAyKSAgIyBRVUFEUkFUSUMgISFAIyQlQCMkISEhISEhCiAgICBjMi5uZXh0KCkKICAgIGZvciBpIGluIGltYXAoYWRkLCBjMSwgYzIpOgogICAgICAgIHlpZWxkIGkKCiNmb3IgaSBpbiBpc2xpY2UoZmlib25hY2NpKCksIDgwMCwgODAxKTogICMgcmVjOiA4MDAtMC4yMiBzZWNzICEhICg0MDAtMC4wNnMpCiMgICAgcHJpbnQoaSksCiNwcmludCAgICAKICAgIAojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KZGVmIGhhbW1pbmdfcmVjKCk6CiAgICBsYXN0ID0gMQogICAgeWllbGQgbGFzdAoKICAgIGEsYixjID0gdGVlKGhhbW1pbmdfcmVjKCksIDMpCgogICAgZm9yIG4gaW4gbWVyZ2UoKDIqaSBmb3IgaSBpbiBhKSwgKDMqaSBmb3IgaSBpbiBiKSwgKDUqaSBmb3IgaSBpbiBjKSk6CiAgICAgICAgaWYgbiAhPSBsYXN0OgogICAgICAgICAgICB5aWVsZCBuCiAgICAgICAgICAgIGxhc3QgPSBuCiAgICAgICAgICAgIAoKZGVmIGhhbW1pbmcoKTogICMgYnkgUmF5bW9uZCBIZXR0aW5nZXIKICAgICMgR2VuZXJhdGUgIjUtc21vb3RoIiBudW1iZXJzLCBhbHNvIGNhbGxlZCAiSGFtbWluZyBudW1iZXJzIgogICAgIyBvciAiUmVndWxhciBudW1iZXJzIi4gIFNlZTogZW4ud2lraXBlZGlhLm9yZy93aWtpL1JlZ3VsYXJfbnVtYmVyCiAgICAjIEZpbmRzIHNvbHV0aW9ucyB0byAyKippICogMyoqaiAqIDUqKmsgIGZvciBzb21lIGludGVnZXJzIGksIGosIGFuZCBrLgogCiAgICBkZWYgZGVmZXJyZWRfb3V0cHV0KCk6CiAgICAgICAgZm9yIGkgaW4gb3V0cHV0OgogICAgICAgICAgICB5aWVsZCBpCiAKICAgIHJlc3VsdCwgcDIsIHAzLCBwNSA9IHRlZShkZWZlcnJlZF9vdXRwdXQoKSwgNCkKICAgIG0yID0gKDIqeCBmb3IgeCBpbiBwMikgICAgICAgICAgICAgICAgICAgICAgICAgICMgbXVsdGlwbGVzIG9mIDIKICAgIG0zID0gKDMqeCBmb3IgeCBpbiBwMykgICAgICAgICAgICAgICAgICAgICAgICAgICMgbXVsdGlwbGVzIG9mIDMKICAgIG01ID0gKDUqeCBmb3IgeCBpbiBwNSkgICAgICAgICAgICAgICAgICAgICAgICAgICMgbXVsdGlwbGVzIG9mIDUKICAgIG1lcmdlZCA9IG1lcmdlKG0yLCBtMywgbTUpCiAgICBjb21iaW5lZCA9IGNoYWluKFsxXSwgbWVyZ2VkKSAgICAgICAgICAgICAgICAgICAjIHByZXBlbmQgYSBzdGFydGluZyBwb2ludAogICAgb3V0cHV0ID0gKGsgZm9yIGssZyBpbiBncm91cGJ5KGNvbWJpbmVkKSkgICAgICAgIyBlbGltaW5hdGUgZHVwbGljYXRlcwogCiAgICByZXR1cm4gcmVzdWx0CiAgICAKICAgICAgICAgICAgCmZvciBpIGluIGlzbGljZShoYW1taW5nKCksIDE2MDAwLCAxNjAwMSk6ICAjIHJlYzogMjAwMC0wLjA2cyAgNDAwMC0wLjE1cwogIHByaW50KGkpLCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyByZWM6IDgwMDAtMC4zOXMgKGxpbmVhcml0aG1pYz8pICAKICAgICAgICAgICAgICAgICAgICAgICAgIyByZWM6IDE2azogMS4wMXMgLi4uIG5eMS4zNyAuLi4gc2hhcmluZzogMC4wNnMgISEh