wu :: forums « wu :: forums - Fibonacci Number? » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 12:26pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, ThudnBlunder, SMQ, william wu, Grimbal, Eigenray, Icarus)    Fibonacci Number? « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Fibonacci Number?  (Read 5910 times)
Barukh
Guest

 Fibonacci Number?   « on: Aug 27th, 2003, 6:10am » Quote Modify Remove

Does there exist a Fibonacci number that has six trailing digits all zeros?
 IP Logged
visitor
Guest

 Re: Fibonacci Number?   « Reply #1 on: Aug 27th, 2003, 7:13am » Quote Modify Remove

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

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

on Aug 27th, 2003, 7:13am, visitor wrote:
 I'll say yes.

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

 Re: Fibonacci Number?   « Reply #5 on: Aug 29th, 2003, 1:21pm » Quote Modify Remove

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

 Re: Fibonacci Number?   « Reply #6 on: Aug 29th, 2003, 1:53pm » Quote Modify Remove

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

 Re: Fibonacci Number?   « Reply #7 on: Aug 29th, 2003, 2:12pm » Quote Modify Remove

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

 Re: Fibonacci Number?   « Reply #8 on: Aug 29th, 2003, 4:17pm » Quote Modify Remove

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

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board