3
$\begingroup$

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

222232244629420445529739893461909967206666939096499764990979600

I need an explanation

  • 8
    Because it's the $300$'th.2012-10-28
  • 1
    @RobertIsrael It really depends. If we use $0,1,1,2,\dots$ then it is the $299$th.2012-10-28
  • 5
    @RobertIsrael Ah, proof by intimidation.2012-10-28
  • 0
    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.2012-10-28
  • 1
    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.2012-10-28
  • 0
    If we start the Fibonacci sequence 1,1,2,3,5,8,13,21,34,55 ... with $F_1=1, F_2=1$ then we have that $F_r|F_{kr}$ for all positive integers $k$ - so this can be regarded as the "natural" place to start.2012-10-28
  • 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.