Project Euler 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle
Project Euler 26 Problem Description
Project Euler 26: A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:


Where 0.1(6) means 0.166666…, and has a 1digit recurring cycle. It can be seen that ^{1}/_{7} has a 6digit recurring cycle.
Find the value of d < 1000 for which ^{1}/_{d} contains the longest recurring cycle in its decimal fraction part.
Analysis
This problem and the HackerRank version are looking for d < N, NOT d ≤ N. This specific problem has N fixed at 1000.
This is a useful application of Fermat’s little theorem that says: 1/d has a cycle of n digits if 10^{n} − 1 mod d = 0 for prime d. This is called a full reptend prime.
Summary
So, this solution comes down to finding the first full reptend prime number below the limit. As an example, for d < 100 the first reptend prime less than 100 is 97 and 1/97 will produce the longest recurring cycle in its decimal fraction part of 971 = 96 digits, without exception, for all denominators less than 100 (with 1 as a numerator).
For N < 8 edge cases
The algorithm works for all N greater than or equal to 8. When the N is less than 8 we return 3 because that is the smallest d that repeats with the longest recurring cycle. 1/2 (0.5), 1/4 (0.25), 1/5 (0.2) don’t repeat. 1/3 (0.33~), 1/6 (0.166~) both repeat with a cycle of 1 of which 3 is the smallest value of d. 3 is not a reptend prime.
Reference: The OnLine Encyclopedia of Integer Sequences (OEIS) A001913: Full reptend primes: primes with primitive root 10.HackerRank Project Euler 26 increases the limit to d < 10000 and runs 1000 trials. Same solution solves all the test cases.
Project Euler 26 Solution
Runs < 0.006 seconds in Python 2.7.Use this link to get the Project Euler 26 Solution Python 2.7 source.
Answer
Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.Afterthoughts
 Fermat’s little theorem is the basis for the Fermat primality test and is one of the fundamental results of elementary number theory. The theorem is named after Pierre de Fermat, who stated it in 1640. It is called the “little theorem” to distinguish it from Fermat’s last theorem.
for d < 2000: 1979
for d < 2500: 2473
for d < 10,000: 9967
for d < 25,000: 24989
for d < 100,000: 99989
d < 1,000,000: 999983A change from:
while (pow(10, c)  1) % p != 0:
to
while pow(10, c, p) != 1:
was a 400 times speed improvement.
i am having quite a hard time to understand how you deduce “1/d has a cycle of n digits if 10n−1 mod d = 0 for prime d” from Fermat’ theorem …
In my estimation, there are two fallacies here.
“1/d has a cycle of n digits if 10^n – 1 mod d = 0 for prime d” – Partially true. Actually, an infinite number of n, lik any n that is a multiple of phi(d) where phi(d) is the euler totient function of d, satisfy that congruence.
The correct statement is “1/d has a cycle of n digits if n is the smallest positive integer satisfying 10^n – 1 mod d = 0, for d coprime to 10”. (So d cannot be 2 or 5, whose cycle lengths are 0, unless you admit the trailing 9 representation for nonrecurring decimals.) Proof can be found in Theorem 4.3 at http://www.math.uconn.edu/~kconrad/blurbs/ugradnumthy/eulerthm.pdf.
Note that n need not be exactly equal to phi(d). But n will always divide phi(d). For the prime 101, phi(101) = 100, but n = 4. Indeed, 1/101 = 0.00990099…
“It also follows that a prime number in the denominator, d, can yield up to d1 repeating decimal digits” – It cannot yield just any number from [1,d1]. The number it will yield will have to divide d – 1, if d is prime.
Great and thoughtful comment. Do you mind if I include it in the analysis?
Sure thing man! And keep up the good work here.
I was trying to check if my comments mattered at all to your algorithm, so I tried to imagine cases where the algo could break. One case could be if, for eg, you had two consecutive primes p1 > p2, p1 being the first prime below the upper bound, and 1/p1 and 1/p2 having d1 > d2 digits, resp., where d2 = p21 but d1 ~= p11. Then your algorithm would incorrectly skip 1/p1 and tag 1/p2 as the answer.
I’m not sure how realistic this case would be, because d1 has to divide evenly into p11. So say d1 is (p11)/2 i.e d1 is the most it can be without being p11. And I’ve assumed that 1/p2 has p21 digits, so p21 p1 > 2*p2 – 1. So we would have that p1 and p2 are consecutive primes with a gap bigger than p21. The gaps between primes certainly increase as we go higher up along the integers, but this is about as much as I can contrive as a counterexample for the algo. So for all I know, your algo works perfectly anyway.
for d≤2000: 1979, not(1997)
OK for the others
Again, you’re right. 1997 was the starting prime not the answer. Thanks!