Project Euler 26 Problem Statement

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.

Solution

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

After much trial and error with brute force testing we found ourselves at this article Full Reptend Prime. 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 < 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. To illustrate why notice that 1/2 (0.5), 1/4 (0.25), 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 of d. 3 is not a reptend prime.

HackerRank version

HackerRank Project Euler 26 increases the limit to d < 10000 and runs 1000 test cases. Same solution solves all the test cases.

Python 2.7 Source

Last Word

A change from:

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

to

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

was a 400 times speed improvement.