project_euler.problem_101.sol1

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) = 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) = u(1).

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) = 6n^2-11n+6 1, 8, 27, 58, … OP(4, n) = n^3 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:

1 - n + n^2 - n^3 + n^4 - n^5 + n^6 - n^7 + n^8 - n^9 + n^10

Find the sum of FITs for the BOPs.

Attributes

Matrix

Functions

interpolate(→ collections.abc.Callable[[int], int])

Given a list of data points (1,y0),(2,y1), ..., return a function that

question_function(→ int)

The generating function u as specified in the question.

solution(→ int)

Find the sum of the FITs of the BOPS. For each interpolating polynomial of order

solve(→ Matrix)

Solve the linear system of equations Ax = b (A = "matrix", b = "vector")

Module Contents

project_euler.problem_101.sol1.interpolate(y_list: list[int]) → collections.abc.Callable[[int], int]

Given a list of data points (1,y0),(2,y1), …, return a function that interpolates the data points. We find the coefficients of the interpolating polynomial by solving a system of linear equations corresponding to x = 1, 2, 3…

>>> interpolate([1])(3)
1
>>> interpolate([1, 8])(3)
15
>>> interpolate([1, 8, 27])(4)
58
>>> interpolate([1, 8, 27, 64])(6)
216
project_euler.problem_101.sol1.question_function(variable: int) → int

The generating function u as specified in the question. >>> question_function(0) 1 >>> question_function(1) 1 >>> question_function(5) 8138021 >>> question_function(10) 9090909091

project_euler.problem_101.sol1.solution(func: collections.abc.Callable[[int], int] = question_function, order: int = 10) → int

Find the sum of the FITs of the BOPS. For each interpolating polynomial of order 1, 2, … , 10, find the first x such that the value of the polynomial at x does not equal u(x). >>> solution(lambda n: n ** 3, 3) 74

project_euler.problem_101.sol1.solve(matrix: Matrix, vector: Matrix) → Matrix

Solve the linear system of equations Ax = b (A = “matrix”, b = “vector”) for x using Gaussian elimination and back substitution. We assume that A is an invertible square matrix and that b is a column vector of the same height. >>> solve([[1, 0], [0, 1]], [[1],[2]]) [[1.0], [2.0]] >>> solve([[2, 1, -1],[-3, -1, 2],[-2, 1, 2]],[[8], [-11],[-3]]) [[2.0], [3.0], [-1.0]]

project_euler.problem_101.sol1.Matrix