Want to improve this question? Update the question so it focuses on one problem only by editing this post.
Closed 3 years ago.
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
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.
I would say that what you are trying to do is impossible. Mostly because there are infinite number of sequences that start with some particular elements. Here you want to find the next numbers after 1, 1, 2, 3, 5, 8, 13, 21, 34 and you claim them to be 55, 89, 144, .... Most people agree with you telling "ah this is a Fibonacci sequence".
But I would tell you that no, the next element can be 55, 91, 149 and the sequence is ceil(e^(n-1)/2)).
In fact I can give you infinite number of sequences with the same starting elements. Do not believe me?
How about this one F(n) = F(n-1) + F(n-2) + F(n-9). Write a program and you will see that the starting elements are the same. Want another one - here you go F(n) = F(n-1) + F(n-2) - 4 * F(n-9) + F(n - 17).
And you will never persuade me or anyone else that your solution is correct and mine are wrong.
Although in mathematics it is possible to define sequences like such, with the following values assumed, this requires a smart mathematician to do some figuring.
Of course you could write a function which has some "hard-coded" pattern detections, it may not be correct. As that is just a list, it is very possible the next value could be 12, even though the context makes it appear as the Fibonacci sequence.
If you need to generate a Fibonacci sequence, consider a generator function:
def fib(n):
# generate the first n Fibonacci numbers
i = 0
last = 0
current = 1
while i < n:
yield current
temp = current + last
last = current
current = temp
i += 1
