From the Perspective of Cyclic Groups

When the Denominator and 10 are Coprime

The process of division is actually the calculation of 10kmodn10^k \mod n, which is the remainder of the k-th division. When the remainder is 1, i.e., 10kmodn=110^k \mod n=1, it indicates a cycle. However, this may not be the first cycle, as the remainder might have appeared twice at another number, such as 2, hence the cycle would be shorter.

First, consider when 10 and n are coprime, forming a cyclic group {10kmodnkN}\{10^k \mod n | k \in \mathbb{N^*}\}, the order of the cyclic group is the smallest number that makes it remainder 1, and it must be a factor of φ(n)\varphi(n). Obviously, if φ(n)\varphi(n) is prime, then the order is φ(n)\varphi(n).

This is because the group is closed, the product of any two group elements is still an element of the group. If we consider all possible powers of akmodma^k \mod m, this set is also closed under modulo m multiplication. Then, if aa generates a cyclic group, the order of the group (the number of elements in the group) is the smallest positive integer kk, such that ak1(modm)a^k \equiv 1 \pmod{m}. This order kk must divide any xx for which ax1(modm)a^x \equiv 1 \pmod{m} holds, including ϕ(m)\phi(m).

Since aϕ(m)1(modm)a^{\phi(m)} \equiv 1 \pmod{m} always holds (according to Euler’s theorem), it means that the order of the group must be a factor of ϕ(m)\phi(m). Because if there exists some k<ϕ(m)k < \phi(m) such that ak1(modm)a^k \equiv 1 \pmod{m}, then ϕ(m)\phi(m) must be a multiple of kk to ensure the group’s cyclic nature and the definition of order.

In short, the cycle of powers completes at most once upon reaching ϕ(m)\phi(m), but the actual cycle may complete at an earlier point, thus the actual cycle length (the order of the group) is a factor of ϕ(m)\phi(m).

Calculating the order Besides directly starting from 1 and finding the smallest positive integer making 10kmodm=110^k \mod m=1, there are simplifications, especially when k is very large.
When m=pqm = pq, where pp and qq are different primes, and aa is coprime with both pp and qq.

Suppose the order of the multiplicative group of akmodpa^k \mod p is npn_p, and the order of the multiplicative group of akmodqa^k \mod q is nqn_q. According to Euler’s theorem, we know aϕ(p)1modpa^{\phi(p)} \equiv 1 \mod p and aϕ(q)1modqa^{\phi(q)} \equiv 1 \mod q, so npϕ(p)n_p | \phi(p) and nqϕ(q)n_q | \phi(q).

The order of the multiplicative group of akmodma^k \mod m, denoted as nmn_m, is the smallest positive integer nn such that an1modma^n \equiv 1 \mod m. Since m=pqm = pq, according to the Chinese Remainder Theorem, if we can simultaneously satisfy an1modpa^n \equiv 1 \mod p and an1modqa^n \equiv 1 \mod q, then an1modma^n \equiv 1 \mod m also holds.

To find nmn_m, we need to find the smallest nn such that an1modpa^n \equiv 1 \mod p and an1modqa^n \equiv 1 \mod q. This means nn must be a multiple of both npn_p and nqn_q. Therefore, nm=lcm(np,nq)n_m = \text{lcm}(n_p, n_q).

This leads to another question, how to quickly calculate the order of 10kmodpb10^k \mod p^b? We only know the order must be a factor of ϕ(pb)=pb1(p1)\phi(p^b)=p^{b-1}(p-1).

When the Denominator and 10 are Not Coprime

When 10 and n are not coprime, n’s factors include 2 or 5, let n=2a5bmn=2^a*5^b*m, m is coprime with 10, a,b are natural numbers and not all 0. In this case,

10kmod(2a5b)10^k \mod (2^a5^b)

When k is large enough, it must be 0. We only need to prove that multiplying a finite decimal by an infinite recurring decimal does not change the length of the recurring cycle. This needs proof, but I don’t know how.

That is, we don’t need to consider the factors of 2 or 5, just extract the factors that are coprime with 10. (I still don’t know how to prove this).


First, remove 2 and 5 completely, the value must be a combination structure like paqbp^aq^b (some exponents can be 0), at this time ϕ(pb)\phi(p^b) is less than pbp^b, then calculate the least common multiple, definitely less than paqb1p^a q^b-1. That is to say, for the prime p, its order is necessarily greater than the order of any number smaller than it. So just find the largest prime pmaxp_{max} within 1000, and compare it with the number that has been removed up to 1000 and is larger than pmaxp_{max}.

This involves the question, between two adjacent primes p, q, is it possible for a number divided by 2 to be larger than p? This is actually equivalent to whether there exists p<x<qp<x<q such that 2p<x<q2p<x<q. I don’t know, but it’s impossible within 1000.

So, between two adjacent primes p,q, is there x=p1a1p2a2pmamx=p_{1}^{a_1}p_{2}^{a_2}\cdots p_{m}^{a_m} not a multiple of 2 or 5, not a prime, but the order of 10^k mod x is larger than the order of 10^k mod p? That is,

gcd(φ(p1a1),,φ(pmam))\mathrm{gcd}\left( \varphi \left( p_{1}^{a_1} \right) ,\cdots ,\varphi \left( p_{m}^{a_m} \right) \right)

Could it be larger than p1p-1?

This number must be less than the product of these Euler’s functions

φ(x)=φ(p1a1)φ(pmam)\varphi \left( x \right) =\varphi \left( p_{1}^{a_1} \right) \cdots \varphi \left( p_{m}^{a_m} \right)

And φ(x)<x\varphi \left( x \right)<x. Moreover, except

for the prime number 2, p-1 is necessarily an even number, so there must be a common factor of 2, back to the previous question, at least within 1000 it is impossible. After dividing by 2, it must be smaller than pp.

Therefore, the number with the longest cycle must be a prime number. If it can be proved:

  1. Between two adjacent prime numbers p, q, any number divided by 2 is definitely smaller than p.
  2. Multiplying a finite decimal by an infinite recurring decimal does not change the length of the recurring cycle.

It seems that there are related theorems that can prove the second point, and also obtain the length of the non-recurring part.

Conventional Intuitive Approach

A recurring decimal must be infinite, and the digits in the recurring cycle may repeat. Based on coding experience, without reading to the last digit, it is impossible to know whether this string of digits is a recurring cycle. Therefore, a maximum possible recurring cycle length must be set.

Secondly, even if it is a recurring cycle, it may not be the shortest recurring cycle; it could be a multiple of the shortest recurring cycle. For example, the cycle of 001 also satisfies the cycle of 001001. So when a cycle is found, its factor length cannot be the cycle length.

The recurring part, choosing the length of the recurring cycle from anywhere, its period does not change. Like the 001 cycle, in fact, only looking at the latter part can also be considered as a 010 cycle.

So, as long as you skip enough decimal places, it will definitely be the recurring part, and the period remains the same. Just look for two segments that match up according to the period length.

-- Generates the decimal representation of 1/deno after the decimal point.
afterPoint :: Int -> [Int]
afterPoint = afterPoint' 1
afterPoint' num deno =
let (d, r) = (10 * num) `divMod` deno -- Multiplies numerator by 10, divides by denominator, and keeps remainder.
in d : afterPoint' r deno -- Recursively continues with remainder as new numerator.

-- Calculates the length of the recurring cycle in the decimal representation of 1/deno.
recurCycle :: Int -> Int
recurCycle deno = recurCycle' onlyCycle maxPossibleLen
maxSkip = myLog2 deno -- Determines the number of digits to skip based on log base 2 of denominator.
onlyCycle = drop maxSkip $ afterPoint deno -- Skips initial digits that don't participate in the cycle.
maxPossibleLen = deno - 1 -- The maximum possible cycle length is deno - 1.
recurCycle' xs len
| all (== 0) (take maxPossibleLen xs) = 0 -- If all digits are zero, cycle length is 0.
| whenLen len && not (any whenLen (factors len)) = len -- Checks if current length satisfies cycle conditions.
| otherwise = recurCycle' xs (len - 1) -- Otherwise, decreases length and tries again.
whenLen l = (l /= 0) && listEq (take l xs) (drop l xs) -- Checks if two subsequences of length l are equal.
myLog2 :: Int -> Int
myLog2 num = floor $ logBase 2 (fromIntegral num) -- Calculates the floor of log base 2 of a number.
listEq [] _ = True -- Base case for equality check: empty list is equal to any list.
listEq (x : xs) (y : ys) = (x == y) && listEq xs ys -- Recursive case: checks if heads are equal and proceeds to tails.

-- Generates the list of factors of a number by finding divisors up to the square root and their complements.
factors :: Int -> [Int]
factors num = let halfFactors = filter ((== 0) . mod num) [2 .. floor . sqrt $ fromIntegral num] in halfFactors ++ map (div num) (reverse halfFactors)

Considering the Length Characteristics of the Recurring Cycle

The recurring part of a recurring decimal is actually a number multiplied by a geometric series, which can be expressed as

0.(a1an)=a1ani=110in0.\left( a_1\cdots a_n \right) =a_1\cdots a_n\sum_{i=1}^{\infty}{10^{-in}}

According to the sum formula, we can get

0.(a1an)=a1an(10nlimi+10in)110n=a1an(1limi+10in)10n10.\left( a_1\cdots a_n \right) =\frac{a_1\cdots a_n\left( 10^{-n}-\lim_{i\rightarrow +\infty} 10^{-in} \right)}{1-10^{-n}} \\ =\frac{a_1\cdots a_n\left( 1-\lim_{i\rightarrow +\infty} 10^{-in} \right)}{10^n-1}

It’s observed that the length of the recurring cycle n is related to, or determined by, the denominator. As long as the denominator can be transformed into the form 10n110^n-1, it will definitely be a recurring decimal. That is to say, for the fraction a/ba/b, find a positive integer nn such that b10n1b|10^n-1, then this nn is the length of the recurring cycle.

The improved code to avoid integer overflow is as follows:

-- Improved version of recurCycle that utilizes an infinite list of numbers composed entirely of 9s to find the cycle length.
recurCycleImprove :: Integer -> Int
recurCycleImprove deno
| any ((== 0) . mod deno) [2, 5] = 0 -- Returns 0 immediately if deno is a multiple of 2 or 5.
| otherwise = maybe 0 (+ 1) (findIndex ((== 0) . (`mod` deno)) all9s) -- Finds the cycle length using an index in the all9s list.

-- Generates an infinite list of integers where each integer is composed entirely of 9s.
all9s :: [Integer]
all9s = map (\n -> 10 ^ n - 1) [1 :: Integer ..]