#101 - Optimum polynomial
If we are presented with the first $k$ terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.
As an example, let us consider the sequence of cube numbers. This is defined by the generating function, $u_n=n^3: 1,8,27,64,125,216,\dots$.
Suppose we were only given the first two terms of this sequence. Working on the principle that “simple is best” we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.
We shall define $OP(k,n)$ to be the $n^{\text{th}}$ term of the optimum polynomial generating function for the first $k$ terms of a sequence. It should be clear that $OP(k,n)$ will accurately generate the terms of the sequence for $n\leq k$, and potentially the first incorrect term ($FIT$) will be $OP(k,k+1)$; in which case we shall call it a bad OP ($BOP$).
As a basis, if we were only given the first term of a sequence, it would be most sensible to assume constancy; that is, for $n\geq 2, OP(1,n)=u_1$.
Hence we obtain the following $OP$s for the cubic sequence:
Optimum Polynomial Sequence $OP(1,n)=1$ $1,\color{red}1\color{black},1,\dots$ $OP(2,n)=7n-6$ $1,8,\color{red}15\color{black},\dots$ $OP(3,n)=6n^2-11n+6$ $1,8,27,\color{red}{58}\color{black},\dots$ $OP(4,n)=n^3$ $1,8,27,64,125,\dots$ Clearly no $BOP$s exist for $k\geq 4$.
By considering the sum of $FIT$s generated by the $BOP$s (indicated in red above), we obatin 1 + 15 + 58 = 74.
Consider the following tenth degree polynomial generating function: \[u_n=1-n+n^2-n^3+n^4-n^5+n^6-n^7+n^8-n^9+n^{10}\]
Find the sum of $FIT$s for the $BOP$s.
The entire problem revolves around how we find the polynomial function given a sequence of numbers? The mentioning of “common difference” in the problem statement. Essentially, we keep taking the difference between consecutive terms in the sequence, until we are left with a common difference. Let the number of times we take the difference be $t$, and the difference itself be $d$. Then, the coefficient of the $n^t$ term in our $OP$ is $\frac{d}{t!}$.
Some intuition as to why this is the case. Taking the difference between terms amounts to finding the rate of change in our sequence. In calculus, this can equivalent to a derivative. Going further, taking the difference $t$ times amounts to taking the $t^{\text{th}}$ derivative. Recall from calculus that the derivative of $x^t$ is $tx^{t-1}$. The second derivative is $t(t-1)x^{t-2}$, and so on. The $t^{\text{th}}$ derivative will be $t!$, as the exponent to the $x$ term will be zeroed out. We offset this constant in our term, as well as multiply the actual difference we see.
Once we’ve calculated this term, we subtract it off from our original sequence, and repeat the process to find the next coefficient one degree down. We keep repeating until the sequence is all 0s.
Example
Let’s say our sequence was 6, 22, 70, 168, 334. The first step is to keep taking differences until we end with a constant difference.
- 1st difference: 16, 48, 98, 166
- 2nd difference: 32, 50, 68
- 3rd difference: 18, 18
It took 3 differences until we reached a common difference of 18. Therefore, this means we have an $n^3$ term in our sequence, and its coefficient is $\frac{18}{3!}=\frac{18}{6} = 3$. Next, we subtract off $3n^3$ from the original sequence and repeat the process.
Subtracted off, we have ${6,22,70,168,334}-{3,24,81,192,375}={3,-2,-11,-24,-41}$.
- 1st difference: -5, -9, -13, -17
- 2nd difference: -4, -4, -4
Our common difference occurred at the 2nd level and is $-4$, so this means the next term is $$\frac{-4}{2!}n^2=\frac{-4}{2}n^2 = -2n^2$.
Subtracting it off results in a sequence of 5, 6, 7, 8, 9. We see immediately that the comman difference is 1, so the next term is $n$. Subtracting off one final time we have a sequence of all 4s, which means the last term is just 4. Together, the polynomial is $\mathbf{3n^3-2n^2+n+4}$.
Back to the problem…
Now you’ve seen how we can find the polynomial function. Since this was defined for $k$ terms, we plug in the value $k+1$ and chances are it differs from the sequence. Since the long tenth degree polynomial has a term for each degree, the value will at $k+1$ will be the first incorrect term.
I calculate the coefficients iteratively with the aid of the numpy package.
# file: "problem101.py"
def kPoly(sequence):
coeffs = []
if len(sequence) == 1 and sequence[0] == 0:
coeffs = [[0, 0]]
# Until we've subtracted off everything...
while not all(sequence == 0):
subSeq = sequence
step = 0
# Until we have a common difference
while not all(subSeq == subSeq[0]):
# Take difference between consecutive terms...
subSeq = np.diff(subSeq)
step += 1
coeffs.append([subSeq[0] / math.factorial(step), step])
# Subtract off...
sequence -= coeffs[-1][0] * np.arange(1, len(sequence) + 1) ** step
# Return coefficients
return np.array(coeffs)
# BOPs won't exist for k > n where n is the degree
# So generate something like the first 12 terms of the sequence
s = 0
seq = np.arange(1, 13, dtype=float)
seq = 1 - seq + seq ** 2 - seq ** 3 + seq ** 4 - seq ** 5 + seq ** 6 - seq ** 7 + seq ** 8 - seq ** 9 + seq ** 10
# seq = seq ** 3
for k in range(1, 11):
subSeq = np.copy(seq[:k])
coeffs = kPoly(subSeq)
# Find the first element which is different
fit = np.sum(coeffs[:, 0] * ((k+1) ** coeffs[:, 1]))
s += fit
print(int(s))
The output is,
37076114526
0.008661100000000033 seconds.
Thus, the sum of all $FIT$s is 37076114526.
