Predict the next number in any sequence

Question

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 first Δⁿ where the sum of the absolute of each value is less than than sum of the absolute values of Δⁿ⁺¹ . 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. Δ¹ of this sequence is 2,3,-2,6,-3,-4,1. The sum of the absolutes this time is 21. We continue, Δ² is 2,1,-5,8,-9,-1,5. The sum of the absolutes is 31. Now, we can see that Δ¹ is the first with a smaller absolute sum than the next Δ in the series. Now, we duplicate the last value of Δ¹, giving 2,3,-2,6,-3,-4,1,1. Since this is Δ¹, 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]) 

Answer 1

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
    for addend in lst:
        s += addend
        yield s

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

Answer 2

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.