\documentclass[12pt]{article}
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 

%\usepackage{sets}

\usepackage{amsmath, amssymb, amstext, amsbsy, amsopn, amsthm, amscd,
amsxtra, verbatim}

\newcommand{\spa}{\hspace*{15pt}}
\newcommand{\spac}{\hspace*{1.0cm}}
\newcommand{\up}{\!\uparrow\!}
\newcommand{\upup}{\!\uparrow\uparrow\!}
\newcommand{\zz}{\mathbb{Z}}
\newcommand{\uu}{\mathbb{U}}
\newcommand{\qq}{\mathbb{Q}}
\newcommand{\s}{\mathcal{S}}
\newcommand{\lcm}{\text{lcm}}
\newcommand{\ord}{\text{ord}}
\newcommand{\img}{\text{image}}
\newcommand{\dv}{\!\mid\!}
\newcommand{\ex}{\text{expon}}


\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}

\DeclareMathOperator*{\E}{\text{E}}
\DeclareMathOperator*{\EE}{\text{\huge{E}}}
\DeclareMathOperator*{\ee}{\text{\Large{E}}}

\makeatletter %% this should really go into a style file!

\renewcommand\section{\@startsection {section}{1}{\z@}%
                                 % {-3.5ex \@plus -1ex \@minus -.2ex}%
        % here is your vskip of 30pt:
                                   {-30pt  \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
        % add a point after section numbers:

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad}

\makeatother

\begin{document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A23}
\vskip 40pt
\begin{center}
\uppercase{\bf Iterated Exponents in Number Theory}
\vskip 20pt
{\bf Daniel B. Shapiro}\\
{\smallit Department of Mathematics, Ohio State University, Columbus, OH
43210}\\
{\tt shapiro@math.ohio-state.edu}\\ 
\vskip 10pt
{\bf S. David Shapiro}\\
{\smallit 1616 Lexington Ave \#D, El Cerrito, CA 94530}\\
{\tt gavelmaven@aol.com}\\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: 8/21/06,
Revised: 2/17/07, Accepted: 4/14/07,
 Published: 5/8/07}
\vskip 30pt 
\centerline{\bf Abstract}

\noindent
We show
that if $a_1, a_2, a_3, \dots$ is a sequence of positive integers
and $k$ is given, then the sequence $a_1, \; a_1^{a_2}, \;
a_1^{a_2^{a_3}}\!, \dots$ becomes constant when reduced (mod $k$).
We also consider the sequence $1^1,\; 2^2,\; 3^3,\dots \pmod{k}$,
showing that this sequence, and related ones like $n^{n^n}$ (mod
$k$), are eventually periodic.


\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
 JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A23\hfill}





\hfill{\it --Dedicated to the memory of Prof. Arnold Ross}

\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt


\section{Introduction}


What is  the units digit of a number like $7^{8^{9^{10}}}$?
Problems of this nature often appear on contests, and we consider
various generalizations in this article.  For instance we show
that if $a_1, a_2, a_3, \dots$ is a sequence of positive integers
and $k$ is given, then the sequence $a_1, \; a_1^{a_2}, \;
a_1^{a_2^{a_3}}\!, \dots$ becomes constant when reduced (mod $k$).
We also consider the sequence $1^1,\; 2^2,\; 3^3,\dots \pmod{k}$,
showing that this sequence, and related ones like $n^{n^n}$ (mod
$k$), are eventually periodic.  With further work we are able
determine their minimal periods.  Using those ideas we prove that
if $u$ is relatively prime to $k$ then the congruences $x^x \equiv
u \pmod{k}$ and $y^{y^y}\equiv u \pmod{k}$ have solutions.
Finally, we lift these ideas to the ring of $p$-adic integers and
pose some open questions.

The methods used here are part of elementary number theory and we
have attempted to present the ideas in as elementary a way as
possible.  The results proved here were originally obtained in
1985, but not published previously.

Many papers have been written about limits of the form
$x^{x^{x^{\cdot^{\cdot^\cdot}}}}$\!\!\!\!,  where  $x$  is a real
or complex number. In fact, such convergence questions go back to
Bernoulli, Goldbach and Euler. Results and references to the
literature appear in Anderson (2004), Knoebel (1981),  and Baker
and Rippon (1985). However, relatively little work has been done
on the arithmetic aspects of such numbers when $x$ is an integer.
Early work in this direction was done by Maurer (1901) and
Cunningham (1907). Fifty years later some related papers appeared
in Polish journals by Sierpi\'{n}ski (1950), Hampel (1955) and
Schinzel-Sierpi\'{n}ski (1959).  More recently Blakley-Borosh
(1983) and Dawson (1994) published further results about the
periodic behavior of these sequences modulo $k$. In this article
we unify and extend these arithmetic results.  In the first
sections below we have repeated some of the results of
Blakley-Borosh and Dawson  in order to have a self-contained
presentation and to clarify the notations.


%\setcounter{section}{0}
\section{Reducing Iterated Exponents  Modulo $k$}
\vspace*{-10pt}
The symbol  $\zz$  stands for the set of integers and  $\zz^+$ is
the subset of positive integers.  We assume the reader is familiar
with some elementary number theory.


\begin{definition} If  $a, b$  are positive integers,
define $a\up b = a^b$. These arrows are always associated to the
right if no parentheses are present:  $a\up b \up c = a\up {(b\up
c)}$. The related ``E'' notation  is defined in analogy with
``$\Sigma$'' for sums:
$$\EE\limits_{j=1}^sa_j \;\; = \;\; a_1\up a_2\up
\dots\up
a_s\;\;  =\;\;   a_1^{a_2^{.^{.^{.^{a_s}}}}}.$$
\end{definition}
\noindent
Recursively we can define: $ \ee\limits_{j=1}^s a_j = a_1\up
\left(\ee\limits_{j=2}^s a_j\right), \text{ if } s>1. $


The goal of this section is to investigate conditions on integer
sequences $\{a_j\}$ and $\{b_j\}$ which imply that
$a_1\up a_2\up  \dots \up a_s \equiv b_1\up b_2\up \dots \up
b_s$ (mod $k$).
To begin let's refine the usual definition of the \emph{order} of
an element (mod $k$) by allowing non-units.

\begin{definition}\label{orddef}  Given $n$ and $k$, the sequence
$1, n, n^2, n^3, \dots$ (mod $k$) is eventually periodic. The
\emph{order}, $o_k(n) = o(n\bmod k)$, is the length of that
periodic cycle. The \emph{tail length} $\rho_k(n)$ is the number
of terms in the sequence before the repeating cycle begins. (The
notations $\rho$ and $o$ are suggested by the shapes of those
letters.)
\end{definition}

For example the powers of 2 (mod 40) are 1, 2, 4, 8, 16, 32, 24,
8, 16, 32, \dots\ . The terms (1, 2, 4) form an initial ``tail''
so that $\rho_{40}(2) = 3$.  The repeating portion or ``cycle'' is
(8, 16, 32, 24), so that $o_{40}(2) = 4$.

\begin{lemma}\label{ordcong} Given positive integers $n$ and
$k$:\\
\spa (a) $\rho_k(n)$  and  $o_k(n)$  depend only on $n$
modulo  $k$.\\
%That is: \\
%\spac If $a \equiv b \pmod{k}$ \; then: \; $o_k(a) = o_k(b)$ \;
%and \; $\rho_k(a) = \rho_k(b)$.\\
\spa (b) If $r\neq s$, then
$n^r \equiv n^s \pmod{k} \; \iff \; r \equiv s \pmod {o_k(n)}$
\; and \; $r, s \geq \rho_k(n)$.
\end{lemma}

\begin{proof}
These statements follow from the definition.  For instance, for
(b), any repetition in the sequence $\{n^r \pmod{k}\}$ must
occur within the repeating cycle.
\end{proof}

When  $n$  is invertible (mod $k$), the sequence $1, n, n^2, n^3,
\dots  \pmod k$  is purely periodic.  Then the cycle length is the
first exponent which yields 1.  That is, $\rho_k(n) = 0$ and
$o_k(n) = \min\{d :\; d > 0$  and  $n^d \equiv 1 \pmod k\}$.



\begin{lemma}\label{ofactor}
Given  $k, n \in  \zz^+$, factor $k = k'(n)k''(n)$,  where $k'(n)$
and $n$ are coprime, and every prime factor of $k''(n)$ also divides $n$.\\
 \spa   (1)   $o_k(n) = o_{k'(n)}(n)$.\\
 \spa   (2) $\rho_k(n) =
\min\{r \in \zz :\; r\geq 0 \; \text{ and }\;   k''(n) \dv n^r
\}$.
\end{lemma}

\begin{proof}
The values $n^r \pmod{k'}$ are purely periodic while  $n^r\equiv 0
\pmod{k''}$ for all large $r$. This yields the expression for
$\rho_k(n)$. To check the length of the eventual cycle, note:  $n^t \equiv n^{t+w}$ for both moduli $k'$ and $k''$ if and only if $n^t \equiv n^{t+w}$ 
mod $k$.
\end{proof}

Suppose $n = p_1^{r_1}p_2^{r_2}\cdots p_t^{r_t}$, where the $p_i$
are distinct primes and every $r_i > 0$. Arrange the prime factors
of $k$ so that $k = p_1^{m_1}p_2^{m_2}\cdots p_t^{m_t}\cdots
p_u^{m_u}$, where $m_i\geq 0$.
Then $k''(n) = p_1^{m_1}p_2^{m_2}\cdots p_t^{m_t}$  %and $k' = p_{t+1}^{m_{t+1}}\cdots p_u^{m_u}$,
and $\rho_k(n) = \max\limits_{1\leq i \leq t}\{\lceil\frac{m_i}{r_i}\rceil \}$. \\
(Here, $\lceil x\rceil$ is the smallest integer $\geq x$.)


Euler proved that  $c^{\varphi(k)} \equiv 1 \pmod{k}$  for every
$c$ coprime to $k$. Here the Euler function  $\varphi(k)$  is the
number of elements in the group of units $\uu_k = (\zz/k\zz)^*$.
Equivalently, $\varphi(k)$ is the number of integers $c$ coprime
to $k$ with  $0 \leq c < k$. For our purposes, the \emph{smallest}
exponent for $\uu_k$ is a more important value.


\begin{definition}\label{lambdef}  For  $k \in \zz^+$  define  $\lambda(k)$
to be the smallest positive integer  $e$  such that $n^e \equiv 1
\pmod{k}$  for every $n$ coprime to  $k$.
Define  $R(k) = \max\{\rho_k(n) :\; 0 \leq n < k\}$.
\end{definition}

This $\lambda(k)$  is the ``exponent'' of the abelian group
$\uu_k$.  Carmichael (1910) showed how to compute $\lambda(k)$
from the prime factorization of $k$.


\begin{proposition}\label{lambda} Suppose  $k = p_1^{m_1}p_2^{m_2}\dots
p_t^{m_t}$ in prime factorization.  \\
(0) $R(k) = \max\{m_i\}$.\\
(1)  $\lambda(k)$ is the maximal order of an element in $\uu_k$.\;
If $d\dv k$ then $\lambda(d)\dv \lambda(k)$. \\
(2)  If $a, b$ are coprime, then $\lambda(ab) = \lcm
\{\lambda(a), \lambda(b)\}$;
In general, $\lambda\big(\lcm\{a, b\}\big)$\;
divides\;
\vskip -10pt \hskip 2pt
 $\lcm\{\lambda(a), \lambda(b)\}$.  \\
(3)  If  $p$  is an odd prime,  $\lambda(p^m) =
 p^{m-1}(p - 1)$. \\
(4) $\lambda(2) = 1,\; \lambda(4) = 2$,\; and\; $\lambda(2^m) =
2^{m-2}$ whenever $m \geq 3$.
\end{proposition}


\begin{proof} These results follow from the ideas used to determine
which of the groups $\uu_n$ are cyclic.  Key steps in an
elementary proof are: \\
\spa (i) If $x, y \in \uu_m$, there exists $z \in \uu_m$ with
$o_k(z) = \lcm\{o_k(x),
o_k(y)\}$.\\
\spa (ii) If $p$ is an odd prime, there is an element of order
$p^{m-1}$ in $\uu_{p^m}$.\\
\spa (iii) There is an element of order $2^{m-2}$ in $\uu_{2^m}$
whenever $m \geq 3$.\\
Further information appears in many references, like [Carmichael:
1910], [Vinogradov: 1954] pp. 106-107, or [H. Shapiro: 1983]
Theorems 6.2.2 and 6.3.1.

For part (2), when $a, b$ are coprime apply the Chinese Remainder
Theorem. For the general case, factor $\lcm\{a, b\} = a'b'$ where
$a'\dv a,\; b'\dv b\;$ and \;$a', b'$ are coprime.  Then
$\lambda(\lcm\{a, b\}) = \lambda(a'b') = \lcm\{\lambda(a'),
\lambda(b')\}$ divides $\lcm\{\lambda(a), \lambda(b)\}$.
\end{proof}


As a corollary we see that  $\lambda(k)$  and  $R(k)$  are the $o$
and  $\rho$ for everything in $\zz/k\zz$,  taken simultaneously.

%  That is, they are the $o$ and  $\rho$  of the sequence of
%  $k$-tuples $(0^s, 1^s, 2^s, . . . , (k - 1)^s)$  as $s = 1, 2, 3, \dots$ .

\begin{corollary}\label{lambdacong}  Let  $k$  be a positive integer.\\
 \spa   (1)  For every  $n \in \zz,\;  o_k(n)\dv \lambda(k)$
 and  $\rho_k(n) \leq R(k)$.\\
 \spa   (2)  Let  $a, b$  be nonnegative integers.
 Then\\
   $n^a \equiv n^b$ (mod $k$)\;  for every   $n   \;\iff\;
 \begin{cases} \text{ either } \;\,   a = b,\\
   \quad \text{ or } \quad  a \equiv b \pmod{\lambda(k)} \;
   \text{ and }\; a, b \geq R(k).
 \end{cases}$
\end{corollary}


\begin{proof} (1)  $o_k(n) = o_{k'}(n)$  which divides
$\lambda(k')$. Since $k' \dv k$  we apply (\ref{lambda})(2) above.
(2) Apply Lemma \ref{ordcong}.
\end{proof}


Consequently, the mod $k$ reduction of, say, $a_1^{a_2^{a_3}} =
a_1\up a_2\up a_3$  should depend only on the residues of $a_1$\!
(mod $k$), of $a_2\! \pmod{\lambda(k)}$ and of $a_3$ (mod
$\lambda(\lambda(k))$). For example, since $\lambda(\lambda(8)) =
1$, this \emph{ought} to imply that the value of\; $a_1 \up a_2\up
x \pmod{8}$ is \emph{independent} of the choice of $x$.  However
$2^{2^1} \not\equiv 2^{2^2}$ (mod 8).  This happens because the
value $2^{2^1}=4$ lies in the ``tail'' rather than the ``cycle''.
The next few results detail the inequalities needed to avoid this
problem.  To simplify notations, define $\lambda^r$ recursively by setting $\lambda^0(k) = k$ and $\lambda^r = \lambda\circ \lambda^{r-1}$ for $r>0$.

\begin{lemma}\label{lambdaineq}
Suppose  $a_r \equiv b_r \pmod{\lambda^{r-1}(k)}$  for  $r
= 1, \dots , s$.  Then 
$\ee\limits_{i=1}^s a_i  \equiv
\ee\limits_{i=1}^s b_i \pmod{k}$, 
provided $\ee\limits_{i=r+1}^s \!a_i$   and $\ee\limits_{i=r+1}^s
\!b_i$ are $\geq R(\lambda^{r-1}(k))$ whenever $1 \leq r < s$.
\end{lemma}


\begin{proof}
Induction on  $s$  using Corollary \ref{lambdacong}.
\end{proof}



\begin{proposition}\label{lambdineq}
Suppose  $a_r \equiv b_r \pmod{\lambda^{r-1}(k)}$ for  $r = 1,
\dots, s$.  Suppose further that\; $a_r, b_r \geq 2$ for $1 < r
\leq s$;\; and $a_s, b_s \geq R(\lambda^{s-2}(k))$.  Then
$\EE\limits_{i=1}^s a_i \equiv \EE\limits_{i=1}^s
b_i \pmod{k}$.
\end{proposition}


\begin{proof} It suffices to verify the inequalities in
(\ref{lambdaineq}).  The case  $r = s - 1$ is assumed.
The other inequalities  follow by repetition of the following claim.\\
\textbf{Claim:} If $a \geq 2$  and  $a \geq
R(\lambda(k))$ then $2^a \geq R(k)$. 
This is clear when $R(k) \leq 4$  since $2^a \geq 2^2 = 4$. If
$R(k) > 4$ the definitions imply that $R(\lambda(k)) \geq R(k)
- 2$. Since $2^{x-2} \geq x$ whenever  $x \geq 4$ we find that
$2^a \geq 2^{R(k)-2} \geq R(k)$.
\end{proof}


%These ideas answer a 1981 question:  Suppose $b, n \in \zz^+$
%with  $n \geq 2$.  \\
%Does  $b^k \equiv k \pmod{10^n}$ imply $b^{b^k} \equiv b^k
%\pmod{10^{n+1}}$.   See [D. B. Shapiro : 1987].
%
%
%  There is an example in Z_p:
% p = 97 is prime with h(p) = 4:
%          \lambda(p) = 96 = 32*3  and  |lambda^2(p)= 8.
% Check  o(5 mod 96) = 8  and  5^4 \equiv 49 (mod 96).
%  Then 5^2^2 \equiv 49 (mod 96)  while  5^2^2^2 \equiv 1 (mod 96).
% Then  5^5^2^2  and 5^5^2^2^2 are different (mod 97),
%   since  5  is a quadratic nonresidue (mod 97).


\begin{definition}\label{height}  For  $k \in \zz^+$  the \emph{height}  of
$k$  is  $h(k) = \min \{s : \lambda^s(k) = 1\}$.
\end{definition}

Checking small cases we find:  $h(k) = 0 \iff k = 1; \;\;  h(k) = 1
\iff k = 2$;\; and\;  $h(k) = 2 \;\iff\; k = 3, 4, 6, 8, 12$ or
24.

\begin{corollary}\label{stab}  If  $a_j \in \zz^+$,  then  the towers
$a_1\up a_2 \up \cdots \up a_{h(k)} \up c$ reduce to the same
value in $\zz/k\zz$, for every $c > 1$.  Consequently, $a_1\up a_2
\up \cdots \up a_s \up x \pmod{k}$ is independent of the value of
$x \in \zz^+$, provided $s > h(k)$.
\end{corollary}

\begin{proof}  If  $a_j = 1$  for some  $j \leq h(k)$,  the result is
trivial, so assume all  $a_j \geq 2$.  Compare two such towers
differing only in the top entries $a_{h(k)+1} = c$ by checking
the conditions in (\ref{lambdineq}) when $s = h(k)+1$.  They all
hold provided $c \geq 2$. The second statement follows using $c =
a_{h(k)+1}\up \cdots \up a_s\up x$.
\end{proof}


Thus, for any   sequence  $\{a_j\} \subseteq \zz^+$ and $k \in
\zz^+$, the sequence of ``partial powers'' $\ee_{i=1}^s a_i$
becomes stable (mod $k$) as $s$ increases;   all terms with $s >
h(k)$ are congruent (mod $k$).




\section{The Sequences  $n \upup t  \pmod{k}$}

Define the double-arrow  $n \upup t$ to be $\ee_{i=1}^t(n)$, an
exponential ladder of  $t$  $n$'s.  Then $n \upup 0 = 1,\;  n
\upup 1 = n,\; n \upup 2 = n^n$,\;  etc.  This is part of the
arrow notation as defined in Knuth (1976).

For a fixed modulus  $k$,  Hampel (1955) showed that the sequence
$1^1, 2^2, 3^3, \dots \pmod{k}$ is eventually periodic and
determined its minimal period.  In this section we generalize that
result, showing for any $t \geq 0$, the sequence $1 \upup t,\;
2\upup t,\; 3\upup t, \dots$ is eventually periodic (mod $k$), and
computing its minimal period, $L_t(k)$.

For fixed $k$ and $n$,  the sequence $n,\; n^n,\; n^{n^n},\;
n\upup4,  \dots$  eventually becomes constant
(mod $k$). In fact, Corollary \ref{stab} implies that
$n \upup t \equiv n \upup (t + 1) \pmod{k}$ 
whenever $t > h(k)$.
The ``stable value'' $\overline{\alpha}_k(n)$ of this
sequence $n \upup t \pmod{k}$ is a well defined element of
$\zz/k\zz$.  However, it is best to define a positive integer
representing this value, since we will also use it as an exponent.

\begin{definition}  For  $k, n \in \zz^+$   let
$\alpha_k(n) = n \upup{(1 + h(k))}$. This is defined recursively
by:\; $\alpha_1(n) = n$  and  $\alpha_k(n) =
n\up\alpha_{\lambda(k)}(n)$ for every $k \geq 2$.
\end{definition}

Then $\alpha_k(n) \equiv n \upup t  \pmod{k}$ for
every $t > h(k)$, and we may consider this value in $\zz/k\zz$
as the ``infinite tower'' of exponents:\\
\hspace*{6cm}  $\alpha_k(n)\; \equiv \;
n^{n^{^{n{^{\cdot{^{\cdot^{\cdot}}}}}}}} \pmod{k}$.


\begin{corollary}\label{fix}
If  $k, n \in \zz^+$  then  $x = \alpha_k(n)$  satisfies  $x
\equiv n^x \pmod{k}$.
\end{corollary}

\begin{proof} With  $t = 1+ h(k)$, Corollary \ref{stab}
implies  $x = n \upup t \equiv n \upup (t + 1) \equiv 
n\up(n \upup t) = n^x \pmod{k}$.
\end{proof}



Let's examine a few numerical cases.  Table 1 lists the sequences
$\alpha_k(n)$  reduced to their least nonnegative residues modulo
$k$,  for the first few values of  $k$  and  $n$.


{\scriptsize
\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{1.2}   %vertical space stretch factor.
\begin{tabular}{c|p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}
p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}
p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}p{1.5pt}}
 $k$ $\backslash^{\text{\scriptsize $n$}}$ & 1  &  2 &  3  & 4 &  5  &
 6  & 7  & 8  & 9 &  10 & 11 &
12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23\\
\hline 2 & (1 &  0) & 1 &  0  & 1 &  0 &  1 &  0 &  1 &  0 &  1  &
0 & 1  & 0 &  1 &  0 &  1 &  0 &  1  & 0   & 1  & 0  &
    1\\
3  & (1 & 1  & 0  & 1 &  2  &  0) & 1 &  1 &  0 &  1 &  2  & 0 & 1
& 1 &  0  & 1 &  2 &  0 &  1  & 1   & 0  & 1  &
    2\\
4  & (1 & 0  & 3  &  0)& 1  & 0  & 3 &  0 &  1 &  0   & 3  &  0 &
1  & 0  & 3  & 0 &  1 &  0 &  3  & 0   & 1  & 0 &
    3\\
5  & (1 & 1 &  2  & 1  & 0  & 1  & 3 &  1  & 4 &  0 &  1  & 1 &  3
& 1 &  0 &  1 &  2  & 1  & 4  &   0)& 1  & 1 &
    2\\
6  & (1 & 4  & 3  & 4  & 5  &  0) &  1 &  4  & 3 &  4 &  5 &  0 &
1  & 4 &  3  & 4 &  5  & 0 &  1  & 4  & 3 &  4 &
    5\\
7  & (1 & 2  & 6 &  4 &  3 &  1  & 0  & 1 &  1  & 4  & 2 &  1 &  6
&  0 &  1  & 2 &  5  & 1 &  5  & 1  & 0 &  1 &
    4\\
8  & (1 & 0 &  3 &  0 &  5  & 0 &  7  & 0)  &  1 &  0 &  3  & 0  &
5  & 0  & 7 &  0&   1 &  0  & 3 &  0 &  5 &  0 &
    7\\
9  & (1 & 7  & 0 &  4  & 2  & 0 &  7 &  1 &  0 &  1 &  5 &  0 &  4
&  4  & 0 &  7 &  8   &  0) &  1 &  7 &  0 &  4 &
    2\\
\end{tabular}\\[5pt]
\caption{\small The  $(k,n)$-entry is \ $\alpha_k(n)  \pmod{k}$.}
\end{center}
\end{table}   }


Here $k$ indexes the rows and $n$ indexes the columns. Parentheses
indicate the first repeating block of each sequence.


As one example let's calculate the residue of  $\alpha_7(5)$ (mod
7). First check that  $h(7) = 3$  (since  $\lambda(7) = 6, \;
\lambda^2(7) = 2$  and   $\lambda^3(7) = 1$). By definition,
$\alpha_7(5) =$ \linebreak $5 \upup 4 = 5^{5^{5^5}}$, a number of
more than $2\cdot 10^{17}$ digits. To reduce it modulo 7 we first
compute that  $5 \upup 3 \equiv 5^{5^5} \equiv (-1)^{5^5} \equiv
-1 \equiv 5 \pmod{6}$.  Conclude from (\ref{lambdacong}) that
$\alpha_7(5) \equiv 5^5 \equiv 3 \pmod{7}$. Further values for $k
= 7$ appear in Table 2 below. These calculations suggest that the
sequence $\alpha_k(n) \pmod{k}$ is always periodic (with no tail).
The minimal periods $L(k)$ are: $L(1) = 1,\; L(2) = 2,\; L(3) =
6,\; L(4) = 4,\; L(5) = 20,\; L(6) = 6,\; L(7) = 42,\; L(8) = 8,\;
L(9) = 18$. Our goal is to find a simple formula for these
periods.

Proposition \ref{lambdineq} shows that the sequences $\{n \upup t
\pmod{k}\}$ are eventually periodic and provides natural
candidates for their periods.


\begin{lemma}\label{lcm}  Suppose  $k, t > 0$  are given and let $L = \lcm\{k, \lambda(k), \lambda^2(k), \dots ,
\lambda^{t-1}(k)\}$, the least common multiple.
If  $t \geq 2$ and integers  $a, b$ satisfy
$a, b \geq R(\lambda^{t-2}(k))$,  then
$a \equiv b \pmod{L}$   implies  $a \upup t
\equiv b \upup t \pmod{k}$.
\end{lemma}

\begin{proof}  If  $a \equiv 1$  or  $b \equiv 1
\pmod{k}$  the conclusion is trivial, so we may assume  $a, b \geq
2$.  By hypothesis, $a \equiv b \pmod{\lambda^{r-1}(k)}$ for  $r =
1, 2, . . . , t$. The implication now follows from Proposition
\ref{lambdineq}.
\end{proof}

\begin{comment}
For example, let  $k = 23$ and note that  $\widetilde{L}_1(23) =
23,\; \widetilde{L}_2(23) = \lcm\{23, 22\} = 506,\;
\widetilde{L}_3(23) = \lcm\{23, 22, 10\} = 2530$ and
$\widetilde{L}_4(23) = \widetilde{L}(k)  = \lcm\{23, 22, 10, 4\} =
5060$.
\end{comment}

\begin{definition}\label{Ldef}  For  $k, t \in \zz^+$, let $L_t(k)$
be the minimal period of the eventually periodic sequence $\{n
\upup t \pmod{k}\}$.
Let  $L(k)$ be the minimal period of the periodic sequence
$\{\alpha_k(n) \pmod{k}\}$.
\end{definition}



Observe that (\ref{stab}) implies   $L_t(k) = L(k)$  whenever  $t
\geq h(k)$. Also $L_1(k) = k$ for all  $k$. Moreover, by
(\ref{lcm}),\;  $L_t(k)$ divides \; $\lcm\{k, \lambda(k),
\lambda^2(k), \dots , \lambda^{t-1}(k)\}$, since any period is a
multiple of the minimal period.

\begin{theorem}\label{minper}   $L_t(k)  =  \lcm\{k, \lambda(k),
\lambda^2(k), \dots , \lambda^{t-1}(k)  \}$.
\end{theorem}


The proof of this theorem is preceded by several lemmas. Our
strategy is to compute $L_t(k)$ when $k$ is a prime power, then to
glue these formulas together using the next lemma.

\begin{lemma}\label{Llcm}  (i)  If  $d\dv k$  then  $L_t(d)\dv L_t(k)$;
(ii)   $L_t\big(\lcm\{k_1,k_2\}\big) =
\lcm\{L_t(k_1), L_t(k_2)\}$; \linebreak
(iii) $\lambda^s(\lcm\{a, b\})$ \ divides \
$\lcm\{\lambda^s(a),
\lambda^s(b)\}$. 
\end{lemma}

\begin{proof}  (i)  If  $a \equiv b \pmod{L_t(k)}$
and  $a, b$  are large then  $a \upup t \equiv b \upup t
\pmod{k}$.  Then if $d\dv k$,  the sequence $\{n \upup t
\pmod{d}\}$ has $L_t(k)$ as a period. Hence the minimal period
$L_t(d)$ divides $L_t(k)$.

(ii)  Let  $l = \lcm\{k_1, k_2\}$  and $m = \lcm\{L_t(k_1),
L_t(k_2)\}$. Part (i) implies that  $m\dv L_t(l)$. Conversely
suppose  $a \equiv b \pmod{m}$  and  $a, b$ are large. Then $a
\equiv b \pmod{L_t(k_j)}$,  implying   $a \upup t \equiv b \upup t
\pmod{k_j}$ for $j = 1, 2$. Then the congruence holds (mod $l$),
and the minimal period $L_t(l)$  divides $m$.

(iii) This property of $\lambda$ follows by repeated application
of (\ref{lambda})(2).
\end{proof}

\begin{lemma}\label{Llem2}  If  $p$  is prime then  $p^m\dv L_t(p^m)$.
\end{lemma}

\begin{proof}
We may assume  $t \geq 2$.  It is easy to check that $p\dv
L_t(p)$, since $n \upup t  \equiv 0 \pmod{p}$  iff  $n \equiv 0
\pmod{p}$. Suppose $m > 1$. By induction  $p^{m-1}\dv
L_t(p^{m-1})$ so it also divides $L_t(p^m)$.  Then $L_t(p^m) =
p^{m-1}y$ for some  $y$,  and we want to prove $p\dv y$.  By
definition of $L_t$  we have $(n + p^{m-1}y) \upup t \equiv n
\upup t \pmod{p^m}$ whenever  $n \geq R(\lambda^{t-2}(p^m) )$.
We use $n = 1 + p^m$, which does satisfy that inequality.
Setting $r = (1 + p^m + p^{m-1}y) \upup (t - 1)$, the congruence becomes:\\
\spac $(1 + p^{m-1}y)^r\equiv  (1 + p^m + p^{m-1}y)\upup t
    \equiv (1 + p^m )\upup t  \equiv 1 \pmod{p^m}$.\\
The binomial
theorem then implies $1 + rp^{m-1}y \equiv 1 \pmod{p^m}$,  so that
$ry \equiv 0 \pmod{p}$. Since $r \equiv 1 \pmod{p}$,  we get $p\dv
y$ as claimed.
\end{proof}


\begin{lemma}\label{Llem3}  If  $p$  is prime and  $t \geq 2$  then
$L_{t-1}(p - 1)\dv L_t(p)$.
\end{lemma}

\begin{proof}  For  $\ell = L_t(p)$, we have $(n+\ell)
\upup t\;\equiv\; n\upup t \pmod{p}$, for every large $n$.
Since $p\dv \ell$ we find:
$n\up((n+\ell)\upup(t-1)) \;\equiv\; (n+\ell)\upup t
\;\equiv\; n\upup t \;\equiv\;
n\up(n\upup(t-1)) \pmod{p}$, 
provided $n \geq R(\lambda^{t-2}(p))$. Suppose $g$ is a generator
of the group $\uu_p$.  Then for any large $n$ with $n \equiv g
\pmod{p}$, the previous congruence implies:

\hspace*{2.8cm}  $(n+\ell)\upup(t -1) \equiv n\upup(t-1)
\pmod{p-1}$.
\hspace*{2.3cm}(*)

Consequently, (*) holds for any large  $n$ of the form $n = g + px
+ wy$,  where $w = L_{t-1}(p - 1)$.  Note that $w$ and $p$ are
coprime, since $w$ divides $\lcm\{p - 1, \lambda(p - 1), \dots
\}$.  Therefore, congruence (*) holds for all large integers $n$,
so that the minimal period $w$ must divide $\ell$.
\end{proof}


\begin{lemma} \label{Llem4} If $p$ is prime, and $t \geq 2$, then
$$\lcm\{p^m, \lambda(p^m), \dots, \lambda^{t-1}(p^m)\} \; =
\; \lcm\{p^m, p-1, \lambda(p-1), \dots, \lambda^{t-2}(p-1)\}.$$
\end{lemma}

\begin{proof} If $p = 2$ both sides equal $2^m$.  Suppose $p$
is odd.  Since $(p-1) \dv \lambda(p^m)$, (\ref{lambda})(1) implies
$\lambda^{r-1}(p-1) \dv \lambda^r(p^m)$, and the right side
divides the left.  To prove:  $\lambda^{r}(p^m)$ divides the right
side, whenever $0\leq r < t$. This is easy for $r = 0, 1$, so
assume $r>1$ and use induction. Since $\lambda^{r}(p^m) =
\lambda^{r-1}(p^{m-1}(p-1))$ divides $\lcm\{\lambda^{r-1}(p^{m-1}),
\lambda^{r-1}(p-1)\}$, by (\ref{Llcm})(iii), we may apply the
induction hypothesis to complete the proof.
\end{proof}

\begin{proof}[Proof of Theorem \ref{minper}.]  We prove this statement by
induction on $k$.  The formula for $k = 1$ is trivial, so we
assume $k > 1$ and that the formula for $L_t(a)$ holds true for
every $a < k$.

First suppose $k = p^m$ is a prime power.  We want to prove that
$L_t(p^m)$ equals the quantity in Lemma \ref{Llem4}, which we call
 $M$ here. As mentioned after (\ref{Ldef}), $L_t(p^m)$ divides $M$. By
induction, $L_{t-1}(p-1) = \lcm\{ p-1, \lambda(p-1), \dots,
\lambda^{t-2}(p-1) \} $, so that $M = \lcm\{ p^m, L_{t-1}(p-1)
\}$.  The fact that $M$ divides $L_t(p^m)$ now follows from
(\ref{Llem2}), (\ref{Llem3}) and (\ref{Llcm})(i).  Hence $L_t(p^m)
= M$.

Proceeding by induction for arbitrary $k$, we may assume that $k
> 1$ is not a prime power.  Then there is a factorization $k = ab$
where $a, b$ are coprime and \mbox{$a, b < k$.}  As noted before,
$L_t(k)$ divides the quantity $u = \lcm\{ k, \lambda(k), \dots, \lambda^{t-1}(k) \}$.  Since $k = ab$, (\ref{Llcm})(iii) implies that $u$ divides
$\lcm\{ a, b, \lambda(a), \lambda(b), \dots, \lambda^{t-1}(a),
\lambda^{t-1}(b) \}$. The induction hypothesis implies that
this last quantity equals $\lcm\{ L_t(a), L_t(b) \}$, which equals
$L_t(ab) = L_t(k)$ by (\ref{Llcm})(ii), since $a, b$ are coprime.
Then all the terms in this divisor chain are equal and the Theorem
follows.
\end{proof}




\begin{corollary}\label{Lthm} (1) If $p$ is prime then $L_t(p^m) =
\lcm\{ p^m, L_{t-1}(p-1) \}$;
(2)  $L_t(k) \; = \; \lcm\{ k, L_{t-1}(\lambda(k)) \} \; = \;
 \lcm_{p|k}\{k, L_{t-1}(p - 1)\}$.
\end{corollary}


\begin{proof}  By this notation we mean that if  $k = p_1^{m_1} p_2^{m_2}
\dots p_s^{m_s}$ is the prime factorization of  $k$  then  $L_t(k)
= \lcm\{k, L_{t-1}(p_1 - 1), \dots ,  L_{t-1}(p_s - 1)\}$. These
formulas follow from (\ref{Llem4}) and Theorem \ref{minper}.
\end{proof}



\begin{corollary}\label{Lproperties}
The period $L(k)$ of the sequence $\overline{\alpha}_k(0),
\overline{\alpha}_k(1), \overline{\alpha}_k(2),
, \dots$ in $\zz/k\zz$ has the following properties:\\
(1) $L(k) = \lcm\{k, \lambda(k),
\lambda^2(k), \dots\}=\lcm_{p|k}\{k, L(p-1)\}$;\\
(2)  If $d\dv k$ then $L(d)\dv L(k)$.
Moreover, $L\big(\lcm\{a,b\}\big) \;=\; \lcm\{L(a), L(b)\}$ and
$L(mn) = \lcm\{mn, L(m), L(n)\}$. \\
(3)  The periods $k = L_1(k),  L_2(k),  \dots , L(k)$
form a divisor chain 
(each term divides the next).\\
(4)  $L\big(\lambda(k)\big)$  divides  $L(k)$. \\
(5)  $L(L(k)) = L(k)$.\\  %In fact, $L_t(L(k)) = L(k)$  for every $t$.
(6)  $L(k) = k\;  \iff\; \lambda(k)\dv k \; \iff\;$  for prime
$p$,\; $p\dv k$ \;implies\;  $(p - 1)\dv k$.
\end{corollary}


\begin{proof}  (1) Use Theorems \ref{minper} and \ref{Lthm},
noting that $L(k) = L_t(k)$ whenever $t \geq h(k)$.  The other
parts follow from (1).  For instance, for (6) note that (1)
implies: $L(k) = k$ if and only if every $\lambda^r(k)\dv k$. By
(\ref{lambda})(1), that is equivalent to: $\lambda(k)\dv k$. The
formula for $\lambda(k)$ in (\ref{lambda}) implies that this
occurs exactly when $(p-1)\dv k$ for every prime factor $p$ of
$k$.
\end{proof}




The sequence  $\alpha_k(n)  \pmod{k}$  was viewed as a mapping
$\overline{\alpha}_k : \zz^+ \to \zz/k\zz$.  Knowing the
periodicity we  re-interpret it (with some abuse of notation)
as a map
$\overline{\alpha}_k : \zz/L(k)\zz \; \to \;
\zz/k\zz.$
This observation explains how to make sense of
$\overline{\alpha}_k(n)$ for negative values of $n$.


\begin{proposition}  (i)  $\overline{\alpha}_k(0) = 0$  and
$\overline{\alpha}_k(-1) = -1$. \\
(ii)  If $n$ is even then  $\overline{\alpha}_k(-n) =
\overline{\alpha}_k(n)$.\\
 (iii) If  $n \in \uu_{L(k)}$ is a unit, then  $\overline{\alpha}_k(-n) =
 -\overline{\alpha}_k(n^{-1})$.
 \end{proposition}


\begin{proof}  Assume  $k > 1$  so that  $L = L(k)$  is even.
(i)  Note that $\overline{\alpha}_k(-1) = \overline{\alpha}_k(L -
1) = (-1)^s$ in $\zz/k\zz$, where $s = a_{\lambda(k)}(L - 1)$  is
odd.

(ii) Induct on  $k$.  By the periodicity we may assume $0
\leq n < L$.  Then  $\overline{\alpha}_k(-n) \equiv \alpha_k(L -
n) \equiv (L - n)^s \equiv (-n)^s \pmod{k}$, where  $s =
\alpha_{\lambda(k)}(L - n)$. Since  $n$ and $L$ are even, $s$ is
even and $\overline{\alpha}_k(-n) \equiv n^s \pmod{k}$. Since  $L$
is a multiple of $L(\lambda(k))$, we have $s \equiv
\overline{\alpha}_{\lambda(k)}(-n) \pmod{\lambda(k)}$. Applying
the induction hypothesis we find $s \equiv \alpha_{\lambda(k)}(n)
\pmod{\lambda(k)}$ and therefore $\overline{\alpha}_k(-n) \equiv
\overline{\alpha}_k(n) \pmod{k}$, as claimed.

(iii)  Using a similar strategy (but with less detail),  we have
$\overline{\alpha}_k(n^{-1}) \equiv n^{-1}\up s
\equiv
n\up(-s) \pmod{k},$
where $s \equiv \overline{\alpha}_{\lambda(k)}(n^{-1})
\pmod{\lambda(k)}$. By induction $s \equiv
-\overline{\alpha}_{\lambda(k)}(-n) \pmod{\lambda(k)}$. Then since
$n$ is odd, $\overline{\alpha}_k(n^{-1}) \equiv n\up
\overline{\alpha}_{\lambda(k)}(-n) \equiv -\overline{\alpha}_k(-n)
\pmod{k}$. \end{proof}


It is interesting to look for patterns in tables of values of $\overline{\alpha}_k(n)$.
%          When  $k = p$  is a prime, the values
%          $\pm 1 \pmod{p}$  seem to occur especially often.
For example, here are the values of $\overline{\alpha}_7(n)$
arranged in rows of seven.  The period is $L(7) = 42$.\\[-.2cm]

{\small
\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{1.0}
\begin{tabular}{ccccccc}
    0  & 1 &  2 &  6  & 4 &  3 &  1\\
    0  & 1 &  1 &  4  & 2 &  1 &  6\\
    0  & 1 &  2 &  5  & 1 &  5 &  1\\
    0  & 1 &  4 &  1  & 4 &  2 &  6\\
    0  & 1 &  1 &  3  & 4 &  6 &  1\\
    0  & 1 &  2 &  4  & 1 &  2 &  6\\[5pt]
\end{tabular}
  \caption{\small  $\overline{\alpha}_7(n)$   for  $n = 0, 1, \dots , 41$.}
\end{center}
\end{table}
}



A number of patterns of  $\pm 1$'s  can be observed from such
charts. The simplest ones are easily explained.

\begin{proposition}\label{alphap}  Let  $p$  be an odd prime, and suppose
$n \not\equiv 0 \pmod{p}$.\\
\spa (i) If  $n \equiv 1 \pmod{p}$ then  $\alpha_p(n) \equiv 1
\pmod{p}$; if  $n \equiv -1 \pmod{p}$ then
$\alpha_p(n) \equiv (-1)^n  \pmod{p}$.\\
\spa  (ii)    If $p \nmid n$ and each prime factor of $p-1$ divides  $n$, then  $\alpha_p(n) \equiv 1  \pmod{p}$.
\end{proposition}



\begin{proof}  $\alpha_p(n) = n^s$  where  $s = \alpha_{p-1}(n)
\equiv n^t  \pmod{p - 1}$, for some large  $t$. (i)  Easy.
(ii) Since  $t$  is large,  $(p - 1)\dv n^t = s$ and the claim follows.
\end{proof}


This frequent occurrence of  $\pm 1$'s  doesn't happen for every
value of  $k$.  In the next section we will prove that when $L(k)
= k$,  the value  1  occurs only once in each period of
$\alpha_k(n)  \pmod{k}$.  For example, since $L(7) = 42$  we know
from Corollary \ref{Lproperties}(5) that $L(42) = 42$. Here is a
table of the values of $\overline{\alpha}_{42}(n)$, arranged in
rows of seven. Note that these values induce those of
$\overline{\alpha}_7(n)$ after reduction \hbox{(mod 7)}.


{\small
\begin{table}[h]
\begin{center}
\renewcommand{\arraystretch}{1.0}
\begin{tabular}{ccccccc}

    0  & 1  & 16 & 27 & 4  & 17 & 36 \\
    7  & 22 & 15 & 4  & 23 & 36 & 13 \\
    28 & 15 & 16 & 5  & 36 & 19 & 22 \\
    21 & 22 & 11 & 36 & 25 & 16 & 27 \\
    28 & 29 & 36 & 31 & 4  & 27 & 22 \\
    35 & 36 & 37 & 4  & 15 & 16 & 41 \\[5pt]
\end{tabular}
  \caption{\small  $\overline{\alpha}_{42}(n)$   for  $n = 0, 1,
\dots , 41$.}
\end{center}
\end{table}
}


\section{ Values Occurring in the Sequences}

Which values in  $\zz/k\zz$  are assumed by the sequence
$\overline{\alpha}_k(n)$ ? That is, for which  $a \in \zz^+$  does
there exist $n$ with  $\alpha_k(n) \equiv a \pmod{k}$? For
example, Table 1 shows that the sequence $\alpha_k(n)$ assumes all
the values in $\zz/k\zz$ when $k = 2, 3, 5, 7$. However, when $k =
4, 6, 8, 9$ some values are missed. An easy argument settles the
question when  $k$ is a prime, or more generally when $k$ and
$\lambda(k)$ have no prime factors in common.


\begin{lemma}\label{coprime}  Suppose  $k$  and  $\lambda(k)$  are coprime.
For any  $t \geq 1$  and any  $a \in\zz$,  there exists $n$
satisfying   $n \upup t  \equiv a \pmod{k}$.
\end{lemma}



\begin{proof}  If $t = 1$ the claim is trivial, so assume $t \geq 2$.
Note that  $R(k) = 1$.  By the Chinese Remainder Theorem there
exists  $n \in\zz^+$  such that $n \equiv a \pmod{k}$  and $n
\equiv 1 \pmod {\lambda(k)}$. Then $n \upup t = n \up n^m$ where
$m = n \upup (t - 2)$. Corollary \ref{lambdacong} implies:  $n
\upup t = n\up n^m \equiv a\up 1 \equiv a \pmod{k}$.
\end{proof}


Define the map  $E_t : \zz^+ \to \zz/k\zz$  by  $E_t(n) = n \upup
t$. It is not always surjective, but we will show that every $E_t$
is at least surjective on units.



Since $E_t$  is eventually periodic with period $L = L_t(k)$, we
can restrict to values  $n \geq R(k)$ to get an induced map
$\zz/L\zz \to \zz/k\zz$. Since $L\dv L(k)$ we can use the possibly larger
domain $\zz/L(k)\zz$ for all values of $t$.  Then $E_t$ induces
a map $\overline{E}_t : \zz/L(k)\zz \;\to\; \zz/k\zz$,\;
which restricts to a map  $\uu_{L(k)} \to \uu_k$. 
Here is a key observation: When $c$ is an exponent  coprime to
$\lambda(k)$ then $n^c \equiv 1 \pmod{k}$ implies $n \equiv 1
\pmod{k}$. Consequently, 
if $x, y \in \uu_k$ then $x^c \equiv y^c \pmod{k} \;
\Longrightarrow  x \equiv y \pmod{k}$.


\begin{proposition}\label{bijective2}  Suppose  $\lambda(k)\dv k$
so that  $k = L(k)$. Then for every  $t$, the map $\overline{E}_t
: \uu_k \to \uu_k$ is bijective.
\end{proposition}

\begin{proof}  Since  $\uu_k$  is a finite set it suffices to prove
$\overline{E}_t$ is injective.  The case  $t = 1$  is trivial so
assume $t \geq 2$. The initial cases  $k = 1, 2$  are also easy,
so we may assume $k > 2$ and use induction on  $k$.  From
$\lambda(k)\dv k$  we know  $\lambda(\lambda(k))\dv \lambda(k)$
and the induction hypothesis implies   $\overline{E}_t :
\uu_{\lambda(k)} \to \uu_{\lambda(k)}$  is injective.  Suppose $x,
y \in \uu_k$ and $E_t(x) \equiv E_t(y) \pmod{k}$. Then this
congruence holds (mod $\lambda(k)$) so that  $x \equiv y
\pmod{\lambda(k)}$, by induction.  Since $L_{t-1}(\lambda(k)) =
\lambda(k)$ by (\ref{Lproperties}) we find that $E_{t-1}(x) \equiv
E_{t-1}(y) \pmod{\lambda(k)}$. Letting  $c = E_{t-1}(x)$ we have
$x^c \equiv E_t(x) \equiv E_t(y) \equiv y^c \pmod{k}$. From the
key observation above we conclude that $x \equiv y \pmod{k}$.
\end{proof}

\begin{comment}
There doesn't seem to be a simple formula for the
inverse function of $\overline{E}_t$ here.  When $t = 2$  the
inverse is given by $\delta_2(a) \equiv -\alpha_k(-a)^{-1}
\pmod{k}$.  The proof is left to the reader.
\end{comment}

\begin{corollary}\label{surjec}  For any  $k$,  the restriction
$\overline{E}_t : \uu_{L(k)} \to \uu_k$ is surjective. In
particular, the map $\overline{\alpha}_k : \zz^+ \to \zz/k\zz$
induces a surjective map $\overline{\alpha}_k : \uu_{L(k)} \to
\uu_k$.
\end{corollary}

\begin{proof}  Let  $a \in \uu_k$.  Since  $k\dv L(k)$  we can
choose $b \in \uu_{L(k)}$ with $b \equiv a \pmod{k}$.  Since
$L(L(k)) = L(k)$ by (\ref{Lproperties}), Proposition
\ref{bijective2} provides  $n \in \uu_{L(k)}$ with
$\overline{E}_t(n) \equiv b \pmod{L(k)}$. Reducing this congruence
shows that $\overline{E}_t(n) \equiv a \pmod{k}$.  The final
statement follows since $\alpha_k(n) \equiv E_t(n) \pmod{k}$
whenever $t \geq h(k)$.
\end{proof}

Here is an alternative approach to the map $\overline{\alpha}_k$. If $c =
\alpha_k(n)$  then by (\ref{fix}),  $n^c \equiv c \pmod{k}$. We
can solve for $n$  to get  $n \equiv c^{1/c} \pmod{k}$, provided
that fractional exponent makes sense.  Recall that for $c^s
\pmod{k}$, the exponent $s$ behaves modulo $\lambda(k)$.  If $s$
is a unit \hbox{(mod $\lambda(k)$),} choose $t\in\zz^+$ with $t
\equiv s^{-1} \pmod{\lambda(k)}$. Then for $c\in\uu_k$:\\
\spac $x \equiv c^t \pmod{k}$ is the unique solution to $x^s
\equiv c
\pmod{k}$. \\
Therefore $c^{1/c} \pmod{k}$ makes sense whenever $c \in \zz^+$ is
coprime to both $k$ and $\lambda(k)$. Since $\lcm\{k,
\lambda(k)\}$ divides $L(k)$, we obtain a well-defined map $\delta
: \uu_{L(k)} \to \uu_k$ given by $\delta(x) = x^{1/x}$.  This
proves the following result, related to (\ref{bijective2}).

\begin{proposition}\label{bijective}  Suppose  $\lambda(k)\dv k$
so that  $L(k) = k$. The map  $\overline{\alpha}_k : \uu_k \to
\uu_k$  is bijective with inverse map  $\delta$.
\end{proposition}



\begin{comment}
\begin{proof}  If  $a = \alpha_k(n)$  then  $n^a \equiv a \pmod{k}$
and we do get $n \equiv a^{1/a} \equiv \delta(a) \pmod{k}$  since
$a$  and $\lambda(k)$ are coprime. Hence $\overline{\alpha}_k$  is
injective. Since  $\uu_k$  is finite, $\overline{\alpha}_k$ is
automatically surjective and  $\delta$  is its inverse.
\end{proof}

This lemma is illustrated by the values of
$\overline{\alpha}_{42}(n)$  given in Table 3 above.  Each value
$a \in \uu_{42}$  occurs exactly once in the chart.

\end{comment}




Proposition \ref{bijective2} can be improved by allowing certain
non-units. We will state our best result along these lines.

\begin{theorem}\label{Wsurjec}  Define  $W_k = \{n \in \zz/k\zz
\;:\; \gcd(n, k, \lambda(k) ) = 1\}$. Then for every  $t$,  the
restriction   $\overline{E}_t : W_{L(k)} \to W_k$ is surjective.
\end{theorem}


When  $\lambda(k)\dv k$  the method used in Proposition
\ref{bijective} can extended to $W_k$.  However the full theorem
does not seem to follow easily from that case.  Our proof of the
theorem starts with the idea in Lemma \ref{coprime} and uses
induction, building up $k$ one prime at a time. It is too long to
include here.

We have not found any other useful conditions to ensure that  $a$
occurs as a value of $\overline{\alpha}_k(n)$.  In the other
direction there is one easy condition for the number  $a$  to be a
missing value for the sequences  (mod $k$).


\begin{proposition}\label{missing}  Suppose  $a, k$, and  $t$  are
given and  $t \geq 2$, and suppose there exists large  $x$  with
$E_t(x) \equiv a \pmod{k}$. If $p^d\dv k$  where  $p^d$  is a
prime power, then either $p\nmid a$  or $p^d \dv a$.
\end{proposition}

\begin{proof}  Suppose  $p\dv a$.  Since  $E_t(x) \equiv a \pmod{p^d}$  we see
that $p\dv x$.  Since  $x$  is large it follows that  $a \equiv
x\up E_{t-1}(x) \equiv 0 \pmod{p^d}$.
\end{proof}


\section{ $p$-adic Interpretations.}

In this section we assume the reader has some knowledge of the
ring  $\zz_p$  of $p$-adic integers.  However, to keep the
presentation more elementary we include a review of some of the
definitions and basic properties.  More details appear in various
texts like Borevich-Shafarevich (1966) or Koblitz (1977).

Let  $p$  be a fixed prime number.  If  $n \geq m$  there is a
natural reduction map \linebreak $\pi_{n,m} : \zz/p^n\zz \to
\zz/p^m\zz$. The ring $\zz_p$ of $p$-adic integers is the
projective limit $\varprojlim(\zz/p^n\zz)$ relative to these maps
$\pi_{n,m}$. An element $c \in \zz_p$  is defined to be a sequence
$(c_1, c_2, c_3, \dots )$ where $c_n \in \zz/{p^n}\zz$ satisfying
the following ``coherence'' condition: if $n \geq m$ then
$\pi_{n,m}(c_n) = c_m$. With component-wise addition and
multiplication, $\zz_p$ becomes an integral domain.  The ring of
integers $\zz$ is embedded as a subring of $\zz_p$ by viewing  $k
\in \zz$ as a constant sequence  $(k, k, \dots )$ in $\zz_p$. Then
$u\in\zz_p$ is a $p$-adic unit (i.e.  $u$  is invertible) iff $u
\not\equiv 0 \pmod{p}$, and every nonzero $c\in\zz_p$ factors
uniquely as $c = p^mu$ for some $m\geq0$ in $\zz$ and some
$p$-adic unit $u\in\zz_p^*$. Let \ $\ord(c)$ \ be that exponent
$m$.

Define the $p$-adic absolute value on $\zz_p$ by setting $|0|_p =
0$ and if $c \neq 0$:
$|c|_p = p^{-\ord(c)}$. 
This absolute value satisfies the following rules:

\noindent
\hskip 64pt $|a|_p \leq 1$,\; with equality$\:\iff\: a$
is a unit in $\zz_p$,\\
\hspace*{60pt} $|ab|_p = |a|_p\cdot |b|_p$,  and \\
\hspace*{60pt} $|a + b|_p \leq
\max\{|a|_p, |b|_p\}$.

That last inequality is stronger than the triangle inequality $|a
+ b|_p \leq |a|_p + |b|_p$. This absolute value makes $\zz_p$ into
a complete metric space (every Cauchy sequence converges), with
$\zz^+$ as a dense subset.

Elements of $\zz_p$  are often viewed as series: every $c \in
\zz_p$ can be expressed as a ``power series'' $c = a_0 + a_1p +
a_2p^2 + \dots$, where $a_n \in \{0, 1, \dots , p-1\}$ for every $n\geq 0$.
Every such power series $\sum a_np^n$ (with $0\leq a_n < p$)
converges relative to the metric above.



\begin{lemma}  For any positive integers  $b_1, b_2, b_3 \dots$,
the iterated exponential \linebreak
${\displaystyle \ee_{j=1}^{\infty} b_j  =
b_1\up b_2\up b_3 \up \dots}$ \; converges in  $\zz_p$.
\end{lemma}


\begin{proof}
Let  $c_n = b_1\up b_2\up \dots \up b_n$.  By Corollary
\ref{stab}, if $s, t > h(p^m)$ then $c_s \equiv c_t \pmod{p^m}$,
that is,  $|c_s - c_t|_p < p^{-m}$. Then $\{c_n\}$ is a Cauchy
sequence so its limit exists in $\zz_p$.
\end{proof}


\begin{definition}  If  $n \in \zz^+$  define  $\alpha(n) = a^{(p)}(n) =
\ee\limits_{j=1}^\infty\! n$ in $\zz_p$.  We could also write this as
$\alpha(n) = n\upup \infty$.
\end{definition}

Since $\alpha(n) = n\up n\up n \up\cdots$, it is natural to expect
that $n^{\alpha(n)} = \alpha(n)$ in $\zz_p$.  This fails when
$p\dv n$, because in that case  $\alpha(n) = 0$  in $\zz_p$.
Difficulties arise even when  $n \not\equiv 0 \pmod{p}$ because
it is not clear how to define $n^x$ for a $p$-adic integer $x$. The
function  $f(x) = n^x$ is defined for $x$ in $\zz$, but it might
have no continuous extension to the larger ring $\zz_p$. The next
lemma shows that when $n \equiv 1 \pmod{p}$ there is no
obstruction to extending the domain of $f(x) = n^x$ from $\zz^+$
to $\zz_p$.


\begin{lemma}\label{padicexp}  Suppose $a \in \zz_p$ and $|a-1|_p < 1$.  Equivalently, $a \equiv 1\pmod{p}$.  Suppose  $x, y \in \zz_p$. \\
(1) For $m\geq 1$,\; $x \equiv y \pmod{p^m}$ \; implies \; $x^p \equiv y^p  \pmod{p^{m+1}}$. \\
(2)  If  $s, t \in \zz^+$ and  $s \equiv t \pmod{p^m}$  then  $a^s
\equiv a^t \pmod{p^{m+1}}$. \\
(3) If $x \in \zz_p$, express  ${\displaystyle x =
\lim_{n\to\infty} x_n}$ where $x_n \in \zz^+$, and define $a^x =
\lim a^{x_n}$.  
Then $a^x$ is well defined, independent of the choice of the
sequence
$\{x_n\}$. Moreover, $f(x) = a^x$ defines a continuous
function $\zz_p\to\zz_p$ satisfying:\\
(4) $a^{x+y} = a^xa^y$;
 $a^x \equiv 1 \pmod{p}$ \;  and \; $(a^x)^y = a^{xy}$;
$|a^x - a^y|_p  \leq  \frac{1}{p}|x - y|_p$. \\
(5)  If  $a, b \in \zz_p$  and  $a \equiv b \equiv 1 \pmod{p}$
then $(ab)^x = a^xb^x$.
\end{lemma}


\begin{proof}[Sketch of proof]  (1)  Express  $y = x + p^mt$  and
use the binomial theorem.  (2) By (1) we know  $a^{p^m} \equiv 1
\pmod{p^{m+1}}$, and the claim follows.  Statement (2) is
equivalent to: $|a^s - a^t|_p \leq  \frac{1}{p}|s - t|_p$.   (3)
If $\{x_n\}$ is convergent, then $\{a^{x_n}\}$ is a Cauchy
sequence, so $a^x$ is defined. Triangle inequalities yield the
inequality in (4)  and this helps show that $a^x$ is independent
of the choice of $\{x_n\}$.  The remaining statements follow
similarly.
\end{proof}


A more sophisticated approach to these ideas is to introduce
$p$-adic exponential and logarithm functions and then define $a^x
= \exp(x\log a)$. Details appear in Borevich-Shafarevich (1966)
pp. 285-288 or Koblitz (1977) pp. 75-82. Since  $\log(1 + x)$
converges on the open unit ball, $\log(a)$ is defined only if $|a
- 1|_p < 1$.  These two definitions of $a^x$ coincide because they
both are continuous extensions of $f(n) = a^n$ on $\zz^+$, which
is dense in $\zz_p$.

The lemma implies that if  $n \equiv 1 \pmod{p}$  and  $f(x) =
n^x$ then $f : \zz_p \to \zz_p$  is a contraction mapping:  $|f(x)
- f(y)|_p < \frac{1}{p} |x - y|_p$.  The Banach fixed point
theorem states that a contraction mapping $f$ on a complete metric
space has a unique fixed point, obtained as\:
$\lim_{n\to\infty}f^n(c)$\: for any initial point $c$.  Then in
our case, this process reflects ideas developed in earlier
sections: the unique $\alpha \in \zz_p$ satisfying $\alpha =
n^\alpha$ is obtained from the map $f(x) = n^x$ by choosing any $c
\in \zz_p$ and taking the limit of the iterates $f(c) = n\up c, \;
ff(c) = n\up n\up c, \; fff(c) = n\up n\up n\up c, \; \dots$. This
$\alpha = \alpha(n)$ is the \emph{unique} solution $x \in \zz_p$
to $x = n^x$,  in the case $n \equiv 1 \pmod{p}$.

Before considering cases when $n \not\equiv 1$, we note that
another contraction map appears in Lemma \ref{padicexp}(1). The
map $g(x) = x^p$ satisfies:  $|g(x) - g(y)|_p \leq
\frac{1}{p}|x-y|_p$.  However, on closer examination we find that
this $g$ isn't a contraction on the whole space $\zz_p$, since
that inequality fails if $x \not\equiv y \pmod{p}$. We can fix
this by separating the metric space $\zz_p$ into $p$ parts,
$\s_b = \{k\in\zz_p : k\equiv b \pmod{p}\}$.
Each $\s_b$ is a closed subspace of $\zz_p$, and  $g(x) = x^p$ is
a contraction sending $\s_b$ to itself. Consequently there is a
unique value $\omega(b)\in \s_b$ satisfying $\omega(b)^p =
\omega(b)$. The uniqueness implies that this value depends only on
the residue $\overline{b}\in\zz/p\zz$. Since $\omega(0) = 0$ we
ignore that case and consider $\omega$ as a map on the nonzero
classes\; $\omega : (\zz/p\zz)^* \to \zz_p$. It is not hard to
check that the image of $\omega$ is the group of
$(p-1)^{\text{st}}$ roots of unity in $\zz_p$.  This $p$-adic
integer $\omega(b) = \lim\limits_{m\to\infty}b^{p^m}$ is the
``Teichm\"{u}ller representative'' of the residue class
$\overline{b}$.


When $n \not\equiv 1 \pmod{p}$ the function $f(k) = n^k$ on
$\zz^+$ does not extend continuously to $\zz_p$. Instead there are
$p-1$ continuous ``branches'', or partial extensions.  Since
$n^{p-1} \equiv 1\pmod{p}$, the powers $(n^{p-1})^x$ are well
defined for $x\in\zz_p$, by (\ref{padicexp}).  We would like to
take the $(p-1)^{\text{st}}$ root to define $n^x$, but there are
several choices involved.

Following Koblitz (1977) p. 27, if $n \not\equiv 0\pmod{p}$,
define $\langle n\rangle = n/\omega(n) \in \zz_p$.  Then $\langle
n\rangle \equiv 1\pmod{p}$ (so that $\langle n\rangle^x$ is well
defined) and $\langle n\rangle^{p-1} = n^{p-1}$. We can now find
continuous $(p-1)^{\text{st}}$ roots of $(n^{p-1})^x$ by setting
$f(x) = \zeta\cdot\langle n\rangle^x$, where $\zeta\in\zz_p$ and
$\zeta^{p-1} = 1$.
For $k\in\zz^+$, this $f(k)$ equals $n^k$ exactly when $\zeta =
\omega(n)^k$.  For $b \in \zz$, this leads to the
definition
$$f_{n,b}(x) = \omega(n)^b\langle n\rangle^x.$$
Then $f_{n,b} : \zz_p\to\zz_p$ is continuous, $f_{n,b}(x)^{p-1} =
(n^{p-1})^x$ for all $x$, and $f_{n,b}(k)= n^k$ for every $k\in
\s_b$. This is the unique function with those properties since
$\s_b$ is dense in $\zz_p$.  The number of different functions
here is $o_p(n)$, since $f_{n,b}$ depends on $n^b \pmod{p}$.


\begin{proposition}\label{uniquefix}  Suppose  $n \in \zz^+$  and
$p\nmid n$. Then  $\alpha(n)$  is the unique fixed point of the
map  $f_{n,b}$ when  $b = \alpha_{p-1}(n)$.
\end{proposition}

\begin{proof}  $f_{n,b}$  is a contraction since
$|f_{n,b}(x) - f_{n,b}(y)|_p = |\langle n\rangle^x - \langle
n\rangle^y|_p \leq  \frac{1}{p}|x - y|_p$. Therefore there is a
unique fixed point in  $\zz_p$.  For any large $t,\; n \upup t
\equiv \alpha_{p-1}(n) \equiv b \pmod{p - 1}$.  Therefore $n \upup
t \in S_b$. Hence $E_{t+1}(n) = n\up(n \upup t) = f_{n,b}(n \upup
t)$.  Now take the limit as  $t \to \infty$.
\end{proof}

For every $b$ the function $f_{n,b}$ has a unique fixed point in
$\zz_p$.  Generally, for $a, c \in \zz_p$ with $c \equiv 1
\pmod{p}$, the function $f(x) = a\!\cdot\! c^x$ is a contraction
with a fixed point $\beta$.  Then $\beta/a$ is the fixed point of
$g(y) = c^{ay}$, obtained as the limit $c^a\up c^a \up \cdots$.

As an application of (\ref{uniquefix}) we consider the injectivity
of $\alpha$ on  $\zz^+$.


\begin{proposition} \label{injec} The map $\alpha = \alpha^{(p)} :
\zz^+ \to \zz_p$ sends every multiple of $p$ to 0.  On the other
positive integers, $\alpha^{(p)}$ is injective.
\end{proposition}

\begin{proof} If $p\dv n$ then $n\up n\up \dots \up n$
involves high powers of $p$ so the limit is 0 in $\zz_p$.  Note
that if $c \neq 1$ and $|c-1|_p < 1$ then the map $g(x) = c^x$ is
injective. (This follows from the $p$-adic logarithm, but there is
a more elementary proof in the style of (\ref{padicexp}).)

Now suppose $n, m \in \zz^+,\;  n, m \not\equiv 0 \pmod{p}$, and
and $x = \alpha(n) = \alpha(m)$ in $\zz_p$.  By (\ref{uniquefix}),
$x = f_{n,b}(x) = f_{m,c}(x)$ for some $b, c$. Then $x^{p-1} =
(n^{p-1})^x = (m^{p-1})^x$ in $\zz_p$ and we find that
$((nm^{-1})^{p-1})^x = 1$.  With $c = (nm^{-1})^{p-1}$ we have
$c\equiv 1\pmod{p}$ and $c^x = 1$.  The injectivity mentioned
above implies $c = 1$. But then $n^{p-1} = m^{p-1}$ in $\zz$, so
that $n = m$.
\end{proof}



We have been considering towers of powers in $\zz_p$.  However it
is perhaps more natural to consider those limits without
restricting to a single prime $p$. Whenever $d\dv k$ there is a
natural reduction map $\pi_{k,d} : \zz/k\zz \to \zz/d\zz$, and the
projective limit makes sense:\; $\widehat{\zz} =
\varprojlim(\zz/k\zz)$. An element $\hat{c} \in \widehat{\zz}$ is
defined to be a sequence $\hat{c} = (c_1, c_2, \dots )$ with $c_k
\in \zz/k\zz$ satisfying the ``coherence'' condition: if $d\dv k$
then $\pi_{k,d}(c_k) = c_d$.  Unique factorization and the Chinese
Remainder Theorem provide a ring
isomorphism:
$${ \displaystyle \widehat{\zz} \;
\overset{\cong}{\longrightarrow} \; \prod_p\zz_p },$$
where the direct product is taken over all primes $p$.  Elements
of $\widehat{\zz}$ can also be thought of as ``profinite
integers'' as described using factorial representations in
Lenstra's paper \cite{L05}.

If  $\{a_n\}$ is a sequence in $\zz^+$, then by (\ref{stab}), the
numbers \; $c_n = a_1\up a_2\up \dots\up a_n$ define an element
$\hat{c}  = \ee\limits_{j=1}^\infty a_j  \in \widehat{\zz}$. In
particular, for $n \in \zz^+$ we have an element
$\widehat{\alpha}(n) = \ee\limits_{j=1}^\infty n = n\up n\up n \up
\cdots$ in $\widehat{\zz}$, which induces the element
$\alpha^{(p)}(n) \in \zz_p$ for every prime $p$. The domain of
$\widehat{\alpha}$ can be enlarged to include all $\hat{n} \in
\widehat{\zz}$ by just taking the limit of the maps
$\overline{\alpha}_k : \zz/L(k)\zz \to \zz/k\zz$ defined in \S 2
to build $\widehat{\alpha} : \widehat{\zz} \to \widehat{\zz}$.
That is, if $\hat{c} = (c_1, c_2, \dots)$, we define
$\widehat{\alpha}(\hat{c})$ by setting
$$\widehat{\alpha}(\hat{c})_k =
\overline{\alpha}_k(c_{L(k)}).$$
By (\ref{injec}) it follows that the restriction $\widehat{\alpha}
: \zz^+ \to \widehat{\zz}$ is injective. However
$\widehat{\alpha}$ is not injective on $\widehat{\zz}$. To see
this, note that any $\hat{c} \in \widehat{\zz}$ is determined by
its list of components $c^{(p)} \in \zz_p$.  Define $\hat{c}$ by
requiring $c^{(p)} = p$ for every $p$.  Check that $\hat{c} \neq 0$ but
$\widehat{\alpha}(\hat{c}) = 0$.


To extend our work with $p$-adic numbers, we would like to define
exponential functions and consider their fixed points.  Starting at the
finite level, define an exponential map \\[5pt]
\spac \spac $\ex_k : (\zz/k\zz) \times (\zz/\lambda(k)\zz) \to (\zz/k\zz)$
\; by: \quad $\ex_k(\overline{a}, \overline{b}) = \overline{a^b}$.\\[5pt]
This can be a bit confusing since $b$ is a residue class (not an
integer) and the value  $\overline{a^b}$ corresponds to a term in
the ``cycle'' part of the sequence $1, a, a^2, a^3, \dots$\ .
For instance, when $k = 40$ the powers of 2 (mod 40) are: 1, \ 2,  \ 4,  \
8, \ 16,  \ 32,  \ 24,
\ 8,  \ 16, \dots\ .  Since $\lambda(40) = 4$, we find that
$\ex_{40}(\overline{2}, \overline{1}) =
\overline{2}^{\overline{1}} = \overline{32}$ \; in \; $\zz/40\zz$,
since that's the term in the cycle corresponding to 1 \!(mod 4).

Now take the limit of those maps \ $\ex_k$ \ as $k \to \infty$,
to obtain
$\ex : \widehat{\zz} \times  \widehat{\zz} \to
\widehat{\zz}$.
We can write $\ex(\hat{a}, \hat{b})$ as $\hat{a}^{\hat{b}}$, but
repeat the warning about interpretations.  Although $\zz$ embeds
as a subring of $\widehat{\zz}$, this exponential map isn't
consistent with traditional exponents of integers. For example, 1
and 2 embed as constant sequences $\hat{1}, \hat{2}$ in
$\widehat{\zz}$, but $\hat{2}^{\hat{1}}$ does not match $2^1$ in
$\zz$.

One interesting point is that this exponential map generalizes all
the $p$-adic exponential maps, but without the concerns about
convergence.  The point is that defining $a^x$ for $a \in
\zz/p^m\zz$ requires the exponent $x$ to live in
$\zz/p^{m-1}(p-1)\zz \cong \zz/p^{m-1}\zz \times \zz/(p-1)\zz$.
Ignoring the $(\zz/(p-1)\zz)$-component of $x$ leads to $p-1$
different branches of the exponential function.  In
$\widehat{\zz}$ those components are not ignored and that
difficulty vanishes.

Not surprisingly, the analysis of functions on $\widehat{\zz}$
present various difficulties not arising in $\zz_p$. It should be
interesting to investigate whether the exponential
maps on  $\widehat{\zz}$ are contractions relative to some nice
metric, and whether
$\widehat{\alpha}(n)$ is the unique fixed point of the function
$f(\hat{x}) = n^{\hat{x}}$.  We leave further development of this
theory to the reader.



\section{Some Problems}

Here are a few open problems related to topics discussed above.

By  (\ref{stab}) for given $k$ every sequence \; $n,\;  n^n, \;
n^{n^n}, \; n \upup 4,\;  \dots \pmod{k}$ becomes stable after at
most $h(k) + 1$ steps.

\begin{problem} How fast does the height function  $h(k)$  grow?
\end{problem}
The corresponding question for the $\varphi$-height has been
studied. In analogy to Definition \ref{height} let the
$\varphi$-height be $h_\varphi(k) = \min\{s : \varphi^s(k) = 1\}$.  In 1943
H. N. Shapiro \cite{Sh43} proved that $h_\varphi(k)$  has
multiplicative properties and grows logarithmically. 
\hspace*{1cm} Does $h(k)$ have the same order of magnitude as
$h_\varphi(k)$? 
See H. N. Shapiro \cite{Sh50} , Parnami \cite{Pa67} and Erd\H{o}s and
Graham \cite{EG80} pp. 80-81 for related questions.



Rather than considering all $n$ simultaneously, define a height
for each $n$:
$$\ell_k(n) = \min\{t  \;:\; E_t(n) \equiv E_{t+1}(n)
\pmod k\}$$
 %n \upup t \equiv n \upup (t+1) \pmod{k} \}$.  \\
For given $n, k$, note that the sequence $E_t(n)$ (mod
$k$) stabilizes after $\ell_k(n)$ steps:

\begin{lemma}  \label{Estable}
If $E_{t-1}(n)  \equiv E_t(n) \pmod k$ \; then \;
$E_t(n)  \equiv E_{t+1}(n) \pmod k$.
\end{lemma}

%If  $n \upup (t - 1) \equiv n \upup t  \pmod{k}$
%then  $n \upup t \equiv n \upup (t + 1) \pmod{k}$.

\begin{proof} To prove that $E_t(n) - E_{t-1}(n)$ \;
divides \; $E_{t+1}(n)- E_t(n)$ for every $n$, check that
$(n^a-a)\dv(n^b-b)\;\Longrightarrow\; (n^{n^a} - n^a)\dv
(n^{n^b}-n^b)$.
\end{proof}Consequently, $\ell_k(n) \leq h(k)$.  Since
$\ell_k(n) = 1 + \ell_{o_k(n)}(n)$
it follows that if $s$ and $L(k)$ are coprime then $\ell_k(n^s) = \ell_k(n)$.


\begin{problem}  Investigate  $\ell_k(n)$.  As $n$ varies,
how do the values $\ell_k(n)$ compare with $h(k)$?
\end{problem}


Let $N_t(a \text{ mod } k)$ be the number of solutions to $E_t(x)
\equiv a \pmod k$, counted in one period.  In (\ref{surjec}) we
proved that $N_t(a \text{ mod } k) > 0$ whenever $a$ is a unit. In
some cases when $(\zz/k\zz)^*$ is cyclic, there is an explicit
formula for $N_2$.  For instance, if $p$ is an
odd prime and $a$ is coprime to $p$ then
$${\displaystyle N_2(a \text{ mod } p^m) \; = \;
      \sum_{d \mid \frac{p-1}{r}}\!}d\thinspace\varphi(\frac{p-1}{d}),$$
where $r = o_p(a)$.  The proof involves choosing a generator $g$
and counting $x$ values by tabulating $s, t$ such that $x \equiv
g^t \pmod {p^m}$ and $x \equiv s \pmod{p^{m-1}(p-1)}$ such that
$x^x \equiv g^{st} \equiv a \pmod{p^m}$. Details are omitted.




\begin{problem} Given $k$, for which  $a$  is there a solution to
$x^x\equiv a \pmod{k}$?  How about
 $E_t(x) \equiv a \pmod{k}$?  More generally,
is there a simple formula for  $N_t(a \text{ mod } k)$? For these
questions, we consider only those $x$ lying in the cyclic part,
$\zz/L_t(k)\zz$.
\end{problem}



Most of the information derived so far about the image of $E_t$ in
$\zz/k\zz$ is independent of $t$.  In addition to Lemma
\ref{Estable}, we make another small observation
relating these images for different $t$ values: 

\centerline{If $E_t(n)\equiv 1 \pmod{k}$ \; then \; $E_{t+1}(n)\equiv 1
\pmod{k}$.}
\noindent
To see this note that  $(E_t(n) - 1)\mid (E_{t+1}(n) - 1)$, since
$a\dv b \; \Longrightarrow \; (n^a-1)\dv (n^b-1)$.


\begin{comment}
   This independence is not automatic.  For example when  $k = 30$  and $a
   = 24$  we have  $18^{18} \equiv E_2(18) \equiv 24  \pmod{30}$, but
   $x \upup 3 \equiv 24 \pmod{30}$  has no solution.   Hence
   $\img(\overline{E}_2) \not\subset \img(\overline{E}_3)$ in
   $\zz/30\zz$. On the other hand, we have been unable to find an
   example where $x^{x^x} \equiv a \pmod{k}$  has a solution but $y^y
   \equiv a \pmod{k}$ does not.

   Characterize the image of $E_t : \zz^+ \to \zz/k\zz$
    in some usable way.  \\
\end{comment}

\begin{problem}
As $t$ varies, how are the sets\;  $\img(E_t)
\subset \zz/k\zz$\;  related?
\end{problem}





Approximations to $\alpha(n) = \alpha^{(p)}(n) \in \zz_p$ can be
easily computed, but not much is known about its
algebraic properties.  We note that $\alpha(n) \notin \qq$:  \\[3pt]
\spac If  $1 < n \in \zz^+$ and $p\nmid n$
then  $\alpha(n)$ is irrational. \\[3pt]
For if $\alpha(n) = r/s$  in lowest terms, then by
(\ref{uniquefix}), $(r/s)^{p-1} = (n^{p-1})^{r/s}$ in $\zz_p$.
This implies $r^{(p-1)s} = n^{(p-1)r}s^{(p-1)s}$ in $\zz$.  But
that equation yields $s = 1$ and $r = n^r$, a contradiction.

\begin{problem}  For $n$ as above, is $\alpha^{(p)}(n) \in \zz_p$
transcendental over the field $\qq$ of rational numbers?
\end{problem}


For any sequence $\{a_1, a_2, a_3, \dots\}$ in $\zz^+$, the limit
$\ee\limits_{j=1}^\infty a_j \; = \;
a_1^{a_2^{\cdot^{\cdot^{\cdot}}}}$ is a well-defined element in
$\widehat{\zz}$, the ring of profinite integers. If  $\{b_n\}$ is
a different sequence in $\zz^+$, it can happen that
$\ee\limits_{j=1}^\infty a_j = \ee\limits_{j=1}^\infty b_j$ in
$\widehat{\zz}$. Examples are easy to produce when some $a_i, b_j$
are allowed to equal 1. For
instance,
$2^{4^5} = 4^{2^{3^2}}$ \quad and \quad $9^{2^3} =
3^{2^{2^2}}$\!\!.
Examples of such equalities seem to be harder to find with
infinite towers.

\begin{problem} Suppose $a_1, a_2, a_3, \dots$ and $b_1, b_2, b_3, \dots$ are
sequences in $\zz^+$ and every $a_i, b_i \geq 2$. If \;
$\ee\limits_{j=1}^\infty a_j = \ee\limits_{j=1}^\infty b_j$ \; in
$\widehat{\zz}$, \; does it follow that every $a_i = b_i$?
\end{problem}






%\newpage

\begin{thebibliography}{99} \footnotesize

\bibitem{AN04}
Joel Anderson, \emph{Iterated exponentials}, Amer. Math Monthly.
\textbf{111} (2004) pp. 668-679.

\bibitem{BR85}
I. N. Baker and P. J. Rippon, \emph{A note on complex iteration},
Amer. Math. Monthly  \textbf{92} (1985), pp. 501-504.

\bibitem{BB83}
G. R. Blakley and I. Borosh, \emph{Modular arithmetic of iterated
powers}, Comput. Math. Appl. \textbf{9} (1983) pp. 567-581.

\bibitem{BS66}
Z. I. Borevich and I. R. Shafarevich, \emph{Number Theory},
Academic Press,  1966.

\bibitem{Br87}
N. Bromer, \emph{Superexponentiation}, Math. Mag. \textbf{60}
(1987) pp. 169-174.

\bibitem{Ca10}
R. D. Carmichael, \emph{Note on a new number theory function},
Bull. Amer. Math. Soc. \textbf{16} (1910), pp. 232-238.

\begin{comment}
\bibitem{CS80}
M. Creutz and R. M. Sternheimer,  \emph{On the convergence of
iterated exponentiation  I, II, III}, Fibonacci Quarterly
\textbf{18} (1980) pp. 341-348,  \textbf{19} (1981) pp. 326-335
and \textbf{20} (1982), pp. 7-12.
\end{comment}

\bibitem{Cr66}
R. Crocker, \emph{On a new problem in number theory}, Amer. Math.
Monthly \textbf{73} (1966) pp. 355-357.


\bibitem{Cr69}
R. Crocker, \emph{On residues of  $n^n$},  Amer. Math. Monthly
\textbf{76} (1969) pp. 1028-1029.


\bibitem{Cu07}
A. C. Cunningham, \emph{On hyper-even numbers and on Fermat's
numbers}, Proc. London Math. Soc. (2) \textbf{5} (1907) pp.
237-274.

\bibitem{Da94}
Robert J. MacG. Dawson, \emph{Towers of powers modulo $m$},
College. Math. J. \textbf{25} (1994) pp. 22-28.

\bibitem{Ec80}
A. Ecker, \emph{Comment on the note: ``The congruence  $a^{r+s}
\equiv a^r$ (mod $m$)'' by A. Livingston and M. L. Livingston},
Amer. Math. Monthly \textbf{87} (1980) pp. 811-814.

\bibitem{EG80}
P. Erd\H{o}s and R. L. Graham,  \emph{Old and New Problems and
Results in Combinatorial Number Theory}, Monographie no. 28 de
L'Enseignement Mathématique, Geneva, 1980.

\bibitem{Ha55}
R. Hampel, \emph{The length of the shortest period of rests of
number $n^n$}, Ann. Polon. Math.  \textbf{1} (1955) pp. 360-366.


\bibitem{Kn81}
R. A. Knoebel,  \emph{Exponentials reiterated}, Amer. Math.
Monthly \textbf{88} (1981), pp. 235-252.


\bibitem{Kn76}
D. E. Knuth, \emph{Coping with finiteness}, Science \textbf{194}
(1976), pp. 1235-1242.

\bibitem{Ko77}
N. Koblitz,  \emph{$p$-adic Numbers, $p$-adic Analysis, and
Zeta-Functions}, Graduate Texts in Math. vol. 58, Springer-Verlag,
1977.

\bibitem{Ko80}
N. Koblitz,  \emph{$p$-adic Analysis:  a Short Course on Recent
Work}, London Math. Soc. Lecture Note Series v. 46, Cambridge
Univ. Press, 1980.

\bibitem{L05}
H. Lenstra, \emph{Profinite Fibonacci numbers}, Nieuw Arch.
Wiskd. (5) \textbf{6} (2005) 297-300.

\bibitem{LL78}
A. E. Livingston and M. L. Livingston, \emph{The congruence
$a^{r+s} \equiv a^r$ (mod $m$)}, Amer. Math. Monthly  \textbf{85}
(1978) pp. 97-100.

\begin{comment}
\bibitem{Ma35}
K. Mahler,  \emph{\"{U}ber transzendente $p$-adische Zahlen},
Compositio Math. \textbf{2} (1935), pp. 259 - 275.
\end{comment}


\bibitem{Ma01}
H. Maurer, \emph{\"{U}ber die Funktion
$x^{[x^{(x^{({.^{.^{.}}})})}]}$ f\"{u}r ganzzahliges Argument
(Abundanzen)},  Mittheilungen der Mathematische Gesellschaft in
Hamburg  \textbf{4} (1901), pp. 33-50.


\bibitem{Pa67}
J. C. Parnami, \emph{On iterates of Euler's $\varphi$-function},
Amer. Math. Monthly  \textbf{74} (1967) pp. 967-968.

\bibitem{SS59}
A. Schinzel and W. Sierpi\'{n}ski, \emph{Sur les congruences  $x^x
\equiv c \pmod{m}$ et\;  $a^x \equiv b \pmod{p}$}, Collect. Math.
11 (1959) pp. 153-164.

\bibitem{Sh87}
D. B. Shapiro, \emph{Comment on problem 559}, Crux Math.
\textbf{13} (1987) pp. 291-294.

\bibitem{Sh43}
H. N. Shapiro, \emph{An arithmetic mean arising from the $\phi$ function}, Amer. Math. Monthly  \textbf{50} (1943) pp. 18-30.

\bibitem{Sh50}
H. N. Shapiro, \emph{On the iterates of a certain class of
arithmetic functions}, Comm. Pure Appl. Math.  \textbf{3} (1950)
pp. 259-272.

\bibitem{Sh83}
H. N. Shapiro, \emph{Introduction to the Theory of Numbers}, John
Wiley and Sons, 1983.

\bibitem{Si50}
W. Sierpi\'{n}ski, \emph{Sur les puissances du nombre 2}, Ann.
Soc. Polon. Math.  \textbf{23} (1950) pp. 246-251.

\bibitem{Si50a}
W. Sierpi\'{n}ski,  \emph{Sur la p\'{e}riodicit\'{e} mod $m$  de
certaines suites infinies d'entiers}, Ann. Soc. Polon. Math.
\textbf{23} (1950) pp. 252-258.

\bibitem{Si66}
D. Singmaster, \emph{A maximal generalization of Fermat's
theorem}, Math. Magazine   \textbf{39} (1966) pp. 103-107.

\bibitem{Vi54}
I. M. Vinogradov, \emph{Elements of Number Theory},  Dover, 1954.

%\bibitem{Wa81}
%A. Wayne, \emph{Solution to Problem 559} (Proposed by Charles W.
%Trigg), Crux Math. \textbf{7} (1981) pp. 192-194.

\bibitem{Pr86}
Problem A - 4 in:  \emph{1985 Putnam Competition}, Math. Mag.
\textbf{59} (1986) pp. 123-126.

\bibitem{Pr92}
Problem 3 in:  \emph{Twentieth Annual U.S.A. Mathematical
Olympiad}, Math. Mag. \textbf{65} (1992) pp. 205 - 206.
\begin{comment}
\end{comment}

\end{thebibliography}



\end{document}





\begin{comment}
There is a $p$-adic analog of the Gelfond-Schneider Theorem: \\[3pt]
\textbf{Theorem} (Mahler, 1935) If  $\beta$ is an algebraic
$p$-adic number with  $0 < |\beta - 1|_p \leq \frac{1}{p}$ and
$\theta$ is an algebraic irrational $p$-adic number, then
$\beta^\theta$ is transcendental over $\qq_p$.

However, that doesn't apply in our case because the number $\alpha = n^\beta$ lies in $\zz_p$.  The question is whether this $p$-adic integer is transcendental over $\qq$, not over $\qq_p$.
\end{comment}