We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
In the references we can find a pseudo code to calculate the period :
def π(m):
if m==1:
return 1
if m is prime:
p=m
if p==2: return 3
if p==5: return 20
if p≡±1 (mod 10):
D = the set of even divisors of p−1
else:
D = the set of divisors of 2p+2 that are not divisors of p+1
find the least d in D such that Ud≡I(modp) (of course, use modular exponentiation)
if Ud≡I(modp2):
print p, exit program, publish a paper - you found a Wall-Sun-Sun prime!
return d
else:
factor m as m=pe11pe22⋯penn
return LCM[pe1−11π(p1),pe2−12π(p2),…,pen−1nπ(pn)]
So the period is either a divisor of (p-1) or 2*(p+1) (except for p = 2 or 5) which can be smaller than p.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Project Euler #137: Fibonacci golden nuggets
You are viewing a single comment's thread. Return to all comments →
I am not really familliar with Pisano period and it seems not so obvious. I found a calculator and some explanation here : http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section6
In the references we can find a pseudo code to calculate the period :
def π(m): if m==1: return 1 if m is prime: p=m if p==2: return 3 if p==5: return 20 if p≡±1 (mod 10): D = the set of even divisors of p−1 else: D = the set of divisors of 2p+2 that are not divisors of p+1 find the least d in D such that Ud≡I(modp) (of course, use modular exponentiation) if Ud≡I(modp2): print p, exit program, publish a paper - you found a Wall-Sun-Sun prime! return d else: factor m as m=pe11pe22⋯penn return LCM[pe1−11π(p1),pe2−12π(p2),…,pen−1nπ(pn)]So the period is either a divisor of (p-1) or 2*(p+1) (except for p = 2 or 5) which can be smaller than p.