%\documentclass[12pt]{amsart}
\documentclass[12pt]{article}
\parindent=0pt \parskip=8pt

\usepackage{verbatim}
\usepackage{fullpage}

\usepackage{amssymb,amsmath,amsthm}
\usepackage[mathscr]{eucal}

\usepackage{makeidx}
\input{../tex/isomath}
\input{../tex/mathenv}

%\makeindex

\usepackage{hyperref}
\usepackage{ifpdf}

\ifpdf
\pdfinfo{
/Author (John Kerl)
/Title  (142857, and more numbers like it)
}
\fi

%--------------------------------------------------------------------
\begin{document}
\title{142857, and more numbers like it}
\author{John Kerl}
\maketitle

\begin{abstract}
These are brief jottings to myself on vacation-spare-time observations about
transposable numbers.  Namely, $1/7$ in base 10 is $0.\overline{142857}$, $2/7$
is $0.\overline{285714}$, $3/7$ is $0.\overline{428571}$, and so on.  That's
neat --- can we find more such?  What happens when we use denominators other
than 7, or bases other than 10?

The results presented here are generally ancient and not essentially original
in their particulars.  The current exposition takes a particular narrative and
data-driven approach; also, elementary group-theoretic proofs preferred when
possible.

As much I'd like to keep the presentation here as elementary as possible, it
makes the presentation far shorter to assume some
first-few-weeks-of-the-semester group theory Since my purpose here is to
quickly jot down some observations, I won't develop those concepts in this
note.  This saves many pages, at the cost of some accessibility, and with
accompanying unevenness of tone.
\end{abstract}

\tableofcontents

%% ================================================================
\newpage
\section{The number 142857, and some notation}
\label{sec:142857}

Decimal expansions of sevenths are particularly appealing.  As soon as we learn
to do long division we can find:

\begin{center}
\begin{tabular}{ccc}
1/7 & = & $0.\overline{142857}$ \\
2/7 & = & $0.\overline{285714}$ \\
3/7 & = & $0.\overline{428571}$ \\
4/7 & = & $0.\overline{571428}$ \\
5/7 & = & $0.\overline{714285}$ \\
6/7 & = & $0.\overline{857142}$ \\
\end{tabular}
\end{center}

The repeating part, 142857, shows up cyclically shifted.  (See also the
Wikipedia articles on \emph{142857}, \emph{Cyclic number}, and
\emph{Transposable integer}.)  If we instead start with $142857$, then
cyclically left-shift by a digit to get $428571$, and so on, we get

\begin{center}
\begin{tabular}{ccc}
1/7 & = & $0.\overline{142857}$ \\
3/7 & = & $0.\overline{428571}$ \\
2/7 & = & $0.\overline{285714}$ \\
6/7 & = & $0.\overline{857142}$ \\
4/7 & = & $0.\overline{571428}$ \\
5/7 & = & $0.\overline{714285}$ \\
\end{tabular}
\end{center}

Is this ordering $1,3,2,6,4,5$ of the numerators random, or is there some sense
to it?

Seeking around for other fractions like this, we find numbers such as 1/13 and
its multiples:

\begin{center}
\begin{tabular}{|ccc|ccc|}
\hline \multicolumn{3}{|c|}{Written in add-order} & \multicolumn{3}{|c|}{Written in shift-order} \\
\hline
 $1/13$ &=& $0.\overline{076923}$  &   $1/13$ &=& $0.\overline{076923}$  \\
 $2/13$ &=& $0.\overline{153846}$  &  $10/13$ &=& $0.\overline{769230}$  \\
 $3/13$ &=& $0.\overline{230769}$  &   $9/13$ &=& $0.\overline{692307}$  \\
 $4/13$ &=& $0.\overline{307692}$  &  $12/13$ &=& $0.\overline{923076}$  \\
 $5/13$ &=& $0.\overline{384615}$  &   $3/13$ &=& $0.\overline{230769}$  \\
 $6/13$ &=& $0.\overline{461538}$  &   $4/13$ &=& $0.\overline{307692}$  \\
 $7/13$ &=& $0.\overline{538461}$  &        & &          \\
 $8/13$ &=& $0.\overline{615384}$  &   $2/13$ &=& $0.\overline{153846}$  \\
 $9/13$ &=& $0.\overline{692307}$  &   $7/13$ &=& $0.\overline{538461}$  \\
$10/13$ &=& $0.\overline{769230}$  &   $5/13$ &=& $0.\overline{384615}$  \\
$11/13$ &=& $0.\overline{846153}$  &  $11/13$ &=& $0.\overline{846153}$  \\
$12/13$ &=& $0.\overline{923076}$  &   $6/13$ &=& $0.\overline{461538}$  \\
        & &                        &   $8/13$ &=& $0.\overline{615384}$  \\
\hline
\end{tabular}
\end{center}

Here, we have not the one number 142857, but the two numbers 076923 and 153846.
Why two, instead of, say, a single 12-digit number?  (See also section
\ref{sec:rep_frac_data} for more data.)

In order to ask and address these questions and others like them, I use the
following terminology and notation:

\begin{itemize}

\item Generalizing from $1/7$, \ldots, $6/7$ in base 10, I refer to
\textbf{numerator} $k$, \textbf{denominator} $n$, and \textbf{base} $b$.

\item For $b<10$,  I use the \textbf{base-$b$ digits} $0, 1, 2, \ldots, b-1$:
e.g. 0, 1, 2, 3, 4, 5, 6 for base 7.  For $b>10$,  as is standard,  I use
include a, b, c, \ldots for 10, 11, 12, \ldots.  E.g. 0, 1, 2, 3, 4, 5, 6, 7,
8, 9, a, b, c, d, e, f for base 16.

\item I only consider $k$'s between $0$ and $n$, and \textbf{relatively prime}
(which means the same as \textbf{coprime}) to $n$.  (E.g. I'll only look at
$1/9$, $2/9$, $4/9$, $5/9$, $7/9$, $8/9$.)  This is because $k$'s non-coprime
to $k$ represent simpler fractions (e.g. $3/9=1/3$), and because I find
empirically that these simplifiable fractions don't share the same digit sets
as the non-simplifiable ones.  (For example, $1/9$, $2/9$, $4/9$, $5/9$, $7/9$,
$8/9$ in base 16 are $0.\overline{1c7}$, $0.\overline{38e}$,
$0.\overline{71c}$, $0.\overline{8e3}$, $0.\overline{c71}$, $0.\overline{e38}$,
whereas $3/9$ and $6/9$ are $0.\overline{5}$ end $0.\overline{a}$
respectively.)

\item The number of repeating digits in the expansion of $k/n$ is called the
\textbf{period}.  It depends on $n$ and $b$, so I write $p=p(n,b)$.  It needs to
be shown that this doesn't depend on $k$, that is, for all $k$'s coprime to $n$,
the period is the same.

\item It turns out that the longest possible period for the $k/n$, in any base
$b$, is $\phi(n)$ where $\phi(n)$ is the \emph{Euler totient function} of $n$.
That is, $\phi(n)$ is the number of $k$'s between 0 and $n$ that are coprime
with $n$.  (E.g.  $\phi(7)=6$ since $1,2,3,4,5,6$ are coprime to 7; $\phi(9)$
is also $6$ since $1,2,4,5,7,8$ are coprime to 9.)  When $k/n$'s have period
$\phi(n)$ in base $b$, I say they have \textbf{full period}.

\end{itemize}

%% ================================================================
\section{Questions}

Having set the stage, I can now pose several questions.

%% ----------------------------------------------------------------
\subsection{Are certain constructions possible?}
\label{sec:ques_spec}

Here's the original question I recently posed to myself.  It seems interesting
that the digits $1,2,4,5,7,8$ in the base-10 expansion of $k/7$ are precisely
the six numbers between 0 and 9 which are relatively prime to 9.  In
hexadecimal, can I find a denominator $n$ such that fractions $k/n$ written out
in hexadecimal have digits $1,2,4,7,8,b,d,e$ in some order (since these are the
eight digits relatively prime to 15)?  If so, what order do those digits go in?
If on the other hand I \emph{can't} find any such $n$, then why not?

(Findings are in section \ref{sec:find_spec}.)

%% ----------------------------------------------------------------
\subsection{What periods can exist?}
\label{sec:ques_what_periods}

Question $(i)$: When I write down $1/7, \ldots, 6/7$ in other bases besides 10,
will they all have period 6?  If not, then what?  More generally: holding
denominator $n$ fixed and varying $b$, what periods can exist?

Question $(ii)$: Why do there seem to be no periods of 8 in base 16 (section
\ref{sec:period_data})?  More generally: holding base $b$ fixed varying $n$,
what periods can exist?

(Findings are in section \ref{sec:find_what_periods}.)

% xxx incl. python -- ?  xref to it?  clean up the code in any case.

%% ----------------------------------------------------------------
\subsection{When can full periods exist?}
\label{sec:ques_full_periods}

Can I find more numbers like $142857$?  That is, when do $k/n$'s have the
longest possible period in base-$b$ expansion, with digits for each fraction
being cyclic permutations of one another?

(Findings are in section \ref{sec:find_full_periods}.)

%% ----------------------------------------------------------------
\subsection{How do digit sets correspond to numerators?}
\label{sec:ques_non_full_periods}

When $k/n$'s have a less-than-longest-possible period in base-$b$ expansion,
how do the digit sets relate to $k$'s?  (E.g. why is it that $1/13$ and $3/13$
are shifts of $076923$, while $2/13$ and $5/13$ are shifts of $153846$?)

(Findings are in section \ref{sec:find_non_full_periods}.)

%% ----------------------------------------------------------------
\subsection{What's the relationship between add order and shift order?}
\label{sec:ques_add_order_shift_order}

What's the connection between writing down 1/7, 2/7, 3/7, 4/7, 5/7, 6/7
(\emph{add order} in the table above) and 1/7, 3/7, 2/7, 6/7, 4/7, 5/7
(\emph{shift order} in the table above)?  Is there some mathematical way to
find out what the shift order is going to be?

(Findings are in section \ref{sec:find_add_order_shift_order}.)

%% ----------------------------------------------------------------
\subsection{Why are half-period shifts special?}
\label{sec:ques_half_period_shifts}

From the expansions of $1/7$ and $1/13$ we note that when we split the numbers
142857, 076923, and 153846 right down the middle, the digits are related in a
very particular way: $142+857=999$, $076+923=999$, and $153+846=999$.  Why is
this?  Does this hold true for other $n$'s and $b$'s?

(Findings are in section \ref{sec:find_half_period_shifts}.)

%% ================================================================
\section{Findings}

%% ----------------------------------------------------------------
\subsection{Relationship between expansions and integers}
\label{sec:expansions_and_integers}

First we need some elaboration on how to work with periods of base-$b$
expansions.

\begin{rem}
\label{rem:periods_vs_groups}
It is well-known that, regardless of base $b$, the expansions of fractions of
integers either eventually terminate or eventually repeat.  To see the
connection between base-$b$ expansions and integers, let's start by example.
Eventually-terminating expansions aren't of interest in this note; for
eventually repeating expansions, we can find the period $p$ of the repetition
and multiply by $10^p$, then subtract.  E.g.  We can see that $1/7$ in base 10
has period 6.  So
\begin{verbatim}
  x=1/7
  1000000x = 142857.142857142857...
         x =      0.142857142857...
  ----------------------------------
   999999x = 142857
   1/7     = 142857/999999
\end{verbatim}
Saying that $1/7$ repeats every 6 decimal places is the same as saying that 7
divides evenly into $999999=10^6-1$.  More generally, the period $p$ is the
smallest positive integer $e$ such that $n$ divides $b^e-1$, i.e. $b^e-1 \equiv
0 \pmod n$, i.e. $b^e \equiv 1 \pmod n$.  This means $p$ is nothing other than
the \textbf{group-theoretic period} of $b$ mod $n$.

For example, with $n=7$ and $b=10 \equiv 3 \pmod 7$, 3 is primitive mod 7 since
its powers mod 7 are $3,2,6,4,5,1$.  With $n=7$ and $b=16 \equiv 2 \pmod 7$, 2
is imprimitive mod 7 since its powers mod 7 are $2,4,1$.
\end{rem}

%% ----------------------------------------------------------------
\subsection{Period is independent of numerator}

\begin{prop}
\label{prop:period_indep_of_k}
For $0<k<n$ and $k$ coprime to $n$, the period of $k/n$ in base $b$ is
independent of $k$.
\begin{proof}
Let $p_1$ be the period of $1/n$ in base $b$.   Let $1<k<n$ and $(k,n)=1$; let
$p_k$ be the period of $k/n$ in base $b$.   It needs to be shown that
$p_k=p_1$.

Since $(k,n)=1$, there exists $a$ such that $ak \equiv 1 \pmod n$ (this is the
reciprocal of $k$ mod $n$).  Then $p_a=p_1$, since $a/n-1/n$ is an integer.
When we multiply each $p_k$-digit block by $a$ and do the carries, we get other
blocks of $p_k$ digits (or shorter).  The same is true for obtaining the
$p_k$-digit blocks from the $p_1$-digit blocks.  This means $p_a \le p_k \le
p_1$.  Since $p_a=p_1$, we have sandwiched $p_k=p_1$.
\end{proof}
\end{prop}

%% ----------------------------------------------------------------
\subsection{Are certain constructions possible?}
\label{sec:find_spec}

(See section \ref{sec:ques_spec} for the statement of the question.)

It seems interesting that the digits $1,2,4,5,7,8$ in the decimal expansion of
$1/7$ are precisely the six numbers between 0 and 9 which are relatively prime
to 9.  Can I find a denominator $n$ such that fractions $k/n$ written out in
hexadecimal have digits $1,2,4,7,8,b,d,e$ in some order (since these are the
eight digits relatively prime to 15)?  If so, what order do they go in?  If on
the other hand I \emph{can't} find any such denominator, then why not?

\begin{prop}
There exist no full-period base-$b$ expansions for any denominator $n$
whenever xxx, or whenever $b$ is a perfect square.
\begin{rem}
xxx These are sufficient but not necessary ... xxx find another example.
\end{rem}
\begin{proof}
xxx no, since from 1a. b is square and non-trivial unit groups (needs xref
...) have even order.
\end{proof}
\end{prop}

%% ----------------------------------------------------------------
\subsection{What periods can exist?}
\label{sec:find_what_periods}

(See section \ref{sec:ques_what_periods} for the statement of the question.)

Question $(i)$: Fixing denominator $n$, varying $b$, what periods can exist?

\begin{prop}
The period $p(n,b)$ of $k/n$'s, with $k$ coprime to $n$, divides $\phi(n)$.
\begin{proof}
It was shown in remark \ref{rem:periods_vs_groups} that $p(n,b)$ is the
group-theoretic period of $b$ mod $n$.  From Fermat's little theorem we know
that the order of $\langle b \rangle$ divides $|(\Z/n\Z)^\times|$, which is
$\phi(n)$.
\end{proof}
\end{prop}

For examples, see section \ref{sec:period_data}.

Question $(ii)$: Fixing $b$, varying $n$, what periods can exist?
In particular, why do there seem to be no periods of 8 in base 16?

xxx xref to the above.  Maybe reorder.

%% ----------------------------------------------------------------
\subsection{When can full periods exist?}
\label{sec:find_full_periods}

(See section \ref{sec:ques_full_periods} for the statement of the question.)

xxx When do $k/n$'s have the longest possible period in base-$b$ expansion, with
digits for each fraction being cyclic permutations of one another?

Note:
full period iff (?) b is primitive mod n (which in turn requires
that n's unit group be cyclic -- cf. n=21).

When that does occur, what properties do those $\phi(n)$ digits (the
\emph{digit set} of $n$ and $b$) have?

xxx none that i can tell ... 142857 being the unit group of 9 appears to be a
coincidence ... :/

%% ----------------------------------------------------------------
\subsection{How do digit sets correspond to numerators?}
\label{sec:find_non_full_periods}

(See section \ref{sec:ques_non_full_periods} for the statement of the question.)

xxx When $k/n$'s have a less-than-longest-possible period in base-$b$ expansion,
how do the digit sets relate to $k$'s?  (E.g. why is it that $1/13$ and $3/13$
are shifts of one another, using $076923$, while $2/13$ and $5/13$ are shifts
of $153846$?)

xxx mapping to partitions are cosets of $\langle b \rangle>$ mod $n$ (orbit and co-orbits).

%% ----------------------------------------------------------------
\subsection{What's the relationship between add order and shift order?}
\label{sec:find_add_order_shift_order}

(See section \ref{sec:ques_add_order_shift_order} for the statement of the question.)

From section \ref{sec:expansions_and_integers} we saw that base-$b$ expansions
of period $p$ could be identified with integer arithmetic mod $b^p-1$.  The key
point is that \textbf{a single left-cyclic shift is nothing more than
multiplication by $b$ mod $b^p-1$}.  For example, multiply 142857 by 10 to get
1428750.  Moving the 1 right six places is the same as subtracting 1000000 and
adding 1, i.e.  subtracting off (a multiple of) 999999, i.e. reducing mod
999999.  Also note that shifts by 1 are equivalent to multiplying by $b$ mod
$n$:  $142857\cdot 3 \equiv 142857 \cdot 10 \pmod{999999}$ since $7\cdot 142857
= 999999$.

We see this in the shift-order tables in sections \ref{sec:142857} and
\ref{sec:rep_frac_data}.  For $n=7,b=10$, $b$ mod $n$ is 3.  The powers of 10
mod 7 are 3, 2, 6, 4, 5, 1 (3 is primitive mod 7).  Likewise for $n=13,b=10$:
$b$ mod $n$ is 10, which is the square of 6 mod 13 and therefore imprimitive
mod 13.  The powers of 10 mod 13 are 10, 9, 12, 3, 4, 1.

Here's a side note:  until we do base-$b$ long division of $1/n$ we don't know
all the digits of the expansion of $1/n$.  But we do know (by the above ... xxx
make it a prop / move it?) the period $p$.  It turns out we also know the last digit
of the expansion.

\begin{prop}
Let $m_1 = (b^p-1)/n$.  (These are the digits of $1/n$ in base $b$, e.g. for
$n=7,b=10$, $m_1=142857$.)  Let $t(m_1)$ be the least-significant digit of
$m_1$.  Then
\begin{eqnarray*}
	t(m_1)\cdot n \equiv -1 \pmod b.
\end{eqnarray*}

\begin{proof}
The first right-cyclic shift (in contrast to the left-cyclic shifts used
elsewhere in this note) is
\begin{eqnarray*}
	m_2 &=& (m_1 + t(m_1)\cdot(b^p-1)) / b   \quad\textrm{but}\quad
		m_1 = (b^p-1)/n   \quad\textrm{so} \\
	m_2 &=& (m_1 + t(m_1) \cdot n \cdot m_1) / b \\
	m_2 &=& (1 + t(m_1) \cdot n)  \cdot  m_1/b.
\end{eqnarray*}
(For example, let $n=7,b=10$.  Then $p=6$.  If $m_1=142857$, then $t(m_1)=7$, and then
$(142857+7\cdot 999999)/10 = (142857+7\cdot 999999)/10 = 714285$.)

xxx fill in the missing step ... reduction mod b?  $b$ has to divide one term
or the other?

This forces $t(m_1)\cdot n \equiv -1 \pmod b$.
\end{proof}
\end{prop}

For example, with $n=27,b=10$ we know two things:  first, $b$ has order 3 mod
27 since its powers are 10,100,1000 which are 10,19,1 mod 27.  Second, from the
theorem we know $t(m_1) \cdot 27 \equiv 9 \pmod{10}$, that is, $1/27$ in base
10 must end with a 7 (which it does:  see \ref{sec:rep_frac_data_27} for this
and other examples).

%% ----------------------------------------------------------------
\subsection{Why are half-period shifts special?}
\label{sec:find_half_period_shifts}

(See section \ref{sec:ques_half_period_shifts} for the statement of the
question.)

From the expansions of $1/7$ and $1/13$ we note that when we split the numbers
142857, 076923, and 153846 right down the middle, the digits are related:
$142+857=999$, $076+923=999$, and $153+846=999$.  (Phrased differently, we have
$142857+857142=999$, $076923+923076=999$, and $153846+846153=999$.) Why is
this?

This is called \emph{Midy's theorem}.  Here's a proof.

\newpage xxx temp newpage

\begin{thm}[Midy's theorem]
Let $n$ have period $p$ in base $b$; let $0<k<n$ with $k$ coprime to $n$.  Let
$m=b^p-1$.  Lastly and most importantly, suppose that $n$ is prime.  Then $(1 +
b^{p/2})\frac{km}{n} \equiv 0 \pmod m$.
\begin{rem}
For example, let $n=7$, $b=10$, and $k=1$.  Then $p=6$ and $m=999999$.  We have
$\frac{km}{n}=142857$.  Since left-shift by one place is multiplication by $b$
mod $m$ (xxx xref), $b^{p/2}\cdot \frac{km}{n} = 142857000 \equiv 857142
\pmod{999999}$.
\end{rem}
\begin{proof}
We need to show that $(1+ b^{p/2})\frac{k}{n}$ is an integer, in spite of the
$n$ in the denominator.  Since we take $k$ coprime to $n$, we need $n$ to
divide $1+b^{p/2}$, i.e.  $b^{p/2} \equiv -1 \pmod n$.  But this is certainly
the case:  since $p$ is the period of $n$ in base $b$, $p$ is the smallest
positive exponent $e$ such that $b^e\equiv 1 \pmod n$.  Since $n$ is prime,
$b^{p/2} \equiv \pm 1 \pmod n$.  But $b^{p/2} \not\equiv 1 \pmod n$, since
$p/2$ is not the period, so $b^{p/2} \equiv -1 \pmod n$.
\end{proof}
\end{thm}

See the data in section \ref{sec:rep_frac_data} for examples.  (Note that
21 isn't prime.   xxx sums of 666666 or 333333; $1000 \equiv 13 \pmod 21$
\ldots .)

xxx also note this means these cyclics are multiples of $b$.

%================================================================
\newpage
\section{Data for periods}
\label{sec:period_data}

%row labels: n
%column labels: base
%cells: period of n in base b

\begin{center}
\begin{scriptsize}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$ & $b=7$ & $b=8$ & $b=9$ & $b=10$ & $b=11$ & $b=12$ & $b=13$ & $b=14$ & $b=15$ & $b=16$ \\
\hline
  2  &  1  &     &  1 &     &   1 &     &   1 &     &   1 &     \\
  3  &  1  &  2  &    &   1 &   2 &     &   1 &   2 &     &   1 \\
  4  &  2  &     &  1 &     &   2 &     &   1 &     &   2 &     \\
  5  &  4  &  4  &  2 &     &   1 &   4 &   4 &   2 &     &   1 \\
  6  &  1  &     &    &     &   2 &     &   1 &     &     &     \\
  7  &     &  1  &  3 &   6 &   3 &   6 &   2 &     &   1 &   3 \\
  8  &  2  &     &  1 &     &   2 &     &   2 &     &   2 &     \\
  9  &  3  &  2  &    &   1 &   6 &     &   3 &   6 &     &   3 \\
 10  &  4  &     &  2 &     &   1 &     &   4 &     &     &     \\
 11  & 10  & 10  &  5 &   2 &     &   1 &  10 &   5 &   5 &   5 \\
 12  &  2  &     &    &     &   2 &     &   1 &     &     &     \\
 13  & 12  &  4  &  3 &   6 &  12 &   2 &     &   1 &  12 &   3 \\
 14  &     &     &  3 &     &   3 &     &   2 &     &   1 &     \\
 15  &  4  &  4  &    &     &   2 &     &   4 &   2 &     &   1 \\
 16  &  2  &     &  2 &     &   4 &     &   4 &     &   2 &     \\
 17  & 16  &  8  &  8 &  16 &  16 &  16 &   4 &  16 &   8 &   2 \\
 18  &  3  &     &    &     &   6 &     &   3 &     &     &     \\
 19  &  3  &  6  &  9 &  18 &   3 &   6 &  18 &  18 &  18 &   9 \\
 20  &  4  &     &  2 &     &   2 &     &   4 &     &     &     \\
 21  &     &  2  &    &   6 &   6 &     &   2 &     &     &   3 \\
 22  & 10  &     &  5 &     &     &     &  10 &     &   5 &     \\
 23  & 22  & 11  & 11 &  22 &  22 &  11 &  11 &  22 &  22 &  11 \\
 24  &  2  &     &    &     &   2 &     &   2 &     &     &     \\
 25  &  4  & 20  & 10 &     &   5 &  20 &  20 &  10 &     &   5 \\
 26  & 12  &     &  3 &     &  12 &     &     &     &  12 &     \\
 27  &  9  &  6  &    &   3 &  18 &     &   9 &  18 &     &   9 \\
 28  &     &     &  3 &     &   6 &     &   2 &     &   2 &     \\
 29  &  7  & 28  & 14 &  28 &  28 &   4 &  14 &  28 &  28 &   7 \\
 30  &  4  &     &    &     &   2 &     &   4 &     &     &     \\
 31  & 15  &  5  & 15 &  15 &  30 &  30 &  30 &  15 &  10 &   5 \\
 32  &  4  &     &  4 &     &   8 &     &   8 &     &   2 &     \\
 33  & 10  & 10  &    &   2 &     &     &  10 &  10 &     &   5 \\
 34  & 16  &     &  8 &     &  16 &     &   4 &     &   8 &     \\
 35  &     &  4  &  6 &     &   3 &  12 &   4 &     &     &   3 \\
 36  &  6  &     &    &     &   6 &     &   3 &     &     &     \\
 37  &  9  & 12  &  9 &   3 &   6 &   9 &  36 &  12 &  36 &   9 \\
 38  &  3  &     &  9 &     &   3 &     &  18 &     &  18 &     \\
 39  & 12  &  4  &    &   6 &  12 &     &     &   2 &     &   3 \\
 40  &  4  &     &  2 &     &   2 &     &   4 &     &     &     \\
 41  & 40  & 20  &  4 &   5 &  40 &  40 &  40 &   8 &  40 &   5 \\
 42  &     &     &    &     &   6 &     &   2 &     &     &     \\
 43  &  6  & 14  & 21 &  21 &   7 &  42 &  21 &  21 &  21 &   7 \\
 44  & 10  &     &  5 &     &     &     &  10 &     &  10 &     \\
 45  & 12  &  4  &    &     &   6 &     &  12 &   6 &     &   3 \\
 46  & 22  &     & 11 &     &  22 &     &  11 &     &  22 &     \\
 47  & 23  & 23  & 23 &  46 &  46 &  23 &  46 &  23 &  46 &  23 \\
 48  &  2  &     &    &     &   4 &     &   4 &     &     &     \\
 49  &     &  7  & 21 &  42 &  21 &  42 &  14 &     &   7 &  21 \\
 50  &  4  &     & 10 &     &   5 &     &  20 &     &     &     \\
 51  & 16  &  8  &    &  16 &  16 &     &   4 &  16 &     &   2 \\
 52  & 12  &     &  3 &     &  12 &     &     &     &  12 &     \\
 53  & 26  & 52  & 26 &  13 &  26 &  52 &  13 &  52 &  13 &  13 \\
 54  &  9  &     &    &     &  18 &     &   9 &     &     &     \\
 55  & 20  & 20  & 10 &     &     &   4 &  20 &  10 &     &   5 \\
 56  &     &     &  3 &     &   6 &     &   2 &     &   2 &     \\
 57  &  3  &  6  &    &  18 &   6 &     &  18 &  18 &     &   9 \\
 58  &  7  &     & 14 &     &  28 &     &  14 &     &  28 &     \\
 59  & 29  & 58  & 29 &  58 &  58 &  29 &  58 &  58 &  29 &  29 \\
 60  &  4  &     &    &     &   2 &     &   4 &     &     &     \\
\hline
\end{tabular}
\end{scriptsize}
\end{center}

%================================================================
\section{Repeating-fraction data}
\label{sec:rep_frac_data}

\begin{itemize}

\item Repeating fractions are shown for denominators $n,7,9,11,13,21,27$ and bases
$b=10,12,16$.

\item Numerators $k$ shown are only those coprime to $n$.

\item The expansions are listed in \emph{add order}, i.e. by increasing $k$, as
well as \emph{shift order}, i.e. grouped by cosets, then by left-shift within
cosets.

\item By $\phi(n)$, I mean the Euler totient function.

\item The period $p(n,b)$ is the period of $n$ in base $b$.

\item For convenience I also show the ratio $r=\phi(n)/p(n,b)$.  (This is the
number of distinct digits sets for $n$ and $b$.)

\end{itemize}

%% ----------------------------------------------------------------
\subsection{Repeating-fraction data for $n=7$}

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \multicolumn{4}{|c|}{$n=7, \phi(n)=6$} \\
\hline
\hline $b=10,p=6,r=1$  & $b=12,p=6,r=1$ &  $b=16,p=3,r=2$ & \\
\hline
\hline & & & \\
 1/7 = $.\overline{142857}$  &  1/7 = $.\overline{186a35}$ &   1/7 = $.\overline{249}$   & add order \\
 2/7 = $.\overline{285714}$  &  2/7 = $.\overline{35186a}$ &   2/7 = $.\overline{492}$   & \\
 3/7 = $.\overline{428571}$  &  3/7 = $.\overline{5186a3}$ &   3/7 = $.\overline{6db}$   & \\
 4/7 = $.\overline{571428}$  &  4/7 = $.\overline{6a3518}$ &   4/7 = $.\overline{924}$   & \\
 5/7 = $.\overline{714285}$  &  5/7 = $.\overline{86a351}$ &   5/7 = $.\overline{b6d}$   & \\
 6/7 = $.\overline{857142}$  &  6/7 = $.\overline{a35186}$ &   6/7 = $.\overline{db6}$   & \\
& & & \\
\hline & & &\\
 1/7 = $.\overline{142857}$  &  1/7 = $.\overline{186a35}$ &   1/7 = $.\overline{249}$   & shift order \\
 3/7 = $.\overline{428571}$  &  5/7 = $.\overline{86a351}$ &   2/7 = $.\overline{492}$   & \\
 2/7 = $.\overline{285714}$  &  4/7 = $.\overline{6a3518}$ &   4/7 = $.\overline{924}$   & \\
 6/7 = $.\overline{857142}$  &                &                & \\
 4/7 = $.\overline{571428}$  &  6/7 = $.\overline{a35186}$ &   3/7 = $.\overline{6db}$   & \\
 5/7 = $.\overline{714285}$  &  2/7 = $.\overline{35186a}$ &   6/7 = $.\overline{db6}$   & \\
                             &  3/7 = $.\overline{5186a3}$ &   5/7 = $.\overline{b6d}$   & \\
& & & \\
\hline
\end{tabular}
\end{center}

%% ----------------------------------------------------------------
\subsection{Repeating-fraction data for $n=9$}

\begin{center}
\begin{tabular}{|c|c|c|}
\hline \multicolumn{3}{|c|}{$n=9, \phi(n)=6$} \\
\hline
\hline $b=10,p=1,r=6$ & $b=16,p=3,r=2$ & \\
\hline
\hline & & \\
1/9 = $.\overline{1}$  & 1/9 = $.\overline{1c7}$  & add order \\
2/9 = $.\overline{2}$  & 2/9 = $.\overline{38e}$  & \\
4/9 = $.\overline{4}$  & 4/9 = $.\overline{71c}$  & \\
5/9 = $.\overline{5}$  & 5/9 = $.\overline{8e3}$  & \\
7/9 = $.\overline{7}$  & 7/9 = $.\overline{c71}$  & \\
8/9 = $.\overline{8}$  & 8/9 = $.\overline{e38}$  & \\
& & \\
\hline & &\\
               & 1/9 = $.\overline{1c7}$  & shift order \\
               & 7/9 = $.\overline{c71}$  & \\
               & 4/9 = $.\overline{71c}$  & \\
               &                          & \\
               & 2/9 = $.\overline{38e}$  & \\
               & 5/9 = $.\overline{8e3}$  & \\
               & 8/9 = $.\overline{e38}$  & \\
& & \\
\hline
\end{tabular}
\end{center}

%% ----------------------------------------------------------------
\subsection{Repeating-fraction data for $n=11$}

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \multicolumn{4}{|c|}{$n=11, \phi(n)=10$} \\
\hline
\hline $b=10,p=2,r=5$  & $b=12,p=1,r=10$ &  $b=16,p=5,r=2$ & \\
\hline
\hline & & & \\
 1/11 = $.\overline{09}$   &  1/11 = $.\overline{1}$    &   1/11 = $.\overline{1745d}$  & add order \\
 2/11 = $.\overline{18}$   &  2/11 = $.\overline{2}$    &   2/11 = $.\overline{2e8ba}$  & \\
 3/11 = $.\overline{27}$   &  3/11 = $.\overline{3}$    &   3/11 = $.\overline{45d17}$  & \\
 4/11 = $.\overline{36}$   &  4/11 = $.\overline{4}$    &   4/11 = $.\overline{5d174}$  & \\
 5/11 = $.\overline{45}$   &  5/11 = $.\overline{5}$    &   5/11 = $.\overline{745d1}$  & \\
 6/11 = $.\overline{54}$   &  6/11 = $.\overline{6}$    &   6/11 = $.\overline{8ba2e}$  & \\
 7/11 = $.\overline{63}$   &  7/11 = $.\overline{7}$    &   7/11 = $.\overline{a2e8b}$  & \\
 8/11 = $.\overline{72}$   &  8/11 = $.\overline{8}$    &   8/11 = $.\overline{ba2e8}$  & \\
 9/11 = $.\overline{81}$   &  9/11 = $.\overline{9}$    &   9/11 = $.\overline{d1745}$  & \\
10/11 = $.\overline{90}$   & 10/11 = $.\overline{a}$    &  10/11 = $.\overline{e8ba2}$  & \\
& & & \\
\hline & & &\\
   1/11 = $.\overline{09}$ &  1/11 = $.\overline{1}$    &  1/11 = $.\overline{1745d}$  &  shift order \\
  10/11 = $.\overline{90}$ &  2/11 = $.\overline{2}$    &  5/11 = $.\overline{745d1}$  & \\
                           &  3/11 = $.\overline{3}$    &  3/11 = $.\overline{45d17}$  & \\
   2/11 = $.\overline{18}$ &  4/11 = $.\overline{4}$    &  4/11 = $.\overline{5d174}$  & \\
   9/11 = $.\overline{81}$ &  5/11 = $.\overline{5}$    &  9/11 = $.\overline{d1745}$  & \\
                           &  6/11 = $.\overline{6}$    &                 & \\
   3/11 = $.\overline{27}$ &  7/11 = $.\overline{7}$    &  2/11 = $.\overline{2e8ba}$  & \\
   8/11 = $.\overline{72}$ &  8/11 = $.\overline{8}$    & 10/11 = $.\overline{e8ba2}$  & \\
                           &  9/11 = $.\overline{9}$    &  6/11 = $.\overline{8ba2e}$  & \\
   4/11 = $.\overline{36}$ & 10/11 = $.\overline{a}$    &  8/11 = $.\overline{ba2e8}$  & \\
   7/11 = $.\overline{63}$ &                            &  7/11 = $.\overline{a2e8b}$  & \\
               &               &                 & \\
   5/11 = $.\overline{45}$ &               &                 & \\
   6/11 = $.\overline{54}$ &               &                 & \\
& & & \\
\hline
\end{tabular}
\end{center}

%% ----------------------------------------------------------------
\subsection{Repeating-fraction data for $n=13$}

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline \multicolumn{4}{|c|}{$n=13, \phi(n)=12$} \\
\hline
\hline $b=10,p=6,r=2$  & $b=12,p=2,r=6$ &  $b=16,p=3,r=4$ & \\
\hline
\hline & & & \\
 1/13 = $.\overline{076923}$  &  1/13 = $.\overline{0b}$  &  1/13 = $.\overline{13b}$  & add order \\
 2/13 = $.\overline{153846}$  &  2/13 = $.\overline{1a}$  &  2/13 = $.\overline{276}$  & \\
 3/13 = $.\overline{230769}$  &  3/13 = $.\overline{29}$  &  3/13 = $.\overline{3b1}$  & \\
 4/13 = $.\overline{307692}$  &  4/13 = $.\overline{38}$  &  4/13 = $.\overline{4ec}$  & \\
 5/13 = $.\overline{384615}$  &  5/13 = $.\overline{47}$  &  5/13 = $.\overline{627}$  & \\
 6/13 = $.\overline{461538}$  &  6/13 = $.\overline{56}$  &  6/13 = $.\overline{762}$  & \\
 7/13 = $.\overline{538461}$  &  7/13 = $.\overline{65}$  &  7/13 = $.\overline{89d}$  & \\
 8/13 = $.\overline{615384}$  &  8/13 = $.\overline{74}$  &  8/13 = $.\overline{9d8}$  & \\
 9/13 = $.\overline{692307}$  &  9/13 = $.\overline{83}$  &  9/13 = $.\overline{b13}$  & \\
10/13 = $.\overline{769230}$  & 10/13 = $.\overline{92}$  & 10/13 = $.\overline{c4e}$  & \\
11/13 = $.\overline{846153}$  & 11/13 = $.\overline{a1}$  & 11/13 = $.\overline{d89}$  & \\
12/13 = $.\overline{923076}$  & 12/13 = $.\overline{b0}$  & 12/13 = $.\overline{ec4}$  & \\
& & & \\
\hline & & &\\
 1/13 = $.\overline{076923}$  &  1/13 = $.\overline{0b}$  &  1/13 = $.\overline{13b}$ & shift order \\
10/13 = $.\overline{769230}$  & 12/13 = $.\overline{b0}$  &  3/13 = $.\overline{3b1}$ & \\
 9/13 = $.\overline{692307}$  &                           &  9/13 = $.\overline{b13}$ & \\
12/13 = $.\overline{923076}$  &  2/13 = $.\overline{1a}$  &              & \\
 3/13 = $.\overline{230769}$  & 11/13 = $.\overline{a1}$  &  2/13 = $.\overline{276}$ & \\
 4/13 = $.\overline{307692}$  &                           &  6/13 = $.\overline{762}$ & \\
                              &  3/13 = $.\overline{29}$  &  5/13 = $.\overline{627}$ & \\
 2/13 = $.\overline{153846}$  & 10/13 = $.\overline{92}$  &              & \\
 7/13 = $.\overline{538461}$  &                           &  4/13 = $.\overline{4ec}$ & \\
 5/13 = $.\overline{384615}$  &  4/13 = $.\overline{38}$  & 12/13 = $.\overline{ec4}$ & \\
11/13 = $.\overline{846153}$  &  9/13 = $.\overline{83}$  & 10/13 = $.\overline{c4e}$ & \\
 6/13 = $.\overline{461538}$  &                           &              & \\
 8/13 = $.\overline{615384}$  &  5/13 = $.\overline{47}$  &  7/13 = $.\overline{89d}$ & \\
                              &  8/13 = $.\overline{74}$  &  8/13 = $.\overline{9d8}$ & \\
                              &                           & 11/13 = $.\overline{d89}$ & \\
                              &  6/13 = $.\overline{56}$  &              & \\
                              &  7/13 = $.\overline{65}$  &              & \\
& & & \\
\hline
\end{tabular}
\end{center}

%% ----------------------------------------------------------------
\subsection{Repeating-fraction data for $n=21$}

\begin{center}
\begin{tabular}{|c|c|c|}
\hline \multicolumn{3}{|c|}{$n=21, \phi(n)=12$} \\
\hline
\hline $b=10,p=6,r=2$ & $b=16,p=3,r=4$ & \\
\hline
\hline & & \\
 1/21 = $.\overline{047619}$  &  1/21 = $.\overline{0c3}$    & add order \\
 2/21 = $.\overline{095238}$  &  2/21 = $.\overline{186}$    & \\
 4/21 = $.\overline{190476}$  &  4/21 = $.\overline{30c}$    & \\
 5/21 = $.\overline{238095}$  &  5/21 = $.\overline{3cf}$    & \\
 8/21 = $.\overline{380952}$  &  8/21 = $.\overline{618}$    & \\
10/21 = $.\overline{476190}$  & 10/21 = $.\overline{79e}$    & \\
11/21 = $.\overline{523809}$  & 11/21 = $.\overline{861}$    & \\
13/21 = $.\overline{619047}$  & 13/21 = $.\overline{9e7}$    & \\
16/21 = $.\overline{761904}$  & 16/21 = $.\overline{c30}$    & \\
17/21 = $.\overline{809523}$  & 17/21 = $.\overline{cf3}$    & \\
19/21 = $.\overline{904761}$  & 19/21 = $.\overline{e79}$    & \\
20/21 = $.\overline{952380}$  & 20/21 = $.\overline{f3c}$    & \\
& & \\
\hline & & \\
 1/21 = $.\overline{047619}$  &   1/21 = $.\overline{0c3}$   & shift order \\
10/21 = $.\overline{476190}$  &  16/21 = $.\overline{c30}$   & \\
16/21 = $.\overline{761904}$  &   4/21 = $.\overline{30c}$   & \\
13/21 = $.\overline{619047}$  &                 & \\
 4/21 = $.\overline{190476}$  &   2/21 = $.\overline{186}$   & \\
19/21 = $.\overline{904761}$  &  11/21 = $.\overline{861}$   & \\
                              &   8/21 = $.\overline{618}$   & \\
 2/21 = $.\overline{095238}$  &                 & \\
20/21 = $.\overline{952380}$  &   5/21 = $.\overline{3cf}$   & \\
11/21 = $.\overline{523809}$  &  17/21 = $.\overline{cf3}$   & \\
 5/21 = $.\overline{238095}$  &  20/21 = $.\overline{f3c}$   & \\
 8/21 = $.\overline{380952}$  &                 & \\
17/21 = $.\overline{809523}$  &  10/21 = $.\overline{79e}$   & \\
                              &  13/21 = $.\overline{9e7}$   & \\
                              &  19/21 = $.\overline{e79}$   & \\
& & \\
\hline
\end{tabular}
\end{center}

%% ----------------------------------------------------------------
\subsection{Repeating-fraction data for $n=27$}
\label{sec:rep_frac_data_27}

\begin{center}
\begin{tabular}{|c|c||c|c|}
\hline \multicolumn{4}{|c|}{$n=27, \phi(n)=18$} \\
\hline
\hline $b=10,p=3,r=6$  & $b=16,p=9,r=2$ & $b=10,p=3,r=6$  & $b=16,p=9,r=2$ \\
\hline \multicolumn{2}{|c||}{add order} & \multicolumn{2}{|c|}{shift order} \\
\hline
\hline & & & \\
 1/27 = $.\overline{037}$ &   1/27 = $.\overline{097b425ed}$ &   1/27 = $.\overline{037}$   &  1/27 = $.\overline{097b425ed}$  \\
 2/27 = $.\overline{074}$ &   2/27 = $.\overline{12f684bda}$ &  10/27 = $.\overline{370}$   & 16/27 = $.\overline{97b425ed0}$  \\
 4/27 = $.\overline{148}$ &   4/27 = $.\overline{25ed097b4}$ &  19/27 = $.\overline{703}$   & 13/27 = $.\overline{7b425ed09}$  \\
 5/27 = $.\overline{185}$ &   5/27 = $.\overline{2f684bda1}$ &                              & 19/27 = $.\overline{b425ed097}$  \\
 7/27 = $.\overline{259}$ &   7/27 = $.\overline{425ed097b}$ &   2/27 = $.\overline{074}$   &  7/27 = $.\overline{425ed097b}$  \\
 8/27 = $.\overline{296}$ &   8/27 = $.\overline{4bda12f68}$ &  20/27 = $.\overline{740}$   &  4/27 = $.\overline{25ed097b4}$  \\
10/27 = $.\overline{370}$ &  10/27 = $.\overline{5ed097b42}$ &  11/27 = $.\overline{407}$   & 10/27 = $.\overline{5ed097b42}$  \\
11/27 = $.\overline{407}$ &  11/27 = $.\overline{684bda12f}$ &                              & 25/27 = $.\overline{ed097b425}$  \\
13/27 = $.\overline{481}$ &  13/27 = $.\overline{7b425ed09}$ &   4/27 = $.\overline{148}$   & 22/27 = $.\overline{d097b425e}$  \\
14/27 = $.\overline{518}$ &  14/27 = $.\overline{84bda12f6}$ &  13/27 = $.\overline{481}$   &                     \\
16/27 = $.\overline{592}$ &  16/27 = $.\overline{97b425ed0}$ &  22/27 = $.\overline{814}$   &  2/27 = $.\overline{12f684bda}$  \\
17/27 = $.\overline{629}$ &  17/27 = $.\overline{a12f684bd}$ &                              &  5/27 = $.\overline{2f684bda1}$  \\
19/27 = $.\overline{703}$ &  19/27 = $.\overline{b425ed097}$ &   5/27 = $.\overline{185}$   & 26/27 = $.\overline{f684bda12}$  \\
20/27 = $.\overline{740}$ &  20/27 = $.\overline{bda12f684}$ &  23/27 = $.\overline{851}$   & 11/27 = $.\overline{684bda12f}$  \\
22/27 = $.\overline{814}$ &  22/27 = $.\overline{d097b425e}$ &  14/27 = $.\overline{518}$   & 14/27 = $.\overline{84bda12f6}$  \\
23/27 = $.\overline{851}$ &  23/27 = $.\overline{da12f684b}$ &                              &  8/27 = $.\overline{4bda12f68}$  \\
25/27 = $.\overline{925}$ &  25/27 = $.\overline{ed097b425}$ &   7/27 = $.\overline{259}$   & 20/27 = $.\overline{bda12f684}$  \\
26/27 = $.\overline{962}$ &  26/27 = $.\overline{f684bda12}$ &  16/27 = $.\overline{592}$   & 23/27 = $.\overline{da12f684b}$  \\
                           &                                 &  25/27 = $.\overline{925}$   & 17/27 = $.\overline{a12f684bd}$  \\
                           &                                 &                 &                     \\
                           &                                 &   8/27 = $.\overline{296}$   &                     \\
                           &                                 &  26/27 = $.\overline{962}$   &                     \\
                           &                                 &  17/27 = $.\overline{629}$   &                     \\
& & & \\
\hline
\end{tabular}
\end{center}

%% ================================================================
\newpage
\section{References}

\begin{itemize}
\item \texttt{http://en.wikipedia.org/wiki/Cyclic\_number}
\item \texttt{http://en.wikipedia.org/wiki/Transposable\_integer}
\item \texttt{http://en.wikipedia.org/wiki/Repeating\_decimal}
\item \texttt{http://en.wikipedia.org/wiki/Cyclic\_permutation\_of\_integer}
\item \texttt{http://en.wikipedia.org/wiki/Parasitic\_number}
\item \texttt{http://mathworld.wolfram.com/CyclicNumber.html}
\item \texttt{http://en.wikipedia.org/wiki/Midy\%27s\_Theorem}
\item \texttt{http://mathworld.wolfram.com/MidysTheorem.html}
\end{itemize}

\end{document}
