Author |
Topic: Fibonacci Number? (Read 5951 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 27th, 2003, 9:10am » |
 Quote  Modify
|
Me too.
Start by showing that the nth 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
|
on Aug 27th, 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 n-last-digits cycle length in Fibonacci sequence, then FpN = pFN mod 10n+1 for every p > 0.
For instance, if n = 1, N = 60, F60 = ...20, then F120 = ...40, F180 = ...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 29th, 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 29th, 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 20-cycle. 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 10m. 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 (12-cycle) series.
|
|
IP Logged |
|
|
|
Barukh
Guest
|
on Aug 29th, 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, FN+M = FNFM+1+FN-1FM (this is easily shown by induction). Now, let N be an n-digit cycle, M = pN. Use induction on p to prove the result:
F(p+1)N = FNFpN+1 + FN-1FpN
We have: FpN = pFNmod 10n+1 (induction hypothesis). Also, because N is an n-digit cycle, we must have FN-1 = FpN+1 = 1 mod 10n. Plugging this into the above formula, proves the result.
This result gives some quantification to n-digit cycles of Fibonacci numbers. Indeed, it shows that in the sequence of n-digit 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove