Problem 399

Squarefree Fibonacci Numbers

The first 15 fibonacci numbers are:

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610.

It can be seen that 8 and 144 are not squarefree: 8 is divisible by 4 and 144 is divisible by 4 and by 9.

So the first 13 squarefree fibonacci numbers are:

1,1,2,3,5,13,21,34,55,89,233,377 and 610.

The 200th squarefree fibonacci number is:
971183874599339129547649988289594072811608739584170445.

The last sixteen digits of this number are: 1608739584170445 and in scientific notation this number can be written as 9.7e53.

Find the 100 000 000th squarefree fibonacci number.

Give as your answer its last sixteen digits followed by a comma followed
by the number in scientific notation (rounded to one digit after the
decimal point).

For the 200th squarefree number the answer would have been: 1608739584170445,9.7e53

Note:

For this problem, assume that for every prime p, the first fibonacci number divisible by p is not divisible by p^{2} (this is part of **Wall's conjecture**). This has been verified for primes 3·10^{15}, but has not been proven in general.

If it happens that the conjecture is false, then the accepted answer to
this problem isn't guaranteed to be the 100 000 000th squarefree
fibonacci number, rather it represents only a lower bound for that
number.

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**