Select Page

#### 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.

#### 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.