(6 votes, average: 4.33 out of 5)

## Project Euler Problem 26 Solution

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

#### Analysis

This is a useful application of Fermat’s little theorem that says: 1/d has a cycle of n digits if 10n−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. We need to find the largest prime, p, under 1000 that has p-1 digits.

#### Solution

Runs < 1 second in Python.

```from Euler import is_prime   n = 997 #starting prime closest to limit for p in range(n, 1 ,-2): if not is_prime(p): continue c = 1 while (pow(10, c) - 1) % p != 0: c += 1 if (p-c) == 1: break   print "Answer to PE26 = ",p```

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

## Discussion

### 3 Responses to “Project Euler Problem 26 Solution”

1. for d≤2000: 1979, not(1997)
OK for the others

Posted by Francky | April 29, 2011, 1:52 PM
2. I want to execute the same program on C++. But, the program does not complete. I don’t know python that well. Can it be explained to me if the following code snippet is right in c++?

int p = 0;
int n = 997;
int c=0;
for ( p=n;p>1;p-2)
{
if(!IsPrime(p))
continue;

c=1;
while (((int)pow(10.0,c) – 1) % p != 0)
{
c += 1;
}
if (p-c==1)
break;

}

Help would be appreciated. Also, really nice approach to solve the problem. Thank you.

Posted by Sameer Shah | October 30, 2012, 2:44 PM