User:R. J. Mathar/oeisPy/oeisPy/oeis trans.py

""" Native python3.1 implementations of OEIS http://oeis.org/classic transforms.
A collection of functionalities related to number theory but not
associated with a particular individual sequence of the OEIS.

==usage==
python3
>>> from oeisPy import *

==author==
Richard J. Mathar, http://www.mpia.de/~mathar/progs/oeisPy-0.0.1.tar.gz
"""

def baseCoeff(n, b=10):
        """ The coeffients of n in base b.

        ==input==
        n -- positive integer

        ==output==
        list -- the list of coefficients [c(0),c(1),..] of n=sum_i c(i)*b^i

        ==examples==
        >>>oeis_core.baseCoeff(67)
        [7,6]
        >>>oeis_core.baseCoeff(0)
        []
        >>>oeis_core.baseCoeff(4,2)
        [0,0,1]

        ==author==
        Richard J. Mathar 2010-07-03
        """
        if n < 0:
                raise ValueError('negative argument '+str(n))
        a = []
        nshft = n
        while nshft >0:
                a.append(nshft % b)
                nshft //= b
        return a

def linRec(Lini, Lcoef, n, offs=0):
        """ The n-th term of the linear homogeneous reccurence with constant coefficients

        ==input==
        Lini -- The list with initial terms a(offs), a(offs+1),...
        Lcoef -- the coefficients in the recurrnce a(n) = sum_k Lcoef[k]*a(n-k-1)
        n -- the index of the term to be returned, n>=offs.
        offs -- the index of the first term in Lini.

        ==output==
        integer -- the n-th term of the sequence.

        ==examples==
        >>>oeis_core.linRec([1,1],[3,-1],10)
        4181
        >>>oeis_core.linRec([1,1],[3,-1],10,3)
        233

        ==author==
        Richard J. Mathar 2010-07-03
        """
        if n < offs:
                raise ValueError('argument '+str(n) +' less than offset '+str(offs))
        a = linRec_list(Lini, Lcoef, n-offs+1)
        return a[-1]
def linRec_list(Lini, Lcoef, n):
        """ The terms of the linear homogeneous reccurence with constant coefficients

        ==input==
        Lini -- The list with initial terms
        Lcoef -- the coefficients in the recurrnce a(n) = sum_k Lcoef[k]*a(n-k-1)
        n -- the length of the list of terms returned.

        ==output==
        list -- The truncated finite list starting with Lini in the first elements.

        ==examples==
        >>>oeis_core.linRec_list([1,1],[3,-1],10)
        [1, 1, 2, 5, 13, 34, 89, 233, 610, 1597]

        ==author==
        Richard J. Mathar 2010-07-03
        """
        a = Lini[:]
        while len(a) < n:
                anxt =0
                for k in range(len(Lcoef)):
                        anxt += Lcoef[k]*a[-1-k]
                a.append(anxt)
        return a[:n]