Ask Your Question
2

Code for guessing formula for integer sequence

asked 2023-05-17 16:27:15 +0200

Johannes Schmitt gravatar image

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 flag offensive close merge delete

Comments

1

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

FrédéricC gravatar imageFrédéricC ( 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.

Johannes Schmitt gravatar imageJohannes Schmitt ( 2023-05-18 14:45:17 +0200 )edit

3 Answers

Sort by » oldest newest most voted
3

answered 2023-05-19 18:00:39 +0200

slelievre gravatar image
edit flag offensive delete link more
3

answered 2023-05-17 22:26:55 +0200

Max Alekseyev gravatar image

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)
edit flag offensive delete link more

Comments

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).

Johannes Schmitt gravatar imageJohannes Schmitt ( 2023-05-18 12:01:34 +0200 )edit
1

answered 2023-05-18 03:21:06 +0200

dazedANDconfused gravatar image

updated 2023-05-18 03:27:12 +0200

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).

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-05-17 16:27:15 +0200

Seen: 174 times

Last updated: May 19