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

\DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\Nm}{Nm}
\DeclareMathOperator{\Tr}{Sp} \DeclareMathOperator{\lcm}{lcm}

\def\card#1{\#{#1}}
\def\rad{\mathrm{rad}}

\def\mand{\qquad \mbox{and} \qquad}

\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\N{\mathbb{N}}
\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cF{\mathcal F}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cJ{\mathcal J}
\def\cL{\mathcal L}
\def\cM{\mathcal M}
\def\cN{\mathcal N}
\def\cP{\mathcal P}
\def\cQ{\mathcal Q}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cW{\mathcal W}

\def\e{{\mathbf{\,e}}}
\def\ep{{\mathbf{\,e}}_p}

\def\eps{\varepsilon}
\def\A{\mathcal A}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\N{\mathbb N}

\def\R{\mathbb{R}}
\def\S{\mathcal{S}}
\def\T{\mathcal{T}}
\def\Zq{\mathbb{Z}_q}
\def\Zqx{\mathbb{Z}_q^*}
\def\Zd{\mathbb{Z}_d}
\def\Zdx{\mathbb{Z}_d^*}
\def\Zp{\mathbb{Z}_p}
\def\Zpx{\mathbb{Z}_p^*}
\def\M{\mathcal M}
\def\E{\mathcal E}
\def\F{\mathbb{F}}
\def\Fp{\mathbb{F}_p}
\def\Z{\mathbb{Z}}
\def\K{\mathbb{K}}
\def\Q{\mathbb{Q}}

\def\Il{\cI_\ell}

\newcommand{\comm}[1]{\marginpar {\fbox{#1}}}
\def\xxx{\vskip5pt\hrule\vskip5pt}
\def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Positive Integers $n$ Such 
That $\sigma(\phi(n))=\sigma(n)$
}
\vskip 1cm
\large
Jean-Marie~De~Koninck \\
D\'epartment de Math\'ematiques \\
Universit\'e Laval \\
Qu\'ebec, PQ G1K 7P4 \\
Canada \\
\href{mailto:jmdk@mat.ulaval.ca}{\tt jmdk@mat.ulaval.ca} \\

\

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 investigate those positive integers $n$ for which
the equality
$\sigma(\phi(n))=\sigma(n)$
holds, where $\sigma$ is the sum of the divisors function and $\phi$
is the Euler function.
\end{abstract}

%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{conjecture}[theorem]{Conjecture}


%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,
%                          amsopn,amstext,amsxtra,euscript,amscd}

\newtheorem{lem}{Lemma}
\newtheorem{lemma}[lem]{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{proposition}[prop]{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{theorem}[thm]{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{corollary}[cor]{Corollary}
\newtheorem{conj}{Conjecture}
\newtheorem{prob}{Problem}
\newtheorem{problem}[prob]{Problem}
\newtheorem{ques}{Question}
\newtheorem{question}[ques]{Question}






\section{Introduction}

For a positive integer $n$ we write $\sigma(n)$ and $\phi(n)$ for
the sum of divisors function and for the Euler function of $n$,
respectively. In this note, we study those positive integers $n$
such that
$$
\sigma(\phi(n))=\sigma(n)
$$
holds.  This is sequence \seqnum{A033631} in Sloane's Online Encylopedia
of Integer Sequences. 
Let $\A$ be the set of all such positive integers $n$ and for
a positive real number $x$ we put $\A(x)=\cA\cap [1,x]$. Our result
is the following.

\begin{theorem}
\label{thm:main} The estimate
$$
\#\cA(x)=O\left(\frac{x}{(\log x)^2}\right)
$$
holds for all real numbers $x&gt;1$.
\end{theorem}

The above upper bound might actually be the correct order of
magnitude of $\#\cA(x)$. Indeed, note that if $m$ is such that
\begin{equation}
\label{eq:m1} \sigma(2\phi(m))=2\sigma(m)
\end{equation}
and if $q&gt;m$ is a Sophie Germain prime, that is a prime number $q$
such that $p=2q+1$ is also prime, then $n=mp\in \cA$. The numbers
$m=2318,~2806,~5734,~5937,~7198,~8097,~\ldots$ all satisfy relation
\eqref{eq:m1}, and form Sloane's sequence \seqnum{A137733}.
More generally, if $k$ and $m$ are positive integers
such that
\begin{equation}
\label{eq:mk} \sigma(2^k\phi(m))=2^k\sigma(m)
\end{equation}
and $q_1&lt;\ldots&lt;q_k$ are primes with $p_i=2q_i+1$ also primes for
$i=1,\ldots,k$ and $q_1&gt;m$, then $n=p_1\ldots p_k m\in \cA$. Now
recall that the {\it Prime $K$-tuplets Conjecture\/} of Dickson
(see, for instance, \cite{Dick,HL,SS}) asserts that, except in cases
ruled out by obvious congruence conditions, $K$ linear forms $a_i n
+ b_i$, $i =1, \ldots, K$, take prime values simultaneously for
about $c x/(\log x)^K$ integers $n \le x$, where $c$ is a positive
constant which depends only on the given linear forms. Under this
conjecture (applied with $K=2$ and the linear forms $n$ and $2n+1$),
we obtain that there should be $\gg x/(\log x)^2$ Sophie Germain
primes $q\le x$, which suggests that $\#\cA(x)\gg x/(\log x)^2$. We
will come back to the Sophie Germain primes later.

\medskip

Throughout, we use the Vinogradov symbols $\gg$ and $\ll$ and the
Landau symbols $O$ and $o$ with their regular meanings. We use
$\log$ for the natural logarithm and $p$, $q$ and $r$ with or
without subscripts for prime numbers.


\section{Preliminary Results}
\label{sec:prel}

In this section, we point out a subset $\cB(x)$ of all the positive
integers $n\le x$ of cardinality $O(x/(\log x)^2)$. For the proof of
Theorem \ref{thm:main} we will work only with the positive integers
$n\in \cA(x)\backslash \cB(x)$. Further, $x_0$ is a sufficiently
large positive real number, where the meaning of sufficiently large
may change from a line to the next.

\medskip

We put
$$
y=\exp\left(\frac{\log x}{\log\log x}\right).
$$
For a positive integer $n$ we write $P(n)$ for the largest prime
factor of $n$. It is well known that
\begin{equation}
\label{eq:Psi} \Psi(x,y)=\#\{n\le x~|~P(n)\le
y\}=x\exp(-(1+o(1))u\log u)\qquad (u \to\infty),
\end{equation}
where $u=\log x/\log y$, provided that $u\le y^{1/2}$ (see
\cite{CEP}, Corollary 1.3 of \cite{HT}, or Chapter III.5 of
\cite{Ten}). In our case, $u=\log\log x$, so, in particular, the
condition $u\le y^{1/2}$ is satisfied for $x&gt;x_0$. We deduce that
$$u\log u=(\log\log
x)(\log\log\log x).$$ Thus, if we set ${\cal B}_1(x)=\{n\le
x~|~P(n)\le y\},$ then
\begin{eqnarray}
\label{eq:B1} \#{\cal B}_1(x) &amp; = &amp;
\Psi(x,y)=x\exp\left(-(1+o(1))(\log\log x)(
\log\log\log x)\right)\nonumber\\
&amp; &lt; &amp; \frac{x}{(\log x)^{10}}\qquad {\text{\rm for}}~x&gt;x_0.
\end{eqnarray}

We now let
$$
z=(\log x)^{26}
$$
and for a positive integer $n$ we write $\rho(n)$ for its largest
{\it squarefull divisor}. Recall that a positive integer $m$ is
squarefull if $p^2\mid m$ whenever $p$ is a prime factor of $m$. It
is well known that if we write ${\cal S}(t)=\{m\le t~|~m~{\text{\rm
is~squarefull}}\}$, then
$$
\#{\cal S}(t)=\frac{\zeta(3/2)}{\zeta(3)}t^{1/2}+O(t^{1/3}),
$$
where $\zeta$ is the Riemann Zeta-Function (see, for example,
Theorem 14.4 in \cite{Iv}). By partial summation, we easily get that
\begin{equation}
\label{eq:sum1overpowerful} \sum_{\substack{m\ge t\\ m~{\text{\rm
squarefull}}}}\frac{1}{m} \ll \frac{1}{t^{1/2}}.
\end{equation}
We now let ${\cal B}_2(x)$ be the set of positive integers $n\le x$
such that one of the following conditions holds:
\begin{itemize}
\item[(i)] $\rho(n)\ge z$,
\item[(ii)] $p\mid n$ for some prime $p$ such that $\rho(p\pm 1)\ge z$,
\item[(iii)] there exist primes $r$ and $p$ such that $p\mid n$,
$p\equiv \pm 1\pmod r$ and $\rho(r\pm 1)\ge z$.
\end{itemize}
We will find an upper bound for $\#{\cal B}_2(x)$. Let ${\cal
B}_{2,1}(x)$ be the set of those $n\in {\cal B}_2(x)$ for which (i)
holds. We note that for every $n\in {\cal B}_{2,1}(x)$ there exists
a squarefull positive integer $d\ge z$ such that $d\mid n$. For a
fixed $d$, the number of such $n\le x$ does not exceed $x/d$. Hence,
\begin{equation}
\label{eq:B21} \#{\cal B}_{2,1}(x) \le \sum_{\substack{d\ge z\\
d~{\text{\rm squarefull}}}} \frac{x}{d} \ll \frac{x}{(\log x)^{13}},
\end{equation}
where we have used estimate \eqref{eq:sum1overpowerful} with $t=z$.
Now let ${\cal B}_{2,2}(x)$ be the set of those $n\in {\cal B}_2(x)$
for which (ii) holds. We note that each $n\in {\cal B}_{2,2}(x)$ has
a prime divisor $p$ such that $p\equiv \pm 1\pmod d$, where $d$ is
as above. Given $d$ and $p$, the number of such $n\le x$ does not
exceed $x/p$. Summing up over all choices of $p$ and $d$ we get that
\begin{eqnarray}
\label{eq:B22} \#{\cal B}_{2,2}(x) &amp; \le &amp; \sum_{\substack{d\ge z\\
d~{\text{\rm squarefull}}}}\sum_{\substack{p\equiv \pm 1\pmod d\\
p\le x}}\frac{x}{p} \ll x\sum_{\substack{d\ge z\\ d~{\text{\rm
squarefull}}}}\frac{\log\log x}{\phi(d)}\nonumber\\
&amp; \ll &amp;  x(\log\log x)^2 \sum_{\substack{d\ge z\\ d~{\text{\rm
squarefull}}}}\frac{1}{d} \ll \frac{x(\log\log x)^2}{(\log x)^{13}},
\end{eqnarray}
where in the above estimates we used aside from estimate
\eqref{eq:sum1overpowerful}, the fact that the estimate
\begin{equation}
\label{eq:sum1overpab} \sum_{\substack{p\equiv a\pmod b\\ p\le
x}}\frac{1}{p}\le \frac{1}{p_1(a,b)}+ O\left(\frac{\log\log
x}{\phi(b)}\right)
\end{equation}
holds uniformly in $a,~b$ and $x$ when $b\le x$, where $a$ and $b$
are coprime and $p_1(a,b)$ is the smallest prime number $p\equiv
a\pmod b$ (note that $p_1(1,b)\ge b+1$ and $p_1(-1,b)=p_1(b-1,b)\ge
b-1\ge \phi(b)$ for all $b\ge 2$), together with the well known
minimal order $\phi(n)/n\gg 1/\log\log x$, valid for $n$ in the
interval $[1,x]$.

\medskip

Let ${\cal B}_{2,3}(x)$ be the set of those $n\in {\cal B}_2(x)$ for
which (iii) holds. Then there exists $r$ such that $r\equiv \pm
1\pmod d$ for some $d$ as above, as well as $p\mid n$ such that
$r\mid p-1$ or $r\mid p+1$. Given $d,~r$ and $p$, the number of such
$n\le x$ does not exceed $x/p$, and now summing up over all choices
of $d,~r$ and $p$, we get that
\begin{eqnarray}
\label{eq:B23} \#{\cal B}_{2,3}(x) &amp; \le &amp; \sum_{\substack{d\ge z\\
d~{\text{\rm squarefull}}}}\sum_{\substack{r\equiv \pm 1\pmod d\\
r\le x}}\quad\sum_{\substack{p\equiv \pm 1\pmod r\\ p\le x}}
\frac{x}{p}\nonumber\\
&amp; \ll &amp;  x\sum_{\substack{d\ge z\\ d~{\text{\rm
squarefull}}}}\sum_{\substack{r\equiv \pm 1\pmod d\\ r\le x}}
\frac{\log\log x}{\phi(r)}\nonumber\\
&amp; \ll &amp;  x(\log\log x)^2 \sum_{\substack{d\ge z\\ d~{\text{\rm
squarefull}}}}\sum_{\substack{r\equiv
\pm 1\pmod d\\ r\le x}}\frac{1}{r} \nonumber \\
&amp; \ll &amp;   x(\log\log x)^3 \sum_{\substack{d\ge z\\ d~{\text{\rm
squarefull}}}}
\frac{1}{\phi(d)}\nonumber\\
&amp; \ll  &amp; x(\log\log x)^4\sum_{\substack{d\ge z\\ d~{\text{\rm
squarefull}}}} \frac{1}{d} \ll \frac{x(\log\log x)^4}{(\log
x)^{13}},
\end{eqnarray}
where in the above estimates we used again estimate
\eqref{eq:sum1overpowerful}, estimate \eqref{eq:sum1overpab} twice
as well as the minimal order of the Euler function on the interval
$[1,x]$.

\medskip

Hence, using estimates \eqref{eq:B21}--\eqref{eq:B23}, we get
\begin{equation}
\label{eq:B2} \#{\cal B}_2(x)\le \#{\cal B}_{2,1}(x)+\#{\cal
B}_{2,2}(x)+\#{\cal B}_{2,3}(x)&lt; \frac{x}{(\log x)^{10}}\qquad
{\text{\rm for}}~x&gt;x_0.
\end{equation}

We now put
$$
w=10\log\log x
$$
and set
$$
S(w,x)=\sum_{\substack{\omega(m)\ge w\\ m\le x}}\frac{1}{m},
$$
where $\omega(m)$ denotes the number of distinct prime factors of
the positive integer $m$. Note that, using the fact that
$\displaystyle{ \sum_{p\le t}\frac{1}{p}=\log\log t+O(1)}$ and
Stirling's formula $k!=(1+o(1))k^ke^{-k} \sqrt{2\pi k}$, we have
\begin{eqnarray}
\label{eq:Swx} S(w,x) &amp; = &amp; \sum_{k\ge
w}\sum_{\substack{\omega(m)=k\\ m\le x}}\frac{1}{m} =  \sum_{k\ge
w}\frac{1}{k!}\left(\sum_{p\le x}\sum_{\alpha\ge 1}
\frac{1}{p^{\alpha}}\right)^k\nonumber\\
&amp; = &amp; \sum_{k\ge w}\frac{1}{k!}\left(\sum_{p\le x}\frac{1}{p}+
O\left(\sum_{p\ge 2}\frac{1}{p^2}\right)\right)^k \ll  \sum_{k\ge
w}\frac{1}{k!}\left(\log\log x+O(1))\right)^k
\nonumber\\
&amp; \leq &amp; \sum_{k\ge w}\left(\frac{e\log\log x+O(1)}{k}\right)^k
\leq  \sum_{k\ge w}\left(\frac{e\log\log x+O(1)}{w}\right)^k\nonumber\\
&amp; \ll &amp; \left(\frac{e\log\log x+O(1)}{w}\right)^w\ll \frac{1}{(\log
x)^{10\log(10/e)}} &lt;  \frac{1}{(\log x)^{11}}
\end{eqnarray}
for $x&gt;x_0$ because $10\log(10/e)&gt;11$.

\medskip

We now let ${\cal B}_3(x)$ be the set of positive integers $n\le x$
such that one of the following conditions holds:
\begin{itemize}
\item[(i)] $\omega(n)\ge w$,
\item[(ii)] $p\mid n$ for some prime $p$ for which $\omega(p\pm 1)\ge w$,
\item[(iii)] there exist primes $r$ and $p$ such that $p\mid n$,
$p\equiv \pm 1\pmod r$ and $\omega(r\pm 1)\ge w$.
\end{itemize}
Let ${\cal B}_{3,1}(x)$, ${\cal B}_{3,2}(x)$ and ${\cal B}_{3,3}(x)$
be the sets of $n\in {\cal B}_3(x)$ for which (i), (ii) and (iii)
hold, respectively.

To bound the cardinality of ${\cal B}_{3,1}(x)$, note that, using
(\ref{eq:Swx}), we have
\begin{equation}
\label{eq:B31} \#{\cal B}_{3,1}(x)= \sum_{\substack{\omega(n)\ge w\\
n\le x}} 1\le \sum_{\substack{\omega(n)\ge w\\ n\le
x}}\frac{x}{n}=xS(w,x) &lt;\frac{x}{(\log x)^{11}}
\end{equation}
for $x&gt;x_0$. To bound the cardinality of ${\cal B}_{3,2}(x)$, note
that each $n\in {\cal B}_{3,2}(x)$ admits a prime divisor $p$ such
that $\omega(p\pm 1) \ge w$. Fixing such a $p$, the number of such
$n\le x$ does not exceed $x/p$. Summing up over all such $p$ we
have, again in light of (\ref{eq:Swx}),
\begin{eqnarray}
\label{eq:B32} \#{\cal B}_{3,2}(x) &amp; \le &amp;
\sum_{\substack{\omega(p\pm 1)\ge w\\ p\le x}} \frac{x}{p} \le
x\left(\sum_{\substack{\omega(p+1)\ge w\\ p+1\le x+1}}
\frac{2}{p+1}+\sum_{\substack{\omega(p-1)\ge w\\ p-1\le
x}}\frac{1}{p-1}
\right)\nonumber\\
&amp; \le &amp;  x(2S(w,x+1)+S(w,x)) &lt; 3xS(w,x)+2 \nonumber\\
&amp; \ll &amp; \frac{x}{(\log x)^{11}}
\end{eqnarray}
for $x&gt;x_0$. To bound the cardinality of ${\cal B}_{3,3}(x)$, note
that for each $n\in {\cal B}_{3,3}(x)$ there exist some prime $r$
with $\omega(r\pm 1)\ge w$ and some prime $p\mid n$ such that
$p\equiv \pm 1\pmod r$. Given such $r$ and $p$, the number of such
$n\le x$ does not exceed $x/p$. Summing up over all choices of $r$
and $p$ given above we get, again using (\ref{eq:Swx}),
\begin{eqnarray}
\label{eq:B33} \#{\cal B}_{3,3}(x) &amp; \le &amp;
\sum_{\substack{\omega(r\pm 1)\ge w \\ r\le x}}
\sum_{\substack{p\equiv \pm 1\pmod r\\ p\le x}}\frac{x}{p} =
x(\log\log x)\sum_{\substack{\omega(r\pm 1)\ge w \\ r\le x}}
\frac{1}{\phi(r)} \nonumber\\
&amp; = &amp; x(\log\log x)\sum_{\substack{\omega(r\pm 1)\ge w \\ r\le x}}
\frac{1}{r-1}\nonumber\\
&amp; \le &amp;  x(\log\log x)\left(\sum_{\substack{\omega(r-1)\ge w \\
r-1\le x}} \frac{1}{r-1}+ \sum_{\substack{\omega(r+1)\ge w \\ r+1\le
x}}\frac{3}{r+1}
\right)\nonumber\\
&amp; \le  &amp; x(\log\log x)(S(w,x)+3S(w,x+1))\nonumber\\
&amp; \le &amp;  4x(\log\log x)S(w,x)+ O(\log\log x) \ll  \frac{x(\log\log
x)}{(\log x)^{11}}
\end{eqnarray}
for $x&gt;x_0$.

\medskip

Hence, using estimates \eqref{eq:B31} to \eqref{eq:B33}, we get
\begin{equation}
\label{eq:B3} \#{\cal B}_3(x)\le \#{\cal B}_{3,1}(x)+\#{\cal
B}_{3,2}(x)+\#{\cal B}_{3,3}(x) &lt;\frac{x}{(\log x)^{10}}\qquad
{\text{\rm for}}~x&gt;x_0.
\end{equation}

\medskip

We now let
$$
{\cal B}_4(x)=\{n\le x~|~n\not\in ({\cal B}_1(x)\cup {\cal B}_2(x))~
{\text{\rm and}}~p^2\mid \phi(n)~{\text{\rm for~some}}~p&gt;z\}.
$$
Let $n\in {\cal B}_4(x)$ and let $p^2\mid \phi(n)$ for some prime
$p$. Then it is not possible that $p^2\mid n$ (because $n\not\in
{\cal B}_2(x)$), nor is it possible that $p^2\mid q-1$ for some
prime factor $q$ of $n$ (again because $n\not\in {\cal B}_2(x)$).
Thus, there must exist distinct primes $q$ and $r$ dividing $n$ such
that $q\equiv 1\pmod p$ and $r\equiv 1\pmod p$. Fixing such $p,~q$
and $r$, the number of acceptable values of such $n\le x$ does not
exceed $x/(qr)$. Summing up over all the possible values of $p,~q$
and $r$ we arrive at
\begin{eqnarray*}
\#{\cal B}_4(x) &amp; \le &amp; \sum_{\substack{z\le p \le x}}\quad
\sum_{\substack{ q\equiv 1\pmod p\\ r\equiv 1 \pmod p\\ q&lt;r,~ qr\le
x}}\frac{x}{qr} \le  x \sum_{\substack{z\le p\le x}}\frac{1}{2}
\left(\sum_{\substack{q\equiv
1\pmod p\\ q\le x}}\frac{1}{q}\right)^2\nonumber\\
&amp; \ll &amp;  x \sum_{\substack{z \le p\le x}}\frac{(\log\log
x)^2}{(p-1)^2}
\ll  x(\log\log x)^2 \sum_{\substack{z\le p\le x}}\frac{1}{p^2}\nonumber\\
&amp; \ll &amp; \frac{x(\log\log x)^2}{(\log x)^{13}},
\end{eqnarray*}
where we used estimates \eqref{eq:sum1overpab} and
\eqref{eq:sum1overpowerful}. Hence,
\begin{equation}
\label{eq:B4} \#{\cal B}_4(x)&lt;\frac{x}{(\log x)^{10}}\qquad
{\text{\rm for~all}}~x&gt;x_0.
\end{equation}

We now let
$$
\tau=\exp\left((\log\log x)^2\right)
$$
and let ${\cal B}_5(x)$ stand for the set of $n\le x$ which are
multiples of a prime $p$ for which either $p-1$ or $p+1$ has a
divisor $d&gt;\tau$ with $P(d)&lt;z$. Fix such a pair $d$ and $p$. Then
the number of $n\le x$ divisible by $p$ is at most $x/p$. This shows
that
\begin{equation}
\label{eq:B5pre} \#{\cal B}_5(x)\le \sum_{\substack{P(d)&lt; z\\
\tau&lt;d\le x}} \quad \sum_{\substack{p\equiv \pm 1 \pmod d\\ p\le
x}}\frac{x}{p} \ll  x\log \log x \sum_{\substack{P(d)&lt;z\\ \tau&lt;d\le
x}}\frac{1}{d}.
\end{equation}
It follows easily by partial summation from the estimates
\eqref{eq:Psi} for $\Psi(x,v)$, that if we write $v=\log \tau/\log
z$, then
$$S=\sum_{\substack{P(d)&lt;z\\ \tau&lt;d\le x}}\frac{1}{d}
\le \frac{\log x}{\exp((1+o(1))v\log v)}.
$$
Since $v=(\log\log x)/26$, we get that
$$
v\log v=(1/26+o(1))(\log\log x)( \log\log\log x)
$$
and therefore that
\begin{equation}
\label{eq:estimateforS} S\le \frac{\log x}{\exp((1+o(1))v\log v)}&lt;
\frac{1}{(\log x)^{11}}
\end{equation}
for all $x&gt;x_0$, which together with estimate \eqref{eq:B5pre} gives
\begin{equation}
\label{eq:B5} \#{\cal B}_5(x)&lt;\frac{x}{(\log x)^{10}}\qquad
{\text{\rm for}}~x&gt;x_0.
\end{equation}

Thus, setting
\begin{equation}\label{eq:defB}
{\cal B}(x)=\bigcup_{i=1}^5 {\cal B}_i(x), \end{equation} we get,
from estimates \eqref{eq:B1}, \eqref{eq:B2}, \eqref{eq:B3},
\eqref{eq:B4} and \eqref{eq:B5} that
\begin{equation}
\label{eq:B} \#{\cal B}(x)\le \sum_{i=1}^5 \#{\cal B}_i(x)\ll
\frac{x}{(\log x)^{10}} \qquad {\text{\rm for~all}}~x&gt;x_0.
\end{equation}

\section{The Proof of Theorem \ref{thm:main}}

We find it convenient to prove  a stronger theorem.

\begin{theorem}
\label{thm:mainab} Let $a$ and $b$ be any fixed positive integers.
Setting
$$
{\cal A}_{a,b}=\{n~|~ \sigma(a\phi(n))=b\sigma(n)\},
$$
then the estimate
$$
\#{\cal A}_{a,b}(x)\ll_{a,b} \frac{x}{(\log x)^2}
$$
holds for all $x\ge 3$.
\end{theorem}

\begin{proof}
Let $x$ be large and let ${\cal B}(x)$ be as in (\ref{eq:defB}). We
assume that $n\le x$ is a positive integer not in ${\cal B}(x)$. We
let ${\cal A}_1(x)$ be the set of $n\in {\cal A}_{a,b}(x)\backslash
{\cal B}(x)$ for which $(P(n)-1)/2$ is not prime but such that there
exists a prime number $r&gt;z$ and another prime number $q\mid P(n)-1$
for which $r\mid \gcd(P(n)+1,q+1)$. To count the number of such
positive integers $n\le x$, let $r$ and $q$ be fixed primes such
that $r\mid q+1$, and let $P$ be a prime such that $q\mid P-1$ and
$r\mid P+1$. The number of positive integers $n\le x$ such that
$P(n)=P$ does not exceed $x/P$. Note that the congruences $P\equiv
-1\pmod r$ and $P\equiv 1\pmod q$ are equivalent to $P\equiv a_{q,r}
\pmod {qr}$, where $a_{q,r}$ is the smallest positive integer $m$
satisfying $m\equiv -1\pmod r$ and $m\equiv 1\pmod q$. We
distinguish two instances:

\medskip

\noindent {\bf Case 1:} $qr&lt;P$.

\medskip

Let ${\cal A}_1'(x)$ be the set of such integers $n\in {\cal
A}_1(x)$. Then
\begin{eqnarray}
\label{eq:A11} \#\A_1'(x) &amp; \le &amp; \sum_{z&lt;r\le
x}\sum_{\substack{q\equiv -1\pmod r
\\ q\le x}}
\sum_{\substack{P\equiv a_{q,r}\pmod {qr}\\ qr&lt;P\le x}}\frac{x}{P}
\nonumber\\
&amp; \ll &amp; x\log\log x\sum_{z&lt;r\le x}\sum_{\substack{q\equiv -1\pmod r\\
q\le x}}\frac{1}{\phi(qr)}\nonumber\\
&amp; \ll &amp;  x\log\log x\sum_{z&lt;r\le x}\frac{1}{r}
\sum_{\substack{q\equiv -1\pmod r\\
q\le x}}\frac{1}{q}\nonumber\\
&amp; \ll &amp; x(\log\log x)^2\sum_{z&lt;r\le x}\frac{1}{r\phi(r)}\nonumber\\
&amp; \ll &amp; x(\log\log x)^2\sum_{z&lt;r}\frac{1}{r^2}\ll \frac{x(\log\log
x)^2}{(\log x)^{11}},
\end{eqnarray}
where in the above inequalities we used estimates
\eqref{eq:sum1overpab} and \eqref{eq:sum1overpowerful}.

\medskip

\noindent {\bf Case 2:} $qr\ge P$.

\medskip
Let ${\cal A}_1''(x)$ be the set of such integers $n\in {\cal
A}_1(x)$. Here we write $n=Pm$. Note that $P&gt;P(m)$ because $y&gt;z$ for
large $x$ and $n\not\in {\cal B}_1(x)\cup {\cal B}_2(x)$.
Furthermore, since $r\mid q+1$, we may write $q=r\ell-1$. Since
$q\mid P-1$, we may write $P=sq+1=s(r\ell-1)+1=sr\ell+1-s$. Since
$r\mid P+1$, we get that $1-s\equiv -1\pmod r$, and therefore that
$s\equiv 2\pmod r$. Hence, there exists a nonnegative integer
$\lambda$ such that $s=\lambda r+2$. If $\lambda=0$, then $s=2$
leading to $P=2q+1$, which is impossible. Thus, $\lambda&gt;0$. Let us
fix the value of $\lambda$ as well as that of $r$. Then
\begin{equation}
\label{eq:linearforms}
r\ell-1=q\qquad {\text{\rm and}}\qquad
(\lambda r^2+2r)\ell-(\lambda r+1)=P
\end{equation}
are two linear forms in the variable $\ell$ which are simultaneously
primes. Note that $P\le x/m$ and since $P\ge \ell r(\lambda r+2)$,
we get that $\ell\le x/(mr(\lambda r+2))$. In particular, $mr
(\lambda r+2)\le x$. Recall that a typical consequence of Brun's
sieve (see  for example Theorem 2.3 in \cite{HR}), is that if
$$
L_1(m)=Am+B\qquad {\text{\rm and}}\qquad L_2(m)=Cm+D
$$
are linear forms in $m$ with integer coefficients such that
$AD-BC\ne 0$ and if we write $E$ for the product of all primes $p$
dividing $ABCD(AD-BC)$, then the number of positive integers $m\le
y$ such that $L_1(m)$ and $L_2(m)$ are simultaneously primes is
$$
\le \frac{Ky}{(\log y)^2}\left(\frac{E}{\phi(E)}\right)^2
$$
for some absolute constant $K$. Applying this result for our linear
forms in $\ell$ shown at \eqref{eq:linearforms} for which
$A=r,~B=-1,~C=\lambda r^2+2r$ and $D=-(\lambda r+1)$, we get that
the number of acceptable values for $\ell$ does not exceed
\begin{eqnarray*}
&amp;~~&amp; K\frac{x}{mr(\lambda r+2)\left(\log(x/(mr(\lambda
r+2))\right)^2} \left(\frac{(\lambda r+2)(\lambda
r+1)r}{\phi((\lambda r+2)(\lambda r+1)r)}
\right)^2\\
&amp; \ll &amp; \frac{x(\log\log x)^2}{mr(\lambda r+2)},
\end{eqnarray*}
where for the rightmost inequality we used again the minimal order
of the Euler function on the interval $[1,x]$. Here, $K$ is some
absolute constant. Summing up over all possible values of $\lambda$,
$r$  and $m$, we get
\begin{eqnarray}
\label{eq:A12} \#{\cal A}_1''(x) &amp; \ll &amp; \sum_{z&lt;r\le x}\sum_{1\le
\lambda\le x}
\sum_{1\le m\le x}\frac{x(\log\log x)^2}{mr(\lambda r+2)}\nonumber\\
&amp; &lt; &amp; x(\log\log x)^2 \left(\sum_{z&lt;r\le
x}\frac{1}{r^2}\right)\left(\sum_{1\le \lambda \le
x}\frac{1}{\lambda}\right)\left(\sum_{1\le m\le x}\frac{1}{m}\right)
\nonumber \\
&amp; \ll &amp; \frac{x(\log\log x)^2(\log x)^2}{(\log x)^{13}}=
\frac{x(\log\log x)^2}{(\log x)^{11}},
\end{eqnarray}
where we used again estimate \eqref{eq:sum1overpowerful}.

\medskip

{From} estimates \eqref{eq:A11} and \eqref{eq:A12}, we get
\begin{equation}
\label{eq:A1} \#\A_1(x)\le \#\A_1'(x)+\A_1''(x)&lt; \frac{x}{(\log
x)^{10}} \qquad {\text{\rm for~all}}~x&gt;x_0.
\end{equation}

Now let ${\cal A}_2(x)$ be the set of those $n\in {\cal
A}_{a,b}(x)\backslash (\A_1(x)\cup {\cal B}(x))$ and such that
$(P(n)-1)/2$ is not prime. With $n\in {\cal A}_2(x)$, we get that
$n=Pm$, where $P&gt;P(m)$ for $x&gt;x_0$ because $y&gt;z$ for large $x$ and
$n\not \in {\cal B}_1(x)\cup {\cal B}_2(x)$. Then
$b\sigma(n)=b\sigma(m)(P+1)$. Let $d_1$ be the largest divisor of
$P+1$ such that $P(d_1)\le z$. Then $P+1=d_1\ell_1$, and
$b\sigma(n)=b\sigma(m)d_1\ell_1$. Furthermore,
$\phi(n)=\phi(m)(P-1)$, so that $a\phi(n)=a\phi(m)(P-1)$. Let $d$ be
the largest divisor of $P-1$ which is $z$-smooth; that is, with
$P(d)\le z$. Then $P-1=d\ell$. Note that $\ell$ is squarefree
(because $n\not\in {\cal B}_2(x)$) and $\ell$ and $\phi(m)$ are
coprime (for if not, there would exist a prime $r&gt;z$ such that
$r\mid \ell$ and $r\mid \phi(m)$, so that $r^2\mid \phi(n)$, which
is impossible because $n\not\in {\cal B}_4(x)$). Since $z&gt;a$ for
$x&gt;x_0$, we get that $a\phi(m)d$ and $\ell$ are coprime, and
therefore that $\sigma(\phi(n))=\sigma(a\phi(m)d)\sigma(\ell).$ We
thus get the equation
$$
\sigma(a\phi(m)d)\sigma(\ell)=b\sigma(m)d_1\ell_1.
$$
Now note that $\ell_1$ and $\sigma(\ell)$ are coprime. Indeed, if
not, since $\ell$ is squarefree, there would exist a prime factor
$r$ of $\ell_1$ (necessarily exceeding $z$) dividing $q+1$ for some
prime factor $q$ of $\ell$, that is of $P-1$.  But this is
impossible because $n\not\in {\cal A}_{1}(x)$.

\medskip

Thus, $\ell_1\mid \sigma(a\phi(m)d)$. Note now that $Pm\le x$, so
that $m\le x/P\le x/y$. Furthermore, $\max\{d,d_1\}\le  \tau$
because $n\not\in {\cal B}_5(x)$. Let us now fix $m,~d$ and $d_1$.
Then $\ell_1\mid \sigma(a\phi(m)d)$, and  therefore the number of
choices for $\ell_1$ does not exceed $\tau(\sigma(a\phi(m)d))$,
where $\tau(k)$ is the number of divisors of the positive integer
$k$. The above argument shows that if we write ${\cal M}$ for the
set of such acceptable values for $m$, then
\begin{equation}
\label{eq:max} \#{\cal A}_2(x)\le
\frac{x\tau^2}{y}\max\{\tau(\sigma(a\phi(m)d))~|~ m\in {\cal
M},~d\le \tau,~d_1\le \tau\}.
\end{equation}
To get an upper bound on $\tau(\sigma(a\phi(m)d))$, we write
$a\phi(m)d$ as
$$
a\phi(m)d=AB,
$$
where $A$ is squarefull, $B$ is squarefree, and $A$ and $B$ are
coprime. Clearly,
$$
\sigma(a\phi(m)d)=\sigma(AB)=\sigma(A)\sigma(B),
$$
so that
$$
\tau(\sigma(a\phi(m)d))\le \tau(\sigma(A))\tau(\sigma(B)).
$$
Since $B$ is squarefree, it is clear that
$$
\sigma(B)\,\Big|\,\prod_{q\mid a\phi(m)d}(q+1).
$$
Furthermore,
\begin{equation}
\label{eq:omegas} \omega(a\phi(m)d)\le \omega(a\phi(n))\le
\omega(a)+\omega(n)+\sum_{p\mid n} \omega(p-1)\le w^2+w+O(1),
\end{equation}
so  that we have $\omega(a\phi(m)d)\le 2w^2$ if $x&gt;x_0$. The above
inequalities follow from the fact that $n\not\in {\cal B}_3(x)$.
Also, for each one of the at most $2w^2$ prime factors $q$ of
$a\phi(m)d$, the number $q+1$ has at most $w$ prime factors itself
and its squarefull part does not exceed $z$, again because $n\not\in
{\cal B}_3(x)$. In conclusion, $\sigma(B)\mid C$, where $C$ is a
number with at most $2w^3$ prime factors whose squarefull part does
not exceed $z^{2w^2}$. Thus,
$$
\tau(\sigma(B))\le \tau(C)\le 2^{\omega(C)}\tau(\rho(C)),
$$
where $\omega(C)\le 2w^3$ and $\rho(C)\le z^{2w^2}$. Clearly,
$$
\tau(\rho(C))\le \rho(C)\le z^{w^2}=\exp(w^2\log z)=\exp(O(\log\log
x)^3),
$$
and since also
$$
2^{\omega(C)}\le 2^{2w^3}=\exp(O(\log\log x)^3),
$$
we finally get that
\begin{equation}
\label{eq:sigmaB} \tau(\sigma(B))=\exp(O(\log\log x)^3).
\end{equation}
We now deal with $\sigma(A)$. We first note that $P(A)\le z$ for
$x&gt;x_0$. Indeed, if $q&gt;z$ divides $A$, then $q^2\mid a\phi(n)$. If
$x&gt;x_0$, then $z&gt;a$, in which case the above divisibility relation
forces $q^2\mid \phi(n)$ which is not possible because $n\not\in
{\cal B}_3(x)$. By looking at the multiplicities of the prime
factors appearing in $A$, we easily see that
$$
A\,\Big|\rho(a)\rho(d)\prod_{p\mid m} \rho(p-1)
\left(\prod_{\substack{q\,\mid \,a\phi(m)d\\ q\le z}}
q\right)^{\omega(a\phi(m)d)}.
$$
As we have seen at estimate \eqref{eq:omegas}, $\omega(a\phi(m)d)\le
2w^2$, in which case the above relation shows that
$$
A\le \rho(a)z^{\omega(a\phi(m)d)+\omega(a\phi(m)d)^2}\ll
z^{4w^4+2w^2}= \exp(O(\log\log x)^5).
$$
But since $\sigma(A)&lt;A^2$ and $\tau(\sigma(A))\ll \sigma(A)\le A^2$,
we get that
\begin{equation}
\label{eq:sigmaA} \tau(\sigma(A))=\exp(O(\log\log x)^{5}),
\end{equation}
which together with estimate \eqref{eq:sigmaB} gives
$$
\tau(\sigma(a\phi(m)d))\le \tau(\sigma(A))\tau(\sigma(B))=
\exp(O(\log\log x)^5).
$$
Returning to estimate \eqref{eq:max}, we get that
\begin{eqnarray}
\label{eq:A2} \#{\cal A}_2(x) &amp; \le &amp;
\frac{x\tau^2}{y}\exp(O(\log\log x)^5)=
x\exp\left(-\frac{\log x}{\log\log x}+O((\log\log x)^5)\right)\nonumber\\
&amp; &lt; &amp; \frac{x}{(\log x)^{10}}\qquad {\text{\rm for~all}}~x&gt;x_0.
\end{eqnarray}
Thus, writing ${\cal C}(x)={\cal A}_{a,b}(x)\backslash ({\cal
A}_1(x) \cup {\cal A}_2(x)\cup {\cal B}(x))$, we get that
\begin{equation}
\label{eq:ABC} {\cal A}_{a,b}(x)=\#{\cal C}(x)+O\left(\frac{x}{(\log
x)^{10}}\right).
\end{equation}
Moreover, if $n\in {\cal C}(x)$, then $n=Pm$, with $P&gt;P(m)$ for
$x&gt;x_0$, and $(P-1)/2$ is a prime. Hence, $P-1=2q$, where $q$ is a
Sophie Germain prime. Since also $P\le x/m$, it follows by Brun's
method that the number of such values for $P$ is
$$
\ll \frac{x}{m(\log x/m)^2}\le \frac{x}{m(\log y)^2}=
\frac{x(\log\log x)^2}{m(\log x)^2}.
$$
In the above inequalities we used the fact that $x/m\ge P\ge y$.
Summing up over all $m\le x$, we get
\begin{equation}
\label{eq:C} \#{\cal C}(x)\ll \sum_{m\le x}\frac{x(\log\log
x)^2}{m(\log x)^2}\ll \frac{x(\log\log x)^2}{\log x}.
\end{equation}
In particular,
\begin{equation}
\label{eq:Aab1} \#{\cal A}_{a,b}(x)\ll \frac{x(\log\log x)^2}{\log
x}.
\end{equation}
This is weaker than  the bound claimed by our Theorem
\ref{thm:mainab}. However, it implies, by partial summation, that
\begin{eqnarray}
\label{eq:sum1overab1} \sum_{n\in {\cal A}_{a,b}(x)} \frac{1}{n} &amp;
\le &amp; 1+\int_{2_{-}}^{x}\frac{1}{t} d(\#{\cal A}_{a,b}(t))
\nonumber\\
&amp; = &amp; 1+\frac{\#{\cal A}_{a,b}(t)}{t}\Big|_{t=2_{-}}^{t=x}+O
\left(\int_{2_{-}}^{x}\frac{t(\log\log t)^2}{t^2\log t} dt\right)\nonumber\\
&amp; = &amp; O((\log\log x)^3).
\end{eqnarray}
To get some improvement, we return to ${\cal C}(x)$. Let $n\in {\cal
C}(x)$ and write it as $n=Pm$, where $P&gt;P(m)$. Write also $P=2q+1$.
Then $\phi(n)=2\phi(m)q$. Moreover, $q&gt;(y-1)/2&gt;z$ for $x&gt;x_0$ so
that $q$ does not divide $a\phi(m)$ (because $q&gt;a$ and $n\not\in
{\cal B}_3(x)$). Hence, $\sigma(a\phi(n))=\sigma(2a\phi(m))(q+1)$.
On the other hand, $b\sigma(n)=b\sigma(m)(P+1)=2b\sigma(m)(q+1)$.
Thus, the equation $\sigma(a\phi(n))=\sigma(bn)$ forces
$\sigma(2a\phi(m))=2b\sigma(m)$, implying that $m\in {\cal
A}_{2a,2b}(x/P)\subset {\cal A}_{2a,2b}(x/y)$. The argument which
leads to estimate \eqref{eq:C} now provides the better estimate
$$ \#{\cal
C}(x)\ll \sum_{m\in {\cal A}_{2a,2b}(x)} \frac{x(\log\log
x)^2}{m(\log x)^2}\ll \frac{x(\log\log x)^5}{(\log x)^2}. $$ In
particular, we get
\begin{equation}
\label{eq:Aab2} \#{\cal A}_{a,b}(x)\ll \frac{x(\log\log x)^5}{(\log
x)^2}.
\end{equation}
This is still somewhat weaker than what Theorem \ref{thm:mainab}
claims. However, it implies that the sum of the reciprocals of the
numbers in ${\cal A}_{a,b}$ is convergent. In fact, by partial
summation, it follows, as in estimates \eqref{eq:sum1overab1}, that
\begin{eqnarray}
\label{eq:sum1overab2} \sum_{\substack{n\in {\cal A}_{a,b}\\ n\ge
y}} \frac{1}{n} &amp; \le &amp; \int_{y-}^{\infty}\frac{1}{t} d(\#{\cal
A}_{a,b}(t))
\nonumber\\
&amp; = &amp; \frac{\#{\cal A}_{a,b}(t)}{t}\Big|_{t=y-}^{t=\infty}+O
\left(\int_{y-}^{x}\frac{t(\log\log t)^5}{t^2(\log t)^2} dt\right)
\nonumber\\
&amp; \ll &amp; \frac{(\log\log y)^5}{(\log y)^2}+\int_{y-}^{\infty}
\frac{1}{t(\log t)^{3/2}} dt\nonumber\\
&amp; \ll &amp; \frac{1}{(\log y)^{1/2}}.
\end{eqnarray}
We now take another look at ${\cal C}(x)$. Let again $n\in {\cal
C}(x)$ and write $n=Pm$. Fixing $m$ and using the fact that $P\le
x/m$ is a prime such that $(P-1)/2$ is also a prime, we get that the
number of choices for $P$ is
$$
\ll \frac{x}{m(\log(x/m))^2}.
$$
Hence,
$$
\#{\cal C}(x)\ll \sum_{m\in {\cal
A}_{2a,2b}(x/y)}\frac{x}{m(\log(x/m))^2}.
$$
We now split the above sum at $m=x^{1/2}$ and use estimate
\eqref{eq:sum1overab2} to get
\begin{eqnarray}
\label{eq:Cfinal} \#{\cal C}(x) &amp; \le &amp; \sum_{m\in {\cal
A}_{2a,2b}(x^{1/2})}
\frac{x}{m(\log(x/m))^2}+\sum_{\substack{m\in {\cal A}_{2a,2b}\\
x^{1/2}\le m\le x/y}}\frac{x}{m(\log(x/m))^2}\nonumber\\
&amp; \le &amp; \frac{x}{(\log x^{1/2})^2}\sum_{m\in {\cal A}_{2a,2b}}
\frac{1}{m}+\frac{x}{(\log y)^2} \sum_{\substack{m\in {\cal
A}_{2a,2b}\\ m\ge x^{1/2}}}
\frac{1}{m}\nonumber\\
&amp; \ll &amp; \frac{x}{(\log x)^2}+\frac{x}{(\log y)^{5/2}} =
\frac{x}{(\log x)^2}+
\frac{x(\log\log x)^{5/2}}{(\log x)^{5/2}}\nonumber\\
&amp; \ll &amp; \frac{x}{(\log x)^2},
\end{eqnarray}
which together with estimate \eqref{eq:ABC} leads to the desired
conclusion of Theorem \ref{thm:mainab}.
\end{proof}

\section{Acknowledgments}

This work was done in April of 2006, while
the second author was in residence at the Centre de recherches
math\'ematiques of the Universit\'e de Montr\'eal for the thematic
year {\it Analysis and Number Theory}. This author thanks the
organizers for the opportunity of participating in this program. He
was also supported in part by grants SEP-CONACyT 46755, PAPIIT
IN104505 and a Guggenheim Fellowship. The first author was supported
in part by a grant from NSERC.

\begin{thebibliography}{99}

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

\bibitem{Dick}
L.~E.~Dickson, A new extension of Dirichlet's theorem on prime
numbers, {\it Messenger of Math.\/} {\bf 33} (1904), 155--161.

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

\bibitem{HL}
G.~H.~Hardy and J.~E.~Littlewood, Some problems on partitio
numerorum~III. On the expression of a number as a sum of primes,
{\it Acta Math.\/} {\bf 44} (1923), 1--70.

\bibitem{sm} A. ~Hildebrand, On the number of positive integers
$\leq x$ and free of prime factors $&gt; y$, {\it J. Number Theory\/}
{\bf 22} (1986), 289--307.

\bibitem{HT} A. ~Hildebrand and G.~Tenenbaum, Integers without
large prime factors, {\it J. de Th\'eorie des Nombres de
Bordeaux\/} {\bf 5} (1983), 411--484.

\bibitem{Iv} A. Ivi\'c, {\it The Riemann Zeta-Function, Theory and
Applications\/}, Dover Publications, 2003.

\bibitem{SS}
A.~Schinzel and W.~Sierpi\'nski, Sur certaines hypoth\`eses
concernant les nombres premiers, {\it Acta Arith.\/} {\bf 4}
(1958), 185--208.  Erratum, {\it Acta Arith.\/} {\bf 5} (1959), 259.

\bibitem{Ten} G.~Tenenbaum, {\it Introduction to analytic and
probabilistic number theory\/}, Cambridge Univ. Press, 1995.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } 
Euler function, sum of divisors.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A033631} and 
\seqnum{A137733}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 26 2007;
revised version received February 9 2008.
Published in {\it Journal of Integer Sequences}, February 9 2008.

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