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

\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 Perfect Totient Numbers
}
\vskip 1cm
{\large
Douglas E. Iannucci\\
University of the Virgin Islands\\
St Thomas, VI 00802\\
USA\\
\href{mailto:diannuc@uvi.edu}{\tt diannuc@uvi.edu} \\
\vskip .2in
Deng Moujie\\
Science and Engineering College\\
Hainan University\\
Haikou City 570228\\
P. R. China\\
\href{mailto:dmj2002@hotmail.com}{\tt dmj2002@hotmail.com} \\
\vskip .2in
Graeme L. Cohen\\
University of Technology, Sydney\\
PO Box 123, Broadway\\
NSW 2007\\
Australia\\
\href{mailto:Graeme.Cohen@uts.edu.au}{\tt Graeme.Cohen@uts.edu.au} \\
}
\end{center}

\vskip .2 in

\begin{abstract}
Let $n&gt;2$ be a positive integer and let $\phi$ denote Euler's totient function. Define $\phi^1(n)=\phi(n)$ and
$\phi^k(n)=\phi(\phi^{k-1}(n))$ for all integers $k\ge2$.
Define the arithmetic function $S$ by
$S(n)=\phi(n)+\phi^2(n)+\cdots+\phi^c(n)+1$, where $\phi^c(n)=2$.
We say $n$ is a perfect totient number if $S(n)=n$.
We give a list of known perfect totient numbers,
and we give sufficient conditions for the existence of
further perfect totient numbers.
\end{abstract}

\newtheorem{theorem}{\sc Theorem}

\section{Introduction}

Let $n&gt;2$ be a positive integer and let $\phi$ denote Euler's totient function. Define $\phi^1(n)=\phi(n)$ and
$\phi^k(n)=\phi(\phi^{k-1}(n))$ for all integers $k\ge2$. Shapiro~\cite{shapiro} defines the {\it class number\/}
$C(n)$ of $n$ by that integer $c$ such that $\phi^c(n)=2$. Define the arithmetic function $S$ by
\[ S(n)=\phi(n)+\phi^2(n)+\cdots+\phi^c(n)+1, \]
where $c=C(n)$. Note that $\phi^{c+1}(n)=1$. We say that $n$ is a {\it perfect totient number\/} (or PTN for
short) if $S(n)=n$.

Since $\phi(n)$ is even if $\phi(n)&gt;1$, it follows that all PTNs are odd. It is easy to show that $3^k$ is a PTN
for all positive integers $k$. In Table~1 the 30 PTNs less than $5\cdot10^9$ which are not powers of~3 are given.

In addition to the PTNs given in Table~1, nine more were found by applying a result of Venkataraman~\cite{ven}: If
$p=2^23^b+1$ is prime then $3p$ is a PTN. A search of $b\le5000$, beyond those giving entries in Table~1, turned
up the following nine values for which $p=2^23^b+1$ is prime (and therefore $3p$ is a PTN): $b=39$, 201, 249, 885,
1005, 1254, 1635, 3306, 3522. The PTN which corresponds to $b=3522$ has 1682 digits. Primality was verified with
either UBASIC or Mathematica, by applying Lehmer's converse of Fermat's Theorem (Theorem~4.3 in
Riesel~\cite{rie}).

%\begin{table}
%\caption{PTNs less than $5\cdot10^9$ (except powers of 3)}
%\begin{align*}
%15&amp;=3\cdot5 \\
%39&amp;=3\cdot13  \\
%111&amp;=3\cdot37   \\
%183&amp;=3\cdot61     \\
%255&amp;=3\cdot5\cdot17 \\
%327&amp;=3\cdot109 \\
%363&amp;=3\cdot11^2 \\
%471&amp;=3\cdot157 \\
%2199&amp;=3\cdot733 \\
%3063&amp;=3\cdot1021 \\
%4359&amp;=3\cdot1453 \\
%4375&amp;=5^4\cdot7 \\
%5571&amp;=3^2\cdot619 \\
%8751&amp;=3\cdot2917 \\
%15723&amp;=3^2\cdot1747 \\
%36759&amp;=3\cdot12253\\
%46791&amp;=3^3\cdot1733\\
%65535&amp;=3\cdot5\cdot17\cdot257\\
%140103&amp;=3^3\cdot5189\\
%208191&amp;=3\cdot29\cdot2393\\
%441027&amp;=3^2\cdot49003\\
%4190263&amp;=7\cdot11\cdot54419\\
%9056583&amp;=3^3\cdot335429\\
%57395631&amp;=3\cdot19131877\\
%172186887&amp;=3\cdot57395629\\
%236923383&amp;=3\cdot1427\cdot55343\\
%918330183&amp;=3^3\cdot34012229\\
%3932935775&amp;=5^2\cdot29\cdot5424739\\
%4294967295&amp;=3\cdot5\cdot17\cdot257\cdot65537\\
%4764161215&amp;=5\cdot11\cdot86621113
%\end{align*}
%\end{table}

\begin{xalignat*}{2}
15&amp;=3\cdot5 &amp; 36759&amp;=3\cdot12253\\
39&amp;=3\cdot13 &amp;46791&amp;=3^3\cdot1733 \\
111&amp;=3\cdot37 &amp; 65535&amp;=3\cdot5\cdot17\cdot257 \\
183&amp;=3\cdot61  &amp;   140103&amp;=3^3\cdot5189\\
255&amp;=3\cdot5\cdot17  &amp;208191&amp;=3\cdot29\cdot239\\
327&amp;=3\cdot109&amp; 441027&amp;=3^2\cdot49003\\
363&amp;=3\cdot11^2&amp; 4190263&amp;=7\cdot11\cdot54419\\
471&amp;=3\cdot157 &amp;9056583&amp;=3^3\cdot335429\\
2199&amp;=3\cdot733 &amp;57395631&amp;=3\cdot19131877\\
3063&amp;=3\cdot1021 &amp;172186887&amp;=3\cdot57395629\\
4359&amp;=3\cdot1453 &amp;236923383&amp;=3\cdot1427\cdot55343\\
4375&amp;=5^4\cdot7 &amp;918330183&amp;=3^3\cdot34012229\\
5571&amp;=3^2\cdot619&amp;3932935775&amp;=5^2\cdot29\cdot5424739 \\
8751&amp;=3\cdot2917 &amp;4294967295&amp;=3\cdot5\cdot17\cdot257\cdot65537\\
15723&amp;=3^2\cdot1747&amp; 4764161215&amp;=5\cdot11\cdot86621113\\
\end{xalignat*}
\vskip-.15in
\centerline{Table 1:  PTNs less than $5\cdot10^9$ (except powers of 3).}

\bigskip

The study of PTNs was initiated by Perez Cacho~\cite{cacho} when he proved that $3p$, for an odd prime $p$, is a
PTN if and only if $p=4n+1$, where $n$ is a PTN. Note that Venkataraman's result, mentioned above, follows as a
corollary. Mohan and Suryanarayana~\cite{ms} proved that $3p$, for an odd prime $p$, is not a PTN if
$p\equiv3\pmod4$. Thus PTNs of the form $3p$ have been completely characterized.

Applying Perez Cacho's result gives the following as the only known chains of PTNs, apart from the nine examples
of length~2 mentioned earlier: $3\to39\to471$, $3^2\to111$, $15\to183\to2199$, $3^3\to327$, $255\to3063\to36759$,
$363\to4359$, $3^6\to8751$, $3^{14}\to57395631$, $3^{15}\to172186887$.

The purpose of this paper is to investigate PTNs of the form $3^kp$, for $k\ge2$ and $p$ prime.

As an aside we note a curious result: the fact that $\phi(n) \leq n/2$ when $n$
is even easily implies that
$\phi(n)&gt;n/2$ when $n$ is a PTN.

\section{Sufficient Conditions for PTNs}

Mohan and Suryanarayana found sufficient conditions on an odd prime $p$ for $3^2p$ and $3^3p$ to be PTNs, given in
their paper as Theorem~5 and Theorem~6. In particular, let $b$ be a nonnegative integer. Then, respectively, if
$q=2^53^b+1$ and $p=2\cdot3^2q+1$ are both prime then $3^2p$ is a PTN, and if $q=2^43^b+1$ and $p=2^2q+1$ are both
prime then $3^3p$ is a PTN. There is one known example of their Theorem~5, that being the PTN $15723=3^21747$
which occurs when $b=1$. Their Theorem~6 has three known examples: the PTNs $46791=3^31733$ ($b=3$),
$140103=3^35189$ ($b=4$), and $918330183=3^3\cdot34012229$ ($b=12$). The values $b\le5000$ (for both theorems)
were tested, but no further examples were found.

Let $p$ be an odd prime. We have found four further sufficient conditions on $p$ for $3^2p$ to be a PTN (three of
which are given in the following Theorem), and two sufficient conditions for $3^3p$ to be a PTN.

\begin{theorem}
Let $b$ be a nonnegative integer. If $r$, $q$, and $p$, as given, are all prime then $3^2p$ is a PTN:
\begin{enumerate}
\item $r=2^43^b+1$, $q=2\cdot3r+1$, and $p=2\cdot3q+1$;
\item $r=2\cdot3^b+1$, $q=2^3r+1$, and $p=2q+1$;
\item $r=2^23^b+1$, $q=2^33r+1$, and $p=2q+1$.
\end{enumerate}
\end{theorem}
\noindent{\sc Proof:} (Part 1) We have $3^2p=2^63^{b+4}+387$ by direct substitution. Also,
\begin{align*}
S(3^2p)&amp;=2^23^2q+2^33^2r+2^73^{b+1}+2^73^{b}+\cdots+2^7+2^6+\cdots+1\\
       &amp;=2^7(3^{b+3}+\cdots+3+1)+451\\
       &amp;=2^63^{b+4}+387\,.
\end{align*}
The proofs of Parts 2~and 3~are similar.\quad$\square$

In Part 1, when $b=0$, we have $r=17$, $q=103$, and $p=619$, giving the PTN 5571. There are no more examples for
$b\le3000$. In Parts~2 and~3, no examples occur for $b\le3000$.

\begin{theorem}
Let $b$ be a nonnegative integer. If $q=2^33^b+1$ and $p=2q+1$ are both prime, then $3^2p$ is a PTN.
\end{theorem}

\begin{theorem}
Let $b$ be a nonnegative integer. If $r=2^23^b+1$, $q=2^4r+1$, and $p=2^2q+1$ are all prime, then $3^3p$ is a PTN.
\end{theorem}

\begin{theorem}
Let $b$ be a nonnegative integer. If $s=2^53^b+1$, $r=2\cdot3^2s+1$, $q=2^43r+1$, and $p=2^2q+1$ are all prime,
then $3^3p$ is a PTN.
\end{theorem}

Direct proofs of Theorems 2--4 may be obtained as above. In Theorem~2, examples do not occur for $b\le5000$, and
in Theorem~3, examples do not occur for $b\le3000$. In Theorem~4, when $b=1$, we have $s=97$, $r=1747$, $q=83857$,
and $p=335429$, giving the PTN 9056583. There are no more examples for $b\le2000$.

\section{PTNs of the form $3^kp$}

In seeking examples of PTNs of the form $3^kp$, $k\ge2$, we considered primes $p$ and $q$ such that $q=2^a3^b+1$
and $p=2^c3^dq+1$, where $a$, $c\ge1$ and $b$, $d\ge0$. Direct substitution gives
$$3^kp=2^{a+c}3^{b+d+k}+2^c3^{d+k}+3^k\,.$$ On the other hand, we have
\begin{align*}
S(3^kp)&amp;=2^{c+1}3^{d+k-1}q+2^{a+c+1}3^{b+d+k-2}+2^{a+c+1}3^{b+d+k-3}+\dotsb\\
       &amp;\phantom{={}}{}+2^{a+c+1}+\dots+1\\
       &amp;=2^{c+1}3^{d+k-1}+2^{a+c+1}(3^{b+d+k-1}+\cdots+3+1)+2^{a+c}+\dots+1\\
       &amp;=2^{c+1}3^{d+k-1}+2^{a+c}3^{b+d+k}+2^{a+c}-1.
\end{align*}
Assuming $3^kp$ is a PTN, we equate the above expressions for $3^kp$ and $S(3^kp)$ and simplify to obtain the
diophantine equation
\begin{equation}\label{pq}
2^c(2^a-3^{d+k-1})=3^k+1.
\end{equation}
Clearly, $a&gt;1$ and $c=1$ or 2 for $k$ even or odd, respectively.

When $k=2$, the right-hand side of (\ref{pq}) is 10; thus $c=1$
and the equation reduces to
\begin{equation}\label{pqk2}
2^a-3^{d+1}=5.
\end{equation}
Since $2^a\equiv2\pmod3$, we must have $a$ odd. We have $a=3$, $d=0$ as one solution, and we have $a=5$, $d=2$ as
another. If $a&gt;5$ then $3^{d+1}\equiv123\pmod{128}$, which implies $d+1\equiv11\pmod{32}$. This in turn implies
$3^{d+1}\equiv7\pmod{17}$, and thus $2^a\equiv7+5\equiv12\pmod{17}$, which is impossible. Thus the only solutions
to (\ref{pqk2}) are given by $a=3$, $d=0$, and by $a=5$, $d=2$. Since also $c=1$, this statement includes both our
Theorem~2 and Theorem~5 of Mohan and Suryanarayana~\cite{ms}.

When $k=3$, (\ref{pq}) reduces to
\begin{equation}\label{pqk3}
2^a-3^{d+2}=7.
\end{equation}
Clearly $a\ge3$. Since $2^a\equiv1\pmod3$ and $3^{d+2}\equiv1\pmod8$, we must have $a$ and $d$ both even. Write
$a=2\alpha$ and $d=2\delta$. Then (\ref{pqk3}) reduces to
\begin{equation}\label{pqk3a}
(2^{\alpha}+3^{\delta+1})(2^{\alpha}-3^{\delta+1})=7.
\end{equation}
Therefore $2^{\alpha}-3^{\delta+1}=1$ and $2^{\alpha}+3^{\delta+1}=7$, implying $\alpha=2$, $\delta=0$, which in
turn implies $a=4$, $d=0$ as the only solution. Together with $c=2$, this includes the statement of Theorem 6 in
Mohan and Suryanarayana~\cite{ms}.

We show next that there are no solutions of (\ref{pq}) when $k\ge4$.

Suppose first that $k$ is even, $k\ge4$. Then $c=1$. Put $x=a+1$ and $y=d+k-1$ so that (\ref{pq}) may be given as
\begin{equation}\label{pqk4even}
2^x-2\cdot3^y=3^k+1,
\end{equation}
where $x\ge3$, $y\ge3$.
Then $2^x\equiv1\pmod{27}$, from which $x\equiv0\pmod{18}$. Since $2^{18}\equiv1\pmod{19}$, we then have
$-2\cdot3^y\equiv3^k\pmod{19}$, so that
\[ \left(\frac3{19}\right)^y=\left(\frac{-2\cdot3^y}{19}\right)=\left(\frac{3^k}{19}\right)
     =\left(\frac3{19}\right)^k, \]
where $\left(\frac\cdot\cdot\right)$ is a Legendre symbol. Also, from (\ref{pqk4even}),
$-2\cdot3^y\equiv3^k+1\equiv2\pmod8$, so $y$ is odd. Then we have a contradiction since $k$ is even, $y$ is odd,
and the Legendre symbol $(3/19)=-1$.

Suppose next that $k$ is odd, $k\ge5$. Then $c=2$. Put $x=a+2$ and $y=d+k-1$ so that (\ref{pq}) becomes
\begin{equation}\label{pqk4odd}
2^x-4\cdot3^y=3^k+1,
\end{equation}
where $x\ge4$, $y\ge4$.
There are two main cases to consider.

(a) If $k\equiv1\pmod4$, then $-4\cdot3^y\equiv3^k+1\equiv4\pmod{16}$, implying that $y$ is odd. Also, as
immediately above, $x\equiv0\pmod{18}$. Since $2^{18}\equiv1\pmod7$, then $-4\cdot3^y\equiv3^k\pmod7$, so
$3^{y+1}\equiv3^k\pmod7$. This is impossible when $y+1$ is even and $k$ is odd.

(b) If $k\equiv3\pmod4$, then $-4\cdot3^y\equiv3^k+1\equiv12\pmod{16}$, so $y$ is even.  Suppose first that
$y\equiv0\pmod4$. Then $2^x\equiv4\cdot3^y+3^k+1\equiv4+2+1\equiv2\pmod5$. This implies that $x$ is odd. But, from
(\ref{pqk4odd}), $2^x\equiv1\pmod3$, so $x$ is even. We have a contradiction.

The most difficult case to eliminate is when $k\equiv3\pmod4$ and $y\equiv2\pmod4$. Consideration of
(\ref{pqk4odd}), modulo 5, implies $2^x\equiv4\pmod5$, so $x\equiv2\pmod4$. From (\ref{pqk4odd}), we also have
$2^x\equiv1\pmod{27}$, so $x\equiv0\pmod{18}$ and then, since $x\equiv2\pmod4$, we have $x\equiv18\pmod{36}$. This
then implies that $2^x\equiv-1\pmod{13}$. Consideration of the nine possibilities that arise from (\ref{pqk4odd}),
modulo 13, taking $y\equiv2$, 6 or $10\pmod{12}$ and $k\equiv3$, 7 or $11\pmod{12}$ shows that in fact
$y\equiv2\pmod{12}$ and $k\equiv3\pmod{12}$. Now consider a further nine cases of (\ref{pqk4odd}), modulo 37,
taking $y\equiv2$, 14 or $26\pmod{36}$ and $k\equiv3$, 15 or $27\pmod{36}$. The only possibility is
$y\equiv2\pmod{36}$ and $k\equiv27\pmod{36}$. But in that case, since $2^{18}\equiv3^{36}\equiv1\pmod{73}$, we
find that $2^x-4\cdot3^y\equiv1-4\cdot9\equiv38\pmod{73}$ and $3^k+1\equiv27+1=28\pmod{73}$. This
contradicts (\ref{pqk4odd}).

We give this conclusion as:
\begin{theorem}
There are no PTNs of the form $3^kp$, $k\ge4$, where $p=2^c3^dq+1$ and $q=2^a3^b+1$ are primes with $a$,
$c\ge1$ and $b$, $d\ge0$.
\end{theorem}

We next considered another possibility: let $a$, $c$, $e\ge1$ and $b$, $d$, $f\ge0$ be integers. Suppose
$r=2^a3^b+1$, $q=2^c3^dr+1$, and $p=2^e3^fq+1$ are all prime, and let $n=3^kp$ for $k\ge2$.

Substitution gives us
\[ n=2^{a+c+e}3^{b+d+f+k}+2^{c+e}3^{d+f+k}+2^e3^{f+k}+3^k, \]
whereas substitution and calculation gives us
\[ S(n)=2^{c+e+3}3^{d+f+k-2}+2^{e+1}3^{f+k-1}+2^{a+c+e}3^{b+d+f+k}+2^{a+c+e}-1. \]
Assuming $n$ is a PTN, we equate the expressions for $n$ and $S(n)$ and simplify to obtain the diophantine
equation
\begin{equation}\label{pqr}
2^e(2^c(2^a-3^{d+f+k-2})-3^{f+k-1})=3^k+1\,.
\end{equation}
We found four solutions to (\ref{pqr}), with $a,c,d,f\le20$ and $k\le10$. Notice that $e=1$ or 2 if $k$ is even or
odd respectively. Our first solution is given by $a=e=2$, $c=4$, $d=f=0$, and $k=3$. Note that this is Theorem~3.
The second solution is given by $a=4$, $c=d=e=f=1$, and $k=2$. This is Part 1 of Theorem~1. The third solution is
given by $a=e=1$, $c=3$, $d=f=0$, and $k=2$ (Part 2 of Theorem 1), and the fourth is given by $a=2$, $c=3$,
$d=e=1$, $f=0$, and $k=2$ (Part 3 of Theorem 1).

Similarly, we also considered integers $a,c,e,g\ge1$, $b,d,f,h\ge0$, where all of $s=2^a3^b+1$, $r=2^c3^ds+1$,
$q=2^e3^fr+1$, and $p=2^g3^hq+1$ are supposed prime. Then, as above, letting $n=3^kp$ for $k\ge3$ and supposing
$S(n)=n$ implies the diophantine equation
\[ 2^g(2^e(2^c(2^a-3^{d+f+h+k-3})-3^{f+h+k-2})-3^{h+k-1})=3^k+1. \]
We found several solutions, but only one of them produced any PTNs: $a=5$, $c=f=1$, $d=g=2$, $e=4$, $h=0$, and
$k=3$. This is Theorem~4, which we have already seen produces one known PTN.

The question remains open as to whether or not any PTNs exist of the form $3^kp$ for $k\ge4$.

\begin{thebibliography}{9}
\bibitem{ms}
A. L. Mohan and D. Suryanarayana, ``Perfect totient numbers'', in: \emph{Number Theory (Proc. Third Matscience
Conf., Mysore, 1981)} Lect. Notes in Math. \textbf{938},
Springer-Verlag, New York, 1982, pp.\ 101--105.
\bibitem{cacho}
L. Perez Cacho, Sobre la suma de indicadores de ordenes sucesivos,
\emph{Revista Matematica Hispano-Americana} \textbf{5.3} (1939), 45--50.
\bibitem{rie}
H. Riesel, \emph{Prime Numbers and Computer Methods for Factorization},
2nd edition, Birkh\"auser, Boston, 1994.
\bibitem{shapiro}
H. Shapiro, An arithmetic function arising from the $\phi$ function,
\emph{Amer. Math. Monthly} \textbf{50} (1943), 18--30.
\bibitem{ven}
T. Venkataraman, Perfect totient number,
\emph{Math. Student} \textbf{43} (1975), 178.
\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:}  totient, perfect totient number, class number, 
diophantine equation.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 23 2003; 
revised version received October 2 2003.
Published in {\it Journal of Integer Sequences}, December 18 2003.
Minor typo corrected, June 8 2009.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


\end{document}

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