<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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{amsthm}

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

\def\RR{I\!\!R}
\def\NN{I\!\! N}
\def\ZZ{Z\!\!\!Z}
\def\QQ{\mathbb Q}
\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 {On the Distribution of Perfect Totients}}
\vskip 1cm
\large
Florian~Luca\\
Instituto de Matem{\'a}ticas\\
Universidad Nacional Aut\'onoma de M{\'e}xico\\
C.P.~58089 \\
Morelia, Michoac{\'a}n \\
M{\'e}xico\\
\href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\
\end{center}

\vskip .2 in




\begin{abstract}
In this paper, we study the sum of iterates of the Euler function.
\end{abstract}

\renewcommand{\theequation}{\arabic{equation}}

\renewcommand{\theequation}{\arabic{equation}}

\newtheorem{prop}{Proposition}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{corollary}[cor]{Corollary}
\newtheorem{conj}[prop]{Conjecture}
\newtheorem{defi}[prop]{Definition}
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{fac}[prop]{Fact}
\newtheorem{facs}[prop]{Facts}
\newtheorem{com}[prop]{Comments}
\newtheorem{prob}{Problem}
\newtheorem{problem}[prob]{Problem}
\newtheorem{ques}{Question}
\newtheorem{question}[ques]{Question}
\newtheorem{remark}[prop]{Remark}

\section{Introduction}

For every positive integer $n$ we put $\phi(n)$ for the Euler function 
of $n$. If $k\ge 1$ we put $\phi^{(k)}(n)$ for the $k$th iterate of the Euler 
function evaluated in $n$ and $\kappa(n)$ for the smallest positive integer
$n$ such that $\phi^{(\kappa(n))}(n)=1$. Let
$$
F(n)=\sum_{k=1}^{\kappa(n)} \phi^{(k)}(n).
$$
Positive integers $n$ such that $F(n)=n$ are called 
{\it perfect totients} and were introduced in \cite{MS} and studied also
in \cite{Ian} and \cite{S}. 
Let ${\cal M}$ be the set of all perfect totients. This set 
contains all powers of $3$ so it is certainly infinite. 
In the recent paper \cite{S} it was shown that ${\cal M}$ 
is of asymptotic density zero. More precisely, if we write 
${\cal M}(x)={\cal M}\cap [1,x]$, then it was shown in Theorem
2.2 in \cite{S} -- a little bit more than -- that the estimate
\begin{equation}
\label{eq:M(x)S}
\#{\cal M}(x)\le \frac{x}{(\log x)^{1+o(1)}}
\end{equation}
holds as $x\to\infty$. The above estimate \eqref{eq:M(x)S} is too weak to
allow one to decide whether the sum
\begin{equation}
\label{eq:sumofreciprocalsM}
\sum_{m\in {\cal M}}\frac{1}{m}
\end{equation}
is finite. Here, we prove a stronger upper bound on $\#{\cal M}(x)$ 
than \eqref{eq:M(x)S} which in particular implies that the sum of the series 
\eqref{eq:sumofreciprocalsM} is convergent.

\begin{theorem}
\label{thm:1}
The estimate
\begin{equation}
\label{eq:M(x)L}
\#{\cal M}(x)\le \frac{x}{(\log x)^{2+o(1)}}
\end{equation}
holds as $x\to\infty$.
\end{theorem}

It was also shown in \cite{S} that the inequality 
\begin{equation}
\label{eq:F(n)minusnS}
|F(n)-n|&gt;(\log n)^{\ln 2+o(1)}
\end{equation}
holds on a set of positive integers $n$ of asymptotic density $1$. Here,
we improve this to:

\begin{theorem}
\label{thm:2}
Let $\varepsilon(x)$ be any function defined on the positive real numbers 
$x$ with values in the positive real numbers which is decreasing for large
$x$ and 
$\lim_{x\to\infty} \varepsilon(x)=0$. Then the inequality 
\begin{equation}
\label{F(n)minusnL}
n-F(n)&gt;\varepsilon(n)n
\end{equation}
holds on a set of positive integers $n$ of asymptotic density $1$.
\end{theorem} 

Let ${\cal U}(x)=\{F(n)\le x\}$. In \cite{S}, it was shown that 
$\#{\cal U}(x)\gg (\log x)^2$ and it was asked to show that 
$\log(\#{\cal U}(x))/\log\log x$ tends to infinity with $x$. We prove:

\begin{theorem}
\label{thm:3}
The estimate 
\begin{equation}
\label{eq:U(x)L}
\log\left(\#{\cal U}(x)\right)\gg  
\frac{(\log\log x)^2}{\log\log\log\log x}
\end{equation}
holds for all positive integers $x$.
\end{theorem}

Throughout this paper, we use $\log x=\max\{\ln x, 1\}$, where $\ln $ is 
the natural logarithm. Further, if $k\ge 1$, we write $\log_k x$ for the 
$k$th fold iterate of the function $\log $. We omit the subscript when $k=1$.
We use the Vinogradov symbols $\ll $, $\gg$ and $\asymp$, as well as the 
Landau symbols $O$ and $o$ with their regular meanings. The constants 
of convergence implied by them may depend on some fixed parameters 
such as $K$ (see Section \ref{sec:aux}). For a positive 
integer $n$, we use $P(n)$ for its largest prime factor with the convention 
that $P(1)=1$, $\omega(n)$ for the number of distinct prime factors of $n$ 
and $\nu_2(n)$ for the $2$-adic order of $n$; i.e., the largest non-negative 
integer $k$ such that $2^k\mid n$. We use $p,~q$ and $r$ to denote prime
numbers and $c_0,~c_1,~\ldots$ to denote positive constants which are 
absolute.


\section{Proof of Theorem 1}
\label{sec:proofThm1}

The proof of inequality \eqref{eq:M(x)S} in \cite{S} is based on the 
 fact that if we put ${\cal V}(x)=\{\phi(n)\le x\}$, then 
$\#{\cal V}(x)\le x/(\log x)^{1+o(1)}$ (see \cite{Fo} and \cite{MP}) 
together with the observation
that if $n\in {\cal M}(x)$, then $n=v+F(v)$ for some $v\in {\cal V}(x)$
(namely, $v=\phi(n)$). 

\medskip

For our proof of Theorem \ref{thm:1}, we take a different approach and 
we exploit the numbers $\nu_2(\phi^{(2)}(n))$  and $\nu_2(\phi^{(3)}(n))$ 
for $n\in {\cal M}(x)$. Before we start, we record a result which might 
be of independent interest.

 
\subsection{An auxiliary result}
\label{sec:aux}

Let $K&gt;0$ be any fixed constant. Put 
$$
{\cal N}(K,x)=\{n\le x~:~\nu_2(\phi^{(2)}(n))\le K\log_2 x\}.
$$

\begin{lemma}
\label{lem:1}
\begin{itemize} 
\item[(i)] The estimate 
$$
\sum_{n\in {\cal N}(K,x)}\frac{1}{n}=(\log x)^{o(1)}
$$
holds as $x\to\infty$.

\item[(ii)] Let $\pi(K,x)=\#\{p\le x~:~p-1\in {\cal N}(K,x)\}$. Then 
$$
\pi(K,x)\le \frac{x}{(\log x)^{2+o(1)}}
$$
holds as $x\to\infty$.
\end{itemize}
\end{lemma}

\begin{proof} (i) Put $L=10\log_2 x$. Let ${\cal N}_1$ be the set 
of $n\in {\cal N}(K,x)$ with $\omega(n)\ge L$ and note that
\begin{eqnarray}
\label{eq:S1}
S_1 &amp; = &amp; \sum_{n\in {\cal N}_1}\frac{1}{n} 
\le \sum_{\substack{n\le x\\ \omega(n)\ge L}}\frac{1}{n}
\le  \sum_{k\ge L}\sum_{\substack{n\le x\\ \omega(n)=k}}\frac{1}{n}
\le  \sum_{k\ge L}\frac{1}{k!}\left(\sum_{p^{\alpha}\le x}
\frac{1}{p^{\alpha}}\right)^k\nonumber\\
&amp; \le &amp;   \sum_{k\ge L}\frac{1}{k!}\left(\log_2 x+c_0\right)^k
 \ll  \sum_{k\ge L}\left(\frac{e\log_2 x+ec_0}{k}\right)^k\nonumber\\
&amp; \le &amp; \sum_{k\ge L}\left(\frac{e\log_2 x+ec_0}{L}\right)^k
 \ll  \left(\frac{e\log_2 x+ec_0}{L}\right)^L
 \ll  1.
\end{eqnarray}
In the above inequalities, we used the multinomial formula, the 
unique factorization, the estimate $k!\gg (k/e)^k$ which 
follows from Stirling's formula, as well as the known fact that the estimate
$$
\sum_{p\le x}\sum_{\alpha\ge 1}\frac{1}{p^{\alpha}}\le \log_2 x + c_0
$$
holds for all $x$ with some absolute constant $c_0$.

\medskip

Put $y=(\log x)^2$ and 
let ${\cal N}_2$ be the subset of $n\in {\cal N}(K,x)$ having two distinct 
prime 
factors $p$ and $q$ such that $\gcd(p-1,q-1)$ is a multiple of some prime 
$r&gt;y$. Writing $n=pqm$ for some positive integer $m$, we see that  
the sum $S_2$ of the reciprocals of $n\in {\cal N}_2$ satisfies
\begin{eqnarray}
\label{eq:S2}
S_2 &amp; = &amp; \sum_{n\in {\cal N}_2}\frac{1}{n}\le \sum_{y&lt;r
\le x}\sum_{\substack{p\le x,~q\le x\\ r\,|\, \gcd(p-1,q-1)}}\sum_{m\le x/pq}
\frac{1}{pqm}\nonumber \\
&amp; \le &amp;  \sum_{y&lt; r\le x}\frac{1}{2}\left(\sum_{\substack{p\le x\\
p\equiv 1\pmod r}}\frac{1}{p}\right)^2\left(\sum_{m\le x}\frac{1}{m}\right)
 \ll  \log x (\log_2 x)^2\sum_{y&lt;r}
\frac{1}{r^2}\nonumber\\
&amp; \ll &amp;  \frac{\log x(\log_2 x)^2}{y\log y}=\frac{\log_2 x}{\log x}\ll 1,
\end{eqnarray}
where we used the known estimate
$$
\sum_{\substack{p\le t\\ p\equiv 1\pmod b}}\frac{1}{p}\ll 
\frac{\log_2 t}{\phi(b)}
$$
which holds 
uniformly for $1\le b\le t$ (see Lemma 1 of \cite{BKW} or the inequality 
(3.1) in \cite{EGPS}), as well as the fact that 
$$
\sum_{t\le p}\frac{1}{p^2}\ll \frac{1}{t\log t}
$$
which follows by partial summation from the Prime Number Theorem.

Now we deal with the numbers $n\in {\cal N}_3={\cal N}(K,x)\backslash 
({\cal N}_1\cup {\cal N}_2)$. Let $z$ be such that 
$\log_2 z=\log_2 x/\log_3 x$. For a positive integer $n$ and a real number 
$t$ write $\omega_{&gt;t}(n)$ for the number of distinct prime factors 
$p&gt;t$ of $n$. Let $n\in {\cal N}_3$ and write it as $n=abc$, where
\begin{itemize}
\item[(i)] all prime factors of $a$ are $\le z$;
\item[(ii)] all prime factors $p$ of $b$ are $&gt;z$ but 
$\omega_{&gt;y}(p-1)&lt;\log_2 p/(\log_3 p)^2$;
\item[(iii)] all prime factors $p$ of $c$ are $&gt;z$ and 
$\omega_{&gt;y}(p-1)\ge \log_2 p/(\log_3 p)^2$.
\end{itemize}
Note that if $p\mid c$, then 
$$
\omega_{&gt;y}(p-1)\ge \frac{\log_2 p}{(\log_3 p)^2}\ge 
\frac{\log_2 z}{(\log_3 z)^2}&gt;
\frac{\log_2 x}{(\log_3 x)^3}
$$
for large $x$. Further, for $t&gt;2$ we have that 
$\omega_{&gt;t}(n)\le\nu_2(\phi(n))$. 
Furthermore, since $n\not\in {\cal N}_2$, we have that 
\begin{eqnarray*}
\sum_{p\, |\, c}\omega_{&gt;y}(p-1) &amp; \le &amp; \sum_{p\, |\, n}\omega_{y}(p-1)= 
\omega_{&gt;y}\left(\prod_{p\, |\, n} (p-1)
\right)\\
&amp; \le &amp; \nu_2\left(\phi\left(\prod_{p\, |\, n} (p-1)\right)\right)\le 
\nu_2(\phi^{(2)}(n))
\le K\log_2 x.
\end{eqnarray*}
We thus get that
$$
\omega(c)\frac{\log_2 x}{(\log_3 x)^3}&lt;\sum_{p\, |\, c}\omega_{&gt;y}(p-1)
\le K\log_2 x,
$$
therefore 
$$
\omega(c)&lt; K(\log_3 x)^3.
$$
Let ${\cal A},~{\cal B}$ and ${\cal C}$ be the subsets of all possible 
values of $a,~b$ and $c$, respectively. Thus,
\begin{equation}
\label{eq:S3}
S_3=\sum_{n\in {\cal N}_3}\frac{1}{n}\le ABC,
\end{equation}
where
\begin{equation}
\label{eq:ABC}
A=\sum_{a\in {\cal A}}
\frac{1}{a},\qquad B=\sum_{b\in {\cal B}}\frac{1}{b}\qquad 
{\text{\rm and}}\qquad C=\sum_{c\in {\cal C}}
\frac{1}{c}.
\end{equation}
Since the union of ${\cal N}_i$ for $i=1,~2$ and $3$ covers 
${\cal N}(K,x)$ it follows, by estimates \eqref{eq:S1}, \eqref{eq:S2}, 
\eqref{eq:S3} and \eqref{eq:ABC},
that in order to establish (i) it suffices to show that
\begin{equation}
\label{eq:maxABC}
\max\{A,B,C\}\le (\log x)^{o(1)}\qquad {\text{\rm as}}~x\to\infty.
\end{equation}
Clearly ${\cal A}\subset \{a\le x~:~P(a)\le z\}$
and ${\cal C}\subset \{c\le x~:~\omega(c)\le K(\log_3 x)^3\}$. Hence,
\begin{eqnarray}
\label{eq:A}
A &amp; \le &amp; \prod_{p\le z}\left(\sum_{\alpha\ge 0}\frac{1}{p^{\alpha}}\right)
\le \exp\left(\sum_{p\le z}\sum_{\alpha\ge 1}\frac{1}{p^{\alpha}}\right)
\le \exp(\log_2 z+c_0)\nonumber\\
&amp; \ll &amp; \log z=(\log x)^{1/\log_3 x}=(\log x)^{o(1)}
\qquad {\text{\rm as}}~x\to\infty,
\end{eqnarray}
while by an argument similar to the one used to bound $S_1$ (see 
estimate \eqref{eq:S1}), we get
\begin{eqnarray}
\label{eq:C}
C &amp; \le &amp; 
\sum_{k\le K(\log_3 x)^3}\sum_{\substack{c\le x\\ \omega(c)=k}}\frac{1}{c}
\le \sum_{k\le K(\log_3 x)^3}\left(\frac{e\log_2 x+ec_0}{k}\right)^k
\nonumber\\
&amp; \ll &amp;
(\log_3 x)^3(e\log_2 x+ec_0)^{K(\log_3 x)^3}\nonumber\\
&amp; = &amp; (\log x)^{O((\log_3 x)^4/\log_2 x)}=
(\log x)^{o(1)}\qquad {\text{\rm as}}~x\to\infty.
\end{eqnarray}
For ${\cal B}$, let $f(t)=(\log t)^{3\log_3 t}$ and 
note that 
\begin{eqnarray*}
f(z)  = \exp(3\log_2 z\log_3 z) &amp; &gt; &amp; \exp(2\log_2 z\log_3 x)=\exp(2\log_2 x)=
(\log x)^2\\
&amp; = &amp; y\qquad {\text{\rm for~large}}~x,
\end{eqnarray*}
therefore all the primes $p$ dividing $b\in {\cal B}$
belong to the set 
$$
{\cal P}=\{p~:~\omega_{&gt;f(p)}&lt;\log_2 p/(\log_3 p)^2\}
$$
for large values of $x$. We show that 
\begin{equation}
\label{eq:sum1overP}
\sum_{p\in {\cal P}}\frac{1}{p}=O(1).
\end{equation}
Note that once the above estimate \eqref{eq:sum1overP} is proved, then 
$$
B=\sum_{b\in {\cal B}}\frac{1}{b}\le \prod_{p\in {\cal P}} 
\left(\sum_{\alpha\ge 0}\frac{1}{p^{\alpha}}\right)\le 
\exp\left(\sum_{p\in {\cal P}}\sum_{\alpha\ge 1}\frac{1}{p^{\alpha}}\right)
=\exp(O(1))=O(1),
$$
which together with estimates \eqref{eq:A} and \eqref{eq:C} 
implies estimate \eqref{eq:maxABC} and completes  the proof of (i). 

\medskip

Thus,
it remains to prove estimate \eqref{eq:sum1overP}. For this, let 
$t&gt;0$ and put ${\cal P}(t)={\cal P}\cap [1,t]$. We estimate 
the counting function $\#{\cal P}(t)$ of ${\cal P}$. Let $p\in {\cal P}(t)$. 
Let ${\cal P}_1=\{p\le t~:~P(p-1)\le t^{1/\log_2 t}\}$. 
By results from \cite{CEP} (see also Chapter III.5 of \cite{Ten}), 
it follows that 
\begin{equation}
\label{eq:P1}
\#{\cal P}_1(t)\le t\exp(-(1+o(1))\log_2 t\log_3 t)=
o\left(\frac{t}{(\log t)^2}\right)\qquad {\text{\rm as}}~t\to\infty.
\end{equation}
For $p\in {\cal P}_2={\cal P}(t)\backslash {\cal P}_1$, we write 
$p-1=q\ell$, where $q=P(p-1)$ and $\ell$ is some positive integer. Fix 
$\ell$. Then $q\le t/\ell$ is such that both linear forms $q$ and $q\ell+1$ 
are primes. By Brun's sieve (see, for example, Theorem 2.3 in \cite{HR}), 
the number of such primes $q$ is 
$$
\ll \frac{t}{\ell(\log(t/\ell))^2}\left(\frac{\ell}{\phi(\ell)}\right)^2
\le \frac{t(\log_2 t)^4}{\ell(\log t)^2},
$$
where we used the minimal order $\phi(\ell)/\ell\gg 1/\log_2 t$ of the
Euler function in the interval $[1,t]$ as well as the fact that 
$$
\log\left(\frac{t}{\ell}\right)\ge \log q\ge \log(t^{1/\log_2 t})=
\frac{\log t}{\log_2 t}.
$$
Since $\ell$ is a divisor of $p-1$, we get that if we write 
$\ell=\ell_1 \ell_2$, where $P(\ell_1)\le f(t)$ and every prime 
factor of $\ell_2$ is $&gt;f(t)$, then 
$$
\omega(\ell_2)=\omega_{&gt;f(t)}(p-1)
\le \omega_{&lt;f(p)}(p-1)\le \frac{\log_2 p}{(\log_3 p)^2}\le 
\frac{\log_2 t}{(\log_3 t)^2}
$$
for large $t$. Hence, summing up over all possible $\ell$'s we get 
\begin{equation}
\label{eq:L1L2}
\#{\cal P}_2(t)\le \frac{t(\log_2 t)^4}{(\log t)^2} L_1L_2,
\end{equation}
where
\begin{equation}
\label{eq:L1L2def}
L_1=\sum_{P(\ell_1)\le f(t)}\frac{1}{\ell_1}\qquad {\text{\rm and }}\qquad 
L_2=\sum_{\substack{\ell_2\le t\\
\omega(\ell_2)\le \log_2 t/(\log_3 t)^2}}\frac{1}{\ell_2}.
\end{equation}
Clearly, by the argument used to bound $A$ 
(see \eqref{eq:A}), we have
\begin{eqnarray}
\label{eq:L1}
L_1 &amp; = &amp; 
\sum_{P(\ell_1)\le f(t)}\frac{1}{\ell_1}\le \exp\left(\sum_{p\le f(t)}
\sum_{\alpha\ge 1}
\frac{1}{p^{\alpha}}\right)\le \exp\left(\log_2 f(t)+c_0\right)\nonumber\\
&amp; = &amp;  
\exp(\log_3 t+\log_4 t+c_0+\log 3)\ll \log_2 t\log_3 t,
\end{eqnarray}
while by the argument used to bound $S_1$ (see \eqref{eq:S1}) or 
$C$ (see \eqref{eq:C}) we have
\begin{eqnarray}
\label{eq:L2}
L_2 &amp; \le &amp; \sum_{\omega(\ell_2)\le \log_2 t/(\log_3 t)^2}\frac{1}{\ell_2}
\le \sum_{k\le \log_2 t/(\log_3 t)^2}
\left(\frac{e\log_2 t+ec_0}{k}\right)^k\nonumber\\
&amp; \ll &amp; \log_2 t(e\log_2 t+
ec_0)^{\log_2 t/(\log_3 t)^2}=\exp(O(\log_2 t/\log_3 t))\nonumber\\
&amp; = &amp; (\log t)^{o(1)}\qquad {\text{\rm as}}~t\to\infty.
\end{eqnarray}
Now estimates \eqref{eq:L1}, \eqref{eq:L2} and 
\eqref{eq:L1L2} show that 
\begin{equation}
\label{eq:P2}
\#{\cal P}_2\le \frac{t}{(\log t)^{2+o(1)}}\qquad {\text{\rm as}}~t\to\infty,
\end{equation}
and since ${\cal P}_i$ with $i=1$ and $2$ cover ${\cal P}(t)$, we get, 
by estimates \eqref{eq:P1} and \eqref{eq:P2}, that  
\begin{equation}
\label{eq:countP}
\#{\cal P}(t)\le \#{\cal P}_1+\#{\cal P}_2\le \frac{t}{(\log t)^{2+o(1)}}
\qquad {\text{\rm as}}~t\to\infty.
\end{equation}
Estimate \eqref{eq:sum1overP} follows now from
the above estimate \eqref{eq:countP} by partial summation, which completes
the proof of (i).

\medskip

(ii) Let ${\cal R}(K,x)=\{p\le x~:~p-1\in {\cal N}(K,x)\}$. Let 
$y=x^{1/\log_2 x}$ and ${\cal R}_1=\{p\le x~:~P(p-1)\le y\}$. Estimate 
\eqref{eq:P1} shows that 
\begin{equation}
\label{eq:R1}
\#{\cal R}_1\le x\exp(-(1+o(1))\log_2 x\log_3 x)=o\left(\frac{x}{(\log x)^2}
\right)\qquad {\text{\rm as}}~x\to\infty.
\end{equation}
For $p\in {\cal R}_2={\cal R}(K,x)\backslash {\cal R}_1$, we write 
$p-1=q\ell$, where $q=P(p-1)$. The argument used in the proof of (i) to 
bound ${\cal P}_2$ shows that for a fixed $\ell$ the number of choices
for $q\le x/\ell$ is 
$$
\ll \frac{x(\log_2 x)^4}{\ell (\log x)^2}.
$$
Upon noticing that $\ell\mid p-1$ implies that $\ell \in {\cal N}(K,x)$, we 
get, by using (i), that 
\begin{equation}
\label{eq:R2}
\#{\cal R}_2\le \frac{x(\log_2 x)^4}{(\log x)^2}\sum_{\ell\in {\cal N}(K,x)}
\frac{1}{\ell}=\frac{x}{(\log x)^{2+o(1)}}\qquad {\text{\rm  as}}~x\to\infty.
\end{equation}
Since 
$$
\pi(K,x)\le \#{\cal R}_1+\#{\cal R}_2,
$$
(ii) follows from estimates \eqref{eq:R1} and \eqref{eq:R2}.
\end{proof}

\subsection{The Proof of Theorem \ref{thm:1}}

We start by sieving off a few sets of positive integers $n\le x$ of 
cardinalities $O(x/(\log x)^2)$. We ignore the following 
positive integers $n\le x$:
\begin{itemize}
\item[(i)] positive integers $n\le x$ with $P(n)\le y=x^{1/\log_2 x}$. 
By the results from \cite{CEP} or Theorem XX in \cite{Ten} we get, as in the 
estimates of $\#{\cal P}_1$ or $\#{\cal R}_1$ in Lemma \ref{lem:1}, that the 
number of such $n$ does not exceed
$$
x\exp(-(1+o(1))\log_2 x\log_3 x)=o\left(\frac{x}{(\log x)^2}\right)\qquad 
{\text{\rm as}}~x\to\infty.
$$
\item[(ii)] positive integers $n\le x$ 
for which there exists a prime 
$q&gt;(\log x)^2$ such that $q^2\mid n$. It is clear that the number 
of such positive integers does not exceed
$$
\sum_{(\log x)^2&lt;q\le x^{1/2}}
\frac{x}{q^2}\ll \frac{x}{(\log x)^2\log_3 x}=
o\left(\frac{x}{(\log x)^2}\right)
\qquad {\text{\rm as}}~x\to\infty.
$$
\item[(iii)] positive integers $n\le x$ not satisfying (i) and (ii) 
above such that if we put $z=y^{1/\log_2 x}$, then 
$n=Pm$, where $P=P(n)$, and $P(p-1)&lt;z$. Fix the number $m$. 
Since $\log P/\log z\ge \log P/\log z\ge \log_2 x$, it follows again by 
the results from \cite{CEP} or Theorem XX in \cite{Ten}, that 
the number of possible values for $P$ is 
$$
\le \frac{x}{m}\exp(-(1+o(1))\log_2\log_3 x)=o\left(\frac{x}{m(\log x)^3}
\right)\qquad {\text{\rm as}}~x\to\infty
$$
and uniformly in $m\le x/P\le x/y$. Thus, summing up over all the possible 
values of $m\le x$, 
we get that the total number of such integers $n$ does not exceed
$$
\frac{x}{(\log x)^3}\sum_{m\le x}\frac{1}{m}\ll\frac{x}{(\log x)^2}
$$
if $x$ is sufficiently large.
\item[(iv)] positive integers $n\le x$ not satisfying (i)--(iii) such that 
$q^2\mid P-1$ for some $q\ge (\log x)^3$, where $P=P(n)$. Write again 
$n=Pm$. For fixed values of $m$ and $q$, the number of such choices for 
$P\le x/m$, even neglecting the fact that it is prime, is at most $x/mq^2$. 
This shows that the totality of such integers $n$ does not exceed  
\begin{eqnarray*}
&amp; &amp; \sum_{m\le x/y}\sum_{(\log x)^3\le q\le (x/m)^{1/2}}
\frac{x}{mq^2}\le x\left(\sum_{m\le x}\frac{1}{m}\right)
\left(\sum_{(\log x)^3\le q}
\frac{1}{q^2}\right)\\
&amp; &amp; \ll x\log x \int_{(\log x)^3}^{\infty} \frac{dt}{t^2}= 
O\left(\frac{x}{(\log x)^2}
\right)\qquad {\text{\rm as}}~x\to\infty.
\end{eqnarray*}
\item[(v)] positive integers $n\le x$ not of the form (i)--(iv) such that 
if we write again $n=Pm$, where $P=P(n)$, then  
there exists a prime $q&gt;(\log x)^2$ with the property that $q\mid
\gcd(P-1,\phi(m))$. 
Since $n$ is not like in (ii), it follows that 
$q^2$ does not divide $n$. Thus, there must exist a prime factor 
$r$ of $m$ such that $q\mid r-1$. Fixing $q$, $r$ and $P$, we get that 
the number of $n\le x$ which are multiples of $Pr$ does not exceed 
$x/Pr$. Hence, the totality of such integers $n$ does not exceed
\begin{eqnarray*}
&amp; &amp; \sum_{(\log x)^2\le q\le x^{1/2}}
\sum_{\substack{q\, |\, \gcd(P-1,r-1)\\
Pr\le x}}\frac{x}{Pr}
\le  x\sum_{(\log x)^2\le q\le x^{1/2}}
\frac{1}{2}\left(\sum_{\substack{p\equiv 1
\pmod q\\ p\le x}}\frac{1}{p}\right)^2
\\
&amp; &amp; \ll x(\log_2 x)^2
\sum_{(\log x)^2\le q\le x^{1/2}}\frac{1}{q^2}
\ll \frac{x\log_2  x}{(\log x)^2}.
\end{eqnarray*}
\item[(vi)] positive integers $n$ not of the form (i)--(v) such that 
if we write $n=Pm$ with $P=P(n)&gt;P(m)$, then 
$m\equiv -1\pmod {2^{M}}$, where $M=\lfloor 5\log_2 x\rfloor$.
For each such fixed $m$, the number of possible choices for $P\le x/m$
is 
$$
\pi\left(\frac{x}{m}\right)\le \frac{x}{m\log(x/m)}\le \frac{x}{m\log y}=
\frac{x\log_2 x}
{m\log x}.
$$
Summing up over all the $m\le x$ of the form $m=2^{M}\lambda-1$ for some 
$\lambda\ge 1$, we get that the totality of such $n$ does not exceed
\begin{eqnarray*}
&amp; &amp; \frac{x\log_2 x}{\log x}\sum_{1\le \lambda\le  x/2^M}
\frac{1}{2^M\lambda-1}\ll 
\frac{x\log_2 x}{2^{M}\log x}\sum_{1\le \lambda\le x}\frac{1}{\lambda}\\
&amp;&amp; \ll 
\frac{x\log_2 x}{2^M}\ll \frac{x\log_2 x}{(\log x)^{5\log 2}}=
o\left(\frac{x}{(\log x)^2}
\right)\qquad {\text{\rm as}}~x\to\infty.
\end{eqnarray*}
\end{itemize}

From now on, we work with the set ${\cal M}'$ 
of the perfect totients $n\le x$ not satisfying any of the conditions 
(i)--(vi) above. Note that if $n&gt;2$, then $F(n)$ is always odd. Hence,
$n$ is odd. 

\medskip

Let ${\cal M}_1$ be the subset 
of $n\in {\cal M}'$ such that $\nu_2(\phi^{(2)}(n))\ge 2M$. We now 
make the observation that if $m$ is an even number, 
then $\nu_2(\phi(m))\ge \nu_2(m)$ {\it except}
when $m$ is a power of $2$. Further, note that if $\phi^{(\ell)}(m)$ is a power
of $2$, then $\phi^{(\ell+i)}(m)$ is also a power of $2$ 
for all $i\ge 0$. Thus, letting $\kappa_1(n)$ be the largest
positive integer $\ell\ge 2$ such that 
$\phi^{(\ell)}(n)$ is not a power of $2$, from the above remark we get that 
for $n\in {\cal M}_1$ we have
$$
2M\le \nu_2(\phi^{(2)}(n))\le \nu_2(\phi^{(3)}(n))\le 
\ldots \le \nu_2(\phi^{(\kappa_1(n)+1)}(n)).
$$
Writing $\phi^{(\kappa_1(n)+1)}(n)=2^{\beta}$ with some $\beta\ge 2M$, we get 
$$
\sum_{k=\kappa_1(n)+1}^{\kappa(n)} \phi^{(k)}(n)=\sum_{i=0}^{\beta}
2^i=2^{\beta+1}-1.
$$
Since $n$ is a perfect totient, we get the following congruence 
\begin{eqnarray}
\label{eq:cong}
n-\phi(n)+1 &amp; = &amp; 1+
\sum_{k=2}^{\kappa(n)}\phi^{(k)}(n) =  1+
\sum_{k=2}^{\kappa_1(n)}\phi^{\ell}(n)+
\sum_{k=\kappa_1(n)+1}^{\kappa(n)}\phi^{(k)}(n)\nonumber\\
&amp; = &amp; \sum_{\ell=2}^{\kappa_1(n)}\phi^{(k)}(n)+2^{\beta+1}
\equiv  0
\pmod {2^{2M}}.
\end{eqnarray}
Write $n=Pm$, where $P&gt;\max\{P(m),y\}$ for large $x$ 
because $n$ is neither as in (i) nor as in (ii). So
$$
n-\phi(n)+1=Pm-(P-1)\phi(m)+1=P(m-\phi(m))+(\phi(m)+1).
$$
Note that $m&gt;2$ if $x$ is large enough. Indeed, since $n$ is odd
we get that if $m\le 2$, then $m=1$ and $n=P$, therefore 
$$
P\ge \phi(P)+\phi(\phi(P))=P-1+\phi(P-1),
$$
leading to $1\ge \phi(P-1)$; thus, $P\le 3$, which is impossible 
for large $x$ since $P&gt;y$. Since 
$m&gt;2$, we get that $m-\phi(m)&gt;0$ and $\phi(m)+1$ is odd. 
Thus, for fixed odd $m&gt;1$ the congruence 
$$
P(m-\phi(m))+\phi(m)+1\equiv 0\pmod {2^{2M}}
$$
puts $P$ into a certain residue class $a_m$ modulo $2^{2M}$. 
Since $P\le x/m$, it follows that the number of possibilities for $P$ 
is $\pi(x/m;2^{2M},a_m)$. By a result of Montgomery and Vaughan \cite{MV},
we know that 
\begin{equation}
\label{eq:pi}
\pi(x/m;2^{2M},a_m)\le \frac{2x}{m\phi(2^{2M})\log(x/m2^{2M})}.
\end{equation}
Note that 
\begin{equation}
\label{eq:2toM}
\frac{x}{m2^{2M}}\ge \frac{y}{(\log x)^{10\ln 2}}&gt;y^{1/2}
\end{equation}
if $x$ is sufficiently large. Hence, inequalities \eqref{eq:pi} and 
\eqref{eq:2toM} lead to 
\begin{equation}
\label{eq:pi1}
\pi(x/m;2^{2M},a_m)\ll \frac{x}{m2^{2M}\log y}\ll \frac{x\log_2 x}
{m(\log x)^{1+10\ln 2}}.
\end{equation}
Summing up over all the possible choices for $m$ we get that 
\begin{eqnarray}
\label{eq:M1}
\#{\cal M}_1 &amp; \le &amp; \sum_{m\le x/y}\pi(x/m;2^{2M},a_m)\ll 
\frac{x\log_2 x}{(\log x)^{1+10\ln 2}}\sum_{m\le x/y}
\frac{1}{m}\nonumber\\
&amp; \ll &amp; \frac{x\log_2 x}{(\log x)^{10\ln 2}}
= 
o\left(\frac{x}{(\log x)^2}\right)\qquad {\text{\rm as}}~x\to\infty.
\end{eqnarray}


Now let ${\cal M}_2$ be the subset of $n\in {\cal M}'\backslash 
{\cal M}_1$ such that $\nu_2(\phi^{(3)}(n))&lt;4M$. Let 
$n=mP$. Since $n\not\in {\cal M}_1$, it follows that $\nu_2(\phi^{(2)}(m))
\le \nu_2(\phi^{(2)}(n))&lt;2M$. In particular,
$m\in {\cal N}(10,x)$. Further, since
$$
\log_2(x/m)\ge \log_2 y\ge (\log_2 x)/2
$$
holds for large $x$ and all $m&lt;x/y$, we get 
$$
\nu_2(\phi^{(2)}(P-1))\le 
\nu_2(\phi^{(3)}(n))&lt; 4M\le 20\log_2 x\le 40\log_2 (x/m).
$$
Thus, $P\in {\cal N}(40,x/m)$. Fixing $m$, it follows by Lemma \ref{lem:1}
(ii) that the number of possibilities for $P$ is 
$$
\le \frac{x}{m(\log(x/m))^{2+o(1)}}\le \frac{x}{m(\log y)^{2+o(1)}}
\le \frac{x}{m(\log x)^{2+o(1)}}\qquad {\text{\rm as}}~x\to\infty
$$
uniformly in $m\le x/y$. Summing up over all $m\in {\cal N}(10,x)$ and using 
Lemma \ref{lem:1} (i), we get that 
\begin{equation}
\label{eq:M2}
\#{\cal M}_2\le \frac{x}{(\log x)^{2+o(1)}}\sum_{m\in {\cal N}(10,x)}
\frac{1}{m}\le \frac{x}{(\log x)^{2+o(1)}}\qquad {\text{\rm as}}~x\to\infty.
\end{equation} 

From now on, we look at positive integers in ${\cal M}_3={\cal M}'\backslash
({\cal M}_1\cup {\cal M}_2)$. Note that if $n\in {\cal M}_3$
then $4M\le \nu_2(\phi^{(3)}(n))$. 

\medskip

For $n\in {\cal M}_3$, we write 
$n=Pm$, where $P=P(n)&gt;P(m)$, and $P-1=Q\ell$, where $Q=P(P-1)$. 
Note that we again have $m\in {\cal N}(10, x)$. Observe also that 
$Q&gt;z$ because $n$ is not like in (iii). Since $z&gt;(\log x)^3&gt;(\log x)^2$ 
for large $x$ and $n$ is not like in (iv) or (v), we get that 
$Q$ does not divide $\phi(m)\ell$.
Let $d$ be the largest divisor of $P-1$ which is divisible 
only by primes dividing $\phi(m)$. Thus, $P(d)&lt;(\log x)^2$ 
and $d$ is a divisor of $\ell$. 
Write $\ell=ds$. From now on we fix $m$, the number $d$ which 
consists only of prime factors of $\phi(m)$ smaller than 
$(\log x)^2$, and the number $s$ which is coprime to $d\phi(m)$. 
Notice that $\phi(n)=(P-1)\phi(m)=Qsd\phi(m)$, every prime 
factor of $d$ divides $\phi(m)$, and $Qs$ is coprime to $\phi(m)$. Thus, 
$\phi(\phi(n))=(Q-1)\phi(s) d\phi(\phi(m))$.

\medskip
 
An argument identical to the one used to  derive congruence 
\eqref{eq:cong} gives 
$$
n-\phi(n)-\phi(\phi(n))+1\equiv 0\pmod {2^{4M}}
$$
for $n\in {\cal M}_3$. Note that 
\begin{eqnarray*}
&amp; &amp; n-\phi(n)-\phi(\phi(n))+1 \\
&amp; &amp; =  P(m-\phi(m))+(\phi(m)+1)-(Q-1)\phi(s)d\phi(\phi(m))\\
&amp; &amp; =  (Qsd+1)(m-\phi(m))+(\phi(m)+1)-(Q-1)\phi(s)d\phi(\phi(m))\\
&amp; &amp; = Q(sd(m-\phi(m))-\phi(s)d\phi(\phi(m)))+(m-\phi(m))+(\phi(m)+1) \\
&amp; &amp; + \phi(s)d\phi(\phi(m))\\ 
&amp; &amp; = Q(sd(m-\phi(m))-\phi(s)d\phi(\phi(m)))+(m+1+\phi(s)d\phi(\phi(m))).
\end{eqnarray*}
Put
$$C_{m,d,s}=sd(m-\phi(m))-\phi(s)d\phi(\phi(m))\quad {\text{\rm and}}\quad 
D_{m,d,s}=m+1+\phi(s)d\phi(\phi(m)).
$$ 
Observe that $C_{m,d,s}\ne 0$ for large $x$. Indeed, if $C_{m,d,s}=0$, 
we then get
\begin{eqnarray}
\label{eq:comp1}
n-\phi(n)-\phi(\phi(n))+1 &amp; = &amp; m+1+\phi(s)d\phi(\phi(m))\nonumber\\
&amp; = &amp; m+1+sd(m-\phi(m))
\nonumber\\
&amp; \le &amp; m+(P-1)\frac{m}{Q}\le \frac{mP}{y}+\frac{mP}{z}\nonumber\\
&amp; \le &amp; \frac{2mP}{z}.
\end{eqnarray}
However, since $n\in {\cal M}(x)$, we get that 
\begin{equation}
\label{eq:comp2}
n-\phi(n)-\phi(\phi(n))+1\ge \phi(\phi(\phi(n)))\gg \frac{n}{(\log_2 x)^3}
=\frac{mP}{(\log_2 x)^3}.
\end{equation}
The last inequality above follows from applying the minimal 
order of the Euler function in the interval $[1,x]$ three times 
as
$$
\frac{\phi^{(3)}(n)}{n}\gg \frac{\phi^{(2)}(n)}{n\log_2 x}\gg 
\frac{\phi(n)}{n(\log_2 x)^2}\gg \frac{1}{(\log_2 x)^3}
$$
for $n\le x$. Comparing 
estimates \eqref{eq:comp1} and \eqref{eq:comp2}, we get that 
$$
\frac{2mP}{z}\gg \frac{mP}{(\log_2 x)^3},
$$
leading to $z\ll (\log_2 x)^3$, which is impossible for large $x$. 

\medskip

Hence, 
$C_{m,d,s}\ne 0$ and 
\begin{equation}
\label{eq:congimportant}
C_{m,d,s}Q+D_{m,d,s}\equiv 0\pmod {2^{4M}}. 
\end{equation}
Let ${\cal M}_4$ be the subset of ${\cal M}_3$ such that 
$2^{2M}$ divides both $C_{m,d,s}$ and $D_{m,d,s}$. Then 
$2^{2M}$ divides also $C_{m,d,s}+D_{m,d,s}=sd(m-\phi(m))+m+1.$ 
Note that $m-\phi(m)$ is odd because $m&gt;1$ is odd. Further, since 
$n$ is not like in (vi), it follows that if we write $m+1=2^{\alpha} m_1$
where $m_1$ is odd, then $\alpha\le M$. 
Since $sd(m-\phi(m))+m+1$ is a multiple of 
$2^{2M}$, we get that $sd=2^{\alpha}s_1d_1$, where $s_1$ and $d_1$ are both 
odd. Further note that if $m&gt;3$, then $\phi(\phi(m))$ is even, therefore 
$d=2^{\alpha}d_1$ and $s=s_1$. If $m=3$, then $\phi(\phi(m))=1$, therefore 
$d=1$ and $s=2^{\alpha}s_1$. Fixing $m$ and $d$ (hence, also 
$\alpha$ and $d_1$) the congruence
$sd(m-\phi(m))+m+1\equiv 0\pmod {2^{2M}}$ leads to 
$s_1d_1(m-\phi(m))+m_1\equiv 0\pmod {2^{2M-\alpha}}$. 
Hence, $s_1$ belongs to a certain odd residue class $b_{m,d}$ modulo $2^{M}$. 
We assume that $b_{m,d}$ is the smallest positive integer in 
this class. Since $P-1=2^{\alpha}d_1s_1Q$, $P\le x/m$ and both $P$ and 
$Q$ are primes, 
it follows, by Brun's method (see again Theorem 2.3 in \cite{HR}), 
that the number of possibilities for $Q\le x/(m2^{\alpha}s_1d_1)$ when 
$m,~d_1$ and $s_1$ are fixed is 
$$
\ll \frac{x}{m\phi(2^{\alpha}s_1d_1)(\log(x/msd))^2}
$$
Since $x/msd\ge Q\ge z$, we get, by using again the minimal order 
of the Euler function in the interval $[1,x]$, 
that the above number is bounded from 
above by 
$$
\ll \frac{x\log_2 x}{msd(\log z)^2}\le 
\frac{x(\log_2 x)^5}{m2^{\alpha}s_1d_1(\log x)^2}\ll 
\frac{x(\log_2 x)^5}{ms_1d_1(\log x)^2}.
$$
Note that $\alpha$ is uniquely determined by $m$ alone. 
Summing up first over all $m\le x/y$ and in ${\cal N}(10,x)$, then 
over all odd $d_1\mid \phi(m)$ such that $P(d_1)\le (\log x)^2$, and 
finally over those $s_1\le x/(2^{\alpha}zmd_1)$ with $s_1
\equiv b_{m,d}\pmod {2^{M}}$, we get 
\begin{eqnarray}
\label{eq:M4}
\#{\cal M}_4 &amp; \ll &amp; \frac{x(\log_2 x)^5}{(\log x)^2}\sum_{\substack{m\le x/y\\
m\in {\cal N}(5,x)}}\frac{1}{m}\sum_{\substack{d_1\, |\, \phi(m)\\
P(d_1)\le (\log x)^2}}\frac{1}{d_1} 
\sum_{0\le \lambda\le x/(2^{M+\alpha}ms_1d_1)}
\frac{1}{b_{m,d}+\lambda 2^{M}}\nonumber\\
&amp; \le &amp; \frac{x(\log_2 x)^5}{(\log x)^2}
\left(\sum_{m\in {\cal N}(10,x)}\frac{1}{m}
\sum_{\substack{d_1\equiv 1\pmod 2\\
p\,|\, d_1 =&gt; p\,|\, \phi(m)}}\frac{1}{d_1}\right)\left(1+
\frac{1}{2^M}\sum_{1\le \lambda\le x}\frac{1}{\lambda}\right)\nonumber\\
&amp; \le &amp; \frac{x(\log_2 x)^5}{(\log x)^2}
\left(\sum_{m\in {\cal N}(10,x)}\frac{1}{m}\frac{\phi(m)}{\phi(\phi(m))}
\right)\left(1+O\left(\frac{\log x}{2^M}\right)\right)\nonumber\\
&amp; \ll &amp; \frac{x(\log_2 x)^6}{(\log x)^2}\sum_{m\in {\cal N}(10,x)}\frac{1}{m} 
\le  \frac{x}{(\log x)^{2+o(1)}}\qquad {\text{\rm as}}~x\to\infty,
\end{eqnarray}
where in the above inequalities we used the obvious fact that if $m$ is a
positive integer then 
\begin{equation}
\label{eq:idphi}
\sum_{\substack{d\ge 1\\ p\, |\, d=&gt; p\,|\, m}}\frac{1}{d}=
\prod_{p\, |\, m}\left(\sum_{\alpha\ge 0}\frac{1}{p^{\alpha}}\right)
=\prod_{p\,|\,m}\left(1-\frac{1}{p}\right)^{-1}=\frac{m}{\phi(m)},
\end{equation}
the inequality $\phi(m)/\phi(\phi(m))\ll \log_2 x$ which follows from 
the minimal order of the Euler function in the interval $[1,x]$, 
as well as Lemma \ref{lem:1} (i).

\medskip

Finally, let ${\cal M}_5={\cal M}_3\backslash {\cal M}_4$. 
If $n\in {\cal M}_5$, then $n=Pm,~P=P(n)&gt;P(m)$, $P-1=Qsd$, 
and $\gamma=\nu_2(\gcd(C_{m,d,s},D_{m,d,s}))&lt;M$. Let 
$C'=C_{m,d,s}/2^{\gamma}$ and $D'=D_{m,d,s}/2^{\gamma}$. Congruence 
\eqref{eq:congimportant} shows that 
$C'Q+D'\equiv 0\pmod {2^{M}}$, therefore $Q$ is in a certain residue 
class $e_{m,d,s}$ modulo $2^M$. Assume that $e_{m,d,s}$ is the smallest 
positive integer in this congruence class. Then $Q=2^M\lambda+e_{m,d,s}\le 
x/(mds)$ is a prime such that $P=sdQ+1=2^Msd\lambda+(sde_{m,d,s}+1)$ 
is also a prime. By Brun's method again, the number 
of such possibilities for fixed $m,~d$ and $s$ is 
$$
\ll \frac{x}{mds 2^{M}(\log(x/(mds2^M)))^2}
\left(\frac{\phi(sde_{m,d,s}(sde_{m,d,s}+1))}{sde_{m,d,s}(sde_{m,d,s}+1)}
\right)^2.
$$
Using again the minimal order of the Euler function in the 
interval $[1,x]$ as well as the fact that
$$
\frac{x}{mds2^M}\ge \frac{Q}{2^{M}}\ge \frac{z}{2^{M}}\ge z^{1/2}
$$ 
for large $x$, we get that the 
above number is at most
$$
\ll \frac{x(\log_2 x)^2}{mds2^M (\log z)^2}\ll 
\frac{x(\log_2 x)^6}{mds2^M(\log x)^2}.
$$
Summing up the above inequality over all the choices of $m\le x/y$ 
in ${\cal N}(10,x)$, $d$ a divisor of $\phi(m)$ with $P(d)\le (\log x)^2$, 
and $s\le x/(zmd)$ coprime to $\phi(m)$, 
we get that 
\begin{eqnarray}
\label{eq:M5}
\#{\cal M}_5 &amp;\ll &amp; \frac{x(\log_2 x)^6}{2^M(\log x)^2}
\sum_{\substack{m\le x/y\\ m\in {\cal N}(10,x)}}\frac{1}{m}
\sum_{\substack{d\ge 1\\ p\, |\, d =&gt; p\, |\, \phi(m)}}\frac{1}{d}
\sum_{s\le x/(zmd)}\frac{1}{s}\nonumber\\
&amp; \ll &amp; \frac{x(\log_2 x)^6}{2^M \log x}\sum_{m\in {\cal N}(10,x)}
\frac{1}{m}\frac{\phi(m)}{\phi(\phi(m))}\ll \frac{x(\log_2 x)^7}{2^M\log x}
\sum_{m\in {\cal N}(10,x)}\frac{1}{m}\nonumber\\
&amp; \ll &amp; \frac{x}{(\log x)^{1+10\ln 2+o(1)}}=
o\left(\frac{x}{(\log x)^{2}}\right)
\qquad {\text{\rm as}}~x\to\infty.
\end{eqnarray}
In the above estimates, we used again identity \eqref{eq:idphi}, the minimal
order of the Euler function in the interval $[1,x]$ as well as
Lemma \ref{lem:1} (i). Since ${\cal M}_4$ and ${\cal M}_5$ cover ${\cal M}_3$, 
we get from estimates \eqref{eq:M4} and \eqref{eq:M5} that 
\begin{equation}
\label{eq:M3}
\#{\cal M}_3=o\left(\frac{x}{(\log x)^2}\right)\qquad {\text{\rm as}}~
x\to\infty.
\end{equation}
which together with the estimates \eqref{eq:M1}, \eqref{eq:M2} and
(i)--(vi) completes the proof of Theorem \ref{thm:1}. 
\qed


\section{Proof of Theorem \ref{thm:2}}

Let $x$ be a large positive real number.
Since $\varepsilon(x)$ decreases and tends to infinity arbitrarily slowly,
we may assume that $\varepsilon(x)\ge 2/\log_3 x$ for if not 
we may replace $\varepsilon(x)$ by $\max\{\varepsilon(x), 2/\log_3 x\}
$. It was shown in \cite{LP} that there exists a positive constant $c_1$ 
such that for all $n\le x$ except $o(x)$ of them $\phi(n)$ is a multiple 
of all the primes $p\le c_1\log_2 x/\log_3 x$. Thus,
$$
\phi^{(2)}(n)\le e^{-\gamma}(1+o(1))\frac{\phi(n)}{\log_3 x}\qquad {\text{\rm 
as}}~x\to\infty
$$
with $o(x)$ exceptions $n$. Here, $\gamma$ is the Euler constant. 
Since $\phi(m)\le m/2$ whenever 
$m$ is even, we get that 
$$
\sum_{k=2}^{\kappa(n)}\phi^{(k)}(n)\le \phi^{(2)}(n)\sum_{k=2}^{\kappa(n)}
\frac{1}{2^{k-2}}&lt; 2\phi^{(2)}(n)&lt;\frac{2n}{\log_3 x}
$$
holds for all $n\le x$ with $o(x)$ exceptions as $x\to\infty$. 
We thus get that 
$$
n-F(n)\ge (n-\phi(n))-\frac{2n}{\log_3 x}.
$$
Since $n-\phi(n)$ counts the number of positive integers $k\le n$ which 
are not coprime to $n$, it follows that $n-\phi(n)\ge n/p(n)$ where 
$p(n)$ is the smallest prime factor of $n$. Since the 
number of $n\le x$ for which $p(n)&gt;(2\varepsilon(x))^{-1}$ is
$O(x/\log((2\varepsilon(x))^{-1}))=o(x)$ as $x\to\infty$, we get that 
$p(n)\le (2\varepsilon(x))^{-1}$ with $o(x)$ exceptions as $x\to\infty$. Thus, 
except for $o(x)$ such $n\le x$, we have 
$$
n-F(n)\ge 
\frac{n}{p(n)}-\frac{2n}{\log_3 x}\ge 2n
\left(\varepsilon(x)-\frac{1}{\log_3 x}\right)\ge \varepsilon(x) n.
$$
Since $n\log n\ge x$ holds for all $n\le x$ with $O(x/\log x)=o(x)$ 
exceptions and $\varepsilon(x)$ is decreasing, we get that the inequality
$$
n-F(n)\ge \varepsilon(n\log n)n
$$  
holds on a set of $n$ of asymptotic density $1$, which implies the desired
conclusion since the function $\varepsilon(x)$ 
is arbitrary, subject to the conditions that it is decreasing for large
$x$ and tends to zero when $x$ tends to infinity.
\qed

\section{Proof of Theorem \ref{thm:3}}

We let $x$ be large and put $s=c_2\log_2 x\log_3 x/\log_4 x$ where 
$c_2&gt;0$ is some absolute constant to be chosen later. Let $L=\lfloor 
{\sqrt{\log x}}\rfloor$ and consider the set of integers 
$$
{\cal W}=\{\prod_{p\le s} p^{\alpha_p}~:~
\alpha_p\in [L,~2L]~{\text{\rm for~all}}~p\le s\}.
$$
Let $M=\prod_{p\le s} p$.
If $n\in {\cal W}$ then 
$$
n\le M^{2L}\le \exp((2+o(1))sL)=\exp(O((\log x)^{1/2}\log_2 x\log_3 x))=
x^{o(1)}$$
as $x\to\infty$, therefore 
$$
F(n)=\sum_{k\ge 1}\phi^{(k)}(n)\le \phi(n)\sum_{k\ge 1}\frac{1}{2^{k-1}}\le 
2n=x^{o(1)}\qquad {\text{\rm as}}~x\to\infty.
$$
In particular $F({\cal W})\subset {\cal U}(x)$ holds for large $x$. 
Note also that 
$$
\#{\cal W}\ge (L+1)^{\pi(s)}=\exp((1+o(1))s\log L/\log s),
$$
therefore
$$
\log(\#{\cal W})\gg \frac{s\log L}{\log s}\gg \frac{(\log_2 x)^2}{\log_4 x}.
$$
From the above considerations, it follows that Theorem 3 will follow provided
that we can show that if $c_2&gt;0$ is suitably chosen and $x$ is large, then
$F$ restricted to ${\cal W}$ is one-to-one.

\medskip

We take a closer look at $F(n)$ for $n\in {\cal W}$. Note that as long 
as $M\mid \phi^{(k)}(n)$, we have that $\phi^{(k+1)}(n)=(\phi(M)/M) 
\phi^{(k)}(n)$. Since clearly $M\mid \phi^{(k)}(n)$ for all $k\le L-1$, 
it follows that if we put $\delta=M/\phi(M)$, then 
$$
\phi^{(k)}(n)=\frac{\phi(n)}{\delta^{k-1}}=\frac{n}{\delta^k}
$$
holds for all $k=1,~2,\ldots,~L$. Thus, for $n\in {\cal W}$ we have
\begin{eqnarray}
\label{eq:Fn}
F(n) &amp; = &amp; \sum_{k\le L}\phi^{(k)}(n)+\sum_{k&gt;L}\phi^{(k)}(n)=
n\sum_{k=1}^{L}\delta^{-k}+
O\left(\phi^{(L+1)}(n)\sum_{j\ge 0}\frac{1}{2^j}\right)
\nonumber \\
&amp; = &amp; n\left(\frac{1-\delta^{-(L+1)}}{1-\delta^{-1}}\right)+
O\left(\frac{n}{\delta^L}\right)=n\left(\frac{1}{1-\delta^{-1}}+
O\left(\frac{1}{\delta^{L}}\right)\right).
\end{eqnarray}
Note that $\delta=\prod_{p\le s}(1-1/p)^{-1}\asymp \log s$. Suppose 
now that $F(n_1)=F(n_2)$ for two distinct integers $n_1,~n_2$ in 
${\cal W}$. From the above relation \eqref{eq:Fn} we get that  
$$
\frac{1}{1-\delta^{-1}}(n_1-n_2)=O\left(\frac{n_1+n_2}{\delta^{L}}
\right)
$$
and since $\delta\to \infty$ when $x\to\infty$, we get that 
$1/2&lt;n_1/n_2&lt;2$ holds when $x$ is sufficiently large. We now get that 
\begin{equation}
\label{eq:n1n2}
|n_1n_2^{-1}-1|\ll \delta^{-L}.
\end{equation}
Note that $n_1n_2^{-1}\ne 1$ is a rational number of the form 
$\prod_{p\le s} p^{\delta_p}$ with some integer exponents $\delta_p\in 
[-L, L]$. Using a linear form in logarithms due to Matveev (see Corollary 
2.3 of \cite{Matv}), 
we get that 
\begin{equation}
\label{eq:Mat}
\log|n_1n_2^{-1}-1|\ge -c_3^{\pi(s)}\Omega \log L,
\end{equation}
where 
$$
\Omega=\prod_{p\le s} \log p\le (\log s)^{\pi(s)}.
$$
Taking logarithms in estimate \eqref{eq:n1n2} and using \eqref{eq:Mat}, we get
$$
L\log \delta\le (c_3\log s)^{\pi(s)}\log L,
$$
therefore 
$$
{\sqrt{\log x }}\le (c_3\log s)^{\pi(s)}(\log_2 x)^2.
$$
Taking logarithms again we get 
$$
(\log_2 x)/2-\log_3 x\le \pi(s)\log_2 s+O(1)\le (1+o(1))
\frac{s\log_2 s}{\log s}+O(1).
$$
Recalling the definition of $s$, we see that if we choose $c_2=1/3$, then 
the above inequality is impossible for large enough values of $x$. This 
completes the proof of Theorem \ref{thm:3}.
\qed 


\section{Acknowledgments}

The author thanks Professor Igor 
E. Shparlinski for useful advice and the anonymous referee for
comments which improved the quality of this paper. Work on this paper was
done during a visit to CRM in Montreal during Spring 2006. 
The hospitality and support of
this institution is gratefully acknowledged. During the
preparation of this paper, the author was  also supported in
part by Grants SEP-CONACyT 46755, PAPIIT IN104005 and a Guggenheim
Fellowship.


\begin{thebibliography}{9999}

\bibitem{BKW} N.~L.~Bassily, I.~K\'atai and M.~Wijsmuller, On the prime 
power divisors of the iterates of the Euler function, {\it Publ. Math. 
(Debrecen)\/} {\bf 55} (1999), 17--32.

\bibitem{CEP} E.~R.~Canfield, P.~Erd{\H o}s and
C.~Pomerance, On a problem of Oppenheim concerning
{``Factorisatio Numerorum''},
{\it J.\ Number Theory\/}, {\bf 17} (1983), 1--28.

\bibitem{EGPS} P.~Erd\H os, A.~Granville, C.~Pomerance and S.~Spiro, 
On the normal behavior of the iterates of some arithmetic function, in 
{\it Analytic Number Theory\/} Birkh\"auser, Boston, 1990, pp.\ 165--204.

\bibitem{Fo} K.~ Ford, On the distribution of totients, {\it Ramanujan
J.\/} {\bf 2} (1998), 67--151.

\bibitem{HR} H.~ Halberstam and H.-E.~ Richert, {\it Sieve Methods\/},
Academic Press, London, 1974.

\bibitem{Ian} D.~E.~Iannucci, D.~Moujie and G.~L.~Cohen, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cohen2/cohen50.html}{On perfect 
totients numbers}, \href{http://www.cs.uwaterloo.ca/journals/JIS/}{\it J. Integer Sequences\/} {\bf 6} (2003), Article 03.4.5. 

\bibitem{LP} F.~Luca and C.~Pomerance, On some problems of 
M\c akowski-Schinzel and Erd\H os concerning the arithmetical functions 
$\phi$ and $\sigma$, {\it Colloq. Math.\/} {\bf 92} (2002), 111--130. 

\bibitem{MP} H.~Maier and C.~Pomerance, On the number of distinct values
of the Euler function, {\it Acta Arith.\/} {\bf 49} (1988), 263--275. 

\bibitem{Matv} E.~M.~Matveev, An explicit lower bound for a homogeneous
rational linear form in logarithms of algebraic numbers II, 
{\it Izv. Ross. Akad. Nauk. Ser. Math.\/} {\bf 64} (2000), 125--180;
English translation in {\it Izv. Math.\/} {\bf 64} (2000), 1217--1269.

\bibitem{MS} A.~L.~Mohan and D.~Suryanarayana, Perfect totient numbers, 
in {\it Number Theory (Proc. 3rd Matscience Conf. Misore 1981)\/}, 
Lect. Notes in Math. {\bf 938}, Springer-Verlag, New York, 1982, 
101--105.

\bibitem{MV} H.~L.~Montgomery and R.~C.~Vaughan, The large sieve, 
{\it Mathematika\/} {\bf 20} (1973), 119--134.

\bibitem{S} I.~E.~Shparlinski, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Shparlinski/shpar43.html}{On the sum of iterations of the Euler function},
\href{http://www.cs.uwaterloo.ca/journals/JIS/}{\it J. Integer Sequences\/}
{\bf 9} (2006), Article 06.1.6.

\bibitem{Ten} G.~Tenenbaum, {\it 
Introduction to Analytic and Probabilistic Number
Theory\/}, Cambridge Univ. Press, Cambridge, 1995.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11N56; Secondary 11N37.

\noindent \emph{Keywords: } Euler function, iterations, congruences.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 4 2006; 
revised version received  August 4 2006.
Published in {\it Journal of Integer Sequences}, September 7 2006.

\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>