Problem Description

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 ¹/₇ 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.

Analysis

This is a useful application of Fermat’s little theorem that says: 1/d has a cycle of n digits if 10ⁿ−1 mod d = 0 for prime d. It also follows that a prime number in the denominator, d, can yield up to d-1 repeating decimal digits.

Since the problem wants the longest string of repeating digits from 1 < d < 1000 we started at the top and worked down calculating the length of the chain until we found one with d − 1 digits.

Calculating a cycle length:
d=7 ; c=1
9 % 7 = 2 ; c=2
99 % 7 = 1; c=3
999 % 7 = 5; c=4
9999 % 7 = 3; c=5
99999 % 7 = 4; c=6
999999 % 7 = 0; break

Solution

Runs < 1 second in Python.

from Euler import is_prime
 
for d in range(999, 1, -2):
  if not is_prime(d): continue
  c = 1
  while (pow(10, c) - 1) % d != 0:
    c += 1
  if (d-c) == 1: break
print "Answer to PE26 = ",d

Comments

More information on the Euler module can be found on the tools page.
for d < 2000: 1997
for d < 2500: 2473
for d < 10,000: 9967
for d < 20,000: 19993
for d < 25,000: 24989