<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin {center}
\vskip 1cm{\LARGE\bf 
Primes in Classes of the \\
\vskip .2in
Iterated Totient Function
}
\vskip 1cm
\large
Tony~D.~Noe\\
14025~NW~Harvest~Lane\\
Portland,~OR~~97229\\
USA\\
\href {mailto:noe@sspectra.com} {\tt noe@sspectra.com} 
\end {center} 

\vskip .2in

\begin {abstract}
As shown by Shapiro, the iterated totient function separates integers into classes having three sections. After summarizing some previous results about the iterated totient function, we prove five theorems about primes $p$ in a class and the factorization of~$p-1$. An application of one theorem is the calculation of the smallest number in classes up to~1000.
\end {abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\section {Introduction}

Let $\phi(x)$ denote Euler's totient function. Defining $\phi^0(x)=x$, the iterated totient function is defined recursively for $n&gt;0$ by $\phi^n(x) = \phi( \phi^{n-1}(x))$. For $x&gt;1$, $\phi(x)&lt;x$. Hence, for some $n$ we will have $\phi^n(x)=2$. That $x$ is said to be in class $n$, and we define the function $C(x)=n$. We define $C(1)=0$. Table~\ref {Ta1}, which is sequence \seqnum{A058812} in Sloane~\cite {Sloane}, shows the numbers in classes~0 to~5. A thorough treatment of the iterated totient function is given by Shapiro~\cite {Shapiro}. The normal behavior of this function is treated by Erdos et al.~\cite {Erdos}. We summarize key results of Shapiro's paper here.

\begin {table}
\begin {center}
{\footnotesize
\begin {tabular} [b] {|c|l|}
\hline
&amp; \\[-6pt]
Class &amp; \qquad \qquad \qquad \qquad \qquad \qquad Numbers in this Class\\
&amp; \\[-6pt]
\hline
0 &amp; 1, 2, \\
1 &amp; 3, 4, 6, \\
2 &amp; 5, 7, 8, 9, 10, 12, 14, 18, \\
3 &amp; 11, 13, 15, 16, 19, 20, 21, 22, 24, 26, 27, 28, 30, 36, 38, 42, 54, \\
4 &amp; 17, 23, 25, 29, 31, 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, 49, 50, 52, 56, 57, 58, 60, \\
 &amp; 62, 63, 66, 70, 72, 74, 76, 78, 81, 84, 86, 90, 98, 108, 114, 126, 162, \\
5 &amp; 41, 47, 51, 53, 55, 59, 61, 64, 65, 67, 68, 69, 71, 73, 75, 77, 79, 80, 82, 87, 88, 91, 92, 93, \\
 &amp; 94, 95, 96, 99, 100, 102, 104, 105, 106, 109, 110, 111, 112, 116, 117, 118, 120, 122, 124, \\
 &amp; 127, 129, 130, 132, 133, 134, 135, 138, 140, 142, 144, 146, 147, 148, 150, 152, 154, 156, \\
 &amp; 158, 163, 168, 171, 172, 174, 180, 182, 186, 189, 190, 196, 198, 210, 216, 218, 222, 228, \\
 &amp; 234, 243, 252, 254, 258, 266, 270, 294, 324, 326, 342, 378, 486, \\
\hline
\end {tabular}}
\caption {Numbers in Classes 0 to 5}
\label {Ta1}
\end {center} 
\end {table}




\section {Properties of the C function}

Shapiro establishes the following properties of the $C$ function:
\begin {enumerate}
\item For $x$ or $y$ odd, $C(x y)=C(x)+C(y)$.
\item For $x$ and $y$ both even, $C(x y)=C(x)+C(y)+1$.
\item The largest odd number in class $n$ is $3^n$; i.e., for odd $x$, $x&lt;3^{C(x)}$.
\item The largest even number in class $n$ is $2 \cdot 3^n$; i.e., for even $x$, $x&lt;2 \cdot 3^{C(x)}$.
\item The smallest even number in class $n$ is $2^{n+1}$; i.e., for even $x$, $x \ge 2^{C(x)+1}$.
\item The smallest odd number in class $n$ is greater than $2^n$; i.e., for odd $x$, $x&gt;2^{C(x)}$.
\item For any integer $x$, $2^{C(x)} &lt; x \le 2 \cdot 3^{C(x)}$.
\end {enumerate}


Thus, Shapiro proves that numbers $x$ in class $n&gt;1$ fall into three sections: 
$$2^n &lt; x &lt; 2^{n+1}, \quad \quad 2^{n+1} \le x \le 3^n, \quad \quad 3^n &lt; x \le 2 \cdot 3^n.$$
Table~\ref {Ta2} shows numbers separated into the three sections. Shapiro establishes the following properties of these classes:

\begin {table}
\begin {center}
{\footnotesize
\begin {tabular} [b] {|c|l|l|l|}
\hline
&amp; &amp; &amp; \\[-6pt]
Class &amp; \qquad \quad Section I &amp; \qquad \qquad \qquad \quad Section II &amp; \quad ~Section III \\
&amp; &amp; &amp; \\[-6pt]
\hline
0 &amp; 1, &amp; 2, &amp; \\
1 &amp; 3, &amp; 4, &amp; 6, \\
2 &amp; 5, 7, &amp; 8, 9, &amp; 10, 12, 14, 18, \\
3 &amp; 11, 13, 15, &amp; 16, 19, 20, 21, 22, 24, 26, 27, &amp; 28, 30, 36, 38, 42, \\
 &amp; &amp; &amp; 54, \\
4 &amp; 17, 23, 25, 29, 31, &amp; 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, &amp; 84, 86, 90, 98, 108, \\
 &amp; &amp; 49, 50, 52, 56, 57, 58, 60, 62, 63, 66, 70, 72, &amp; 114, 126, 162, \\
 &amp; &amp; 74, 76, 78, 81, &amp; \\
5 &amp; 41, 47, 51, 53, 55, 59, 61, &amp; 64, 65, 67, 68, 69, 71, 73, 75, 77, 79, 80, 82, &amp; 252, 254, 258, 266, \\
 &amp; &amp; 87, 88, 91, 92, 93, 94, 95, 96, 99, 100, 102, &amp; 270, 294, 324, 326, \\
 &amp; &amp; 104, 105, 106, 109, 110, 111, 112, 116, 117, &amp; 342, 378, 486,\\
 &amp; &amp; 118, 120, 122, 124, 127, 129, 130, 132, 133, &amp; \\
 &amp; &amp; 134, 135, 138, 140, 142, 144, 146, 147, 148, &amp; \\
 &amp; &amp; 150, 152, 154, 156, 158, 163, 168, 171, 172, &amp; \\
 &amp; &amp; 174, 180, 182, 186, 189, 190, 196, 198, 210, &amp; \\
 &amp; &amp; 216, 218, 222, 228, 234, 243, &amp; \\
\hline
\end {tabular}}
\caption {Numbers in Classes 0 to 5 Organized by Section}
\label {Ta2}
\end {center} 
\end {table}

\begin {enumerate}
\item [8.] Numbers in section I are odd.
\item [9.] Numbers in section II are even or odd.
\item [10.] Numbers in section III are even.
\item [11.] If integer $x$ is in section I, then every divisor of $x$ is in section~I of its class.
\end {enumerate}


This last property~\cite [Theorem 15] {Shapiro} is most interesting. For example, it tells us that the factors~5 and~11 of~55 must both be in section~I because~55 is in section~I. Table~\ref {Ta3} shows Section~I numbers (sequence \seqnum{A005239}); each composite number, shown in bold, has all its factors in section~I.

\begin {table} [H]
\begin {center}
{\footnotesize
\begin {tabular} [b] {|c|l|}
\hline
&amp; \\[-6pt]
Class &amp; \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad Numbers in Section I \\
&amp; \\[-6pt]
\hline
0 &amp; 1, \\
1 &amp; 3, \\
2 &amp; 5, 7, \\
3 &amp; 11, 13, \textbf{15}, \\
4 &amp; 17, 23, \textbf{25}, 29, 31, \\
5 &amp; 41, 47, \textbf{51}, 53, \textbf{55}, 59, 61, \\
6 &amp; 83, \textbf{85}, 89, 97, 101, 103, 107, 113, \textbf{115}, \textbf{119}, \textbf{121}, \textbf{123}, \textbf{125}, \\
7 &amp; 137, 167, 179, \textbf{187}, 193, \textbf{205}, \textbf{221}, 227, 233, \textbf{235}, 239, 241, \textbf{249}, 251, \textbf{253}, \textbf{255}, \\
8 &amp; 257, \textbf{289}, 353, 359, 389, \textbf{391}, 401, 409, \textbf{411}, \textbf{415}, \textbf{425}, 443, \textbf{445}, 449, \textbf{451}, 461, 467, 479,... \\
9 &amp; 641, \textbf{685}, \textbf{697}, 719, 769, \textbf{771}, 773, \textbf{799}, 809, 821, 823, \textbf{835}, 857, \textbf{867}, 881, 887, \textbf{895}, \textbf{901},... \\
10 &amp; 1097, 1283, \textbf{1285}, 1361, 1409, \textbf{1411}, 1433, 1439, \textbf{1445}, \textbf{1507}, \textbf{1513}, 1543, 1553, 1601,... \\
11 &amp; \textbf{2329}, 2657, 2741, 2789, 2819, \textbf{2827}, \textbf{2839}, 2879, \textbf{3043}, 3089, \textbf{3151}, \textbf{3179}, 3203, \textbf{3205},... \\
12 &amp; \textbf{4369}, \textbf{4913}, 5441, 5483, \textbf{5485}, \textbf{5617}, 5639, \textbf{5911}, \textbf{6001}, 6029, 6053, \textbf{6103}, 6173, 6257,... \\
\hline
\end {tabular}
}
\caption {Numbers in Section I of Classes 0 to 12}
\label {Ta3}
\end {center} 
\end {table}


Shapiro, observing that the smallest number in each of the classes 1 through 8 is prime, conjectured that the smallest number is prime for all classes. However, Mills~\cite {Mills} found counterexamples. Later, Catlin~\cite [Theorem 1] {Catlin} proved that if the smallest number in a class is odd, then it can be factored into the product of other such numbers. For example, the smallest numbers in classes 11 and 12 factor as $2329=17 \cdot 137$ and $4369=17 \cdot 257$; note that 17, 137, and 257 are the smallest numbers in classes 4, 7, and 8, respectively.





\section {Theorems about primes in classes}

Although Shapiro and Catlin give a nice characterization of the composite section~I numbers, their papers say little about the prime numbers in sections~I and~II. We prove five theorems about those primes.

\begin {theorem} \label {T.section-I}	%-------------------------------------------------------------------------- theorem 1
Suppose $p$ is an odd prime and $p=1+2^k m$, with $k&gt;0$ and $m$ odd. Then $p$ is in section~I of its class if and only if $m$ is in section~I of its class.
\end {theorem}
\begin {proof} 
Observe that for prime $p$, $\phi(p)=p-1$, and hence, $C(p-1)=C(p)-1$. From Shapiro's properties of the $C$ function, we have $C(p-1) = k-1 + C(m)$. Therefore, $C(p) = C(m) + k$. For a prime $p$ in section~I, we have the inequality
\begin {equation*}
2^{C(p)} &lt; p &lt; 2^{C(p)+1}.
\end {equation*}
Substituting $p=1+2^k m$, we obtain
\begin {equation*}
2^{C(m)+k} &lt; 1+2^k m &lt; 2^{C(m)+k+1}.
\end {equation*}
Dividing by $2^k$ produces the inequality
\begin {equation*}
2^{C(m)} &lt; m &lt; 2^{C(m)+1},
\end {equation*}
showing that $m$ is a number in section~I of its class, which is $C(p)-k$. The proof in the other direction is just as easy. For a number $m$ in section~I, we have the inequality
\begin {equation*}
2^{C(m)} &lt; m &lt; 2^{C(m)+1}.
\end {equation*}
Multiplying by $2^k$ produces the inequality
\begin {equation*}
2^{C(m)+k} &lt; 2^k m &lt; 2^{C(m)+k+1}.
\end {equation*}
Adding 1 to $2^k m$ does not change the inequality because there is always an odd number between two evens. Hence, we obtain
\begin {equation*}
2^{C(m)+k} &lt; 1+2^k m &lt; 2^{C(m)+k+1}.
\end {equation*}
But, for integers, this inequality is the same as
\begin {equation*}
2^{C(p)} &lt; p &lt; 2^{C(p)+1},
\end {equation*}
which means $p$ is in section~I of its class, which is $C(m)+k$.
\end {proof}

\begin {theorem} \label {T.section-II}	%-------------------------------------------------------------------------- theorem 2
Suppose $p$ is an odd prime and $p=1+2^k m$, with $k&gt;0$ and $m$ odd. Then $p$ is in section~II of its class if and only if $m$ is in section~II of its class.
\end {theorem}
\begin {proof} 
Negating Theorem~\ref {T.section-I}, we have that $p$ is not in Section~I if and only if $m$ is not in section~I. Because section~III consists of only even numbers greater than 2, a prime (and an odd number) not in section~I must be in section~II. Hence, the theorem follows.
\end {proof}

\begin {theorem} \label {T.factors}	%-------------------------------------------------------------------------- theorem 3
If prime $p$ is in section~I of a class, then the factors of $p-1$ are 2 and primes in section~I of their class.
\end {theorem}
\begin {proof} 
Factor $p-1$ into the product of an even number and an odd number: $p-1 = 2^k m$, where $m$ is an odd number and $k&gt;0$. By Theorem~\ref {T.section-I}, $m$ is a number in section~I of its class. Using Shapiro's Property~11, we conclude that the prime factors of $m$ are all in section~I of their class. Clearly, 2 is also a factor of $p-1$, proving the theorem.
\end {proof}

\begin {theorem} \label {T.prime}	%-------------------------------------------------------------------------- theorem 4
If the smallest number in a class is odd prime $p$, then the prime factors of $p-1$ are 2 and primes that are the smallest numbers in their class.
\end {theorem}
\begin {proof} 
From properties of the $C$ function, we know that the smallest number in class~$n$ is either~$2^{n+1}$ or a number in section~I of the class. By assumption, the smallest number is prime. Hence, the prime $p$ must be in section~I. By Theorem~\ref {T.section-I}, if~$p$ is a prime in section~I and $p=1+2^k m$, with $k&gt;0$ and~$m$ odd, then~$m$ is a number in section~I of its class. Let~$q$ be a prime factor of~$m$. Then we can write $m= q \, s$ and
$$p = 1 + 2^k ~ q \, s$$
$$C(p) = k + C(q)+C(s).$$
Because~$m$ is in section~I, by Property~11,~$q$ is also. The prime~$q$ must be the least number in its class, otherwise if there is a smaller number,~$p$ would be smaller (but in the same class), which would contradict the assumption that~$p$ is the smallest number in its class. It is obvious that 2 is a prime factor of $p-1$.
\end {proof}


Combining this result with Catlin's theorem, the next theorem gives us a more complete description of the smallest number in a class.

\begin {theorem} \label {T.combined}	%------------------------------------------------------------------ theorem 5
Suppose that the smallest number $x$ in a class is odd. If $x$ is composite, then its prime factors are the smallest numbers in their respective classes. If~$x$ is prime, then the prime factors of $x-1$ are~2 and primes that are the smallest numbers in their respective classes.
\end {theorem}
\begin {proof} 
The composite case is implied by Catlin's theorem. The prime case is Theorem~\ref {T.prime}.
\end {proof}




\section {A multiplicative function}

For more insight into the odd numbers in sections I and II, it is useful to introduce the function
$$D(x)=\frac {x} {2^{C(x)}}$$
for odd integers $x$. (Here, D could mean ``depth''; we want low values of D.) Using Property~1, it is easy to show that $D$ is completely multiplicative; that is, for odd integers $x$ and $y$,
$$D(x y)=D(x) D(y).$$
Observe that $D(x) &lt; 2$ if and only if $x$ is in section~I of its class. If we write a prime number $p=1+2^k m$ with $m$ odd, then it is easy to show that
$$D(p)=2^{-C(p)}+D(m).$$
Hence, if $D(m)$ is very small, then $D(p)$ will be small. Clearly $D(1)=1$ is the smallest value of the $D$ function. If $F_5=2^{16}+1=65537$ is the largest Fermat prime, then $D(F_5)$ is the second-lowest value of the $D$ function. This value is so low that the first $45426=\lfloor (\log 2)/(\log D(F_5)) \rfloor$ powers of $F_5$ are also section~I numbers!




\section {Computing the least number in a class}

Let $c_n$ be the least number in class $n$. For $n=1, 2, 3,\ldots, 16, c_n$ is 
$$3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2329, 4369, 10537, 17477, 35209, 65537,$$
which is sequence \seqnum{A007755}. When computing $c_n$, there are two cases to consider: whether $c_n$ is composite or prime. As mentioned above, Catlin proves that when $c_n$ is composite, its factors are among the $c_k$ for $k&lt;n$. For instance, 
$$2329=c_{11}=c_4~c_7 \quad \text {and} \quad 4369=c_{12}=c_4~c_8.$$
When $c_n$ is prime, we know from Theorem~\ref {T.prime} that factors of $c_n-1$ are 2 and prime $c_k$ for $k&lt;n$. For instance, 
$$1097=c_{10}=1+2^3~c_7 \quad \text {and} \quad 17477=c_{14}=1+2^2~c_4~c_8.$$
For composite $c_n$, it follows from Property~1 that the sum of the subscripts (with repetition) in the product must be~$n$. For prime~$c_n$, it follows from Property~1 applied to $c_n-1$ that the sum of the exponent of~2 and subscripts (with repetition) in the product must be $n$. See Tables~\ref {Ta4} and~\ref {Ta5} for more examples of these formulas.



Hence, Catlin's theorem and Theorem~\ref {T.prime} give us the tools for finding the least number in a class. We start with $c_1=3$. If the $c_k$ are known for $k&lt;n$, we can compute $c_n$ using the following procedure:
First define the set of possible subscripts
$$K_n = \{k&lt;n: c_k \text{ is prime} \}.$$
Second, define the sets of restricted products of $c_k$
$$P_r = \Big \{ \prod_{}^{} c_{k_i} : k_i \in K_n, ~ r=\sum_{}^{} k_i \Big \} ,\quad r=1,2,3,\ldots,n,$$
that is, all products of prime $c_k$ such that the sum of the subscripts is $r$. Of course, $P_0=\{1\}$. Third, define the set
$$Q_n = \bigcup_{k=1}^{n} \Big (1+2^k P_{n-k} \Big ) .$$
Here, the notation $1+2^k P_{n-k}$ means that each element of the set $P_{n-k}$ is multiplied by $2^k$ and then incremented by~1. Finally, $c_n$ is the smallest of the three quantities: $2^{n+1}$, the least number in~$P_n$, and the least prime number in $Q_n$.



We have used the procedure described above, with some optimizations, to compute~$c_n$ for $n \le 1000$. For all these $n$, we found $c_n &lt; 2^{n+1}$, which supports the conjecture that all~$c_n$ are odd. The 280 values of $n \le 1000$ for which $c_n$ is a provable prime are in sequence \seqnum{A136040}. Tables~\ref {Ta4} and~\ref {Ta5} show~$c_n$ numerically and symbolically for~$n$ up to 100.



 We found that the first 22 powers (and only those powers) of Fermat prime $F_5$ are the least numbers in their class, which extends the result of Mills, who found that the first 15 powers of $F_5$ are the least numbers in their class. Moreover, as shown in the figure below, it appears that this 22nd power may be an upper bound: we found $D(c_n)&lt;D(F_5^{22})\approx 1.00034$ for $352&lt;n \le 1000$. The change at $n=352$ can be explained by there finally being enough primes $p$ having low $D(p)$ values  so that  for $n \ge 352$ the set $K_n$ is large enough to ensure that the $P_n$ and $Q_n$ sets have numbers very close to $2^n$; that is, very low $D$ values.

\begin {figure} [h]
\begin {center}
\includegraphics{D_Plot.eps}
\caption {$n$ versus $\log (D(c_n)-1)$}
\end {center}
\end {figure}

\begin {table} [H]
\begin {center}
{\footnotesize
\begin {tabular} [b] {|r|r|l|}
\hline
 &amp; &amp; \\[-6pt]
$n$ &amp; $c_n$ &amp; ~~~$c_n$ symbolically~~~ \\
 &amp; &amp; \\[-6pt]
\hline
1 &amp; 3 &amp; ~~~$1+2$ \\
2 &amp; 5 &amp; ~~~$1+2^{2}$ \\
3 &amp; 11 &amp; ~~~$1+2 ~c_{2}$ \\
4 &amp; 17 &amp; ~~~$1+2^{4}$ \\
5 &amp; 41 &amp; ~~~$1+2^{3} ~c_{2}$ \\
6 &amp; 83 &amp; ~~~$1+2 ~c_{5}$ \\
7 &amp; 137 &amp; ~~~$1+2^{3} ~c_{4}$ \\
8 &amp; 257 &amp; ~~~$1+2^{8}$ \\
9 &amp; 641 &amp; ~~~$1+2^{7} ~c_{2}$ \\
10 &amp; 1097 &amp; ~~~$1+2^{3} ~c_{7}$ \\
11 &amp; 2329 &amp; ~~~$c_{4} ~c_{7}$ \\
12 &amp; 4369 &amp; ~~~$c_{4} ~c_{8}$ \\
13 &amp; 10537 &amp; ~~~$c_{5} ~c_{8}$ \\
14 &amp; 17477 &amp; ~~~$1+2^{2} ~c_{4} ~c_{8}$ \\
15 &amp; 35209 &amp; ~~~$c_{7} ~c_{8}$ \\
16 &amp; 65537 &amp; ~~~$1+2^{16}$ \\
17 &amp; 140417 &amp; ~~~$1+2^{7} ~c_{10}$ \\
18 &amp; 281929 &amp; ~~~$c_{8} ~c_{10}$ \\
19 &amp; 557057 &amp; ~~~$1+2^{15} ~c_{4}$ \\
20 &amp; 1114129 &amp; ~~~$c_{4} ~c_{16}$ \\
21 &amp; 2384897 &amp; ~~~$1+2^{10} ~c_{4} ~c_{7}$ \\
22 &amp; 4227137 &amp; ~~~$1+2^{6} ~c_{8}^{2}$ \\
23 &amp; 8978569 &amp; ~~~$c_{7} ~c_{16}$ \\
24 &amp; 16843009 &amp; ~~~$c_{8} ~c_{16}$ \\
25 &amp; 35946497 &amp; ~~~$1+2^{15} ~c_{10}$ \\
26 &amp; 71304257 &amp; ~~~$1+2^{6} ~c_{4} ~c_{16}$ \\
27 &amp; 143163649 &amp; ~~~$c_{8} ~c_{19}$ \\
28 &amp; 286331153 &amp; ~~~$c_{4} ~c_{8} ~c_{16}$ \\
29 &amp; 541073537 &amp; ~~~$1+2^{7} ~c_{22}$ \\
30 &amp; 1086374209 &amp; ~~~$c_{8} ~c_{22}$ \\
31 &amp; 2281701377 &amp; ~~~$1+2^{27} ~c_{4}$ \\
32 &amp; 4295098369 &amp; ~~~$c_{16}^{2}$ \\
33 &amp; 9198250129 &amp; ~~~$c_{4} ~c_{29}$ \\
34 &amp; 18325194049 &amp; ~~~$c_{8} ~c_{26}$ \\
35 &amp; 36507844609 &amp; ~~~$c_{16} ~c_{19}$ \\
36 &amp; 73016672273 &amp; ~~~$c_{4} ~c_{16}^{2}$ \\
37 &amp; 139055899009 &amp; ~~~$c_{8} ~c_{29}$ \\
38 &amp; 277033877569 &amp; ~~~$c_{16} ~c_{22}$ \\
39 &amp; 586397253889 &amp; ~~~$c_{8} ~c_{31}$ \\
40 &amp; 1103840280833 &amp; ~~~$c_{8} ~c_{16}^{2}$ \\
41 &amp; 2336533512737 &amp; ~~~$1+2^{5} ~c_{4} ~c_{16}^{2}$ \\
42 &amp; 4673067091009 &amp; ~~~$c_{16} ~c_{26}$ \\
43 &amp; 9382516064513 &amp; ~~~$c_{8} ~c_{16} ~c_{19}$ \\
44 &amp; 17868687216769 &amp; ~~~$c_{22}^{2}$ \\
45 &amp; 35460336394369 &amp; ~~~$c_{16} ~c_{29}$ \\
46 &amp; 71197706535233 &amp; ~~~$c_{8} ~c_{16} ~c_{22}$ \\
47 &amp; 149535863144449 &amp; ~~~$c_{16} ~c_{31}$ \\
48 &amp; 281487861809153 &amp; ~~~$c_{16}^{3}$ \\
49 &amp; 600470787982337 &amp; ~~~$1+2^{10} ~c_{8} ~c_{31}$ \\
50 &amp; 1200978242389313 &amp; ~~~$c_{8} ~c_{16} ~c_{26}$ \\
\hline
\end {tabular}
}
\caption {Least Number in Classes 1 to 50}
\label {Ta4}
\end {center} 
\end {table}

\begin {table} [H]
\begin {center}
{\footnotesize
\begin {tabular} [b] {|r|r|l|}
\hline
 &amp; &amp; \\[-6pt]
$n$ &amp; $c_n$ &amp; ~~~$c_n$ symbolically~~~ \\
 &amp; &amp; \\[-6pt]
\hline
51 &amp; 2278291849363457 &amp; ~~~$1+2^{14} ~c_{8} ~c_{29}$ \\
52 &amp; 4538923050090497 &amp; ~~~$1+2^{14} ~c_{16} ~c_{22}$ \\
53 &amp; 9113306453352833 &amp; ~~~$~c_{8} ~c_{16} ~c_{29}$ \\
54 &amp; 18155969234239553 &amp; ~~~$~c_{16}^{2} ~c_{22}$ \\
55 &amp; 38280596832649217 &amp; ~~~$1+2^{51} ~c_{4}$ \\
56 &amp; 72342380484952321 &amp; ~~~$~c_{8} ~c_{16}^{3}$ \\
57 &amp; 153129396824244769 &amp; ~~~$~c_{16} ~c_{41}$ \\
58 &amp; 291621356718522497 &amp; ~~~$1+2^{7} ~c_{51}$ \\
59 &amp; 583242713437044737 &amp; ~~~$1+2^{22} ~c_{8} ~c_{29}$ \\
60 &amp; 1166485424718217217 &amp; ~~~$1+2^{30} ~c_{8} ~c_{22}$ \\
61 &amp; 2323964066277761153 &amp; ~~~$~c_{16}^{2} ~c_{29}$ \\
62 &amp; 4666084093199565121 &amp; ~~~$~c_{8} ~c_{16}^{2} ~c_{22}$ \\
63 &amp; 9800131862897754113 &amp; ~~~$~c_{16}^{2} ~c_{31}$ \\
64 &amp; 18447869999386460161 &amp; ~~~$~c_{16}^{4}$ \\
65 &amp; 39352453561210372097 &amp; ~~~$1+2^{26} ~c_{8} ~c_{31}$ \\
66 &amp; 74656206327888494657 &amp; ~~~$1+2^{6} ~c_{8} ~c_{52}$ \\
67 &amp; 148731430780247474177 &amp; ~~~$1+2^{22} ~c_{16} ~c_{29}$ \\
68 &amp; 297467399933780901889 &amp; ~~~$~c_{16} ~c_{52}$ \\
69 &amp; 592619738273148829697 &amp; ~~~$1+2^{29} ~c_{8} ~c_{16}^{2}$ \\
70 &amp; 1189887755704357584961 &amp; ~~~$~c_{16}^{3} ~c_{22}$ \\
71 &amp; 2426509543591652400137 &amp; ~~~$1+2^{3} ~c_{8}^{3} ~c_{22}^{2}$ \\
72 &amp; 4741102589842320261377 &amp; ~~~$~c_{8} ~c_{16}^{4}$ \\
73 &amp; 9630651773242695532609 &amp; ~~~$~c_{22} ~c_{51}$ \\
74 &amp; 19111988855261800431617 &amp; ~~~$1+2^{21} ~c_{8} ~c_{16} ~c_{29}$ \\
75 &amp; 38223977710523600863489 &amp; ~~~$~c_{8} ~c_{67}$ \\
76 &amp; 76447955279757801750529 &amp; ~~~$~c_{16} ~c_{60}$ \\
77 &amp; 152300948808147367100417 &amp; ~~~$1+2^{45} ~c_{8}^{2} ~c_{16}$ \\
78 &amp; 305801153216019899334977 &amp; ~~~$~c_{8} ~c_{16}^{3} ~c_{22}$ \\
79 &amp; 618769376430842916376577 &amp; ~~~$1+2^{12} ~c_{8}^{2} ~c_{22} ~c_{29}$ \\
80 &amp; 1209018056149790439571457 &amp; ~~~$~c_{16}^{5}$ \\
81 &amp; 2446371901576743388450817 &amp; ~~~$1+2^{12} ~c_{8} ~c_{16}^{2} ~c_{29}$ \\
82 &amp; 4892594491879703116251137 &amp; ~~~$1+2^{31} ~c_{51}$ \\
83 &amp; 9747411779045078715138049 &amp; ~~~$~c_{16} ~c_{67}$ \\
84 &amp; 19495120989460198967099393 &amp; ~~~$~c_{16}^{2} ~c_{52}$ \\
85 &amp; 38838519787207354851852289 &amp; ~~~$~c_{16} ~c_{69}$ \\
86 &amp; 77981673845596483045589057 &amp; ~~~$~c_{16}^{4} ~c_{22}$ \\
87 &amp; 157179431859730823152143377 &amp; ~~~$1+2^{4} ~c_{16}^{2} ~c_{22} ~c_{29}$ \\
88 &amp; 310717640430496142969864449 &amp; ~~~$~c_{8} ~c_{16}^{5}$ \\
89 &amp; 623843871662726366947180577 &amp; ~~~$1+2^{5} ~c_{16}^{2} ~c_{52}$ \\
90 &amp; 1252542413607292614886883329 &amp; ~~~$~c_{16} ~c_{74}$ \\
91 &amp; 2505084822584743524518887489 &amp; ~~~$~c_{22} ~c_{69}$ \\
92 &amp; 5010169645169487053324419073 &amp; ~~~$~c_{16}^{2} ~c_{60}$ \\
93 &amp; 9981347282039553997660028929 &amp; ~~~$~c_{16} ~c_{77}$ \\
94 &amp; 20041290178318296142716387649 &amp; ~~~$~c_{8} ~c_{16}^{4} ~c_{22}$ \\
95 &amp; 40394497616832409545668591809 &amp; ~~~$~c_{29} ~c_{66}$ \\
96 &amp; 79235416345888816038194577409 &amp; ~~~$~c_{16}^{6}$ \\
97 &amp; 160327875017320676305425408289 &amp; ~~~$~c_{8} ~c_{89}$ \\
98 &amp; 320645965214320103129750765569 &amp; ~~~$~c_{16} ~c_{82}$ \\
99 &amp; 638816125763277323754002317313 &amp; ~~~$~c_{16}^{2} ~c_{67}$ \\
100 &amp; 1277651744286253059706792919041 &amp; ~~~$~c_{16}^{3} ~c_{52}$ \\
\hline
\end {tabular}
}
\caption {Least Number in Classes 51 to 100}
\label {Ta5}
\end {center} 
\end {table}





\begin {thebibliography} {9}

\bibitem {Catlin}
P.~A.~Catlin, Concerning the iterated $\phi$ function, 
\emph{Amer. Math. Monthly}, \textbf{77} (1970), 60--61.

\bibitem {Erdos}
P.~Erdos, A.~Granville, C.~Pomerance, and C.~Spiro, On the normal behavior of the iterates of some arithmetic functions, in: \emph{Analytic Number Theory, Proceedings of a Conference in Honor of P. T. Bateman}, Birkhauser, Boston, 1990, 165-204.

\bibitem {Mills}
W.~H.~Mills, Iteration of the $\phi$ function,
\emph{Amer. Math. Monthly} \textbf{50} (1943), 547--549.

\bibitem {Shapiro}
Harold~Shapiro, An arithmetic function arising from the $\phi$ function,
\emph{Amer. Math. Monthly} \textbf{50} (1943), 18--30.

\bibitem {Sloane}
N.~J.~A.~Sloane, {\em \htmladdnormallink {The On-Line Encyclopedia of Integer Sequences}{http://www.research.att.com/~njas/sequences}}, published electronically at www.research.att.com/$\sim$njas/sequences.

\end {thebibliography}




\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 11A25.

\noindent \emph {Keywords:} Euler function, iteration, class number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A005239},
\seqnum{A007755},
\seqnum{A058811},
\seqnum{A058812},
\seqnum{A092878},
and
\seqnum{A136040}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 14 2007;
revised version received January 7 2008. 
Published in {\it Journal of Integer Sequences}, January 13 2008.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                







</pre></body></html>