# Explaining a Fibonacci

Explain why the number below is not 299th Fibonacci number:

222232244629420445529739893461909967206666939096499764990979600

I need an explanation

-
Because it's the $300$'th. – Robert Israel Oct 28 '12 at 19:42
@RobertIsrael It really depends. If we use $0,1,1,2,\dots$ then it is the $299$th. – Pedro Tamaroff Oct 28 '12 at 19:48
@RobertIsrael Ah, proof by intimidation. – WimC Oct 28 '12 at 19:50
One possible approach: you could try using the "closed form" expression for Fibonnaci numbers to estimate the size of the 299th and show that it's smaller than the number you give above. – Jonah Sinick Oct 28 '12 at 20:16
Another possible approach: the Fibonacci numbers are periodic (mod $p$) for every prime p. For each $p$, you can write out a list of remainders that the Fibonacci numbers leave (mod $p$) and which indices give which remainders. Then you can divide the number by $p$ and see if the one above leaves a remainder consistent with it having an index of 299. You can try p=2, p = 3, p = 5, etc. until you find one that works. – Jonah Sinick Oct 28 '12 at 20:17

If you start with $1, 1, 2, 3, \dotsc$ then only every third Fibonacci number is even. Now $299$ is not divisible by three.

-

Before spotting the easy argument given by WimC, I answered the question in a very different fashion. It’s ugly enough that I was going to ignore it, but now that I see that Jonah Sinick actually suggested it, I’ll toss it out for anyone who might be interested.

$F_{299}$ is the integer nearest to $$\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^{299}\;.$$

Let $n$ be your number. Then $n>2\times10^{62}$, so $\log_{10}n>62.3$. However,

$$\log_{10}\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^{299}=299\Big(\log_{10}(1+\sqrt5)-\log_{10}2\Big)-\frac12\log_{10}5\approx62.1378\;,$$

and the difference between this and $62.3$ is too large to be attributable to roundoff error in the calculation with the logs. (With sufficient work one can justify that last claim rigorously.)

-

I used GNP/PARI to find the answer using the formula $$F(n)=\frac{g^n-(-g)^{-n}}{\sqrt{5}}$$ where $g=(1+\sqrt{5})/2$.

$F(300)$ matches your result digit by digit.

-

WimC said it, but I guess since I wrote this all out before reading that particular post, I guess I might as well post it.

$$13*23=299$$ $$f(13)=233$$ $$f(23)=28657$$

$$222232244629420445529739893461909967206666939096499764990979600\mod{233}=89$$ $$222232244629420445529739893461909967206666939096499764990979600\mod{28657}=17711$$ Not the 299th Fibonacci Number. $$2^2\times3\times5^2=300$$ f(20)=6765 f(100)=354224848179261915075 f(150)=9969216677189303386214405760200

$$222232244629420445529739893461909967206666939096499764990979600\mod{6765}=0$$ $$222232244629420445529739893461909967206666939096499764990979600\mod{354224848179261915075}=0$$ $$222232244629420445529739893461909967206666939096499764990979600\mod{9969216677189303386214405760200}=0$$

-