Project Euler Problem 26 Solution

Project Euler & HackerRank Problem 26 Solution

Reciprocal cycles
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 26 Statement

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/20.5
1/30.(3)
1/40.25
1/50.2
1/60.1(6)
1/70.(142857)
1/80.125
1/90.(1)
1/100.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.

Solution

This problem and the HackerRank version are looking for d < N, NOT d ≤ N. This specific problem has N fixed at 1000.

After some trial and error with brute force testing and exceeding an acceptable time limit, we found ourselves at this article Full Reptend Prime on Wolfram Mathword. It explains that a full reptend prime is a prime p for which 1/p will have the longest recurring cycle of p−1 digits. It further explains a prime p is full reptend if

10k ≡ 1 (mod p)

for k = p−1 and no other k less than this. Here are some examples to help illustrate this concept:

(101, 102, 103, 104, 105, 106) ≡ (3, 2, 6, 4, 5, 1) (mod 7)

7 is a full reptend prime because 1 occurs only at the last position

(101, 102, 103, …, 1010) ≡ (10, 1, 10, 1, 10, 1, 10, 1, 10, 1) (mod 11)
(101, 102, 103, …, 1012) ≡ (10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1) (mod 13)

11 and 13 are NOT full reptend primes because 1 occurs before the last positions.

Summary

So, this problem can answered by finding the first full reptend prime number below a limit. As an example, for d < 100 the first reptend prime less than 100 is 97. Therefore, 1/97 will produce the longest recurring cycle in its decimal fraction part (96 digits) for all unit fractions with denominators less than 100.

For N < 7 edge cases

The algorithm works for all N greater than or equal to 7. When the N is less than 7 we return 3 because that is the smallest denominator that repeats with the longest recurring cycle. To understand why, let’s look at all denominators less than 7: Notice that 1/2 (0.5), 1/4 (0.25), and 1/5 (0.2) never repeat; their cycle is 0. 1/3 (0.(3)), 1/6 (0.1(6)) both repeat with a cycle of 1 of which 3 is the smallest value denominator.

HackerRank version

HackerRank Project Euler 26 increases the limit to d < 10,000 and runs 1,000 test cases. For those instances when there is more than one denominator with the same cycle, report the smallest denominator. This condition only happens with N < 7. Same solution solves all the test cases.

Python Source Code

Last Word

Reference: The On–Line Encyclopedia of Integer Sequences (OEIS) A001913: Full reptend primes: primes with primitive root 10.

for d < 2000: 1979
for d < 2500: 2473
for d < 10,000: 9967
for d < 25,000: 24989
for d < 100,000: 99989, 0.17 sec.
for d < 1,000,000: 999983, 1.74 sec
for d < 2,000,000: 1999979, 4.7 sec

A change from:

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

to

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

was a 400 times speed improvement.