\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>0$ by $\phi^n(x) = \phi( \phi^{n-1}(x))$. For $x>1$, $\phi(x)2^{C(x)}$.
\item For any integer $x$, $2^{C(x)} < x \le 2 \cdot 3^{C(x)}$.
\end {enumerate}
Thus, Shapiro proves that numbers $x$ in class $n>1$ fall into three sections:
$$2^n < x < 2^{n+1}, \quad \quad 2^{n+1} \le x \le 3^n, \quad \quad 3^n < 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
& & & \\[-6pt]
Class & \qquad \quad Section I & \qquad \qquad \qquad \quad Section II & \quad ~Section III \\
& & & \\[-6pt]
\hline
0 & 1, & 2, & \\
1 & 3, & 4, & 6, \\
2 & 5, 7, & 8, 9, & 10, 12, 14, 18, \\
3 & 11, 13, 15, & 16, 19, 20, 21, 22, 24, 26, 27, & 28, 30, 36, 38, 42, \\
& & & 54, \\
4 & 17, 23, 25, 29, 31, & 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, & 84, 86, 90, 98, 108, \\
& & 49, 50, 52, 56, 57, 58, 60, 62, 63, 66, 70, 72, & 114, 126, 162, \\
& & 74, 76, 78, 81, & \\
5 & 41, 47, 51, 53, 55, 59, 61, & 64, 65, 67, 68, 69, 71, 73, 75, 77, 79, 80, 82, & 252, 254, 258, 266, \\
& & 87, 88, 91, 92, 93, 94, 95, 96, 99, 100, 102, & 270, 294, 324, 326, \\
& & 104, 105, 106, 109, 110, 111, 112, 116, 117, & 342, 378, 486,\\
& & 118, 120, 122, 124, 127, 129, 130, 132, 133, & \\
& & 134, 135, 138, 140, 142, 144, 146, 147, 148, & \\
& & 150, 152, 154, 156, 158, 163, 168, 171, 172, & \\
& & 174, 180, 182, 186, 189, 190, 196, 198, 210, & \\
& & 216, 218, 222, 228, 234, 243, & \\
\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
& \\[-6pt]
Class & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad Numbers in Section I \\
& \\[-6pt]
\hline
0 & 1, \\
1 & 3, \\
2 & 5, 7, \\
3 & 11, 13, \textbf{15}, \\
4 & 17, 23, \textbf{25}, 29, 31, \\
5 & 41, 47, \textbf{51}, 53, \textbf{55}, 59, 61, \\
6 & 83, \textbf{85}, 89, 97, 101, 103, 107, 113, \textbf{115}, \textbf{119}, \textbf{121}, \textbf{123}, \textbf{125}, \\
7 & 137, 167, 179, \textbf{187}, 193, \textbf{205}, \textbf{221}, 227, 233, \textbf{235}, 239, 241, \textbf{249}, 251, \textbf{253}, \textbf{255}, \\
8 & 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 & 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 & 1097, 1283, \textbf{1285}, 1361, 1409, \textbf{1411}, 1433, 1439, \textbf{1445}, \textbf{1507}, \textbf{1513}, 1543, 1553, 1601,... \\
11 & \textbf{2329}, 2657, 2741, 2789, 2819, \textbf{2827}, \textbf{2839}, 2879, \textbf{3043}, 3089, \textbf{3151}, \textbf{3179}, 3203, \textbf{3205},... \\
12 & \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>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)} < p < 2^{C(p)+1}.
\end {equation*}
Substituting $p=1+2^k m$, we obtain
\begin {equation*}
2^{C(m)+k} < 1+2^k m < 2^{C(m)+k+1}.
\end {equation*}
Dividing by $2^k$ produces the inequality
\begin {equation*}
2^{C(m)} < m < 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)} < m < 2^{C(m)+1}.
\end {equation*}
Multiplying by $2^k$ produces the inequality
\begin {equation*}
2^{C(m)+k} < 2^k m < 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} < 1+2^k m < 2^{C(m)+k+1}.
\end {equation*}
But, for integers, this inequality is the same as
\begin {equation*}
2^{C(p)} < p < 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>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>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>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) < 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