\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\<{\langle} \def\>{\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>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>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<\ldotsm$, 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>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) & = & \Psi(x,y)=x\exp\left(-(1+o(1))(\log\log x)( \log\log\log x)\right)\nonumber\\ & < & \frac{x}{(\log x)^{10}}\qquad {\text{\rm for}}~x>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) & \le & \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\\ & \ll & 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) & \le & \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\\ & \ll & 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\\ & \ll & 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 \\ & \ll & x(\log\log x)^3 \sum_{\substack{d\ge z\\ d~{\text{\rm squarefull}}}} \frac{1}{\phi(d)}\nonumber\\ & \ll & 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)< \frac{x}{(\log x)^{10}}\qquad {\text{\rm for}}~x>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) & = & \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\\ & = & \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\\ & \leq & \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\\ & \ll & \left(\frac{e\log\log x+O(1)}{w}\right)^w\ll \frac{1}{(\log x)^{10\log(10/e)}} < \frac{1}{(\log x)^{11}} \end{eqnarray} for $x>x_0$ because $10\log(10/e)>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) <\frac{x}{(\log x)^{11}} \end{equation} for $x>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) & \le & \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\\ & \le & x(2S(w,x+1)+S(w,x)) < 3xS(w,x)+2 \nonumber\\ & \ll & \frac{x}{(\log x)^{11}} \end{eqnarray} for $x>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) & \le & \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\\ & = & x(\log\log x)\sum_{\substack{\omega(r\pm 1)\ge w \\ r\le x}} \frac{1}{r-1}\nonumber\\ & \le & 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\\ & \le & x(\log\log x)(S(w,x)+3S(w,x+1))\nonumber\\ & \le & 4x(\log\log x)S(w,x)+ O(\log\log x) \ll \frac{x(\log\log x)}{(\log x)^{11}} \end{eqnarray} for $x>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) <\frac{x}{(\log x)^{10}}\qquad {\text{\rm for}}~x>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>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) & \le & \sum_{\substack{z\le p \le x}}\quad \sum_{\substack{ q\equiv 1\pmod p\\ r\equiv 1 \pmod p\\ qx_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>\tau$ with $P(d)x_0$, which together with estimate \eqref{eq:B5pre} gives \begin{equation} \label{eq:B5} \#{\cal B}_5(x)<\frac{x}{(\log x)^{10}}\qquad {\text{\rm for}}~x>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>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>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:} $qrP(m)$ because $y>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>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*} &~~& 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\\ & \ll & \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) & \ll & \sum_{zx_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>P(m)$ for $x>x_0$ because $y>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>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>a$ for $x>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>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>x_0$. Indeed, if $q>z$ divides $A$, then $q^2\mid a\phi(n)$. If $x>x_0$, then $z>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)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>P(m)$ for $x>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} & \le & 1+\int_{2_{-}}^{x}\frac{1}{t} d(\#{\cal A}_{a,b}(t)) \nonumber\\ & = & 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\\ & = & 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>P(m)$. Write also $P=2q+1$. Then $\phi(n)=2\phi(m)q$. Moreover, $q>(y-1)/2>z$ for $x>x_0$ so that $q$ does not divide $a\phi(m)$ (because $q>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} & \le & \int_{y-}^{\infty}\frac{1}{t} d(\#{\cal A}_{a,b}(t)) \nonumber\\ & = & \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\\ & \ll & \frac{(\log\log y)^5}{(\log y)^2}+\int_{y-}^{\infty} \frac{1}{t(\log t)^{3/2}} dt\nonumber\\ & \ll & \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) & \le & \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\\ & \le & \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\\ & \ll & \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\\ & \ll & \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 $> 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}