Project Euler 435 - Polynomials of Fibonacci numbers

Official link: https://projecteuler.net/problem=435

Thought Process

Using a trick used in problem 137 we can simplify Fn(x)

We now have a neat closed form for Fn(x), however f(10^15) is too massive even for python so we need to incorporate the mod 15!, I simply modified my Fibonacci Number Generator to incorporate a modulus argument.

Our next problem is that 100^(10^15) is way too massive as well so we need to incorporate the mod 15! as well, however it is harder than before because in general a/b mod n ≠ a mod n / b mod n, but notice that Fn(x) is a product of integers and is therefore an integer itself which means the denominator divides the numerator in equation (4), and therefore we can use a special property of modulus.

Using this we can calculate the answer efficiently and extremely quickly!

Interactive Code

Enter 3 numbers separated by a space (n, x, mod)

Code will output Fn(x) mod (mod)