3
$\begingroup$

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

222232244629420445529739893461909967206666939096499764990979600

I need an explanation

  • 0
    @Peter: Robert means that the number given in the problem is $F_{300}$ and therefore is not $F_{299}.2012-10-29

5 Answers 5

12

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

2

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.)

1

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.

0

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$

0

There is a simple test whether a given number n is a member of the Fibonacci sequence: Either 5n²+4 or 5n²-4 must be a perfect square.