```python
import sys
import sympy
from sympy import *
from sympy.abc import x, n, z, t, k
from sympy.core.cache import *
    
clear_cache()    
    
init_printing(use_latex='mathjax') # for nice printing, a-la' TeX

sys.setrecursionlimit(100000)
```


```python
from itertools import *
```

# Difference analysis of Polynomial sequences

Let $\{a_{n}\}_{n\in\mathbb{N}}$ be a sequence of Natural numbers. Assume that each coefficient $a_{n}$ can be written as a polynomial $\mathcal{A}_{k}$, of order $k$, in the variable $n$, namely: 
$$ a_{n} = \hat{a}_{0} + \hat{a}_{1}n + \ldots + \hat{a}_{k}n^{k} = \mathcal{A}_{k}(n)$$
where $\hat{a}_{i}\in\mathbb{Q}$ and $\hat{a}_{k}\neq0$.


```python
def first_sequence_poly(n): return 1+n+2*n**2
```


```python
first_sequence_exploded = [first_sequence_poly(i) for i in range(14)]
first_sequence_exploded
```




$$\left [ 1, \quad 4, \quad 11, \quad 22, \quad 37, \quad 56, \quad 79, \quad 106, \quad 137, \quad 172, \quad 211, \quad 254, \quad 301, \quad 352\right ]$$




```python
def evaluate_poly_sym(polynomial):
    return lambda n: Poly(polynomial(n), polynomial.gen)

def difference(polynomial):
    return lambda n: (polynomial(n+1) - polynomial(n)).simplify()

def difs(sequence):
    
    if not sequence: return []
    elif len(sequence) is 1: return []
    else:
        n, m, *rest = sequence
        return [m-n] + difs([m]+rest)
        
def constant(l):
    if not l: return True
    else:
        car, *cdr = l
        return all(map(lambda a: car == a, cdr))
        
def difLists(lists):
    if not lists: return []
    else:
        l, *rest = lists
        if constant(l): return lists
        else: return difLists([difs(l)]+lists)
        
def firstDifs(sequence):
    return reversed(list(map(lambda l: l[0], difLists([sequence]))))

def genDifs(sequence):
    return reversed(list(map(lambda l: l[-1], difLists([sequence]))))

def nextD(lasts):
    new_coeff = list(accumulate(lasts))[-1]
    new_lasts = [new_coeff]
    for i in range(1,len(lasts)): new_lasts.append(new_lasts[i-1]-lasts[i-1])
    assert new_lasts[-1] == lasts[-1]
    return new_lasts

def next_element(sequence):
    return nextD(list(genDifs(sequence)))[0]
    
def continue_sequence(sequence):
    lasts = list(genDifs(sequence))
    while True:
        lasts = nextD(lasts)
        yield lasts[0]
```


```python
f=first_sequence_poly(n+1)
f
```




$$n + 2 \left(n + 1\right)^{2} + 2$$




```python
differentiated_poly = difference(first_sequence_poly)(n) # keep it simbolically
mapped_difference = map(lambda i: differentiated_poly.subs(n,i), range(13))
list(mapped_difference)
```




$$\left [ 3, \quad 7, \quad 11, \quad 15, \quad 19, \quad 23, \quad 27, \quad 31, \quad 35, \quad 39, \quad 43, \quad 47, \quad 51\right ]$$




```python
difs(first_sequence_exploded)
```




$$\left [ 3, \quad 7, \quad 11, \quad 15, \quad 19, \quad 23, \quad 27, \quad 31, \quad 35, \quad 39, \quad 43, \quad 47, \quad 51\right ]$$




```python
second_sequence = [-12, -11, 6, 45, 112, 213, 354, 541, 780, 1077]
```


```python
first_difference_sequence = difs(second_sequence)
first_difference_sequence
```




$$\left [ 1, \quad 17, \quad 39, \quad 67, \quad 101, \quad 141, \quad 187, \quad 239, \quad 297\right ]$$




```python
second_difference_sequence = difs(first_difference_sequence)
second_difference_sequence
```




$$\left [ 16, \quad 22, \quad 28, \quad 34, \quad 40, \quad 46, \quad 52, \quad 58\right ]$$




```python
third_difference_sequence = difs(second_difference_sequence)
third_difference_sequence
```




$$\left [ 6, \quad 6, \quad 6, \quad 6, \quad 6, \quad 6, \quad 6\right ]$$




```python
difLists([second_sequence])
```




$$\left [ \left [ 6, \quad 6, \quad 6, \quad 6, \quad 6, \quad 6, \quad 6\right ], \quad \left [ 16, \quad 22, \quad 28, \quad 34, \quad 40, \quad 46, \quad 52, \quad 58\right ], \quad \left [ 1, \quad 17, \quad 39, \quad 67, \quad 101, \quad 141, \quad 187, \quad 239, \quad 297\right ], \quad \left [ -12, \quad -11, \quad 6, \quad 45, \quad 112, \quad 213, \quad 354, \quad 541, \quad 780, \quad 1077\right ]\right ]$$




```python
list(firstDifs(second_sequence))
```




$$\left [ -12, \quad 1, \quad 16, \quad 6\right ]$$




```python
lasts = list(genDifs(second_sequence))
lasts
```




$$\left [ 1077, \quad 297, \quad 58, \quad 6\right ]$$




```python
nextD(lasts)
```




$$\left [ 1438, \quad 361, \quad 64, \quad 6\right ]$$




```python
next_element(second_sequence)
```




$$1438$$




```python
take(continue_sequence(second_sequence),20)
```




$$\left [ 1438, \quad 1869, \quad 2376, \quad 2965, \quad 3642, \quad 4413, \quad 5284, \quad 6261, \quad 7350, \quad 8557, \quad 9888, \quad 11349, \quad 12946, \quad 14685, \quad 16572, \quad 18613, \quad 20814, \quad 23181, \quad 25720, \quad 28437\right ]$$




```python
fibs = [fibonacci(i) for i in range(20)]
fibs
```




$$\left [ 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad 89, \quad 144, \quad 233, \quad 377, \quad 610, \quad 987, \quad 1597, \quad 2584, \quad 4181\right ]$$




```python
take(continue_sequence(fibs),20)
```




$$\left [ 13530, \quad 142065, \quad 1357325, \quad 9618830, \quad 54023390, \quad 254254950, \quad 1041111056, \quad 3806846406, \quad 12666486037, \quad 38897569993, \quad 111464146280, \quad 300666911313, \quad 768860983418, \quad 1874805032081, \quad 4380558827899, \quad 9848298629580, \quad 21378856330309, \quad 44949237172189, \quad 91775250522398, \quad 182390568524187\right ]$$




```python
difLists([fibs])
```




$$\left [ \left [ 4181\right ], \quad \left [ -2584, \quad 1597\right ], \quad \left [ 1597, \quad -987, \quad 610\right ], \quad \left [ -987, \quad 610, \quad -377, \quad 233\right ], \quad \left [ 610, \quad -377, \quad 233, \quad -144, \quad 89\right ], \quad \left [ -377, \quad 233, \quad -144, \quad 89, \quad -55, \quad 34\right ], \quad \left [ 233, \quad -144, \quad 89, \quad -55, \quad 34, \quad -21, \quad 13\right ], \quad \left [ -144, \quad 89, \quad -55, \quad 34, \quad -21, \quad 13, \quad -8, \quad 5\right ], \quad \left [ 89, \quad -55, \quad 34, \quad -21, \quad 13, \quad -8, \quad 5, \quad -3, \quad 2\right ], \quad \left [ -55, \quad 34, \quad -21, \quad 13, \quad -8, \quad 5, \quad -3, \quad 2, \quad -1, \quad 1\right ], \quad \left [ 34, \quad -21, \quad 13, \quad -8, \quad 5, \quad -3, \quad 2, \quad -1, \quad 1, \quad 0, \quad 1\right ], \quad \left [ -21, \quad 13, \quad -8, \quad 5, \quad -3, \quad 2, \quad -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2\right ], \quad \left [ 13, \quad -8, \quad 5, \quad -3, \quad 2, \quad -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5\right ], \quad \left [ -8, \quad 5, \quad -3, \quad 2, \quad -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13\right ], \quad \left [ 5, \quad -3, \quad 2, \quad -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34\right ], \quad \left [ -3, \quad 2, \quad -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad 89\right ], \quad \left [ 2, \quad -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad 89, \quad 144, \quad 233\right ], \quad \left [ -1, \quad 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad 89, \quad 144, \quad 233, \quad 377, \quad 610\right ], \quad \left [ 1, \quad 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad 89, \quad 144, \quad 233, \quad 377, \quad 610, \quad 987, \quad 1597\right ], \quad \left [ 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad 21, \quad 34, \quad 55, \quad 89, \quad 144, \quad 233, \quad 377, \quad 610, \quad 987, \quad 1597, \quad 2584, \quad 4181\right ]\right ]$$




```python

```

1c73c4c66246808a67dfdfa7c7651847927ecf39
ipynb
Jupyter Notebook
notebooks/difference-analysis-of-polynomial-sequences.ipynb
massimo-nocentini/Ph.D
7b5174c669d2c1acfe4538e69338064d8acfbe92
Apache-2.0
notebooks/difference-analysis-of-polynomial-sequences.ipynb
massimo-nocentini/Ph.D
7b5174c669d2c1acfe4538e69338064d8acfbe92
Apache-2.0
notebooks/difference-analysis-of-polynomial-sequences.ipynb
massimo-nocentini/Ph.D
7b5174c669d2c1acfe4538e69338064d8acfbe92
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES