What would be a good general algorithm for approaching integer sequence problems?

Question

Say the input will always be the same number N of numbers (e.g., 5) and assume the integers actually have a mathematical relation (no lengths of the numbers 'one', 'two', days in the nth month, etc.). The output would be either the next integer and the rule discovered or a message that no rule could be detected. I was thinking to have in one-two-three order, a module that tries to find arithmetic sequence rules by doing sums and/or differences between numbers adjacent, one away, two away, etc. looking for patterns, then having a module focused on geometric sequences by multiplying and/or dividing in the same way, and then, if there is a general approach, a module for detecting recursive sequences.

Thanks!

Answer 1

The On-Line Encyclopedia of Integer Sequences solves precisely this problem :-)

Answer 2

Given any sequence of numbers, we can come up with a formula which 'fits'!

Given a1, a2, ..., an

All you need to do is find an n-1 degree polynomial (using Polynomial interpolation) so that

P(i) = ai

and that's it, you have a formula. Polynomial interpolation can be as easy as solving a matrix equation Ax = b (with A being a Vandermonde matrix).

Check out: http://en.wikipedia.org/wiki/Polynomial_interpolation

That is one of the reasons I find these 'guess the next number' problems a bit silly (read: pathetic IQ tests). Not everyone thinks the same way.