"""
Python version: 3.1
author: Kirby Urner, 4D Solutions
release: 1.01, July 15, 2009

quick and dirty implementation of Bernoulli numbers
as a generator, getting clues from Wikipedia article

code of seidel generator slightly streamlined by Gregor Lingl


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
    """
    yield 1
    yield 1
    row = [1]
    while True:
        t = 0
        newrow = []
        for i in row:
            t += i
            newrow.append(t)
        newrow.append(t)
        yield t
        row = reversed(newrow)

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)