"""
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)