This is a spot of Pari/GP code to guess a linear recurrence from a vector of numbers (or vector of polynomials for guessing with 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
by Charles R. Greathouse and
ggf() in the OEIS
Sequence Tools. Bill Allombert points out too that
gives a generating function. 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(45k, and sig)
recurrence-guess-9.tar.gz(42k, and sig)
This page Copyright 2016, 2017, 2018, 2019 Kevin Ryde, except for the GPLv3 logo which is Copyright Free Software Foundation and used here in accordance with its terms.
(Back to the sitemap, or the Pari/GP section there)