"""
Python 2.5+ module for OEIS sequence number A007318.

Examples of use.
----------------------------------------------------------------
>>> from a007318 import *
>>> a = a007318_list(20)
>>> print a
[1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5]
>>> print a[4]
2
>>> for x in a007318_list_pairs(6):
...     print x
...
(0, 1)
(1, 1)
(2, 1)
(3, 1)
(4, 2)
(5, 1)
>>> print a007318_list_row(6)
[1, 6, 15, 20, 15, 6, 1]
>>> print a007318_list_rows(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
>>> print a007318(125)
3003
>>> a007318_list_inv(3003)
[111, 113, 125, 130, 3083, 3157, 4510507, 4513508]
----------------------------------------------------------------
"""

import itertools
import bisect

__author__ = 'Nick Hobson <nickh@qbyte.org>'

def a007318_gen(p=None):
    """Generator function for OEIS sequence A007318."""
    it = itertools.count() if p is None else range(p, p+1)
    for row in it:
        x = 1
        yield x
        for m in xrange(row):
            x = (x * (row - m)) / (m + 1)
            yield x

def a007318_list(n):
    """Returns a list of the first n >= 0 terms."""
    return list(itertools.islice(a007318_gen(), n))

def a007318_list_pairs(n):
    """Returns a list of tuples (n, a(n)) of the first n >= 0 terms."""
    return list(itertools.izip(xrange(n), a007318_gen()))

def a007318_list_row(m):
    """Returns row m >= 0 of Pascal's triangle, as a list."""
    return list(a007318_gen(m))

def a007318_list_rows(m):
    """Returns a list of the first m >= 0 rows, each of which is a list."""
    return [a007318_list_row(i) for i in xrange(m)]

def a007318(n):
    """Returns the term with index n >= 0; offset 0."""
    row = int(((1 + 8*n)**0.5 - 1)/2)
    col = n - row*(row + 1)/2
    if col > row:
        row += 1
        col = n - row*(row + 1)/2
    if 2 * col > row:
        col = row - col
    return list(itertools.islice(a007318_gen(row), col, col+1)).pop()

def a007318_list_inv(m):
    """Returns a list of all indices n for which a(n) = m > 1."""
    if m < 5: return [[], [], [4], [7, 8], [11, 13]][m]
    r = []
    # Search up to and including the row in which m might appear in the third
    # column; i.e., in column 1, 3, 6, 10, ... , the triangular numbers.
    for row in xrange(4, int(round(((1 + 8*m)**0.5 - 1)/2)) + 2):
        s = list(itertools.islice(a007318_gen(row), row//2 + 1))
        # Use binary search on the first half of the row.
        col = bisect.bisect_right(s, m)
        if m == s[col - 1]:
            r.append(row*(row + 1)/2 + col - 1)
            if row%2 == 1 or col < len(s):
                r.append((row + 1)*(row + 2)/2 - col)
    # Finally, append the positions where m appears in row (m + 1).
    r.append(m*(m + 1)/2 + 1)
    r.append((m + 1)*(m + 2)/2 - 2)
    return r