Decimal Recurring Cycles and Cyclic Groups

From the Perspective of Cyclic Groups

When the Denominator and 10 are Coprime

The process of division is actually the calculation of $10^k \mod n$, which is the remainder of the k-th division. When the remainder is 1, i.e., $10^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 $\{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 $\varphi(n)$. Obviously, if $\varphi(n)$ is prime, then the order is $\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 $a^k \mod m$, this set is also closed under modulo m multiplication. Then, if $a$ generates a cyclic group, the order of the group (the number of elements in the group) is the smallest positive integer $k$, such that $a^k \equiv 1 \pmod{m}$. This order $k$ must divide any $x$ for which $a^x \equiv 1 \pmod{m}$ holds, including $\phi(m)$.

Since $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 $\phi(m)$. Because if there exists some $k < \phi(m)$ such that $a^k \equiv 1 \pmod{m}$, then $\phi(m)$ must be a multiple of $k$ to ensure the group’s cyclic nature and the definition of order.

In short, the cycle of powers completes at most once upon reaching $\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 $\phi(m)$.

Calculating the order Besides directly starting from 1 and finding the smallest positive integer making $10^k \mod m=1$, there are simplifications, especially when k is very large.
When $m = pq$, where $p$ and $q$ are different primes, and $a$ is coprime with both $p$ and $q$.

Suppose the order of the multiplicative group of $a^k \mod p$ is $n_p$, and the order of the multiplicative group of $a^k \mod q$ is $n_q$. According to Euler’s theorem, we know $a^{\phi(p)} \equiv 1 \mod p$ and $a^{\phi(q)} \equiv 1 \mod q$, so $n_p | \phi(p)$ and $n_q | \phi(q)$.

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

To find $n_m$, we need to find the smallest $n$ such that $a^n \equiv 1 \mod p$ and $a^n \equiv 1 \mod q$. This means $n$ must be a multiple of both $n_p$ and $n_q$. Therefore, $n_m = \text{lcm}(n_p, n_q)$.

This leads to another question, how to quickly calculate the order of $10^k \mod p^b$? We only know the order must be a factor of $\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=2^a*5^b*m$, m is coprime with 10, a,b are natural numbers and not all 0. In this case,

$$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).

Algorithm

First, remove 2 and 5 completely, the value must be a combination structure like $p^aq^b$ (some exponents can be 0), at this time $\phi(p^b)$ is less than $p^b$, then calculate the least common multiple, definitely less than $p^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 $p_{max}$ within 1000, and compare it with the number that has been removed up to 1000 and is larger than $p_{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<q$ such that $2p<x<q$. I don’t know, but it’s impossible within 1000.

So, between two adjacent primes p,q, is there $x=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,

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

Could it be larger than $p-1$?

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

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

And $\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 $p$.

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
  where
    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
  where
    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.
      where
        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.\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.\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 $10^n-1$, it will definitely be a recurring decimal. That is to say, for the fraction $a/b$, find a positive integer $n$ such that $b|10^n-1$, then this $n$ 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 ..]