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 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. It also follows that a prime number in the denominator, d, can yield up to d − 1 repeating decimal digits. We need to find the largest prime under 1000 that has d − 1 digits. This is called a full reptend prime.
Reference: The OnLine Encyclopedia of Integer Sequences (OEIS) A001913: Full reptend primes: primes with primitive root 10.Project Euler 26 Solution
Runs < 0.001 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: 99989A 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!