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

\usepackage{verbatim}
\usepackage{fullpage}

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

\usepackage{makeidx}

\makeindex

%--------------------------------------------------------------------
\begin{document}
\title{On cyclic and transposable numbers}
\author{John Kerl}
\maketitle

\tableofcontents

%% ================================================================
\section{What}

links:
\begin{verbatim}
http://en.wikipedia.org/wiki/Cyclic_number
http://en.wikipedia.org/wiki/Transposable_integer
http://en.wikipedia.org/wiki/Repeating_decimal
http://en.wikipedia.org/wiki/Cyclic_permutation_of_integer
http://en.wikipedia.org/wiki/Parasitic_number
http://mathworld.wolfram.com/CyclicNumber.html
http://en.wikipedia.org/wiki/Midy%27s_Theorem
http://mathworld.wolfram.com/MidysTheorem.html
\end{verbatim}

%% ================================================================
\section{xxx}

Generalization of 0.142857 for 1/7, 2/7, ... 6/7 in base 10.  These are cyclic
permutations of one another.
Also note that 1,2,4,5,7,8 are units mod 9 (=b-1).

Notation: $n=7$ $b=10$ $k=1,2,3,4,5,6$.

Note that cyclic numbers (wikipedia xref) take n prime.  I don't require that.
C.f. transposable integers \ldots.

"A cyclic number is an integer in which cyclic permutations of the digits
are successive multiples of the number. The most widely known is 142857."

"The digits of some specific integers permute or shift cyclically when they are multiplied by a number n. Examples are:
\begin{itemize}
\item 142857 × 3 = 428571 (shifts cyclically one place left)
\item 142857 × 5 = 714285 (shifts cyclically one place right)
\item 128205 × 4 = 512820 (shifts cyclically one place right)
\item 076923 × 9 = 692307 (shifts cyclically two places left)
\end{itemize}
These specific integers, known as transposable integers, can be but are not always cyclic numbers."

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

1a. When do $k/n$'s, for $(k,n)=1$, have:
\begin{itemize}
\item period (in base-b expansion) equal to phi(n), and
\item all values cyclic permutations of one another?
\end{itemize}

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
"digit set" of $n$ and $b$, $d(n,b))$ have?

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

2. For shorter periods, how do the digit-sets partition (e.g. in relation to
n and b), and what is the mapping of k's to partitions?

xxx mapping to partitions are cosets of <b> mod n (orbit and co-orbits).

3a. Fixing n, varying b, what periods can exist?

xxx They are all divisors of $\phi(n)$.  This is because the period, $p(n,b)$,
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 \mod n$:  so, the group-theoretic
period of $b$ mod $n$.

3b. Fixing $b$, varying $n$, what periods can exist?
In particular, why do there seem to be no periods of 8 in base 16?

xxx this needs work.

4. Using $b=16$, can I find $n$ so that period is 8 and digits are relatively
prime to 15 (namely, 1 2 4 7 8 b d e)?  (This is analog of $n=7,b=10$.)  If
not, why not?

xxx no, since from 1a.  b is square and non-trivial unit groups (needs xref
...) have even order.

5. What's the relationship between add order (which cuts across digit-sets) and
shift order (which preserves digit sets)?  E.g. for n=7,b=10, shift order is
the same as multiplication by 3 (i.e. tripled add order).

xxx Left shift is, visibly, multiplication by $b$, mod $b^p-1$.  Multiplication
by $b$ is the same as by $b$ mod $n$.

6. Note for shift order: let $m_1 = (b^p-1)/n$ (i.e. digits of $1/n$ in base
$b$).  Let $t(m_1)$ = trailing digit of $m_1$.  Then the first shift is
\begin{eqnarray*}
	m_2 &=& (m_1 + t(m_1)*(b^p-1)) / b   \qquad\textrm{but}\qquad
		m_1 = (b^p-1)/n   \qquad\textrm{so} \\
	m_2 &=& (m_1 + t(m_1)*n*m1) / b \\
	m_2 &=& (1 + t(m_1)*n) * m1/b
\end{eqnarray*}

so $t(m_1)\cdot n \equiv -1 \pmod b$.

7. Half-period shifts: 142+857=999.  How does this generalize (if at all)?

xxx Midy's theorem.  Does it apply for b != 10?  Look for counterexamples.

%================================================================
%(1:4)  n=5  base=7: 0.1254
%
%(1:4)  n=5  base=8: 0.1463
%(1:10) n=11 base=8: 0.0564272135
%
%(2:3)  n=7  base=11: 0.163; 0.479
%
%(1:4)  n=5  base=12: 0.2497
%(1:6)  n=7  base=12: 0.186a35  (13568a missing 2479b)
%
%(1:4)  n=5  base=13: 0.27a5
%(1:12) n=11 base=13: 0.12495ba837 (missing 6)
%
%(1:6)  n=9  base=14: 0.17ac63 (1367ac missing 24589b)
%
%(1:12) n=13 base=15: 0.124936dca5b8 (missing 7)
%
%(2:3)  n=7  base=16: 0.249; 0.6db
%(2:3)  n=9  base=16: 0.1c7; 0.38e
%(2:5)  n=11 base=16: 0.1745d; 0.2e8ba
%(4:3)  n=13 base=16: 0.13b; 0.276; 0.4ec; 0.89d
%(2:9)  n=19 base=16: 0.0d79435e5; 0.1af286bca
%
%----------------------------------------------------------------
%totients:
%
%   7    8    9   10   11   12   13   14   15   16   17   18   19
%---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
%   6    4    6    4   10    4   12    6    8    8   16    6   18

%row labels: n
%column labels: base
%cells: period of n in base b
%
%n\b     7     8     9    10    11    12    13    14    15    16
%--- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
%  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                  

%================================================================
\section{Data}

%% ----------------------------------------------------------------
\subsection{Data for $b=10$}

\begin{verbatim}
n=7 b=10 p=6 f=6 r=1
   1/7 = .142857     1 qr=1
   3/7 = .428571     2 qr=0
   2/7 = .285714     4 qr=1
   6/7 = .857142     1 qr=0
   4/7 = .571428     2 qr=1
   5/7 = .714285     4 qr=0
\end{verbatim}

\begin{verbatim}
n=13 b=10 p=6 f=12 r=2
   1/13 = .076923     1**2 =   1 qr=1
  10/13 = .769230    10**2 =   9 qr=1
   9/13 = .692307     9**2 =   3 qr=1
  12/13 = .923076    12**2 =   1 qr=1
   3/13 = .230769     3**2 =   9 qr=1
   4/13 = .307692     4**2 =   3 qr=1

   2/13 = .153846     2**2 =   4 qr=0
   7/13 = .538461     7**2 =  10 qr=0
   5/13 = .384615     5**2 =  12 qr=0
  11/13 = .846153    11**2 =   4 qr=0
   6/13 = .461538     6**2 =  10 qr=0
   8/13 = .615384     8**2 =  12 qr=0

   1/13 = .076923     1**2 =   1 qr=1    B0
   2/13 = .153846     2**2 =   4 qr=0 A0
   3/13 = .230769     3**2 =   9 qr=1    B4
   4/13 = .307692     4**2 =   3 qr=1    B5
   5/13 = .384615     5**2 =  12 qr=0 A2
   6/13 = .461538     6**2 =  10 qr=0 A4
   7/13 = .538461     7**2 =  10 qr=0 A1
   8/13 = .615384     8**2 =  12 qr=0 A5
   9/13 = .692307     9**2 =   3 qr=1    B2
  10/13 = .769230    10**2 =   9 qr=1    B1
  11/13 = .846153    11**2 =   4 qr=0 A3
  12/13 = .923076    12**2 =   1 qr=1    B3
\end{verbatim}

\begin{verbatim}
n=17 b=10 p=16 f=16 r=1
   1/17 = .0588235294117647     1**2 =   1 qr=1
  10/17 = .5882352941176470    10**2 =  15 qr=0
  15/17 = .8823529411764705    15**2 =   4 qr=1
  14/17 = .8235294117647058    14**2 =   9 qr=0
   4/17 = .2352941176470588     4**2 =  16 qr=1
   6/17 = .3529411764705882     6**2 =   2 qr=0
   9/17 = .5294117647058823     9**2 =  13 qr=1
   5/17 = .2941176470588235     5**2 =   8 qr=0
  16/17 = .9411764705882352    16**2 =   1 qr=1
   7/17 = .4117647058823529     7**2 =  15 qr=0
   2/17 = .1176470588235294     2**2 =   4 qr=1
   3/17 = .1764705882352941     3**2 =   9 qr=0
  13/17 = .7647058823529411    13**2 =  16 qr=1
  11/17 = .6470588235294117    11**2 =   2 qr=0
   8/17 = .4705882352941176     8**2 =  13 qr=1
  12/17 = .7058823529411764    12**2 =   8 qr=0
\end{verbatim}

\begin{verbatim}
n=21 b=10 p=6 f=12 r=2
   1/21 = .047619     1**2 =   1 qr=1
  10/21 = .476190    10**2 =  16 qr=0
  16/21 = .761904    16**2 =   4 qr=1
  13/21 = .619047    13**2 =   1 qr=0
   4/21 = .190476     4**2 =  16 qr=1
  19/21 = .904761    19**2 =   4 qr=0

   2/21 = .095238     2**2 =   4 qr=0
  20/21 = .952380    20**2 =   1 qr=0
  11/21 = .523809    11**2 =  16 qr=0
   5/21 = .238095     5**2 =   4 qr=0
   8/21 = .380952     8**2 =   1 qr=0
  17/21 = .809523    17**2 =  16 qr=0
\end{verbatim}

\begin{verbatim}
n=27 b=10 p=3 f=18 r=6
   1/27 = .037     1**2 =   1 qr=1
  10/27 = .370    10**2 =  19 qr=1
  19/27 = .703    19**2 =  10 qr=1

   2/27 = .074     2**2 =   4 qr=0
  20/27 = .740    20**2 =  22 qr=0
  11/27 = .407    11**2 =  13 qr=0

   4/27 = .148     4**2 =  16 qr=1
  13/27 = .481    13**2 =   7 qr=1
  22/27 = .814    22**2 =  25 qr=1

   5/27 = .185     5**2 =  25 qr=0
  23/27 = .851    23**2 =  16 qr=0
  14/27 = .518    14**2 =   7 qr=0

   7/27 = .259     7**2 =  22 qr=1
  16/27 = .592    16**2 =  13 qr=1
  25/27 = .925    25**2 =   4 qr=1

   8/27 = .296     8**2 =  10 qr=0
  26/27 = .962    26**2 =   1 qr=0
  17/27 = .629    17**2 =  19 qr=0
\end{verbatim}


%% ----------------------------------------------------------------
\subsection{Data for $b=12$}

%% ----------------------------------------------------------------
\subsection{Data for $b=16$}

\begin{verbatim}
n=7 b=16 p=3 f=6 r=2
   1/7 = .249     1**2 =   1 qr=1
   2/7 = .492     2**2 =   4 qr=1
   4/7 = .924     4**2 =   2 qr=1

   3/7 = .6db     3**2 =   2 qr=0
   6/7 = .db6     6**2 =   1 qr=0
   5/7 = .b6d     5**2 =   4 qr=0
\end{verbatim}

\begin{verbatim}
n=9 b=16 p=3 f=6 r=2
   1/9 = .1c7     1**2 =   1 qr=1
   7/9 = .c71     7**2 =   4 qr=1
   4/9 = .71c     4**2 =   7 qr=1

   2/9 = .38e     2**2 =   4 qr=0
   5/9 = .8e3     5**2 =   7 qr=0
   8/9 = .e38     8**2 =   1 qr=0
\end{verbatim}

\begin{verbatim}
n=11 b=16 p=5 f=10 r=2
   1/11 = .1745d     1**2 =   1 qr=1
   5/11 = .745d1     5**2 =   3 qr=1
   3/11 = .45d17     3**2 =   9 qr=1
   4/11 = .5d174     4**2 =   5 qr=1
   9/11 = .d1745     9**2 =   4 qr=1

   2/11 = .2e8ba     2**2 =   4 qr=0
  10/11 = .e8ba2    10**2 =   1 qr=0
   6/11 = .8ba2e     6**2 =   3 qr=0
   8/11 = .ba2e8     8**2 =   9 qr=0
   7/11 = .a2e8b     7**2 =   5 qr=0
\end{verbatim}

\begin{verbatim}
n=13 b=16 p=3 f=12 r=4
   1/13 = .13b     1**2 =   1 qr=1
   3/13 = .3b1     3**2 =   9 qr=1
   9/13 = .b13     9**2 =   3 qr=1

   2/13 = .276     2**2 =   4 qr=0
   6/13 = .762     6**2 =  10 qr=0
   5/13 = .627     5**2 =  12 qr=0

   4/13 = .4ec     4**2 =   3 qr=1
  12/13 = .ec4    12**2 =   1 qr=1
  10/13 = .c4e    10**2 =   9 qr=1

   7/13 = .89d     7**2 =  10 qr=0
   8/13 = .9d8     8**2 =  12 qr=0
  11/13 = .d89    11**2 =   4 qr=0
\end{verbatim}

\begin{verbatim}
n=19 b=16 p=9 f=18 r=2
   1/19 = .0d79435e5     1**2 =   1 qr=1
  16/19 = .d79435e50    16**2 =   9 qr=1
   9/19 = .79435e50d     9**2 =   5 qr=1
  11/19 = .9435e50d7    11**2 =   7 qr=1
   5/19 = .435e50d79     5**2 =   6 qr=1
   4/19 = .35e50d794     4**2 =  16 qr=1
   7/19 = .5e50d7943     7**2 =  11 qr=1
  17/19 = .e50d79435    17**2 =   4 qr=1
   6/19 = .50d79435e     6**2 =  17 qr=1

   2/19 = .1af286bca     2**2 =   4 qr=0
  13/19 = .af286bca1    13**2 =  17 qr=0
  18/19 = .f286bca1a    18**2 =   1 qr=0
   3/19 = .286bca1af     3**2 =   9 qr=0
  10/19 = .86bca1af2    10**2 =   5 qr=0
   8/19 = .6bca1af28     8**2 =   7 qr=0
  14/19 = .bca1af286    14**2 =   6 qr=0
  15/19 = .ca1af286b    15**2 =  16 qr=0
  12/19 = .a1af286bc    12**2 =  11 qr=0
\end{verbatim}

\begin{verbatim}
n=21 b=16 p=3 f=12 r=4
   1/21 = .0c3     1**2 =   1 qr=1
  16/21 = .c30    16**2 =   4 qr=1
   4/21 = .30c     4**2 =  16 qr=1

   2/21 = .186     2**2 =   4 qr=0
  11/21 = .861    11**2 =  16 qr=0
   8/21 = .618     8**2 =   1 qr=0

   5/21 = .3cf     5**2 =   4 qr=0
  17/21 = .cf3    17**2 =  16 qr=0
  20/21 = .f3c    20**2 =   1 qr=0

  10/21 = .79e    10**2 =  16 qr=0
  13/21 = .9e7    13**2 =   1 qr=0
  19/21 = .e79    19**2 =   4 qr=0
\end{verbatim}

\begin{verbatim}
n=27 b=16 p=9 f=18 r=2
   1/27 = .097b425ed     1**2 =   1 qr=1
  16/27 = .97b425ed0    16**2 =  13 qr=1
  13/27 = .7b425ed09    13**2 =   7 qr=1
  19/27 = .b425ed097    19**2 =  10 qr=1
   7/27 = .425ed097b     7**2 =  22 qr=1
   4/27 = .25ed097b4     4**2 =  16 qr=1
  10/27 = .5ed097b42    10**2 =  19 qr=1
  25/27 = .ed097b425    25**2 =   4 qr=1
  22/27 = .d097b425e    22**2 =  25 qr=1

   2/27 = .12f684bda     2**2 =   4 qr=0
   5/27 = .2f684bda1     5**2 =  25 qr=0
  26/27 = .f684bda12    26**2 =   1 qr=0
  11/27 = .684bda12f    11**2 =  13 qr=0
  14/27 = .84bda12f6    14**2 =   7 qr=0
   8/27 = .4bda12f68     8**2 =  10 qr=0
  20/27 = .bda12f684    20**2 =  22 qr=0
  23/27 = .da12f684b    23**2 =  16 qr=0
  17/27 = .a12f684bd    17**2 =  19 qr=0
\end{verbatim}

\end{document}
