Problem #101 concerns polynomials that approximate higher degree polynomials based on consecutive outputs. The question reads:
Project Euler Problem 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,
un = n3: 1, 8, 27, 64, 125, 216,...
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 nth 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 ≤ 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 sequence, it would be most sensible to assume constancy; that is, for n ≥ 2, OP(1, n) = u1.
Hence we obtain the following OPs for the cubic sequence:
OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n2−11n+6 1, 8, 27, 58, ...
OP(4, n) = n3 1, 8, 27, 64, 125, ...
Clearly no BOPs exist for k ≥ 4.
By considering the sum of FITs generated by the BOPs (indicated in red above), we obtain 1 + 15 + 58 = 74.
Consider the following tenth degree polynomial generating function:
un = 1 − n + n2 − n3 + n4 − n5 + n6 − n7 + n8 − n9 + n10
Find the sum of FITs for the BOPs.
Much like 2019 Putnam Problem B5, this question can be solved most easily with finite differences. Here’s my solution:
Solution #1: Finite Differences Approach
Effectively, the values of the BOPs can be determined with the Finite Difference Method. By evaluating these values until an FIT is encountered, it is possible to find the sum of the FITs of all of the BOPs. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #101
'''
import time
def evaluatePolynomial(poly,n):
power = 1
total = 0
for x in poly:
total+=power*x
power*=n
return total
def partialDifferenceNextTerm(myList):
l = len(myList)
pyramid = [myList]
for x in range(1,l):
row = []
theRow = pyramid[x-1]
for z in range(len(theRow)-1):
row.append(theRow[z+1]-theRow[z])
pyramid.append(row)
total = 0
for x in pyramid:
total+=x[len(x)-1]
return total
def projectEulerProblemOneHundredOne(poly):
degree = len(poly)-1
values = []
for x in range(1,degree+3):
values.append(evaluatePolynomial(poly, x))
total = 0
for x in range(1,degree+1):
total+=partialDifferenceNextTerm(values[0:x])
return total
start = time.time()
print projectEulerProblemOneHundredOne([1,-1,1,-1,1,-1,1,-1,1,-1,1])
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
37076114526
--- 9.67979431152e-05 seconds ---
for input of [1,-1,1,-1,1,-1,1,-1,1,-1,1]
'''
And with that, we’re done. This is a great example of how knowing math can make Project Euler problems much easier.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 