Yesterday, I came up with a simple method to predict the next value in a sequence.
The method works like this:
Start with a sequence, say
1,4,9,16,25,36, call it Δ0.
Now, Δ1 is the difference between every adjacent element in Δ0. (The first element is left unchanged). For our chosen sequence, this is
In general, Δn is the difference between every adjacent element in Δn-1.
┌──────────────────┐ │Δ0: 1,4,9,16,25,36│ │Δ1: 1,3,5,7,9,11 │ │Δ2: 1,2,2,2,2,2 │ │Δ3: 1,2,0,0,0,0 │ │Δ4: 1,1,0,0,0,0 │ │Δ5: 1,0,-1,0,0,0 │ │Δ6: 1,-1,-1,1,0,0 │ │... │ └──────────────────┘
Now we pick first Δn where the sum of the absolute of each value is less than than sum of the absolute values of Δn+1 . In this case it is
Δ5: 1,0,-1,0,0,0. Now we duplicate the last value. (
1,0,-1,0,0,0,0). Now we repeatedly take the running sums of this list n times, successfully undoing all the "difference between every adjacent element" function, but because we have an extra element, we will have an extra element in this new sequence. In our chosen sequence, this new sequence is
Another example would be the sequence
2,5,3,9,6,2,3(unlike the previous sequence, this one doesn't follow a clear pattern). The sum of the absolutes of this sequence is 30. Δ1 of this sequence is
2,3,-2,6,-3,-4,1. The sum of the absolutes this time is 21. We continue, Δ2 is
2,1,-5,8,-9,-1,5. The sum of the absolutes is 31. Now, we can see that Δ1 is the first with a smaller absolute sum than the next Δ in the series. Now, we duplicate the last value of Δ1, giving
2,3,-2,6,-3,-4,1,1. Since this is Δ1, we take the running sums 1 time giving
2,5,3,9,6,2,3,4 as a final result.
Here's my code.
def runningSums(lst): res = [lst] for elem in lst[1:]: res.append(res[-1] + elem) return res def antiRunningSums(lst): res = [lst] for i in range(1,len(lst)): res.append(lst[i] - lst[i-1]) return res def predict(lst): deriv = 0 while True: nxt = antiRunningSums(lst) if sum(map(abs, nxt)) > sum(map(abs, lst)): break lst = nxt deriv += 1 lst.append(lst[-1]) for i in range(deriv): lst = runningSums(lst) return lst # Example call. Correctly gives back [1,4,9,16,25,36,49]. print predict([1,4,9,16,25,36])