Project Euler #137: Fibonacci golden nuggets

  • + 1 comment

    Easy mate, the value of 2^(2^28) is 682106198 and I confirm your value for 2^(2^27).

    Actually, I discovered the Pisano serie (Fibonacci series modulo M have a cycle) and in particular the Fibonacci series modulo 10^9+7 has a cycle of "only" 2000000016 = 2*10^9+16. So the values have also the same cycle. It improved my submitted code by a factor 2 on last test case =).

    I am now able to give you "any" gold nugget, the difficulty is now to compute the number you give modulo 2000000016. For example the 1234567891011121314151617181967^ 1234567891011121314151617182009th (> 2^(2^106)) modulo 10^9+7 is 782429593 (I used 2 big primes numbers).

    End of the story I think =).