<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,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 On the Sum of Iterations \\
\vskip .1in
of the Euler Function}
\vskip 1cm
\large
Igor E.~Shparlinski \\
Department of Computing \\
Macquarie University \\
Sydney, NSW 2109 \\
Australia \\
\href{mailto:igor@ics.mq.edu.au}{\tt igor@ics.mq.edu.au} \\
\end{center}

\vskip .2 in

\begin{abstract}
We study the sum
$$
F(n) = \sum_{k=1}^{\kappa(n)} \varphi^{(k)}(n) .
$$
of consecutive iterations of the Euler function
$\varphi(n)$ (where the last iteration satisfies 
$\varphi^{(\kappa(n))}(n)=1$).
We show that for almost all $n$, the difference $|F(n) - n|$ is not
too small, and the ratio $n/F(n)$ is not an integer.   The latter result
is related to a question
about the so-called {\it perfect totient numbers\/}, for which $F(n) = n$.
\end{abstract}

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


%\documentclass[12pt]{article}
%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,
%               latexsym,amsopn,amstext,amsxtra,euscript,amscd}

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

\renewcommand{\vec}[1]{\mathbf{#1}}

%\begin{document}

%\newtheorem{prop}{Proposition}
%\newtheorem{lemma}[prop]{Lemma}
%\newtheorem{cor}[prop]{Corollary}
%\newtheorem{corollary}[prop]{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}

%% DEFINITIONS

\def\scr{\scriptstyle}
\def\\{\cr}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\&lt;{\langle}
\def\&gt;{\rangle}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\rf#1{\left\lceil#1\right\rceil}
\def\lcm{{\rm lcm\/}}

\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\N{\mathbb N}

\def\e{{\bf e}}
\def\ord{{\mathrm{ord}\/}}

\def\xxx{\vskip5pt\hrule\vskip5pt}
\def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt}

\newcommand{\comm}[1]{\marginpar{\fbox{#1}}}

\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cC{{\mathcal C}}
\def\cD{{\mathcal D}}
\def\cE{{\mathcal E}}
\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}
\def\cH{{\mathcal H}}
\def\cI{{\mathcal I}}
\def\cJ{{\mathcal J}}
\def\cK{{\mathcal K}}
\def\cL{{\mathcal L}}
\def\cM{{\mathcal M}}
\def\cN{{\mathcal N}}
\def\cO{{\mathcal O}}
\def\cP{{\mathcal P}}
\def\cQ{{\mathcal Q}}
\def\cR{{\mathcal R}}
\def\cS{{\mathcal S}}
\def\cT{{\mathcal T}}
\def\cU{{\mathcal U}}
\def\cV{{\mathcal V}}
\def\cW{{\mathcal W}}
\def\cX{{\mathcal X}}
\def\cY{{\mathcal Y}}
\def\cZ{{\mathcal Z}}

\newcommand{\li}{\operatorname{li}}

\def\cAt{\widetilde{\cA}}
\def\cBt{\widetilde{\cB}}
\def\cQt{\widetilde{\cQ}}
\def\pit{\widetilde{\pi}}
\def\cAb{\overline{\cA}}
\def\tn{\widetilde n}






\section{Introduction}

Let $\varphi $ denote the {\it Euler function\/},
which, for an integer $n\ge 1$, is defined as usual by
$$
\varphi(n)= \# \{j \in \Z \ | \ 1 \le j \le n, \ \gcd(j,n) = 1\}.
$$

Moreover, for an integer $k\ge 1$, we use $\varphi^{(k)}$ to
denote the $k$th iteration of $\varphi$, that is, the function
defined recursively as $\varphi^{(1)}(n) = \varphi(n)$
and $\varphi^{(k+1)}(n) = \varphi^{k}(\varphi(n))$, $k =1,2, \ldots$.

Clearly for every $n$ there exists a uniquely defined integer
$\kappa(n)$ such that $\varphi^{(\kappa(n))}(n)=1$.
Accordingly, we define the function
$$
F(n) = \sum_{k=1}^{\kappa(n)} \varphi^{(k)}(n) ,
$$
which is an additive analogue of the function
$$
G(n) = \prod_{k=1}^{\kappa(n)} \varphi^{(k)}(n)
$$
considered in the paper~\cite{EGPS}. (In fact, the results of~\cite{EGPS}
are formulated for $n G(n)$ but one can easily reformulate them
for $G(n)$.)

The function $F(n) $ also appears in the definition of
{\it perfect totient numbers\/}, which are
the integers $n\ge 2$ with $F(n) = n$; see~\cite{IMC,MoSu}
and references therein. Here we use some very elementary arguments
to establish several properties of this function, which seem
to be new.

Let
$$
\cV(x) =  \{\varphi(n) \le x\ | \ n =1, 2, \ldots\}, \qquad
\cU(x) =   \{F(n) \le x\ | \ n =1, 2, \ldots\}.
$$

We start with the observation
that
$$
\cU(x) \subseteq \{v + F(v) \ | \ v \in \cV(x)\},
$$
therefore
$$
\# \cU(x) \le \# \cV(x).
$$

There are several very tight  bounds on
the value set of the Euler function (see~\cite{Ford,MP}).
These immediately imply that
\begin{eqnarray}
\label{eq:value set}
\# \cU(x) \le \frac{x}{\log x} \exp\((C+ o(1)) (\log \log \log x)^2\),
\qquad x \to \infty,
\end{eqnarray}
for some absolute constant $C = 0.8178\cdots$.
This, in turn,
implies that the set of   perfect totient numbers
is of density  zero.
On the other other hand, it is easy to check that
$F(3^s) = 3^s$, $s =1, 2, \ldots$. Thus there are infinitely
many perfect totient numbers, and in fact $\# \cU(x) \ge \log x/\log 3 - 
1$.
Here we show that in fact one can get a better bound by considering
integers of the form $2^r3^s$, $r,s =1, 2, \ldots$.

As in the case of the classical {\it perfect numbers\/}, 
see~\cite{HornWir}, one
can  consider {\it multiply perfect totient numbers\/} for which
$F(n) | n$. We show that
multiply perfect totient numbers  form a zero density set.

We also show that
$$
|F(n) - n| \ge (\log n)^{\log 2 + o(1)}
$$
for almost all $n$. Hence such ``approximately''
perfect totient numbers form a set of density zero, too.

Throughout the paper, the implied constants in the symbols ``$O$'', 
``$\gg$''
and ``$\ll$'' are absolute. (We recall that the notation $U \ll V$ and
$V\gg U$ is equivalent to the statement that $U = O(V)$ for positive
functions $U$ and $V$). We also use the symbol ``$o$''
with its usual meaning: the statement $U=o(V)$ is equivalent to
$U/V\to 0$.

Finally, for any real number $z&gt;0$ and any integer
$\nu\ge 1$,
we write $\log_\nu z$
for the function defined inductively by
$\log_1 z=\max\{\log z,\,1\}$, where $\log z$ is the natural
logarithm of $z$ and $\log_\nu z=\log_1(\log_{\nu-1} z)$
for $\nu&gt;1$. When $\nu=1$, we omit the subscript in order to
simplify the notation; however, we
continue to assume that $\log z\ge 1$ for any $z &gt;0$.



\section{Main Results}

\begin{theorem}
\label{thm:value set}
The following bound holds:
$$
\# \cU(x) \gg (\log x)^2.
$$
\end{theorem}

\begin{proof} For positive integer $r$ and $s$, we have
\begin{eqnarray*}
F(2^{2r} 3^{2s}) &amp; = &amp; \sum_{i=1}^{2s} 3^{2s-i} 2^{2r} + \sum_{j=0}^{2r}
2^{2r-j} \\
&amp; = &amp; 2^{2r-1} (3^{2s} -1) + 2^{2r} -1 = 2^{2r-1} 3^{2s} +2^{2r-1} -1.
\end{eqnarray*}
Assume that
$$
2^{2r-1} 3^{2s} +2^{2r-1} -1 = 2^{2u-1} 3^{2v} +2^{2u-1} -1
$$
for some positive integers $u$ and $v$.
Then
$$
(3^{2s} + 1) =  2^{2u-2r} (3^{2v} +1)
$$
which is impossible unless $u = r$, $v = s$, since
$$
  3^{2s} + 1 \equiv  3^{2v} +1 \equiv 2 \pmod 4.
$$
This means that the values of $F(2^{2r} 3^{2s})$
are pairwise distinct and the result follows.
\end{proof}

Denoting by $M(x)$ the number of
multiply perfect totient numbers $n \le x$,
we have the following result.

\begin{theorem}
\label{thm:mult perfect}
For all positive integers $n \le x$ except possibly $o(x)$
of them, the bound
$$
M(x) \ll \frac{x}{\log x} \exp\((C+ o(1)) (\log_3 x)^2\)
$$
holds.
\end{theorem}

\begin{proof}
Let
$$
\Delta = \max_{n \le x} \frac{n}{\varphi(n)}.
$$
Since
$\varphi(n) \gg n/\log_2 n$ (see \cite[Theorem 4, Chapter I.5]{Ten})
we conclude that  $\Delta = O(\log_2 x)$.
Clearly,
every $n$ with $F(n) | n$ must be of the form $n = du$ with
an positive integer  $d  \le \Delta$ and $u \in \cU(x/d)$.
Therefore, using~\eqref{eq:value set}, we deduce,
\begin{eqnarray*}
M(x) &amp;\le &amp; \sum_{1 \le d \le \Delta} \# \cU(x/d) \\
&amp;\le &amp; x \sum_{1 \le d \le \Delta}\frac{1}{d \log (x/d)}
\exp\((C+ o(1)) (\log_3(x/d) )^2\) \\
&amp;\le &amp; \frac{x}{\log x} \exp\((C+ o(1)) (\log_3 x)^2\)
  \sum_{1 \le d \le \Delta}\frac{1}{d}\\
&amp;\ll &amp;  \frac{x}{\log x} \exp\((C+ o(1)) (\log_3 x)^2\)  \log \Delta\\
&amp;=&amp; \frac{x}{\log x} \exp\((C+ o(1)) (\log_3 x)^2\) ,
\end{eqnarray*}
which finishes the proof.
\end{proof}


\begin{theorem}
\label{thm:approx perfect}
For all positive integers $n \le x$, except possibly $o(x)$
of them, the bound
$$
|F(n) - n| \ge (\log x)^{\log 2 + o(1)}
$$
holds.
\end{theorem}

\begin{proof}
Let $\nu(m)$ denote the largest power of
$2$ that  divides $m$. We start with an observation that
if $m$ is not a power of $2$ itself, we have
$\nu(\varphi(m)) \ge \nu(m)$.
It is also clear that $\nu(\varphi(m)) \ge \omega(m)-1$
where $\omega(m)$ is the number of distinct prime divisors
of $n$.
This implies that
$$
F(n) \equiv 2^{\omega(n)-1} + \cdots + 1 \equiv -1 \pmod 
{2^{\omega(n)-1}}.
$$
{From} the classical {\it Hardy-Ramanujan\/} inequality,
for any $y \ge 1$,
$$
|\omega(n) - \log_2 x| \le y \sqrt{\log_2 x}
$$
for at most $O(xy^{-2})$ positive integers $n \le x$
(see \cite[Theorem 4, Chapter III.3]{Ten}).
Take $y =  (\log_2 x)^{1/6}$ and put
$$r = \fl{\log_2 x -  y \sqrt{\log_2 x} - 1}, \qquad
s = \fl{\log_2 x -  2y \sqrt{\log_2 x} }.
$$
We see that
$$
F(n) \equiv   -1 \pmod {2^{r}}
$$
for all but $O(x (\log_2 x)^{-1/3})$ positive integers $n \le x$.
Therefore, for every of the
remaining integers $n$ we see that
  if $|F(n) - n| &lt; 2^s$ then $n$ belongs to one of the
$O(2^s)$ residue classes modulo $2^r$. Thus this is
possible for at most $O\(2^{s} (x/2^r + 1)\)  = O(x2^{s-r})$
positive integers $n \le x$, which finishes the proof.
\end{proof}



\section{Open Questions}

It seems quite plausible that considering integers $n$ composed out of
more fixed primes, for example, $n = 2^r3^s5^t$ one can improve
the lower bound of Theorem~\ref{thm:value set}. We however do not see
how to create a more generic argument, which would lead
to, say,  the estimate
$$
\frac{\log \# \cU(x)}{\log_2 x} \to \infty, \qquad x \to \infty,
$$
which, no doubt, is correct.

It is also  natural to expect that the bounds of
Theorems~\ref{thm:mult perfect} and \ref{thm:approx perfect}
  are not tight and can be improved.

One can easily derive from \cite[Theorem~4.2]{EGPS} that
$$
  \frac{1}{x} \sum_{n \le x} F(n) \sim  \frac{3}{\pi^2} x.
$$
In fact, using the full strength of \cite[Theorem~4.2]{EGPS},
one can obtain a
more precise asymptotic expansion for  the average value of $F(n)$.



Finally, one can also ask similar questions for the sums of
iterations of other number theoretic functions, such as the
the sum of divisors function $\sigma(n)$ or the
Carmichael functions $\lambda(n)$.

\begin{thebibliography}{99}

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

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

\bibitem{HornWir} B. Hornfeck and E. Wirsing, {\"U}ber die H{\"a}ufigkeit
vollkommener Zahlen, {\it  Math. Ann.\/}, {\bf  133}  (1957), 431--438.

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

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


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

\bibitem{Ten} G. Tenenbaum, {\it Introduction to Analytic and
Probabilistic Number Theory}, Cambridge University Press, 1995.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

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

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A082897}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 27 2005;
revised version received  January 18 2006.
Published in {\it Journal of Integer Sequences}, January 23 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>