An algorithm to generate the next element from a sequence, by finding a pattern [closed]

Question

I was wondering if it is possible to take a list of numbers eg.

lst = [1, 1, 2, 3, 5, 8, 13, 21, 34]

And create an algorithm to figure out what the pattern is: the F(n) = F(n-1) + F(n-2) one and then keep going and add the next number:

lst.append(x) # x being the next number which is 55

Possibly an algorithm that could be applied to any list of numbers

Answer 1

The short answer is: what you are asking for is impossible.

What you are looking for is an algorithm that relates to curve fitting in general. For this particular problem, one possible approach is Lagrange Polynomials.

But note that, in general, what you want may have no real solution. For example, consider the simple sequence: 2, 4, 6, 8, 10, 12, 14. What will the next few numbers be ?

You may say that the answer is 16, 18, 20 and so on, since you use the equation f(n) = 2*n where n is the location of the term (starting from 1).

Note that there is an infinitude of equations of the form:

f(n) = [(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) * g(n)] + 2*n

The second term yields the right values for n = 1..7 while the first term yields a 0 for only those values of n. So you can choose any function (with finite range) for the last g(n) multiplier in the first term and get whatever values you want from n=8 onwards.

For example, with g(n) = 20*n,

f(n) = (n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) * 20 * n + 2*n

will yield a list: 2, 4, 6, 8, 10, 12, 14, 806416

Hence the problem as you state it is unsolvable.

However, if you characterize the form of your algorithm (or characterize the function families that you wish to use, to solve the problem), you can get functions that optimally fit the numbers. For example, you could say that f(n) is a polynomial of order 1 (linear equation), which would reduce the number of possibilities and give you f(n) = 2 * n. Some of those approaches are used traditionally in Machine Learning, especially Linear and Logistic regression.