Wow! It’s been a really really long time since I’ve completed one of these problems! Sure is good to be back. This is a problem I’ve been thinking about for ages and ages, probably about 2 years. I finally found the time and energy to sit down and make it happen.
I used the numpy package for this one. Until now I’ve tried to stay away from
using python packages for these problems. But the thing is, if it works, use
it. What was nice about the numpy package is that it has linear algebra tools.
I knew I needed to solve a system of linear equations and doing a quick google
search reminded me that linear algebra makes this a snap. It took a bit to
figure out how to build the matrixes. Especially the coefs matrix was very
tough because it involved a list comprehension within a list comprehension.
#!/usr/bin/python
import numpy
def generating_function(n):
"""
Generating function as given in the problem
"""
return 1 - n + n**2 - n**3 + n**4 - n**5 + n**6 - n**7 + n**8 - n**9 + n**10
def OP(fn, k, n):
"""
From the problem: "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."
Adds in the fn (generating function) arg
"""
# First we need to solve a system of linear equations so we can find the
# optimum polynomial generating function. This means putting in values of n
# to the generating function so we can solve for the coefficients.
coefs = numpy.array(
[[row ** exp for exp in range(k)[::-1]] for row in range(1, k + 1)]
)
ans = numpy.array([fn(i) for i in range(1, k + 1)])
opt_poly_gen_fn_coefs = numpy.linalg.solve(coefs, ans).tolist()
# return opt poly at n
val = 0
for exp, coef in enumerate(opt_poly_gen_fn_coefs[::-1]):
val += (n ** exp) * coef
return val
if __name__ == '__main__':
total_FITs = 0
for k in xrange(1, 11):
FIT = OP(generating_function, k, k + 1)
total_FITs += FIT
print total_FITs