"""
Python version: 3.1
author: Kirby Urner, 4D Solutions
release: 1.0, July 13, 2009
quick and dirty implementation of Bernoulli numbers
as a generator, getting clues from Wikipedia article
Dedication:
"to Ada Byron, with respect and admiration"
(hence name ada.py)
"In note G of Ada Lovelace's notes on the
Analytical engine from 1842, Lovelace
describes an algorithm for generating
Bernoulli numbers with Babbage's machine [~ 1].
As a result, the Bernoulli numbers have
the distinction of being the subject of
the first computer program."
Wikipedia: http://en.wikipedia.org/wiki/Bernoulli_number
Source code (current version):
http://www.4dsolutions.net/ocn/python/ada.py
"""
from fractions import Fraction
def seidel():
"""
"...in 1877 Philipp Ludwig von Seidel published an ingenious
algorithm which makes it extremely simple to calculate Tn."
(Ibid, Wikipedia)
See OEIS:
http://www.research.att.com/~njas/sequences/A000111
"""
row = [1]
k = 1
yield 1
yield 1
while True:
newrow = []
if not k%2:
t = row[0]
row.insert(0, t)
left = 0
for i in row:
term = i + left
left = term
newrow.append(term)
row = newrow
else:
t = row[-1]
row.append(t)
left = 0
for i in reversed(row):
term = i + left
left = term
newrow.append(term)
row = list(reversed(newrow))
yield t
k += 1
def bernoulli():
yield Fraction(1,1)
yield Fraction(-1,2)
seidelgen = seidel()
next(seidelgen)
sign = 1
n = 2
while True:
sign *= -1
denom = 2**n -4**n
numer = sign * n * next(seidelgen)
next(seidelgen)
n += 2
yield Fraction(numer, denom)