Project Euler Problem 26 Solution

Project Euler Problem 26 Solution & HackerRank version

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.16)
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 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 < 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 the fractions 1/2 (0.5), 1/4 (0.25), and 1/5 (0.2) never repeat; their cycle is zero. 1/3 (0.3) and 1/6 (0.16) both repeat with a cycle of 1 of which 1/3 has the smallest 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.

Python Source Code

  1. def prime_sieve(n):
  2. sieve = [True] * (n//2)
  3. for i in range(3,int(n**0.5)+1,2):
  4. if sieve[i//2]:
  5. sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
  6. return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
  7. def f(N):
  8. if N <= 7: return 3
  9. for d in prime_sieve(N)[::-1]:
  10. k = d//2
  11. while pow(10, k, d) != 1: k+= 1
  12. if d-1 == k: return d
  13. N = int(input('The longest recurring cycle for 1/d where d < '))
  14. d = f(N)
  15. print ("The longest repeating decimal for d < %d is 1/%d with %d repeating digits" % (N, d, (1 if N<8 else d-1)))
download Project Euler 26 Python source code Use this link to download the Project Euler 26: Reciprocal cycles Python source.

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.