Algorithm to find the next number in a sequence

Question

Ever since I started programming this has been something I have been curious about. But seems too complicated for me to even attempt.

I'd love to see a solution.

1, 2, 3, 4, 5    // returns 6 (n + 1)
10, 20, 30, 40, 50   //returns 60 (n + 10)
10, 17, 31, 59, 115  //returns 227 ((n * 2) - 3)

Answer 1

What you want to do is called polynomial interpolation. There are many methods (see http://en.wikipedia.org/wiki/Polynomial_interpolation ), but you have to have an upper bound U on the degree of the polynomial and at least U + 1 values.

If you have sequential values, then there is a simple algorithm.

Given a sequence x1, x2, x3, ..., let Delta(x) be the sequence of differences x2 - x1, x3 - x2, x4 - x3, ... . If you have consecutive values of a degree n polynomial, then the nth iterate of Delta is a constant sequence.

For example, the polynomial n^3:

1, 8, 27, 64, 125, 216, ...
7, 19, 37, 61, 91, ...
12, 18, 24, 30, ...
6, 6, 6, ...

To get the next value, fill in another 6 and then work backward.

6, 6, 6, 6 = 6, ...
12, 18, 24, 30, 36 = 30 + 6, ...
7, 19, 37, 61, 91, 127 = 91 + 36, ...
1, 8, 27, 64, 125, 216, 343 = 216 + 127, ...

The restriction on the number of values above ensures that your sequence never becomes empty while performing the differences.

Answer 2

Sorry to disappoint, but this isn't quite possible (in general), as there are an infinite number of sequences for any given k values. Maybe with certain constraints..

You can take a look at this Everything2 post, which points to Lagrange polynomial.

Answer 3

Formally there is no unique next value to a partial sequence. The problem as usually understood can be clearly stated as:

Assume that the partial sequence exhibited is just sufficient to constrain some generating rule, deduce the simplest possible rule and exhibit the next value generated.

The problem turns on the meaning of "simplest", and is thus not really good for algorithmatic solutions. It can be done if you confine the problem to a certain class of functional forms for the generating rule, but the details depend on what forms you are willing to accept.