// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (21 votes, average: 4.81 out of 5)
Loading...

Project Euler Solutions

Project Euler 26 Solution

Project Euler 26 Solution

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:

1/2 0.5
1/3 0.(3)
1/4 0.25
1/5 0.2
1/6 0.1(6)
1/7 0.(142857)
1/8 0.125
1/9 0.(1)
1/10 0.1

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.

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 10n − 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 97-1 = 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 On-Line 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
This program and method
solves all test cases for
Project Euler 26 on HackerRank

Project Euler 26 Solution

Runs < 0.006 seconds in Python 2.7.
download arrowUse 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.
|983|

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: 999983

  • A change from:

while (pow(10, c) - 1) % p != 0:

to

while pow(10, c, p) != 1:

was a 400 times speed improvement.

Project Euler 26 Solution last updated

Discussion

6 Responses to “Project Euler 26 Solution”

  1. 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 …

    Posted by kmonsoor | January 14, 2014, 4:12 AM
    • 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 co-prime to 10”. (So d cannot be 2 or 5, whose cycle lengths are 0, unless you admit the trailing 9 representation for non-recurring 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 d-1 repeating decimal digits” – It cannot yield just any number from [1,d-1]. The number it will yield will have to divide d – 1, if d is prime.

      Posted by VPATEL | January 21, 2014, 7:13 PM
      • Great and thoughtful comment. Do you mind if I include it in the analysis?

        Posted by Mike | January 21, 2014, 11:18 PM
      • 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 = p2-1 but d1 ~= p1-1. 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 p1-1. So say d1 is (p1-1)/2 i.e d1 is the most it can be without being p1-1. And I’ve assumed that 1/p2 has p2-1 digits, so p2-1 p1 > 2*p2 – 1. So we would have that p1 and p2 are consecutive primes with a gap bigger than p2-1. 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.

        Posted by VPATEL | January 29, 2014, 11:57 AM
  2. for d≤2000: 1979, not(1997)
    OK for the others

    Posted by Francky | April 29, 2011, 1:52 PM

Post a comment