Problem 26 - Reciprocal Cycles

Problem

This problem comes from Project Euler 26

Problem

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 20 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. In 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 solution involved a bit of research, but here are three Wikipedia pages that I found helpful: Full Reptend Primes, Multiplicative Order, and Cyclic Number.

Here are the important bits from those pages:

From Full Reptend Primes:

In number theory, a full reptend prime … in base $b$ is an odd prime number $p$ such that the Fermat Quotient

$q_p(b) = \dfrac{b^{p-1} -1}{p}$

gives a cyclic number.

…

The cyclic number corresponding to prime $p$ will possess $p -1$ digits if and only if $p$ is a full reptend prime. That is, the multiplicative order $\text{ord}_p(b) = p - 1$

From Multiplicative Order:

In number theory, given a positive integer $n$ and an integer $a$ coprime to $n$, the multiplicative order of a modulo $n$ is the smallest positive integer $k$ such that $a^k \equiv 1 (\text{mod } n)$ .

…

The order of a modulo $n$ is sometimes written as $\text{ord}_n(a)$

We can see from the Full Reptend Primes quote that we can generate cyclic numbers that will have $p - 1$ digits if and only if $p$ is a full reptend prime.

For example, if the prime number 17 is a full reptend prime (which it is), then it will create a cyclic number with 16 repeating digits!

We check if a prime number is a full reptend prime by checking its multiplicative order. Combining some of the equations and information we have, we get

Or more simply

Note that

• Our base $b$ is 10 and,
• that $k$ is some integer, whose range we’ll set between 1 and $p$

From the Full Reptend Primes quote, if $k = p-1$, then the prime is full reptend and therefore cyclic.

Code

# Project Euler: Problem 26
# Reciprocal cycles

from PEF import soe

def full_reptend_check(p) -> bool:
    for k in range(1, p):
        if (10**k) % p == 1:
            if k == p-1:
                return True
            else:
                return False

primes = soe(1000)
for p in reversed(primes):
    if(full_reptend_check(p)):
        print(p)
        break

The program carries out what was discussed in the Solution. The function full_reptend_check() finds if a prime is a full reptend prime and returns True if it is.

One thing of note is that I check for full reptend primes in reverse, starting from the largest prime. The reason is pretty simple: If a prime is full reptend, then the cyclic number is $p-1$ digits long, so it’s faster to check starting from the largest number.