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 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
This is a useful application of Fermat’s little theorem that says: 1/d has a cycle of n digits if 10n − 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 On-Line Encyclopedia of Integer Sequences (OEIS) A001913: Full reptend primes: primes with primitive root 10.
Project Euler 26 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 26 Solution Python 2.7 source.
AnswerSlowly 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.
- 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
A change from:
while (pow(10, c) - 1) % p != 0:
while pow(10, c, p) != 1:
was a 400 times speed improvement