@@ -0,0 +1,2509 @@
+%22%22%22%0AIf we are presented with the first k terms of a sequence it is impossible to%0Asay with certainty the value of the next term, as there are infinitely many%0Apolynomial functions that can model the sequence.%0A%0AAs an example, let us consider the sequence of cube numbers. This is defined by%0Athe generating function,%0A    u_n = n3: 1, 8, 27, 64, 125, 216, ...%0A%0ASuppose we were only given the first two terms of this sequence. Working on the%0Aprinciple that %22simple is best%22 we should assume a linear relationship and%0Apredict the next term to be 15 (common difference 7). Even if we were presented%0Awith the first three terms, by the same principle of simplicity, a quadratic%0Arelationship should be assumed.%0A%0AWe shall define OP(k, n) to be the nth term of the optimum polynomial%0Agenerating function for the first k terms of a sequence. It should be clear%0Athat OP(k, n) will accurately generate the terms of the sequence for n %E2%89%A4 k, and%0Apotentially the first incorrect term (FIT) will be OP(k, k+1); in which case we%0Ashall call it a bad OP (BOP).%0A%0AAs a basis, if we were only given the first term of sequence, it would be most%0Asensible to assume constancy; that is, for n %E2%89%A5 2, OP(1, n) = u1.%0A%0AHence we obtain the following OPs for the cubic sequence:%0A%0A    OP(1, n) = 1%09        1, 1, 1, 1, ...%0A    OP(2, n) = 7n%E2%88%926%09        1, 8, 15, ...%0A    OP(3, n) = 6n2%E2%88%9211n+6  %091, 8, 27, 58, ...%0A    OP(4, n) = n3%09        1, 8, 27, 64, 125, ...%0A%0AClearly no BOPs exist for k %E2%89%A5 4.%0A%0ABy considering the sum of FITs generated by the BOPs (indicated in red above),%0Awe obtain 1 + 15 + 58 = 74.%0A%0AConsider the following tenth degree polynomial generating function:%0A%0Aun = 1 %E2%88%92 n + n2 %E2%88%92 n3 + n4 %E2%88%92 n5 + n6 %E2%88%92 n7 + n8 %E2%88%92 n9 + n10%0A%0AFind the sum of FITs for the BOPs.%0A%0ASolution comment: Very simple. Just a straight forward implementation%0A                  of the stuff in the problem statement. Very quick.%0A%22%22%22%0A%0Aimport numpy as np%0Afrom itertools import count%0A%0A%0Adef OP(f, k):%0A    n = list(range(1, k + 1))%0A    u = %5Bf(n_i) for n_i in n%5D%0A    g = np.poly1d(np.polyfit(n, u, k - 1))%0A    return g%0A%0A%0Adef FIT(guess, correct, rtol=1e-5):%0A    for i, (g, c) in enumerate(zip(guess, correct)):%0A        if abs((g - c) / g) %3E rtol:%0A            return g%0A    return None%0A%0A%0Adef generator(n):%0A    return sum((-1) ** p * n ** p for p in range(11))%0A%0A%0Afit_sum = 0%0Afor k in count(1):%0A    op = OP(generator, k)%0A    fit = FIT(*zip(*%5B(round(op(n)), generator(n)) for n in range(1, k + 2)%5D))%0A    if fit is None:%0A        break%0A    fit_sum += fit%0A%0Aprint('Answer: ', int(fit_sum))%0A

Add solution to 101.