CODEWITHSUNDEEP
mathfibonaccinumber-theory
Mubin Likhon
Mubin Likhon

Reputation: 9

Pisano Period length finding

Can 0 and 1 come together in other positions of the Pisano Period except the first two positions? I am trying to solve a problem where it’s needed to know the Pisano Period length. So I was thinking about searching 0 and 1 in the period.

Upvotes: 1

Views: 1544

Answers (2)

coder_a
coder_a

Reputation: 109

Here's a quick Python code to determine the Pisano Period

def pisanoPeriod(m): 
previous, current = 0, 1
for i in range(0, m * m): 
    previous, current \ 
    = current, (previous + current) % m 
      
    # A Pisano Period starts with 01 
    if (previous == 0 and current == 1): 
        return i + 1

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372992

Yes, if 0 and 1 are adjacent, you're at a point where the sequence is repeating.

A quick proof idea: suppose that you find 0 and 1 adjacent to one another in a Fibonacci sequence mod some number n. In other words, you've found some positions k and k+1 in the sequence such that the kth position is equal to F0 mod n and the (k+1)st position is equal to F1 mod n. That means that position k+2 is equal to F0 + F1 = F2 mod n, and the position after that is equal to F1 + F2 = F3 mod n, etc. This means that if you see 0 and 1 adjacent in the sequence, what follows must be equivalent to the sequence of numbers that you'd find if you started the Fibonacci sequence again from scratch.

Hope this helps!

Upvotes: 3

Related Questions