OEIS/Holonomic Project - Revision history

imported>Gfis: /* Database table */ columns names were offset, shift

2022-07-14T07:51:03Z

Database table: columns names were offset, shift

imported>Gfis: Parameters of hypergeometric series

2021-05-08T18:58:12Z

Parameters of hypergeometric series

← Older revision		Revision as of 18:58, 8 May 2021
Line 102:		Line 102:
	COMMIT;		COMMIT;
	The tab-separated data loaded into the database table can be found under '''[http://www.teherba.org/OEIS-mat/holref.txt holref.txt]'''.		The tab-separated data loaded into the database table can be found under '''[http://www.teherba.org/OEIS-mat/holref.txt holref.txt]'''.
			=== Parameters of hypergeometric series ===
			There is a number of OEIS sequences that can be generated by a recurrence
			f(n) * a(n) = g(n) * a(n-1)
			For example, formulae like
			[https://oeis.org/A217364 A217364] a(n) = 2^nbinomial(5n, n)/(4*n+1).
			[https://oeis.org/A274136 A274136] a(n) = (n+1)(2n+2)!/(n+2)
			[https://oeis.org/A275655 A275655] a(n) = binomial(6n,3n)binomial(2n,n).
			are of this type.
			In these cases, the parameters for <code>HolonomicRecurrence</code> can be computed by the following Maple procedure:
			with(StringTools):
			holo := proc(as,f); local b, num, den, fd, str, filename;
			b := simplify(simplify(-f(n)/f(n-1), GAMMA));
			printf("***** b = %a\n", b);
			num := seq(coeff(numer(b),n,j),j=0..degree(numer(b)));
			den := seq(coeff(denom(b),n,j),j=0..degree(denom(b)));
			str := cat("[[0],", DeleteSpace(convert([num],string)), ",", DeleteSpace(convert([den],string)), "]");
			printf("%a\tholos\t0\t\%s\t[%a]\t0\t\n", as, str, f(0));
			end;
			We obtain, for example:
			holo(A217364, proc(n) 2^nbinomial(5n, n)/(4*n+1) end);
			***** b = (-3125n^4+6250n^3-4375n^2+1250n-120)/(128n^4-64n^3-8n^2+4n)
			A217364 holos 0 [[0],[-120,1250,-4375,6250,-3125],[0,4,-8,-64,128]] [1] 0
			Now we follow the Maple file above by an empty line and a ''pattern specification'' line:
			holo($(PARM0),proc(n) $(PARM3) end proc);
			Then it forms a pattern file for the Perl program [http://github.com/gfis/OEIS-mat/common/callmaple.pl callmaple.pl] which merges the pattern file with a list of recurrence expressions in "seq4" format, and the output is in the same format with all recurrence expressions replaced by the parameters suitable for <code>HolonomicRecurrence</code>.

imported>Gfis: Typos

2021-02-26T10:38:20Z

Typos

← Older revision		Revision as of 10:38, 26 February 2021
Line 38:		Line 38:
	PeriodicSequence		PeriodicSequence
	PrependSequence		PrependSequence
	Currently the following numbers of sequences are covered by ~~the holonomic~~ project:		Currently the following numbers of sequences are covered by this project:
	36 block		36 block
	2911 conti		2911 conti
Line 55:		Line 55:
	===Program for holonomic recurrences===		===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.		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, [https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis/HolonomicRecurrence.java HolonomicRecurrence.java] uses a ring buffer of size <code>k</code> for the recurrence variables <code>a(n), a(n-1), ... a(n-k+1)</code>, and a second array where the powers of the index <code>n</code> are maintained. The length of this array corresponds with the degree if the equation (the highest power of <code>n</code>.		In jOEIS, [https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis/HolonomicRecurrence.java HolonomicRecurrence.java] uses a ring buffer of size <code>k</code> for the recurrence variables <code>a(n), a(n-1), ... a(n-k+1)</code>, and a second array where the powers of the index <code>n</code> are maintained. The length of this array corresponds with the degree of the equation (the highest power of <code>n</code>).
	The program is not too big, and could be rewritten in other languages, for example Python.		The program is not too big, and could be rewritten in other languages, for example Python.
	===Parameterization===		===Parameterization===

imported>Gfis: DDL of table holref

2021-02-14T19:26:18Z

DDL of table holref

← Older revision		Revision as of 19:26, 14 February 2021
Line 86:		Line 86:
	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.		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.
	===Database table===		===Database table===
	The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.		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:
	The table ~~has~~ the following ~~columns that correspond with~~ the ~~parameters of the program HolonomicRecurrence.java:~~		-- Table for holonomic recurrences in the OEIS
	* A-number ~~of the sequence~~		DROP TABLE IF EXISTS holref;
	* source type		CREATE TABLE holref
	* offset		( aseqno VARCHAR(10) NOT NULL -- A-number
	* array of coefficient polynomials for ''constant, a(n-~~k), a(n~~-~~k+1) ... a(~~n~~-1)~~, a(n)''		, callcode VARCHAR(32) -- "holos", generate calls for HolonomicRecurrence
	* initial terms		, offset INT -- offset
	* optional shift ~~for ''n''~~		, matrix VARCHAR(8192) -- coefficients of polynomials in n
	* derived attributes (constant, ~~periodic~~, ~~linear recurrence~~, ~~hypergeometric, D~~-~~finite~~ etc.)		, init VARCHAR(4096) -- initial terms for the recurrence
	The tab-separated data loaded in the database table can be found under [http://www.teherba.org/OEIS-mat/holref.txt ~~teherba.org/OEIS-mat/~~holref.txt].		, 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 '''[http://www.teherba.org/OEIS-mat/holref.txt holref.txt]'''.

imported>Gfis: database table contents file holref.txt

2021-02-13T09:49:41Z

database table contents file holref.txt

← Older revision		Revision as of 09:49, 13 February 2021
Line 71:		Line 71:
	2na(n) +(12-7n)a(n-1) +2(3-2n)*a(n-2)=0		2na(n) +(12-7n)a(n-1) +2(3-2n)*a(n-2)=0
	is represented by:		is represented by:
	[[0],[6,-4],[12,-7],[2]]		[[0],[6,-4],[12,-7],[0,2]]
	=====Constant term=====		=====Constant term=====
	The first polynomial allows for a constant term, but normally the homogenous form is used with <code>p[0] = [0]</code>.		The first polynomial allows for a constant term, but normally the homogenous form is used with <code>p[0] = [0]</code>.
Line 87:		Line 87:
	===Database table===		===Database table===
	The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.		The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.
	The table has the following ~~column~~ that correspond with the parameters of the program HolonomicRecurrence:		The table has the following columns that correspond with the parameters of the program HolonomicRecurrence.java:
	* A-number of the sequence		* A-number of the sequence
			* source type
	* offset		* offset
	* array of coefficient polynomials for ''constant, a(n-k), a(n-k+1) ... a(n-1), a(n)''		* array of coefficient polynomials for ''constant, a(n-k), a(n-k+1) ... a(n-1), a(n)''
	* initial terms		* initial terms
	* optional shift for ''n''		* optional shift for ''n''
	* derived attributes (constant, periodic, linear recurrence, hypergeometric, d-finite etc.)		* derived attributes (constant, periodic, linear recurrence, hypergeometric, D-finite etc.)
			The tab-separated data loaded in the database table can be found under [http://www.teherba.org/OEIS-mat/holref.txt teherba.org/OEIS-mat/holref.txt].

imported>Gfis: completed

2021-02-10T21:24:29Z

completed

← Older revision		Revision as of 21:24, 10 February 2021
Line 56:		Line 56:
	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.		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, [https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis/HolonomicRecurrence.java HolonomicRecurrence.java] uses a ring buffer of size <code>k</code> for the recurrence variables <code>a(n), a(n-1), ... a(n-k+1)</code>, and a second array where the powers of the index <code>n</code> are maintained. The length of this array corresponds with the degree if the equation (the highest power of <code>n</code>.		In jOEIS, [https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis/HolonomicRecurrence.java HolonomicRecurrence.java] uses a ring buffer of size <code>k</code> for the recurrence variables <code>a(n), a(n-1), ... a(n-k+1)</code>, and a second array where the powers of the index <code>n</code> are maintained. The length of this array corresponds with the degree if the equation (the highest power of <code>n</code>.
			The program is not too big, and could be rewritten in other languages, for example Python.
	===Parameterization===		===Parameterization===
	The program uses these parameters:		The program uses these parameters:
Line 82:		Line 83:
	* that there are more initial terms, in which case the recurrence only applies to the last <code>k</code> terms,		* that there are more initial terms, in which case the recurrence only applies to the last <code>k</code> terms,
	* that there are fewer initial terms, in which case a suitable number of zeroes is implied before the first term.		* that there are fewer initial terms, in which case a suitable number of zeroes is implied before the first term.
	======Black startable sequences=====		=====''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.		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.
	===Database table===		===Database table===
	The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.		The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.
	* a ~~single program that computes~~ a ~~holonomic recurrence~~,		The table has the following column that correspond with the parameters of the program HolonomicRecurrence:
	*		* A-number of the sequence
			* offset
			* array of coefficient polynomials for ''constant, a(n-k), a(n-k+1) ... a(n-1), a(n)''
			* initial terms
			* optional shift for ''n''
			* derived attributes (constant, periodic, linear recurrence, hypergeometric, d-finite etc.)

imported>Gfis: Black st.

2021-02-04T21:03:38Z

Black st.

← Older revision		Revision as of 21:03, 4 February 2021
Line 38:		Line 38:
	PeriodicSequence		PeriodicSequence
	PrependSequence		PrependSequence

	Currently the following numbers of sequences are covered by the holonomic project:		Currently the following numbers of sequences are covered by the holonomic project:
	36 block		36 block
Line 56:		Line 55:
	===Program for holonomic recurrences===		===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.		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, [https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis/HolonomicRecurrence.java HolonomicRecurrence.java] uses a ring buffer of size <code>k</code> for the recurrence variables <code>a(n), a(n-1), ... a(n-k+1)</code>, and a second array where the powers of the index <code>n</code> are maintained. The length of this array corresponds with the degree if the equation (the highest power of <code>n</code>.		In jOEIS, [https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis/HolonomicRecurrence.java HolonomicRecurrence.java] uses a ring buffer of size <code>k</code> for the recurrence variables <code>a(n), a(n-1), ... a(n-k+1)</code>, and a second array where the powers of the index <code>n</code> are maintained. The length of this array corresponds with the degree if the equation (the highest power of <code>n</code>.
	===Parameterization===		===Parameterization===
Line 69:		Line 67:
	[p[0], p[1], p[2], ... p[k]]		[p[0], p[1], p[2], ... p[k]]
	where each polynomial p[i] is represented by an array [c0, c1, c2 ... cm] that defines the exponents of <code>n</code>.		where each polynomial p[i] is represented by an array [c0, c1, c2 ... cm] that defines the exponents of <code>n</code>.
	====Constant term====		The initial example equation
			2na(n) +(12-7n)a(n-1) +2(3-2n)*a(n-2)=0
			is represented by:
			[[0],[6,-4],[12,-7],[2]]
			=====Constant term=====
	The first polynomial allows for a constant term, but normally the homogenous form is used with <code>p[0] = [0]</code>.		The first polynomial allows for a constant term, but normally the homogenous form is used with <code>p[0] = [0]</code>.
	====Index shifting====		=====Index shifting=====
	Usually the last recurrence variable is <code>a(n)</code>, but it is also possible to ''shift'' the recurrence index, for example to have		Usually the last recurrence variable is <code>a(n)</code>, but it is also possible to ''shift'' the recurrence index, for example to have
	2a(n) - 2a(n+1) - a(n+2) = 0		2a(n) - 2a(n+1) - a(n+2) = 0
	Such a shifting is specified by an additional parameter <code>dist</code> which is 0 by default. The example would get <code>dist=2</code>.		Such a shifting is specified by an additional parameter <code>dist</code> which is 0 by default. The example would get <code>dist=2</code>.
			In the future, all equations will be recomputed such that the constant term as well as the shift become always zero.
			====Initial terms====
			For an ''order'' (number of variables - 1) <code>k</code> a recurrence normally needs <code>k</code> 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 <code>k</code> terms,
			* 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.
	===Database table===		===Database table===
	The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.		The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered.
	* a single program that computes a holonomic recurrence,		* a single program that computes a holonomic recurrence,
	*		*

imported>Gfis: Parameters

2021-02-04T20:45:12Z

Parameters

@@ Line 2: / Line 2: @@
 :Whereas the usual linear recurrence has constant coefficients, a holonomic recurrence has coefficients that are polynomials in <code>n</code> (the sequence index). Holonomic recurrences can be derived from linear differential equations, and are applicable to a wide class of series - see [https://en.wikipedia.org/wiki/Holonomic_function Wikipedia: Holonomic function].
-===Hierarchy of recurrences===
+===Example===
-There is a list of sequence types which are included in this project, with increasing complexity and computational effort:
+ [https://oeis.org/A000957 A000957] Fine's sequence (or Fine numbers):
 * constant
 * periodic
-* recurrent with constant coefficients = defined by a rational generating function (fraction of tow polynomials in x)
+** finite (followed by infinitely many zeroes), polynomials
-* holonomic recurrent
+** continued fractions of sqrt(n)
+* recurrent with constant coefficients (cf. [https://oeis.org/wiki/Index_to_OEIS:_Section_Rec OEIS Index entries for linear recurrences with constant coefficients])
 ===Embedding in jOEIS===
 [https://github.com/archmageirvine/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.
@@ Line 26: / Line 38: @@
   PeriodicSequence
   PrependSequence

imported>Gfis: Initial

2021-02-04T18:58:32Z

Initial

New page

This project tries to define as many existing [https://oeis.org OEIS] sequences as possible by '''holonomic recurrences'''.

:Whereas the usual linear recurrence has constant coefficients, a holonomic recurrence has coefficients that are polynomials in <code>n</code> (the sequence index). Holonomic recurrences can be derived from linear differential equations, and are applicable to a wide class of series - see [https://en.wikipedia.org/wiki/Holonomic_function Wikipedia: Holonomic function].
===Hierarchy of recurrences===
There is a list of sequence types which are included in this project, with increasing complexity and computational effort:
* constant
* finite
* periodic
* recurrent with constant coefficients = defined by a rational generating function (fraction of tow polynomials in x)
* holonomic recurrent

===Embedding in jOEIS===
[https://github.com/archmageirvine/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 https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis]:
BlockMultAddSequence
ContinuedFractionOfSqrtSequence
CoordinationSequence
CoxeterSequence
FiniteSequence
GeneratingFunctionSequence
HolonomicRecurrence
LatticeCoordinationSequence
LinearRecurrence
PaddingSequence
PeriodicSequence
PrependSequence

← Older revision		Revision as of 07:51, 14 July 2022
Line 92:		Line 92:
	( aseqno VARCHAR(10) NOT NULL -- A-number		( aseqno VARCHAR(10) NOT NULL -- A-number
	, callcode VARCHAR(32) -- "holos", generate calls for HolonomicRecurrence		, callcode VARCHAR(32) -- "holos", generate calls for HolonomicRecurrence
	, ~~offset~~ INT -- offset		, offset1 INT -- offset
	, matrix VARCHAR(8192) -- coefficients of polynomials in n		, matrix VARCHAR(8192) -- coefficients of polynomials in n
	, init VARCHAR(4096) -- initial terms for the recurrence		, init VARCHAR(4096) -- initial terms for the recurrence
	, ~~shift~~ INT -- optional shift (0)		, dist INT -- optional shift of the index n (0)
	, gftype INT -- 0 for o.g.f, 1 for e.g.f		, gftype INT -- 0 for o.g.f, 1 for e.g.f
	, keyword VARCHAR(128) -- list of keywords for source sequence type etc.		, keyword VARCHAR(128) -- list of keywords for source sequence type etc.
Line 102:		Line 102:
	COMMIT;		COMMIT;
	The tab-separated data loaded into the database table can be found under '''[http://www.teherba.org/OEIS-mat/holref.txt holref.txt]'''.		The tab-separated data loaded into the database table can be found under '''[http://www.teherba.org/OEIS-mat/holref.txt holref.txt]'''.

	=== Parameters of hypergeometric series ===		=== Parameters of hypergeometric series ===
	There is a number of OEIS sequences that can be generated by a recurrence		There is a number of OEIS sequences that can be generated by a recurrence