Return to Revisions

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 Δ⁰.

• Now, Δ¹ is the difference between every adjacent element in Δ⁰. (The first element is left unchanged). For our chosen sequence, this is 1,3,5,7,9,11.

• In general, Δⁿ 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 the Δⁿ with the smallest sum of the absolute of every value. If two Δ's has the same sum, we pick the later one. 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 1,4,9,16,25,36,49.

Here's my code.

def runningSums(lst):
 res = [lst[0]]
 for elem in lst[1:]:
 res.append(res[-1] + elem)
 return res
def antiRunningSums(lst):
 res = [lst[0]]
 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])