patternMinor
Is there any hope to use a computer to guess combinatorial formulas for a sequence of integer values, given some initial terms?
Viewed 0 times
anygivenformulashopecombinatorialsequencetermscomputerforsome
Problem
So sometimes in combinatorics, you are computing the count $a_n$ of something that depends on a natural number parameter $n$. Either by hand or using a computer, you can often compute some initial terms in the sequence $(a_n)_n$. Now, you can enter those initial terms into the Online Encyclopedia of Integer Sequences, and if you are lucky you can get a match with a formula and info that will help you prove that your sequence satisfies that formula. But what if your exact sequence is undocumented but is directly related to a known sequence? Like if your sequence is double or the square of another known sequence? Or if your sequence can be expressed either directly or as a summation involving hypergeometric terms? If a computer could propose formulas for a sequence given some initial terms, it might help the mathematician immensely because when they finally look at the correct formula, it might become clear to them why the formula is true based on the structure of the problem and the formula. Has there been any progress in enabling computers to "guess" succinct formulas for integer sequences given some initial terms?
Solution
An exact solution to this problem is of course impossible (for example is $3,5,7$ the sequence of odd integers or of primes?) but there are ways to get answers when the sequence is not in oeis but its "related" to some sequence in the database.
One way to do so is to use superseeker. Basically you send the sequence that you got to superseeker@oeis.org and then the server tries some algorithms in order to find a relationship between your sequence and the ones in oeis.
Hence a good start is to check what kind of tests/algorithms are used by superseeker (iirc there is a description about that somewhere on the site)
One way to do so is to use superseeker. Basically you send the sequence that you got to superseeker@oeis.org and then the server tries some algorithms in order to find a relationship between your sequence and the ones in oeis.
Hence a good start is to check what kind of tests/algorithms are used by superseeker (iirc there is a description about that somewhere on the site)
Context
StackExchange Computer Science Q#29691, answer score: 6
Revisions (0)
No revisions yet.