r"""
Python module for OEIS sequence number A011971.

Aitken's array: triangle of numbers {a(n,k), n >= 0, 0 <= k <= n} read
by rows, defined by a(0,0) = 1, a(n,0) = a(n-1,n-1),
a(n,k) = a(n,k-1) + a(n-1,k-1).

Examples of use.
-----------------------------------------------------------------------
>>> from a011971 import *
>>> print a011971_list(16)
[1, 1, 2, 2, 3, 5, 5, 7, 10, 15, 15, 20, 27, 37, 52, 52]
>>> print a011971_offset
0
>>> for x in a011971_list_pairs(6):
...     print x
...
(0, 1)
(1, 1)
(2, 2)
(3, 2)
(4, 3)
(5, 5)
>>> print a011971_list_row(4)
[15, 20, 27, 37, 52]
>>> print a011971_list_rows(5)
[[1], [1, 2], [2, 3, 5], [5, 7, 10, 15], [15, 20, 27, 37, 52]]
>>> a011971_list_upto(15)
[1, 1, 2, 2, 3, 5, 5, 7, 10, 15, 15]
>>> print a011971(4)
3
-----------------------------------------------------------------------
"""

from itertools import islice, izip, takewhile, count

__all__ = ('a011971_offset', 'a011971_list', 'a011971_list_pairs',
           'a011971_list_row', 'a011971_list_rows', 'a011971_list_upto', 'a011971', 'a011971_gen')
__author__ = 'Nick Hobson <nickh@qbyte.org>'

a011971_offset = offset = 0

def a011971_gen():
    """Generator function for OEIS sequence A011971."""
    d = {0:{}, 1:{}}
    d[0][0] = x = 1
    yield x
    for row in count(1):
        d[row%2][0] = x
        yield x
        for k in xrange(1, row+1):
            d[row%2][k] = x = x + d[(row+1)%2][k-1]
            yield x

def a011971_list(n):
    """Returns a list of the first n >= 0 terms."""
    if n < 0: raise ValueError, 'Input must be a non-negative integer'
    return list(islice(a011971_gen(), n))

def a011971_list_pairs(n):
    """Returns a list of tuples (n, a(n)) of the first n >= 0 terms."""
    if n < 0: raise ValueError, 'Input must be a non-negative integer'
    return list(izip(xrange(offset, n+offset), a011971_gen()))

def a011971_list_row(m):
    """Returns row m >= 0 of Aitken's array, as a list."""
    if m < 0: raise ValueError, 'Input must be a non-negative integer'
    return list(islice(a011971_gen(), m*(m+1)/2, (m+1)*(m+2)/2))

def a011971_list_rows(m):
    """Returns a list of the first m >= 0 rows, each of which is a list."""
    if m < 0: raise ValueError, 'Input must be a non-negative integer'
    gen = a011971_gen()
    return [list(islice(gen, i+1)) for i in xrange(m)]

def a011971_list_upto(m):
    """Returns a list of all terms not exceeding m >= 0."""
    if m < 0: raise ValueError, 'Input must be a non-negative integer'
    return list(takewhile(lambda t: t <= m, a011971_gen()))

def a011971(n):
    """Returns the term with index n >= 0; offset 0."""
    if n < offset: raise ValueError, 'Input must be an integer >= offset = ' + str(offset)
    return list(islice(a011971_gen(), n-offset, n-offset+1)).pop()