`recurrence-guess.gp`

This is a spot of Pari/GP code to guess a linear recurrence from a vector of numbers (or polynomials for a symbolic parameter). If successful the result is pretty printed. For example,

recurrence_guess([1, 3, 9, 25, 65, 161, 385, 897, 2049, 4609]); => Recurrence length=3 Coefficients v[n-3]* [4, -8, 5] *v[n-1] = v[n] v[n] = v[n-1]* [5, -8, 4] *v[n-3] Characteristic polynomial x^3 - 5*x^2 + 8*x - 4 = factors (x - 2)^2 root 2.00000 x - 1 root 1.00000 Generating function (1 - 2*x + 2*x^2)/(1 - 5*x + 8*x^2 - 4*x^3) = partial fractions 1/(1 - x) - 1/(1 - 2*x) + 1/(1 - 2*x)^2 As powers n * 2^n + 1

The guess is found by a simple `matsolve()`

. Linear recurrences
include powers, polynomials, and polynomials times powers. Similar code can
be found in
`findrec()`

by Charles R. Greathouse and
`ggf()`

in the OEIS
Sequence Tools. The nice display here in various forms is the tedious
part. Of course "nice" is a matter of personal preference and the output is
still quite mechanical.

`recurrence-guess.gp`

is
free software (free
as in freedom), published under the terms of the
GNU General Public
License (v3 or higher). Download version
7 here. Requires my
`pol-pfrac.gp`

.

`recurrence-guess.gp`

(43k, and sig)

`recurrence-guess-7.tar.gz`

(39k, and sig)

Just `recurrence-guess.gp`

and
`pol-pfrac.gp`

are
enough to run. The `tar`

file includes some self-tests. The sig
files are Gnu PG ascii armoured signatures
generated from my key.

This page Copyright 2016, 2017 Kevin Ryde, except for the GPLv3 logo which is Copyright Free Software Foundation and used here in accordance with its terms.