1
$\begingroup$

Is anybody aware if there exists good computer software which tries to find, in a brute force manner, patterns in given finite sequences of numbers. For example , if you would give the Fibonacci sequence to it, it will see that there is a polynomial $P = x_1 + x_2 - x_3$, such that for all 3 consecutive integers in the sequence $x_1, x_2, x_3$ we have $P(x_1, x_2, x_3) = 0$.

Of course I understand that this is kind of an open question, furthermore it is slightly ill-posed, because one could always interpolate a finite sequence with a polynomial. But that polynomial will not be very nice in general. So, I guess the question is, more precisely, if there is a computer program (like sage or mathematica) which on input a sequence starts generating a list of algebraic relations satisfied by the elements, where the algebraic relations are of growing complexity in a suitable sense.

  • 1
    One could always write something that will query the OEIS for you... as for *Mathematica*, it has a function called `FindSequenceFunction[]`.2012-07-13
  • 1
    Wolfram Alpha can sort of do this, for example http://www.wolframalpha.com/input/?i=%7B1%2C1%2C2%2C3%2C5%2C8%2C13%2C21%2C...%7D2012-07-13
  • 1
    Your explicit example $P(x_1,x_2,x_3)=0$ at [W|A](http://tinyurl.com/c7yf7my)...2012-07-13
  • 1
    Douglas Hofstadter has written long ago about Seek Whence, a program that tried to do that. I believe it was in his Metamagical Themas book.2012-10-10
  • 1
    +1 for the humor in saying that this problem is "slightly" ill-posed :). And I second the reference to Hofstadter... his treatment shows why this is as rich a question as any in artificial intelligence, and not likely to be cracked by brute force.2012-10-10

4 Answers 4