\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\<{\langle} \def\>{\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>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>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 >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}) & = & \sum_{i=1}^{2s} 3^{2s-i} 2^{2r} + \sum_{j=0}^{2r} 2^{2r-j} \\ & = & 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) &\le & \sum_{1 \le d \le \Delta} \# \cU(x/d) \\ &\le & x \sum_{1 \le d \le \Delta}\frac{1}{d \log (x/d)} \exp\((C+ o(1)) (\log_3(x/d) )^2\) \\ &\le & \frac{x}{\log x} \exp\((C+ o(1)) (\log_3 x)^2\) \sum_{1 \le d \le \Delta}\frac{1}{d}\\ &\ll & \frac{x}{\log x} \exp\((C+ o(1)) (\log_3 x)^2\) \log \Delta\\ &=& \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| < 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}