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.
I got 771000711 for 2^(2^25)th gold nugget and 268044267 for the 2^(2^26)th but with a slightly modified version of my submitted code. But I got 885511592 for the 2^(2^24)th. :-/.
Easy mate, the value of 2^(2^28) is 682106198 and I confirm your value for 2^(2^27).
Actually, I discovered the Pisano serie (Fibonacci series modulo M have a cycle) and in particular the Fibonacci series modulo 10^9+7 has a cycle of "only" 2000000016 = 2*10^9+16. So the values have also the same cycle.
It improved my submitted code by a factor 2 on last test case =).
I am now able to give you "any" gold nugget, the difficulty is now to compute the number you give modulo 2000000016.
For example the 1234567891011121314151617181967^ 1234567891011121314151617182009th (> 2^(2^106)) modulo 10^9+7 is 782429593 (I used 2 big primes numbers).
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 →
My last test case got passed in 1.35 sec.
I can find upto 2^(2^26)th golden nugget mod 10^9+7 The value of 2^(2^24)th golden nugget mod 10^9+7 is 609810998.
Can you tell me the value of 2^(2^25)th and 2^(2^26)th golden nugget mod 10^9+7.
pls give the solution
You can find some indications here : http://www.mathblog.dk/project-euler-137-fibonacci-golden-nuggets/
I got 771000711 for 2^(2^25)th gold nugget and 268044267 for the 2^(2^26)th but with a slightly modified version of my submitted code. But I got 885511592 for the 2^(2^24)th. :-/.
Apologies Mate !!! I did some silly mistakes while mapping.
The value of 2^(2^24)th golden nugget mod 10^9+7 is 885511592.
But the value of 2^(2^25)th golden nugget mod 10^9+7 is 771000771, kindly recheck.
And the value of 2^(2^26)th golden nugget mod 10^9+7 is 268044267.
Lets Move further,I have found the value of 2^(2^27)th golden nugget mod 10^9+7 , and its value is 793677690.
Can you tell me the value of 2^(2^28)th golden nugget mod 10^9+7 ?
Easy mate, the value of 2^(2^28) is 682106198 and I confirm your value for 2^(2^27).
Actually, I discovered the Pisano serie (Fibonacci series modulo M have a cycle) and in particular the Fibonacci series modulo 10^9+7 has a cycle of "only" 2000000016 = 2*10^9+16. So the values have also the same cycle. It improved my submitted code by a factor 2 on last test case =).
I am now able to give you "any" gold nugget, the difficulty is now to compute the number you give modulo 2000000016. For example the 1234567891011121314151617181967^ 1234567891011121314151617182009th (> 2^(2^106)) modulo 10^9+7 is 782429593 (I used 2 big primes numbers).
End of the story I think =).
prime p = 10^9+7 , is not that special, so its pisano period is 2(p+1).
But there are many primes p, whose pisano period is less than p.
can you Explain?
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.