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)
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.
I like the idea and sequence one and two would seem to me that this is possible, but then again you cannot generalize as the sequence could totally go off base. The answer is probably that you cannot generalize, what you can do is write an algorithm to perform a specific sequence knowing the (n+1) or (2n+2) etc...
One thing you may be able to do is take a difference between element i and element i+1 and element i+2.
for example, in your third example:
10 17 31 59 115
Difference between 17 and 10 is 7, and the difference between 31 and 17 is 14, and the difference between 59 and 31 is 28, and the diffeerence between 115 and 59 is 56.
So you note that it becomes the element i+1 = i + (7*2^n).
So 17 = 10 + (7*2^0)
And 31 = 17 + (7*2^1)
And so on...
You can try to use extrapolation. It will help you to find formulas to describe a given sequence.
I am sorry, I can't tell you much more, since my mathematic education happened quite a while ago. But you should find more informations in good books.
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.
That kind of number series are often part of "intelligence tests", which leads me to think in the terms of such an algorithm being something passing (at least part of) a Turing Test, which is something quite hard to accomplish.
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.
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.
For an arbitrary function it can't be done, but for a linear function like in each of your examples it's simple enough.
You have f(n+1) = a*f(n) + b, and the problem amounts to finding a and b.
Given at least three terms of the sequence, you can do this (you need three because you have three unknowns -- the starting point, a, and b). For instance, suppose you have f(0), f(1) and f(2).
We can solve the equations:
f(1) = a*f(0) + b
f(2) = a*f(1) + b
The solution for is:
a = (f(2)-f(1))/(f(1)-f(0))
b = f(1) - f(0)*(f(2)-f(1))/(f(1)-f(0))
(You'll want to separately solve the case where f(0) = f(1) to avoid division by zero.)
Once you have a and b, you can repeatedly apply the formula to your starting value to generate any term in the sequence.
One could also write a more general procedure that works when given any three points in the sequence (e.g. 4th, 7th, 23rd, or whatever) . . . this is just a simple example.
Again, though, we had to make some assumptions about what form our solution would have . . . in this case taking it to be linear as in your example. One could take it to be a more general polynomial, for instance, but in that case you need more terms of the sequence to find the solution, depending on the degree of the polynomial.
See also the chapter "To Seek Whence Comes a Sequence" from the book "Fluid concepts and creative analogies: computer models of the fundamental mechanisms of thought" by Douglas Hofstadter