<!--
.. title: a time to repeat
.. slug: a-time-to-repeat
.. date: 2025-09-30 22:25 UTC-05:00
.. tags: math, primes, arithmetic
.. category: nerdery
.. description: In which I wonder about decimal representations.
.. type: text
.. previewimage: expansions.svg
.. has_math: true
-->

Consider the following decimal expansions:

$$\begin{aligned}
\textstyle \frac{1}{ 1 } &= 1.0 &
\textstyle \frac{1}{ 11 } &= 0.[09] &
                                            % 0.09090909090909091 \\\\
\textstyle \frac{1}{ 21 } &= 0.[04761\,9] \\\\
                                            % 0.047619047619047616 \\\\
%
\textstyle \frac{1}{ 2 } &= 0.5 &
\textstyle \frac{1}{ 12 } &= 0.08[3] &
                                            % 0.08333333333333333 \\\\
\textstyle \frac{1}{ 22 } &= 0.0[45] \\\\
                                            % 0.045454545454545456 \\\\
%
\textstyle \frac{1}{ 3 } &= 0.[3] &
                                            % 0.3333333333333333 \\\\
\textstyle \frac{1}{ 13 } &= 0.[07692\,3] &
                                            % 0.07692307692307693 \\\\
\textstyle \frac{1}{ 23 } &= 0.[04347\,82608\,69565\,21739\,13] \\\\
                                            % 0.043478260869565216 \\\\
%
\textstyle \frac{1}{ 4 } &= 0.25 &
\textstyle \frac{1}{ 14 } &= 0.0[71428\,5] &
                                            % 0.07142857142857142 \\\\
\textstyle \frac{1}{ 24 } &= 0.041[6] \\\\
                                            % 0.041666666666666664 \\\\
%
\textstyle \frac{1}{ 5 } &= 0.2 &
\textstyle \frac{1}{ 15 } &= 0.0[6] &
                                            % 0.06666666666666667 \\\\
\textstyle \frac{1}{ 25 } &= 0.04 \\\\
%
\textstyle \frac{1}{ 6 } &= 0.1[6] &
                                            % 0.16666666666666666 \\\\
\textstyle \frac{1}{ 16 } &= 0.0625 &
\textstyle \frac{1}{ 26 } &= 0.0[38461\,5] \\\\
                                            % 0.038461538461538464 \\\\
%
\textstyle \frac{1}{ 7 } &= 0.[14285\,7] &
                                            % 0.14285714285714285 \\\\
\textstyle \frac{1}{ 17 } &= 0.[05882\,35294\,11764\,7] &
                                            % 0.058823529411764705 \\\\
\textstyle \frac{1}{ 27 } &= 0.[037] \\\\
                                            % 0.037037037037037035 \\\\
%
\textstyle \frac{1}{ 8 } &= 0.125 &
\textstyle \frac{1}{ 18 } &= 0.0[5] &
                                            % 0.05555555555555555 \\\\
\textstyle \frac{1}{ 28 } &= 0.035[71428\,5] \\\\
                                            % 0.03571428571428571 \\\\
%
\textstyle \frac{1}{ 9 } &= 0.[1] &
                                            % 0.1111111111111111 \\\\
\textstyle \frac{1}{ 19 } &= 0.[05263\,15789\,47368\,421] &
                                            % 0.05263157894736842 \\\\
\textstyle \frac{1}{ 29 } &= 0.[03448\,27586\,20689\,65517\,24137\,931] \\\\
                                            % 0.034482758620689655 \\\\
%
\textstyle \frac{1}{ 10 } &= 0.1 &
\textstyle \frac{1}{ 20 } &= 0.05 &
\textstyle \frac{1}{ 30 } &= 0.0[3] \\\\
                                            % 0.03333333333333333 \\\\
\end{aligned}$$

Each of these either terminates, like $\frac18 = 0.125$, or repeats,
like $\frac{1}{27} = 0.[037]$.  What determines the length of these
repeating sequences?

<!-- TEASER_END -->

# Rational numbers *must* terminate or repeat

Decimal expansions are produced by long division, which is a process
of repeatedly taking quotients and remainders.  An example:

```
    __0.037⋯
 27 ) 1.000
      - 81
        190
        189
          1
```

Here we have

  * Twenty-seven goes into one zero times, with remainder one.
  * Multiply the remainder by ten.
    Twenty-seven goes into ten zero times, with remainder ten.
  * Multiply the remainder by ten.
    Twenty-seven goes into one hundred three times, with remainder nineteen.
  * Multiply the remainder by ten.
    There are seven twenty-sevens in one hundred ninety, with remainder
    one.
  * Multiply the remainder by ten.
    We've already asked whether twenty-seven goes into ten,
    so we've entered a loop.

An integer $b$ can in principle have $b-1$ different nonzero
remainders, so $a/b$ can have *at most* $b-1$ repeating digits in its
decimal representation.  In the table above, we see that $1/7$, $1/17$,
$1/19$, $1/23$, and $1/29$ have this "maximum-length" representation.
But other representations, such as $1/11$ and $1/27$, are substantially shorter.

Of course, if we ever hit a remainder of zero, then the decimal
expansion terminates.

## Terminating decimals must have denominators $2^j 5^k$

If a rational number $a/b$ has a decimal representation which
terminates, then we can say

$$ \frac ab = \frac c {10^n} $$

for integers $a,b,c$.  There must exist some integer $d$
so that $ad = c$ and $bd = 10^n$.  Because the product $bd$ is a
factor of ten, the integers $b$ and $d$ can have only two and five as
prime factors.

## Immediately-repeating decimals can be written with an "all nines" denominator

Let's limit ourselves to repeating decimals which start
immediately at the decimal point, like $1/7$.  These can be written as

$$\begin{aligned}
\frac ab &= \frac{c}{10^n} + \frac{c}{10^{2n}} + \frac{c}{10^{3n}} + \cdots
\end{aligned}$$

for integers $a,b,c$, where the $n$ repeating digits are the digits of $c$.
We can rewrite as a geometric series,

$$\begin{aligned}
\frac ab &= c\times\left(
    \frac{1}{10^n} + \frac{1}{10^{2n}} + \frac{1}{10^{3n}} + \cdots \right)
\\\\ &= c\sum_{i=1}^{\infty}\left(\frac{1}{10^n}\right)^i
 = \frac{c}{10^n - 1}
\end{aligned}$$

This suggests, for instance, that $142\,857 \times 7 = 999\,999$,
because $142\,857$ are the digits in the decimal expansion of $1/7$.
You can even imagine using this as a way to factorize numbers of the
"all-nines" form $10^n-1$, by asking what numbers have decimal
expansions of length $n$.

## Non-immediately-repeating decimals are annoying

Expansions like $\frac{1}{15} = 0.0[6]$, which eventually repeat but
have some cruft at the front, are annoying.

I think these always have a factor of two or five in the denominator,
and that fractions without any factors of two or five in the
denominator always have representations that repeat immediately.
I haven't tried to prove this.  <!-- FIXME -->

You *can* always make the repeat start
at the decimal point by multiplying by enough powers of ten.
If there are $\ell$ leading digits that don't repeat,
and then the repeating pattern has period $p$,
then we can write our number as

$$\begin{aligned}
\frac ab &= \frac c {10^\ell} + \frac{1}{10^\ell}\cdot\frac{d}{10^p - 1}
\end{aligned}$$

for integers $a,b,c,d$.
Then

$$\begin{aligned}
\frac ab \times 10^\ell &= c + \frac{d}{10^p-1} = \frac ef
\end{aligned}$$

starts repeating at the decimal point.  Note that no all-nines number
$10^p-1$ is ever divisible by any factor of two or five, so the new
denominator $f$ doesn't have two or five as a factor.

Is that a proof?  It doesn't feel like one.

# Repeating digit patterns do cyclic group-y things

Consider now the fractions with denominator seven:

$$\begin{aligned}
\textstyle \frac{ 1 }{ 7 } &= { 142\,857 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 2 }{ 7 } &= { 285\,714 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 3 }{ 7 } &= { 428\,571 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 4 }{ 7 } &= { 571\,428 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 5 }{ 7 } &= { 714\,285 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 6 }{ 7 } &= { 857\,142 } / \textcolor{lightgray}{ 999\,999 } \\\\
\end{aligned}$$

Our list of digits $142\,857$ has the maximum allowed length, which
means we must reach it in *every* fraction with denominator seven.
For the fractions with denominator thirteen, there are *two* digit lists of
length six:

$$\begin{aligned}
\textstyle \frac{  1 }{ 13 } &= \textcolor{red}{ \ 76\,923 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  2 }{ 13 } &= \textcolor{blue}{ 153\,846 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  3 }{ 13 } &= \textcolor{red}{  230\,769 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  4 }{ 13 } &= \textcolor{red}{  307\,692 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  5 }{ 13 } &= \textcolor{blue}{ 384\,615 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  6 }{ 13 } &= \textcolor{blue}{ 461\,538 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  7 }{ 13 } &= \textcolor{blue}{ 538\,461 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  8 }{ 13 } &= \textcolor{blue}{ 615\,384 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{  9 }{ 13 } &= \textcolor{red}{  692\,307 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 10 }{ 13 } &= \textcolor{red}{  769\,230 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 11 }{ 13 } &= \textcolor{blue}{ 846\,153 } / \textcolor{lightgray}{ 999\,999 } \\\\
\textstyle \frac{ 12 }{ 13 } &= \textcolor{red}{  923\,076 } / \textcolor{lightgray}{ 999\,999 } \\\\
\end{aligned}$$

With denominator eleven, the ten repeating numerators are given by five distinct
digit lists with length two:

$$\begin{aligned}
\textstyle \frac{ 1 }{11} &= 0.[09] &
\textstyle \frac{ 2 }{11} &= 0.[18] &
\textstyle \frac{ 3 }{11} &= 0.[27] &
\textstyle \frac{ 4 }{11} &= 0.[36] &
\textstyle \frac{ 5 }{11} &= 0.[45] \\\\
\textstyle \frac{ 10}{11} &= 0.[90] &
\textstyle \frac{ 9 }{11} &= 0.[81] &
\textstyle \frac{ 8 }{11} &= 0.[72] &
\textstyle \frac{ 7 }{11} &= 0.[63] &
\textstyle \frac{ 6 }{11} &= 0.[54] \\\\
\end{aligned}$$

The fractions with denominator twenty-one are interesting.  There are
twenty numerators, repeating with length six.  Eight of those numerators
we have seen already: the six with form $3n/21$, and the two with
form $7n/21$.  The remaining twelve are divided into two groups with
length six:

$$\begin{aligned}
\textstyle \frac{  1 }{ 21 } &= 0.[\textcolor{red}{ 047619 }] \\\\
\textstyle \frac{  2 }{ 21 } &= 0.[\textcolor{blue}{ 095238 }] \\\\
\textstyle \frac17 = \frac{  3 }{ 21 } &= 0.[\textcolor{green}{ 142857 }] \\\\
\textstyle \frac{  4 }{ 21 } &= 0.[\textcolor{red}{ 190476 }] \\\\
\textstyle \frac{  5 }{ 21 } &= 0.[\textcolor{blue}{ 238095 }] \\\\
\textstyle \frac27 = \frac{  6 }{ 21 } &= 0.[\textcolor{green}{ 285714 }] \\\\
\textstyle 1/3 = \frac{  7 }{ 21 } &= 0.[\textcolor{lightblue}{ 333333 }] \\\\
\textstyle \frac{  8 }{ 21 } &= 0.[\textcolor{blue}{ 380952 }] \\\\
\textstyle \frac37 = \frac{  9 }{ 21 } &= 0.[\textcolor{green}{ 428571 }] \\\\
\textstyle \frac{ 10 }{ 21 } &= 0.[\textcolor{red}{ 476190 }] \\\\
\textstyle \frac{ 11 }{ 21 } &= 0.[\textcolor{blue}{ 523809 }] \\\\
\textstyle \frac47 = \frac{ 12 }{ 21 } &= 0.[\textcolor{green}{ 571428 }] \\\\
\textstyle \frac{ 13 }{ 21 } &= 0.[\textcolor{red}{ 619047 }] \\\\
\textstyle 2/3 = \frac{ 14 }{ 21 } &= 0.[\textcolor{lightblue}{ 666666 }] \\\\
\textstyle \frac57 = \frac{ 15 }{ 21 } &= 0.[\textcolor{green}{ 714285 }] \\\\
\textstyle \frac{ 16 }{ 21 } &= 0.[\textcolor{red}{ 761904 }] \\\\
\textstyle \frac{ 17 }{ 21 } &= 0.[\textcolor{blue}{ 809523 }] \\\\
\textstyle \frac67 = \frac{ 18 }{ 21 } &= 0.[\textcolor{green}{ 857142 }] \\\\
\textstyle \frac{ 19 }{ 21 } &= 0.[\textcolor{red}{ 904761 }] \\\\
\textstyle \frac{ 20 }{ 21 } &= 0.[\textcolor{blue}{ 952380 }] \\\\
\textstyle \frac{ 21 }{ 21 } &= 0.[\textcolor{lightgray}{ 999999 }] \\\\
\end{aligned}$$

It's cute how these have to all fit together, without any leftovers.
The prime-checking for the all-nines denominators has the smell of
[Fermat's Little Theorem](https://en.wikipedia.org/wiki/Fermat's_little_theorem)
about it.
Why do expansions with period three and five not show up until after a
bunch of expansions with period six?

And how do these things act when you look at "decimal" expansions in
other bases?  We can measure these periods without actually doing
expansions:

```python
base = 10
for p in range(0,100):
    for n in range(1,p):
        q,r = divmod(base**n-1,p)
        if r == 0:
            print(f'in base {base}, 1/{p} has period {n}');
            break
```

There are also some funny things happening with powers.
In decimal, $1/27$ has period three, and $1/81$ has period nine.
One way to think of that would be that each new power of three in the
denominator triples the length of the sequence?  It's likewise the
case that $1/49$ has period $6\times 7 = 42$.  But I'm kind of horsing
around with that stuff.