# Predict the next number in any sequence

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 1,3,5,7,9,11.

• 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 1,4,9,16,25,36,49.

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[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])

• It also fails to find the right next value for: predict([n**n for n in range(7)]) and predict([1,-1,1,-1]) Commented Jul 7, 2016 at 19:37
• For which kind of sequences does this algoritmh work? If you do not give is sufficient context to the applicability of your algoritmh (exactly in which cases it should work) the question is unclear. Commented Jul 7, 2016 at 19:40
• @Caridorc: I don't want to sound rude, but could you please give feedback on the code itself, and not so much on the algorithm? I know that the algorithm doesn't work for all sequences, and that is isn't perfect, I came up with it just to give rough estimates on simple sequences. Commented Jul 7, 2016 at 19:54
• Nowadays, the #1 method for predicting the next number from a sequence (assuming the sequence has come up in a "natural" way) is to look it up in the Online Encyclopedia of Integer Sequences. Commented Jul 7, 2016 at 20:21
• @Caridorc those described by a polynomial equation, of degree strictly less than the number of examples. Commented Jul 8, 2016 at 3:10

### antiRunningSums

You should use a pairwise helper to raise abstraction:

def antiRunningSums(lst):
return [b - a for a, b in pairwise(lst)]


pairwise can easily be found in the itertools documentation.

### runningSums

I think that referencing the list while you are building it is overcomplicated, I would use a variable to be incremented:

def runningSums(lst):
s = 0
yield s


To obtain a list call list on the result of this function.

• Your recommendation for antiRunningSums is better than what I was thinking of with enumerate. Commented Jul 7, 2016 at 20:06

Apart from the to be specified applicability, I see only minor PEP8 nitpicks:

1. Function names should be in snake_case.
2. There should be two empty lines after a function definition (allowing easy copy-n-paste into the console)
3. There should be spaces in comma-separated argument lists (in antiRunningSums one is missing)

Performance-wise: For long lists it becomes cheaper to pre-allocate the list to the right length and override elements than appending to a list.

It is very important to mention one point. Every sequence has an infinity of polynomial formulas and there is a very simple mathematical proof for it. You should consider a formula that is the most humane formula possible. In the case of other types of patterns, the program should give the necessary warning that it is likely that another pattern is intended.

When the distance of the polynomial degree and the length of the sequence is one, the program gives an deviated number. This is a big problem for this program Just give 1 4 9 and the next number will be 15

for this exam answer is not correct:

1.2,1.35,1.5,1.65

The reason for this issue is the problem of Python, which can be solved by defining a special function

The algorithm is too complicated and it can be written much simpler. Also, the program does not give the necessary warnings about the next number

• As was mentioned in a comment on the last answer could you please merge the contents of this answer and the last one into the second answer (i.e. the one with a positive score)? Then delete these other answers. Commented Mar 15 at 22:49