3

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

222232244629420445529739893461909967206666939096499764990979600

I need an explanation

Anne
  • 31
  • 1
  • 10
    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 Oct 28 '12 at 19:48
  • 5
    @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
  • 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. – Jonah Sinick Oct 28 '12 at 20:17
  • 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. – Mark Bennet Oct 28 '12 at 21:31
  • @Peter: Robert means that the number given in the problem is $F_{300}$ and therefore is not $F_{299}. – Brian M. Scott Oct 29 '12 at 06:04

6 Answers6

14

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

WimC
  • 32,192
  • 2
  • 48
  • 88
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.)

Brian M. Scott
  • 616,228
1

There is a simple test whether a given number n is a member of the Fibonacci sequence:

  • For Fibonacci numbers with an odd index, 5n²-4 must be a perfect square
  • For Fibonacci numbers with an even index, 5n²+4 must be a perfect square

E.g. we have

  • 5*1²-4 = 1²
  • 5*1²+4 = 3²
  • 5*2²-4 = 4²
  • 5*3²+4 = 7²
  • 5*5²-4 = 11²

In the given case, the number passes the 5*n²+4 test case, so it is a Fibonacci number, but one with an even index, hence it can't be the 299th one.

In order to just disprove the 5 * n² - 4 case, we can e.g. work in modulo 7: The number is 4 mod 7, and 5 * 4² - 4 = 76 = 6 mod 7, but jacobi(6, 7) = -1, so this number can't be a square.

Landei
  • 397
  • This number passes that test. You had to show that it is not specifically the 299th Fibonacci number. – Oscar Lanzi Apr 30 '21 at 23:38
  • @Oscar Lanzi To be more precise, the test is alternating for Fibonacci Numbers with even or odd index, e.g. 52²-4 = 16 is a square, 53²+4 = 49 is a square, 55²-4 =121 is a square etc. If you calculate the square root of the 5F², you get 496926405783746676393791436882468230898067489522034699520200001.999999999999999999999999999999999999999999999999999999999999995..., which means to get an exact result, we would have to add 4 before taking the square root, but for Fibonacci numbers with an odd index we should have to subtract 4 – Landei May 02 '21 at 18:05
  • Don't tell me here (actually I already knew). Tell readers in the answer. Then I will update. Thank you. – Oscar Lanzi May 02 '21 at 18:07
  • An additional tip: Render the number $\bmod 16$. That will be sufficient to show the failure. – Oscar Lanzi May 02 '21 at 18:08
  • Mod 16 would have been simpler, but this is OK with me. – Oscar Lanzi May 02 '21 at 18:49
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.

Alexander Gruber
  • 26,963
B.Sahu
  • 55
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$$

Thomas Olson
  • 63
  • 6
0

If $n\equiv 19\bmod 20$, then $F_n\equiv1\bmod 5$:

$1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,\color{blue}{1},0,1,1,2,...$

The given number misses the required residue. It does, of course, hit the required residue $\bmod 5$ for $F_{300}$.

Oscar Lanzi
  • 39,403