This project tries to define as many existing OEIS sequences as possible by holonomic recurrences.
- Whereas the usual linear recurrence has constant coefficients, a holonomic recurrence has coefficients that are polynomials in
n(the sequence index). Holonomic recurrences can be derived from linear differential equations, and are applicable to a wide class of series - see Wikipedia: Holonomic function.
A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n edges having root of even degree. 0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, ... G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar
Types of recurrences
There is a hierarchy of sequence types which are included in this project, with increasing complexity and computational effort:
- finite (followed by infinitely many zeroes), polynomials
- continued fractions of sqrt(n)
- recurrent with constant coefficients (cf. OEIS Index entries for linear recurrences with constant coefficients)
- defined by a rational generating function (fraction of two polynomials in x), among them sequences for Coexter groups and (lattice) coordination sequences
- holonomic recurrent (D-finite, hypergeometric functions, algebraic equations)
For all types the recurrence frequently starts only after some initial terms which do not participate in the recurrence equation.
Exponential generating function
The project also handles e.g.f.s, in which case the terms are multiplied by
n! during the generation.of the sequence.
Embedding in jOEIS
jOEIS is a project which aims to implement all OEIS sequences in Java. Currently (Feb. 2021) there are more than 104,000 sequences implemented. They are compiled in a single jar file, and any sequence can be called repeatedly in a uniform way to produce the next terms.
In jOEIS there is a series of basic Java classes which generate sequences of the holonomic type. They can all be found under https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis:
BlockMultAddSequence ContinuedFractionOfSqrtSequence CoordinationSequence CoxeterSequence FiniteSequence GeneratingFunctionSequence HolonomicRecurrence LatticeCoordinationSequence LinearRecurrence PaddingSequence PeriodicSequence PrependSequence
Currently the following numbers of sequences are covered by this project:
36 block 2911 conti 946 coord 2251 coxet 4601 finit 8520 gener 5902 holon 340 latti 20035 linea 336 paddi 1202 perio 700 prepe ------------ 47780 total
Program for holonomic recurrences
Recurrences are attractive because it is rather simple to implement them in any programming language. A CAS may have special functions for them (e.g. LinearRecurrence and RecurrenceTable in Mathematica). The algorithm is straightforward, at it needs only fixed space even in the holonomic case.
In jOEIS, HolonomicRecurrence.java uses a ring buffer of size
k for the recurrence variables
a(n), a(n-1), ... a(n-k+1), and a second array where the powers of the index
n are maintained. The length of this array corresponds with the degree of the equation (the highest power of
The program is not too big, and could be rewritten in other languages, for example Python.
The program uses these parameters:
- recurrence equation
- initial terms
- index of the first term to be returned (OEIS offset1)
Given that the recurrence equation is written in the form of an annihilator:
p*1 + p*a[n-k+1] + p*a[n-k+2] + ... + p[k-1]*a[n-k+k-1] + p[k]*a[n] = 0
then the corresponding parameter is represented by the array
[p, p, p, ... p[k]]
where each polynomial p[i] is represented by an array [c0, c1, c2 ... cm] that defines the exponents of
The initial example equation
2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0
is represented by:
The first polynomial allows for a constant term, but normally the homogenous form is used with
p = .
Usually the last recurrence variable is
a(n), but it is also possible to shift the recurrence index, for example to have
2*a(n) - 2*a(n+1) - a(n+2) = 0
Such a shifting is specified by an additional parameter
dist which is 0 by default. The example would get
In the future, all equations will be recomputed such that the constant term as well as the shift become always zero.
For an order (number of variables - 1)
k a recurrence normally needs
k initial terms to be computable. With the current implementation it is possible
- that there are more initial terms, in which case the recurrence only applies to the last
- that there are fewer initial terms, in which case a suitable number of zeroes is implied before the first term.
Black startable sequences
As a special possibility a recurrence can be started "out of nothing", that is the initial terms can be omitted altogether. The implementation then implies a leading sequence term one, and a suitable number of zeroes before. We call this property black startable (an expression used for power stations), and there is a surprising number of sequences that have it.
The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered. The table is create with the following MySQL statements:
-- Table for holonomic recurrences in the OEIS DROP TABLE IF EXISTS holref; CREATE TABLE holref ( aseqno VARCHAR(10) NOT NULL -- A-number , callcode VARCHAR(32) -- "holos", generate calls for HolonomicRecurrence , offset INT -- offset , matrix VARCHAR(8192) -- coefficients of polynomials in n , init VARCHAR(4096) -- initial terms for the recurrence , shift INT -- optional shift (0) , gftype INT -- 0 for o.g.f, 1 for e.g.f , keyword VARCHAR(128) -- list of keywords for source sequence type etc. , PRIMARY KEY(aseqno, callcode) ); COMMIT;
The tab-separated data loaded into the database table can be found under holref.txt.