Fibonacci Sequence in amazing!

Consider the Fibonacci Sequence but addition of terms is done ( m o d 10 ) \pmod {10} ( 1 , 1 , 2 , 3 , 5 , 8 , 3 , 1 , 4 , 5 , 9 , 4 , 3 , (1,1,2,3,5,8,3,1,4,5,9,4,3,\ldots are the first few terms of the sequence).

This sequence is periodic. Find its fundamental period.


The answer is 60.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

James Pohadi
Apr 18, 2017

Let, p ( x ) p(x) be the period for the fibonacci sequence in mod x \text{mod x}

It is easy to find that p ( 2 ) = 3 p(2)=3 [ 1 , 1 , 0 ] \implies [1,1,0] , and p ( 5 ) = 20 [ 1 , 1 , 2 , 3 , 0 , 3 , 3 , 1 , 4 , 0 , 4 , 4 , 3 , 2 , 0 , 2 , 2 , 4 , 1 , 0 ] p(5)=20 \implies [1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0]

To find p ( 10 ) p(10) , we need to find when the fibonacci sequence in mod 2 \text{ mod 2} and mod 5 \text{ mod 5} meets (since a (mod 10) = a (mod 2) a \text{ (mod 10)}= a \text{ (mod 2)} and a (mod 10) = a (mod 5) a \text{ (mod 10)}= a \text{ (mod 5)} ), so it is equal with L C M ( p ( 2 ) , p ( 5 ) ) LCM(p(2),p (5)) , then p ( x ) = L C M ( 3 , 20 ) = 60 p(x)=LCM (3,20)=60

Generally, p ( x 1 × x 2 × . . . × x i ) = L C M ( p ( x 1 ) , p ( x 2 ) , . . . , p ( x n ) ) p(x_1 \times x_2\times ... \times x_i)=LCM(p (x_1),p (x_2),...,p (x_n) )

展豪 張
Mar 23, 2016

solution in python:

>> a='11'
>> while a[-2:]not in a[:-1]:a+=str((int(a[-2])+int(a[-1]))%10)

>> a
'11235831459437077415617853819099875279651673033695493257291011'
>> print(len(a)-2)
60


0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...