Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

222232244629420445529739893461909967206666939096499764990979600

I need an explanation

share|improve this question
8  
Because it's the $300$'th. –  Robert Israel Oct 28 '12 at 19:42
1  
@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
4  
@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
show 2 more comments

4 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.