wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Fibonacci Number?
        
(Message started by: Barukh on Aug 27th, 2003, 6:10am)
Title: Fibonacci Number?
Post by Barukh on Aug 27th, 2003, 6:10am
Does there exist a Fibonacci number that has six trailing digits all zeros?
Title: Re: Fibonacci Number?
Post by visitor on Aug 27th, 2003, 7:13am
I'll say yes. [hide]
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.[/hide]
Title: Re: Fibonacci Number?
Post by James Fingas on Aug 27th, 2003, 9:10am
Me too.

[hide]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.[/hide]
Title: Re: Fibonacci Number?
Post by Barukh on Aug 29th, 2003, 11:21am

on 08/27/03 at 07:13:06, 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? ???)
Title: Re: Fibonacci Number?
Post by James Fingas on Aug 29th, 2003, 12:17pm
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.
Title: Re: Fibonacci Number?
Post by DH on Aug 29th, 2003, 1:21pm

on 08/29/03 at 12:17:25, 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.
Title: Re: Fibonacci Number?
Post by visitor on Aug 29th, 2003, 1:53pm
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.
Title: Re: Fibonacci Number?
Post by DH on Aug 29th, 2003, 2:12pm
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.
Title: Re: Fibonacci Number?
Post by visitor on Aug 29th, 2003, 4:17pm
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.
Title: Re: Fibonacci Number?
Post by Barukh on Aug 31st, 2003, 11:01am

on 08/29/03 at 12:17:25, 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, ...


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