7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ at heart this is the "problem of induction" and also very deeply involved with automated theorem proving. see machine-learning. the problem in general is undecidable & subject to false positives/ negatives (misidentification). $\endgroup$ – vzn Sep 5 '14 at 22:48
6
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

this is actually implemented in a relatively new mathematica function called FindSequenceFunction and succeeds in basic cases. it can be regarded as a model and nearly state of the art in the area.

however the general problem is very crosscutting and touches on many fields/ techniques such as Machine learning, automated theorem proving, mathematical induction, & Kolmogorov complexity (where the very similar problem solution is based on "finding the smallest TM that generates a sequence") and even croscutting into philosophy as "the problem of induction". all these fields have active research in the area. it also shows up in curve fitting and statistics/big data but there the sequences are more approximate, although generally same abstract principles apply.

the general problem is not decidable, but neither is it exactly accurate to call it "undecidable". it is always subject to "false positives" (sequences that match on the limited # of inputs but not further) and "false negatives" (sequences that have formulas but which arent discoverable by "the" or any algorithm). it is safe to say that research in this area will continue for decades into the future and actually, probably as long as there is mathematical research done by humans.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.