Author 
Topic: Fibonacci Number? (Read 5910 times) 

Barukh
Guest

Does there exist a Fibonacci number that has six trailing digits all zeros?


IP Logged 



visitor
Guest

I'll say yes. Obviously the final digits are going to go into a repetitive pattern. A quick check tells me the last digit cycles every 60 numbers. At that point the second last digit is 2, so the second digit will cycle every 300 numbers. Every digit must eventually enter a cycle, it's just a question of how long.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Fibonacci Number?
« Reply #2 on: Aug 27^{th}, 2003, 9:10am » 
Quote Modify

Me too. Start by showing that the n^{th} and (n+1)^{st} elements of the Fibonacci sequences generated using seed numbers x and y versus seed numbers u and v are the same only if u=x and v=y.


IP Logged 
Doc, I'm addicted to advice! What should I do?



Barukh
Guest


Re: Fibonacci Number?
« Reply #3 on: Aug 29^{th}, 2003, 11:21am » 
Quote Modify
Remove

on Aug 27^{th}, 2003, 7:13am, visitor wrote: Visitor, you are right! And your approach works, although it was far from obvious for me... The crusial point is this implicitly used statement: If N is an nlastdigits cycle length in Fibonacci sequence, then F_{pN} = pF_{N} mod 10^{n+1} for every p > 0. For instance, if n = 1, N = 60, F_{60} = ...20, then F_{120} = ...40, F_{180} = ...60, and so on. It took me a long time to prove this statement (am I so stupid? )


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Fibonacci Number?
« Reply #4 on: Aug 29^{th}, 2003, 12:17pm » 
Quote Modify

Barukh, Your result is interesting, and I have no idea how you could prove it. You don't need it to prove that you get zero eventually, though. My statement (easily proven) can be used to prove that each digit will have a cycle (as visitor states). If you consider the first Fibonacci number to be zero, you can see that there exist Fibonacci numbers with any finite number of trailing zeros.


IP Logged 
Doc, I'm addicted to advice! What should I do?



DH
Guest

on Aug 29^{th}, 2003, 12:17pm, James Fingas wrote:Barukh, Your result is interesting, and I have no idea how you could prove it. You don't need it to prove that you get zero eventually, though. My statement (easily proven) can be used to prove that each digit will have a cycle (as visitor states). If you consider the first Fibonacci number to be zero, you can see that there exist Fibonacci numbers with any finite number of trailing zeros. 
 In the same way it can be proven that for each positive n there exists a Fibonacci number that is a multiple of n.


IP Logged 



visitor
Guest

I'm no mathematician, so I'm not much into proving anything I say. I just hope my guess is right and let others laugh at my naivity. My reasoning (not proof) was as follows. The last digit cycles every 60 iterations. At that point the last 2 digits=20. I figured you could split it up into 2 segments. The last digit will follow the same cycle. The 2 adds to the mix its own cycle, which, you can quickly check and see that a 2 would cycle every 20 iterations (02246066280886404482), so that cycle will be back on a 2 when the first cycle finishes, which adds to the ones cycle to give you a 40 ending after 120 iterations. All even numbers have the same 20cycle. So the 4 will end up a 4 plus the 20 from the ones cycle to get your 60 after 180 iterations. If it's legitimate to split up the fibonacci sequence this way, then I took it for granted that the 3rd,4th 5th digits...will cycle similarly, although it gets more complicated as each digit's cycle is influenced by more and more following digits.


IP Logged 



DH
Guest

A simple way to prove that all digits cycle is to consider F(n) mod 10^{m}. To generate the next number in the sequence you need only the last two numbers. There are a finite number of possible pairs and the sequence is infinite so it will cycle.


IP Logged 



visitor
Guest

It's times like this when I think I really should register. That last message of mine was invalid. How long it takes the 2 to cycle depends on what the previous number was. I checked, and the previous digit was a 4, so you can think of the series from that point on as two fibonacci series that will be added together at the end. one starting from scratch, the other continuing from 4,2. And that actually has a last digit cycle of just 4 (2684). It still will end up back at the starting number at iteration 60. Any pair of digits will cycle evenly after 60 iterations. The original 60 cycle uses all the possible two digit combinations except 2 even digits in a row, the 0,5,5 series, and the 1,3,4,7,1,8,9,7,6,3,9,2 (12cycle) series.


IP Logged 



Barukh
Guest


Re: Fibonacci Number?
« Reply #9 on: Aug 31^{st}, 2003, 11:01am » 
Quote Modify
Remove

on Aug 29^{th}, 2003, 12:17pm, James Fingas wrote:Barukh, Your result is interesting, and I have no idea how you could prove it. You don't need it to prove that you get zero eventually, though. 
 James, I agree with you on that. Still, because this is interesting (as you pinted out), here's the proof. Start with the following identity on Fibonacci numbers: for every N, M, F_{N+M} = F_{N}F_{M+1}+F_{N1}F_{M} (this is easily shown by induction). Now, let N be an ndigit cycle, M = pN. Use induction on p to prove the result: F_{(p+1)N} = F_{N}F_{pN+1} + F_{N1}F_{pN} We have: F_{pN} = pF_{N}mod 10^{n+1} (induction hypothesis). Also, because N is an ndigit cycle, we must have F_{N1} = F_{pN+1} = 1 mod 10^{n}. Plugging this into the above formula, proves the result. This result gives some quantification to ndigit cycles of Fibonacci numbers. Indeed, it shows that in the sequence of ndigit cycles every member is a multiple of 5 or 10 of its predecessor. The first few members are: 60, 300, 1500, 7500, 75000, ...


IP Logged 



