# Code for guessing formula for integer sequence

Hey everyone, I was wondering if there already exists some code in SageMath for solving a problem of the shape:

Given a sequence A_n of numbers/polynomials/etc, guess a formula for A_n.


E.g. a very basic use-case would be something like

sage: n = SR('n')
sage: guess({1:1,2:4,3:9,4:16,5:25,6:36,7:49}, n)
n^2
sage: R.<a,b> = PolynomialRing(QQ)
sage: guess({1:a+b, 2:a^2 + a*b + b^2, 3:a^3 + a^2*b + a*b^2 + b^3}, n)
(a^(n + 1) - b^(n + 1))/(a - b)


Of course for integer sequences, one approach is to query the Online Encyclopedia of Integer Sequences with the oeis-function. But this will not return a symbolic expression/SageMath function, and would also fail if A_n is e.g. a random polynomial of degree 5 in n.

Apart from finding a symbolic expression as above, other possible outputs could be a generating function or even a Python function. I have seen that both maple (example) and Mathematica (example) have similar functionality. In this context, I would also be interested in any references to descriptions of algorithms that can be used for such a task.

I realize this is a very open-ended question, so I am very grateful for any pointers to software/literature/etc.

edit retag close merge delete

1

After installing Fricas, you can try fricas.guess[TAB] to see available useful tools.

( 2023-05-18 08:37:09 +0200 )edit

Thanks a lot, this is really helpful, and an impressive library! Also there are associated papers with more references.

( 2023-05-18 14:45:17 +0200 )edit

Sort by » oldest newest most voted

The ore_algebra package has a guessing module.

more

The problem without any additional assumptions is ill-posed. However, if we restrict our attention to linear recurrence (C-finite) sequences it starts making sense:

C.<x> = CFiniteSequences(QQ)
C.guess([1,4,9,16,25,36,49])


which gives

C-finite sequence, generated by (-x - 1)/(x^3 - 3*x^2 + 3*x - 1)

more

Thanks a lot for pointing this out, I agree that sequences from linear recurrences are very important examples! Also, I agree that the problem is not in general mathematically well-defined. However, in purely practical terms, it is still a very important task that comes up in mathematical research (which I guess is one reason why the OEIS exists).

( 2023-05-18 12:01:34 +0200 )edit

With respect to sequences, look into the Lagrange (interpolation) polynomial for a set points which is here in the documentation. If you type in:

R = PolynomialRing(QQ, 'x')
R.lagrange_polynomial([(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49)])


You'll get

x^2


There is no correct guess to a sequence, this is just one possible answer. To see this, add another term to the sequence above. For example, add (8,63) to the list of points

R = PolynomialRing(QQ, 'x')
R.lagrange_polynomial([(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,63)])


and Sage will give you this polynomial:

-1/5040*x^7 + 1/180*x^6 - 23/360*x^5 + 7/18*x^4 - 967/720*x^3 + 649/180*x^2 - 363/140*x + 1


which is a formula that goes through your 7 points but not (8,64).

more