Project Euler Problem 26 Solution: Reciprocal cycles

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:

$Table of fractions$

Where 0.1(6) means 0.166666…, and has a 1–digit recurring cycle. It can be seen that ¹/₇ has a 6–digit recurring cycle.

Find the value of d < 1000 for which ¹/_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

10^k ≡ 1 (mod p), for k=p−1 and no other k less than this.

Here are some examples to help illustrate this concept with p=7:

(10¹, 10², 10³, 10⁴, 10⁵, 10⁶) ≡ (3, 2, 6, 4, 5, 1) (mod 7)

7 is a full reptend prime because 1 occurs only at the last position. Here are two counter examples with p=11 and p=13:

(10¹, 10², 10³, …, 10¹⁰) ≡ (10, 1, 10, 1, 10, 1, 10, 1, 10, 1) (mod 11)
(10¹, 10², 10³, …, 10¹²) ≡ (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 is solved 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, for all unit fractions with a denominator less than 100, 1/97 will produce the longest recurring cycle in its decimal fraction part (96 digits).

For $N$ < 8 edge cases

The algorithm is designed to work for all $N\ge 8$. For values of $N$ less than 8, we return 3 because it is the smallest denominator that produces a repeating decimal with the longest recurring cycle. Here's why:

Fractions like $\frac{1}{2}$ (0.5), $\frac{1}{4}$ (0.25), and $\frac{1}{5}$ (0.2) do not produce repeating decimals; their recurring cycle length is zero.

Fractions $\frac{1}{3} (0.\overline{3}$) and $\frac{1}{6} (0.1\overline{6}$) produce repeating decimals with a cycle length of $1$. Among these, $\frac{1}{3}$ has the smallest denominator.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 26

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.

Python Source Code

import Euler

def find_reptend_prime(N):
    if N < 8:
        return 3
    for d in reversed(Euler.prime_sieve(N)):
        k = d // 2
        while pow(10, k, d) != 1: k+= 1
        if d - 1 == k:
            return d

print(*(find_reptend_prime(int(input())) for _ in range(int(input()))), sep="\n")

Last Word

The prime_sieve function will be imported instead of hard coded into the source code. This provides flexibility to include different sieves as required to solve a problem.

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

Look at the repl.it for the prime_sieve function.

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.