WARNING: The text below provides a guidance for a Project Euler problem.

  • If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.

  • If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.

  • If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.

  • Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.

A lagged Fibonacci sequence

The problem tasks us with solving a Fibonacci-like recurrence

for a large value of . The first approach that comes to mind is to use matrix exponentiation in the same way as one does for calculating large values of the Fibonacci sequence; this however does not work by far fast enough due to the size of the matrix needed. There are, however, employable simplifications.

Let be the matrix corresponding to the recurrence, that is:

The matrix has by definition the property that:

and we are thus looking for a way to compute , whereupon the bottommost entry of this will be the sought . The power is clearly too large; and this is where the »Cayley-Hamilton theorem« comes to the rescue! The theorem states that every square matrix satisfies its characteristic equation. What is the characteristic equation of ? Well, this can be read off easily from the recurrence itself: .

From this it follows that may be rewritten as a polynomial of degree , this being the corresponding representative in the quotient ring . Let this polynomial be (This can without fancy terms be understood as the unique polynomial of degree such that for some polynomial ; i.e. a polynomial version of the concept of remainder.). But then:

Reading off the bottommost entries in the above equation, we obtain:

Hence the only thing that we need to do is to find the polynomial representing in and sum up its coefficients! The following piece of Julia code returns the answer in about 0.1 seconds.

using Nemo
P, x = PolynomialRing(ResidueRing(ZZ, 20092010), "x")
evaluate(data(RR(x)^(10^18)), 1)