GPLv3

recurrence-guess.gp

This is a spot of Pari/GP code to guess a linear recurrence from a vector of numbers (or even from 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 findrec() by Charles R. Greathouse and ggf() in the OEIS Sequence Tools. Bill Allombert points out too that bestapprPade(Ser(vec)) 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 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.

(Back to the sitemap, or the Pari/GP section there)