Project Euler 435 - Polynomials of Fibonacci numbers
Official link: https://projecteuler.net/problem=435
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!
Enter 3 numbers separated by a space (n, x, mod)
Code will output Fn(x) mod (mod)