Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
One could always write something that will query the OEIS for you... as for Mathematica, it has a function called FindSequenceFunction[]. –  J. M. Jul 13 '12 at 15:24
1  
Wolfram Alpha can sort of do this, for example wolframalpha.com/input/… –  Cocopuffs Jul 13 '12 at 15:24
    
Your explicit example $P(x_1,x_2,x_3)=0$ at W|A... –  draks ... Jul 13 '12 at 16:33
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. –  Ross Millikan Oct 10 '12 at 19:27
    
+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. –  mjqxxxx Oct 10 '12 at 19:34
add comment

2 Answers

You might want to take a look at the On-Line Encyclopedia of Integer Sequences or OEIS. It doesn't compute the sequences on demand but it has a very useful search engine for finding sequences. In addition, the database contains useful information about the relationships between different sequences.

share|improve this answer
add comment

There are an infinite number of possible combinations for equations: polynomials can have any number of terms, any powers as exponents, and any coefficients. There could be non-polynomials, too. There could be ugly relationships to transcendental functions, or other arbitrary man-made/defined functions such as the exponential integral function. What about relating a sequence to another more well known sequence?

There are an infinitude of ways of trying to relate, using brute force, one sequence to one equation. This systematic approach is not really feasible.

The program could go on forever testing all possible linear monomials. Why not? Sure, it will reach a point where its absurd to keep trying linear monomials, but how would it know to stop and try the next thing? It would have to be able to analyze the sequence and derive properties from it to know if its reached the limit of feasibility of any possible form. You know what I mean? So its not just a brute force program anymore, it has become a computer algebra system all over again, capable of thinking beyond brute force techniques.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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