Algorithm to find the next number in a sequence

algorithm numbers sequence

12,886

Solution 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.

Solution 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.

Solution 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.

Solution 4

The book Numerical Recipes has pages and pages of real practical algorithms to do this kind of stuff. It's well worth the read!

The first two cases are easy:

>>> seq1 = [1, 2, 3, 4, 5]
>>> seq2 = [10, 20, 30, 40, 50]
>>> def next(seq):
...   m = (seq[1] - seq[0])/(1-0)
...   b = seq[0] - m * 0
...   return m*len(seq) + b
>>> next(seq1)
6
>>> next(seq2)
60

The third case would require solving for a non-linear function.

View more solutions

12,886

Author by

Ben Shelock

i do internets and that

Updated on June 27, 2022

Comments

Ben Shelock almost 2 years
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)
```
Ben Shelock about 14 years

Yes there may well be lots of possibilities however couldn't you just find one that works for the given array and use that? It doesn't necessarily need to cover every single possibility. Does that make sense?
Larry about 14 years

The problem is the next number can be literally anything, and you can figure out a pattern/polynomial to fit that new pattern. For example, there's a pattern that fits, 1, 2, 3, 4, 5, 6, but also 1, 2, 3, 4, 5, 5, 5, 5, 5, 5..
Ben Shelock about 14 years

But I mean just find a formula to fit those 5 numbers then use that to get the 6th.
Larry about 14 years

That said, the statement "with certain constraints" is not a throwaway, if you have certain constraints (let's say you restrict them to a polynomial order 2, ax^2 + bx + c) you might be able to come up with something. But in general, it is not.
Larry about 14 years

You can find an infinite number of formulas that fit the 5 numbers to get a 6th.
Graphics Noob about 14 years

@Larry, I think it's safe to assume in this case, that the numbers are following a pattern that is represented in the given data. Otherwise the question is meaningless.
Instantsoup about 14 years

1, 2, 3, 4, 5 // returns 0 (n % 6)
Larry about 14 years

In any case, take a look at the set of links - the discussion is probably what you are expecting.
Larry about 14 years

On a side note, a number of years ago, I wrote one of those fun "sequences" online test to see how much of a "math geek" you are, with the understanding of what I claimed above as the disclaimer. I still get angry emails to this day about how useless it is. ;)
EvilTeach about 14 years

Ya, this is really the basis of the Babbage difference engine. Figure out that the Nth derivative is a constant, and simply addition give you the next number.