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

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf {On Positive Integers $n$ with a Certain 
\\
\vskip .1in
Divisibility Property}}
\vskip 1cm
\large
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}\\
\ \\
Vicentiu~Tipu \\
Department of Mathematics\\
University of Toronto\\
Toronto, Ontario, M5S 2E4 \\
Canada\\
\href{mailto:vtipu@math.toronto.edu}{\tt vtipu@math.toronto.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we study the positive integers $n$ having at least
two distinct prime factors such that the sum of the prime factors of $n$ divides
$2^{n-1}-1$.
\end{abstract}

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

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


\section{Introduction}

For every positive integer $n$ with factorization $n=\prod_{p\mid n}
p^{a_p}$, we put $\beta(n)=\sum_{p\mid n} p$. Several authors have
considered this function or one of the closely related functions
$B(n)=\sum_{p\mid n} p^{a_p}$, or $f(n)=\sum_{p\mid n} a_p p$, or
$\beta_k(n)=\sum_{p\mid n} p^k$ for some fixed positive integer $k$.
In general, the questions studied were the sets of positive integers
satisfying certain algebraic or divisibility relations involving one
of the above functions. For example, Erd\H os and Pomerance 
\cite{ErPom,Pom1,Pom2} studied the set of positive integers
$n$ such that $f(n)=f(n+1)$, referred to as {\it Ruth-Aaron
numbers}. De Koninck and Luca \cite{KoLu1,KoLu2} studied positive integers $n$ with at least two distinct prime factors for
which $\beta_k(n)$ divides $n$.  De Koninck and Luca \cite{KoLu3} studied positive integers $n$ with at least two distinct prime
factors such that $B(n)=\beta(n)^2$, while Banks and Luca \cite{BaLu}
studied positive integers $n$ such that $\beta(n)\mid 2^n-1$.

Here, we add to the literature on this topic and study positive
integers $n$ such that $\beta(n)\mid 2^{n-1}-1$. Note that if $n=p$
is an odd prime, then
$$
\beta(n)=p\mid 2^{p-1}-1= 2^{n-1}-1.
$$
In particular, by the Prime Number Theorem, there are at least
$\pi(x)\sim x/\log x$ such positive integers $n$ not exceeding $x$
as $x\to\infty$. Hence, to make our problem more interesting, we
look at the set
$$
\mathfrak{B}=\{n~{\rm is~not~a~prime~and}~\beta(n)\mid 2^{n-1}-1\}.
$$
For any subset ${\mathcal A}$ of positive integers and a positive
real number $x$ we put ${\mathcal A}(x)={\mathcal A}\cap [1,x]$. Our
first result shows that the counting function $\#\mathfrak{B}(x)$ is
of a smaller order of magnitude then the counting function of the
primes.

\begin{theorem}
\label{thm:1} The estimate $\#\mathfrak{B}(x)=o(x/\log x)$ holds as
$x\to\infty$.
\end{theorem}
Thus, if a ``random" number $n$ satisfies $\beta(n)\mid 2^{n-1}-1$,
then it is likely to be a prime.

Observe that if $n=p^k$ is a power of an odd prime (of exponent
$>1$), then $n\in \mathfrak{B}$. Thus, again by the Prime Number
Theorem, $\#\mathfrak{B}(x)\ge \sum_{k\ge 2} \pi(x^{1/k})\ge
(2+o(1))x^{1/2}/\log x$ as $x\to\infty$. A quick computation with
Mathematica revealed that $\mathfrak{B}(10^6)$ has $3871$ elements
of which only $236$ are prime powers. So, one would guess that the
main contribution to $\#\mathfrak{B}(x)$ should not come from prime
powers for large $x$. Our next result shows that this is indeed so.

\begin{theorem}
\label{thm:2} The estimate $\mathfrak{B}(x)=x^{1+o(1)}$ holds as
$x\to\infty$.
\end{theorem}

Our proofs of both Theorem \ref{thm:1} and \ref{thm:2} are effective
in that in both cases specific functions bounding
$\#\mathfrak{B}(x)$ from above and from below and which have the
indicated orders of magnitude are provided. In fact, for Theorem
\ref{thm:2}, we show that there are at least $x^{1+o(1)}$ {\it
squarefree} numbers in $\mathfrak{B}(x)$ as $x\to\infty$. We
choose not to be too specific in the above statements in order not
to complicate the exposition.

Throughout this paper, we use the Landau symbols $O$ and $o$ as well
as the Vinogradov symbols $\gg$ and $\ll$ with the usual meanings.
The constants implied by the symbols $O,~\gg$ and $\ll$ are
absolute. We recall that $U=O(V)$, $U\ll V$ and $V\gg U$ are all
equivalent to the statement that $|U|<cV$ holds with some positive
constant $c$, while $U=o(V)$ means that $U/V\to 0$. We write
$c_1,~c_2,~\ldots$ for positive constants which are labeled
increasingly throughout the paper.



\section{Proof of Theorem \ref{thm:1}}

In \cite{BaLu}, it was shown that the counting function of the set
positive integers $n\le x$ such that $\beta(n)\mid 2^n-1$ is
$O(x\log\log x/\log x)$. Here, we follow the basic approach of
\cite{BaLu}, except that we bring in new arguments
since we want an upper bound of a smaller order of magnitude than
$x/\log x$. First, some notations. Given a positive integer $n$, we
write $P=P(n)$ for the largest prime factor of $n$ and $Q=Q(n)$ for
the largest prime factor of $\beta(n)$. If $n$ is odd, we write
$t(n)$ for the order of $2$ modulo $n$; that is, the smallest
positive integer $k$ such that $2^k\equiv 1\pmod n$. Finally, we
write $\omega(n)$ and $\Omega(n)$ for the number of prime and prime
power divisors of $n$ (of exponent $\ge 1$), respectively.

We let $x$ be a large positive number. We let $\alpha>\beta\ge
\gamma$ be numbers in $(0,1)$. Let $y,~z$ and $\Omega$ be functions
of $x$ of growth
$$
y=\exp\left((\log x)^{\alpha+o(1)}\right),\quad z=\exp\left((\log
x)^{\beta+o(1)}\right),\quad \Omega=(\log x)^{\gamma+o(1)}
$$
as $x\to\infty$. We shall make these functions more precise later.
We split the set $\mathfrak{B}(x)$ into six subsets as follows:
\begin{eqnarray*}
\label{eq:Bees} \mathfrak{B}_1 & = & \{n\in \mathfrak{B}(x):P\le
y\};\\
\mathfrak{B}_2 & = & \{n\in \mathfrak{B}(x)\backslash
\mathfrak{B}_1:p^2\mid n~{\rm for~some~prime}~p\ge y\};\\
\mathfrak{B}_3 & = & \{n\in \mathfrak{B}(x)\backslash
(\mathfrak{B}_1\cup \mathfrak{B}_2):\Omega(n)\ge \Omega\};\\
\mathfrak{B}_4 & = & \{n\in \mathfrak{B}(x)\backslash (\cup_{j=1}^3
\mathfrak{B}_j):Q\le z\};\\
\mathfrak{B}_5 & = & \{n\in \#\mathfrak{B}(x)\backslash
(\cup_{j=1}^4
\mathfrak{B}_j):t(Q)\ge Q^{1/3}~{\text{\rm and}}~\Omega(t(Q))\le \Omega\};\\
\mathfrak{B}_6 & = & \mathfrak{B}(x)\backslash (\cup_{j=1}^5
\mathfrak{B}_j).
\end{eqnarray*}
We now bound the cardinalities of each of the sets $\mathfrak{B}_i$
for $i=1,\ldots,6$.

{\bf The set $\mathfrak{B}_1$}. Numbers in $\mathfrak{B}_1$ are
called {\it $y$-smooth}. Well-known results concerning the number of
$y$-smooth numbers $n\le x$ (see \cite{CEP}) show that in our range
the estimate
$$
\#\mathfrak{B}_1=xu^{-u+o(u)}
$$
holds as $u\to\infty$, where $u=\log x/\log y$ ($=(\log
x)^{1-\alpha+o(1)}$ as $x\to\infty$). Thus,
\begin{equation}
\label{eq:B1} \#\mathfrak{B}_1\le x\exp(-(1+o(1))u\log u)\qquad
{\text{\rm as}}~x\to\infty.
\end{equation}

{\bf The set $\mathfrak{B}_2$.} If $p\in [y,x^{1/2}]$ is a fixed
prime, then there are $\lfloor x/p^2\rfloor\le x/p^2$ positive
integers $n\le x$ divisible by $p^2$. Summing up over all the
possible values for $p$, we get that
\begin{equation}
\label{eq:B2} \#\mathfrak{B}_2\le \sum_{y\le p\le
x^{1/2}}\frac{x}{p^2}\le x\sum_{y\le m} \frac{1}{m^2}\le
x\int_{y-1}^{\infty} \frac{dt}{t}\ll \frac{x}{y}.
\end{equation}

{\bf The set $\mathfrak{B}_3$.} Lemma 13 in \cite{LuPo} shows that
uniformly for all integers $k\ge 1$ we have
\begin{equation}
\label{eq:LuPo}
\sum_{\substack{n\le x\\ \Omega(n)\ge k}}1\ll
\frac{kx\log x}{2^k}.
\end{equation}
Applying this with $k=\lfloor \Omega \rfloor$, we get that
\begin{equation}
\label{eq:B3} \#\mathfrak{B}_3\le x\exp\left(-(\log
2+o(1))\Omega\right)\qquad {\text{\rm as}}~x\to\infty.
\end{equation}

From now on until the end of the argument, we consider $n\in
\mathfrak{B}(x)\backslash (\cup_{j=1}^3\mathfrak{B}_j)$. Write $n=Pm$
and observe that $P(m)<P$ and that $y\le P\le x/m$. Thus, $m\le
x/y$. Note also that $m\ge 2$ since $n$ is not prime.


{\bf The set $\mathfrak{B}_4$.} Let us fix a positive integer $m\le
x/y$. Note that $\beta(n)=P+\beta(m)<P\Omega(n)<x\Omega/m$ and that
if $m$ is fixed and $\beta(n)$ is known, then $P=\beta(n)-\beta(m)$
is determined uniquely; thus, $n$ is also determined uniquely. Since
$n\in \mathfrak{B}_4$, it follows that $\beta(n)\le x\Omega/m$ is a
$z$-smooth number. As in the argument for $\mathfrak{B}_1$, it
follows from the results from \cite{CEP} that for a fixed $m$, the
number of possibilities for $n$ is
$$
\le \frac{x\Omega}{m} v_m^{-v_m+o(v_m)},
$$
as $v_m\to\infty$, where $v_m=\log(x\Omega/m)/\log z$. Since $x/m\ge
y$, we get that $v_m\ge v=\log y/\log z$ ($=(\log
x)^{\alpha-\beta+o(1)}$ as $x\to\infty$). Thus, for large $x$, it
follows that uniformly in $m\le x/y$, the number of possibilities
for $n\in \mathfrak{B}_4$ is
$$
\le \frac{x}{m}\exp(-(1+o(1))v\log v)
$$
as $x\to\infty$. Summing up now over all the possible values for $m\le x/y$, we get
that
\begin{eqnarray*}
\#\mathfrak{B}_4  & \le & x\exp(-(1+o(1))v\log v)\sum_{2\le m\le
x/y}\frac{1}{m}\\
&  \le &  x(\log x)\exp(-(1+o(1))v\log v)
\end{eqnarray*}
as $x\to\infty$, which implies that
\begin{equation}
\label{eq:B4} \#\mathfrak{B}_4\le x\exp(-(1+o(1))v\log v)
\end{equation}
as $x\to\infty$. 

{\bf The set $\mathfrak{B}_5$.} This is by far the most interesting
set. We fix again $m\le x/y$. Since $Q\mid \beta(n)$, we have that
$P\equiv -\beta(m)\pmod Q$. Further, since $Q\mid \beta(n)\mid
2^{n-1}-1$, we get that $n-1\equiv 0\pmod {t(Q)}$, so $Pm\equiv
1\pmod {t(Q)}$. By the Chinese Remainder Theorem (note that
$t(Q)\mid Q-1$, so $t(Q)$ and $Q$ are coprime), it follows that $P$
is uniquely determined modulo $Qt(Q)$. The number of such
possibilities for $P\le x/m$ (without even accounting for the fact
that $P$ is prime) is
\begin{equation}
\label{eq:possforP}
\le 1+\frac{x}{mQt(Q)}.
\end{equation}
We now distinguish several cases according to the size of $Qt(Q)$
versus $x/m$. We also write $d=t(Q)$. Note that $d=t(Q)\ge Q^{1/3}>
z^{1/3}$.

{\bf Case 1.} $Qt(Q)\le x/m$. Let us write $\mathfrak{B}_{5,1}$ for
the subset of $\mathfrak{B}_5$ formed by such numbers $n$. In this
instance, the second term in equation \eqref{eq:possforP} dominates
and the number of possibilities for $P$ when $m$ and $Q$ are fixed
is
$$
\le \frac{2x}{mQt(Q)}.
$$
Fix $d=t(Q)$ and sum up the above bound over all primes $Q$ such
that $t(Q)=d$. Since $Q\equiv 1\pmod d$, it follows that $Q=1+d\ell$
for some positive integer $\ell \le x\Omega/(md)<x\Omega$ (the case
$\ell=0$ is not accepted since $Q=1$ is not prime). Thus, the number
of possibilities for $n\in \mathfrak{B}_{5,1}$ when $m$ and $d$ are
fixed does not exceed
$$
\frac{2x}{md}\sum_{1\le \ell< x\Omega}\frac{1}{1+d\ell}<
\frac{2x}{md^2}\sum_{1\le \ell< x\Omega}\frac{1}{\ell}\ll \frac{x\log
x}{md^2}.
$$
Summing up the above bound over all $m\le x/y$ and $d\ge z^{1/3}$,
we get that
\begin{eqnarray}
\label{eq:B51} \#\mathfrak{B}_{5,1} & \ll & x\log x\sum_{m\le
x/y}\frac{1}{m}\sum_{z^{1/3}\le d\le x\Omega}\frac{1}{d^2}\nonumber\\
& \ll & x(\log x)^2\int_{z^{1/3}}^{\infty}\frac{dt}{t^2}\ll
\frac{x(\log x)^2}{z^{1/3}}.
\end{eqnarray}

{\bf Case 2.} $Qt(Q)>x/m$. We write $\mathfrak{B}_{5,2}$ for the
subset of $\mathfrak{B}_5$ consisting of these numbers. We write
also $\beta(n)=P+\beta(m)=Q\delta$, where $1\le \delta<x\Omega/m$ is
some positive integer. Since $P\le x/m$ is uniquely determined
modulo $Qt(Q)>x/m$, it follows that $P$ (hence, $n$) is uniquely
determined by $Q$. We now fix both $m$ and $\delta$ and observe that
$Q\le x\Omega/(m\delta)$. Note also that
$$
P=\beta(n)-\beta(m)=Q\delta-\beta(m)\equiv \delta-\beta(m)\pmod {d}.
$$
Since also $Pm\equiv 1\pmod d$, we get that $d$ divides
$m(\beta(m)-\delta)+1$. This last number is not zero since $m\ge 2$
(if it were zero, then $m(\delta-\beta(m))=1$, which is impossible
for $m\ge 2$). Since $\delta\ge 1$, the size of this number is
\begin{eqnarray*}
|m(\beta(m)-\delta)+1| & < & \max\{m\delta, m P(m)\Omega(m)\}\\
& < & \max\{xm\Omega, m^2\Omega\}\\
& < & xm\Omega<\frac{x^2\Omega}{y}<x^2
\end{eqnarray*}
for large values of $x$. Thus,
$$
\Omega(|m(\beta(m)-\delta)+1|)<\frac{\log(x^2)}{\log 2}<3\log x.
$$
Since $d$ is a divisor of the fixed integer $m(\beta(m)-\delta)+1$
having $\Omega(d)<\Omega$, it follows that $d$ can be chosen in at
most
\begin{equation}
\label{eq:choicesford} (3\log x)^{\Omega}<\exp\left((\log\log
x+\log 3)\Omega\right)
\end{equation}
ways for large values of $x$. Now $Q\le x\Omega/(m\delta)$ is a
prime with $Q\equiv 1\pmod d$, so the number of possibilities for
$Q$ (hence, for $P$) is
$$
\le \frac{x\Omega}{m\delta d}.
$$
Keeping $m$ and $\delta$ fixed and summing up over all the possible
values of $d$ (the number of which is indicated by upper bound
\eqref{eq:choicesford}) we conclude that once $m$ and $\delta$ are
fixed, then $Q$ (hence, $P$; so also $n$) can be fixed in at most
$$
\frac{x\Omega\exp\left((\log\log x+\log
3)\Omega\right)}{z^{1/3} m\delta}
$$
ways. Summing up over all the possibilities for $\delta<x\Omega$ and
$m\le x/y$, we get that
\begin{eqnarray}
\label{eq:B52} \#\mathfrak{B}_{5,2} & \le &
\frac{x}{z^{1/3}}\exp\left((\log\log x+\log
3)\Omega\right)\sum_{m\le x/y}\frac{1}{m}\sum_{\delta\le
x\Omega}\frac{1}{\delta}\nonumber\\
& \ll & \frac{x}{z^{1/3}} (\log x)^2\exp\left((\log\log
x+\log 3)\Omega\right)
\end{eqnarray}
as $x\to\infty$. Comparing estimates \eqref{eq:B51} and
\eqref{eq:B52}, we conclude that for large $x$ we have
\begin{eqnarray}
\label{eq:B5} \#\mathfrak{B}_{5} & \le &
\#\mathfrak{B}_{5,1}+\#\mathfrak{B}_{5,2}\nonumber\\
& < & x\exp\left(-\frac{\log z}{3}+(\log\log x+\log
3)\Omega+O(\log\log x)\right)
\end{eqnarray}
as $x\to\infty$.

{\bf The set $\mathfrak{B}_6$.} Suppose that $n\in \mathfrak{B}_6$.
Then either $t(Q)< Q^{1/3}$, or $\Omega(d)> \Omega$. Let
$\mathfrak{B}_{6,1}$ and $\mathfrak{B}_{6,2}$ be the subsets of
$\mathfrak{B}_6$ such that the first and second inequality holds,
respectively.

We first deal with $\mathfrak{B}_{6,1}$. Let ${\mathcal Q}$ be the
set of primes such that $t(Q)<Q^{1/3}$, and let ${\mathcal Q}(t)=
{\mathcal Q}\cap [1,t]$. The first few elements of
the set ${\mathcal Q}$ are $\{8191,43691,65537,\ldots\}$. We
first show that ${\mathcal Q}$ is sparse. Let $t$ be large and let
$k=\#{\mathcal Q}(t)$. Let $8191=q_1<\cdots<q_k$ be all the numbers
in ${\mathcal Q}(t)$. Then
$$
8191^k<\prod_{i=1}^k q_i\mid \prod_{j\le
t^{1/3}}(2^j-1)<2^{\sum_{j\le t^{1/3}} j}<2^{t^{1/3}(t^{1/3}+1)/2},
$$
which leads easily to the conclusion that the inequality $k<0.04t^{2/3}$ holds for large
values of $t$. By partial summation, we conclude that uniformly in
$s\le t$, we have
\begin{equation}
\label{eq:sumQ}
\sum_{\substack{s\le q\le t\\ q\in {\mathcal
Q}}}\frac{1}{q}=\int_{s}^{t} \frac{d\#{\mathcal Q}(u)}{u}=
\frac{\#{\mathcal
Q}(u)}{u}\Big|_{u=s}^{u=t}+\int_s^t\frac{\#{\mathcal Q}(u)}{u^2} du
\ll \frac{1}{s^{1/3}}.
\end{equation}
Returning to our problem, let $n\in \mathfrak{B}_{6,1}$. To count
such $n$, write again $n=Pm$ and $\beta(n)=Q\delta$ and assume that
$m\le x/y$ and $Q\in [z,x\Omega]$ are fixed. Then $\delta$ can be
chosen in at most
$$
\frac{x\Omega}{mQ}
$$
ways. Note that $Q\in {\mathcal Q}$. Summing up the above bound over
$m\le x/y$ and $Q\in {\mathcal Q}\cap [z,x\Omega]$, we get that
\begin{eqnarray}
\label{eq:B61} \#\mathfrak{B}_{6,1} & \ll &  x\Omega\sum_{m\le
x/y}\frac{1}{m}\sum_{\substack{z\le Q\le x\Omega\\ Q\in {\mathcal
Q}}}\frac{1}{Q}\nonumber\\
& \ll & \frac{x(\log x)\Omega}{z^{1/3}}=\frac{x}{z^{1/3+o(1)}}
\end{eqnarray}
as $x\to\infty$, where in the above estimate we used
the upper bound \eqref{eq:sumQ} with $s=z$ and $t=x\Omega$.

We now deal with $\mathfrak{B}_{6,2}$. Note that for such numbers,
$Q-1$ is a multiple of $d$, so $\Omega(Q-1)\ge \Omega(d)>\Omega$.
Fix $m$ and $Q<x\Omega$. Then $\delta$ (hence, $P$; so, $n$) can be
fixed in at most
\begin{equation} \label{eq:bounds}
\frac{x\Omega}{Q}<\frac{x\Omega}{Q-1}
\end{equation}
ways. It follows easily by partial summation from formula \eqref{eq:LuPo}
that uniformly in $k\ge 1$ and $t$, we have
\begin{equation}
\label{eq:sumlargeOmega}
\sum_{\substack{n\le t\\ \Omega(n)\ge
k}}\frac1n\ll \frac{k(\log t)^2}{2^k}.
\end{equation}
Summing up bounds \eqref{eq:bounds} over all primes $Q$ with
$\Omega(Q-1)>\Omega$ and using bound \eqref{eq:sumlargeOmega} for
$t=x\Omega$ and $k=\lfloor \Omega\rfloor$, we get that
\begin{equation}
\label{eq:B62} \#\mathfrak{B}_{6,2}\ll \frac{x(\log
x)^2\Omega^2}{2^{\Omega}}=x\exp(-(\log 2+o(1))\Omega)
\end{equation}
as $x\to\infty$. From estimates \eqref{eq:B61} and \eqref{eq:B62},
we get
\begin{equation}
\label{eq:B6} \#\mathfrak{B}_6\le
\frac{x}{z^{1/3+o(1)}}+\frac{x}{\exp{((\log 2+o(1))\Omega)}}
\end{equation}
as $x\to\infty$.

Comparing bounds \eqref{eq:B1}, \eqref{eq:B2}, \eqref{eq:B3},
\eqref{eq:B4}, \eqref{eq:B5} and \eqref{eq:B6}, we see that the
optimal bounds are obtained when the parameters $y,~z$ and $\Omega$
are chosen such that
$$
\Omega \log 2=\frac{\log z}{3}-(\log\log x+\log 3)\Omega=v\log
v=u\log u.
$$
This gives
\begin{eqnarray*}
\log y & = & (c_1+o(1))(\log x)^{2/3}(\log\log x)^{2/3},\\
\log z & = & (c_2+o(1))(\log x)^{1/3}(\log\log x)^{4/3},\\
\Omega & = & (c_3+o(1))(\log x)^{1/3}(\log\log x)^{1/3}
\end{eqnarray*}
as $x\to\infty$, where $c_1=(\log 2)^{-1/3},~c_2=(\log
2)^{-2/3},~c_3=c_2/3$. Note that this agrees with the conventions we
made at the beginning on $y,~z,~\Omega$ with
$\alpha=2/3,~\beta=\gamma=1/3$. Therefore we have just shown that
\begin{equation}
\label{eq:upB} \#\mathfrak{B}(x)\le x\exp\left(-(c_4+o(1))(\log
x\log\log x)^{1/3}\right)
\end{equation}
as $x\to\infty$, where $c_4=(\log 2)^{1/3}/3$. This finishes the
proof of Theorem \ref{thm:1}.

\medskip

\noindent {\bf Remark.} Notice that as a byproduct of our effort we conclude
immediately, by partial summation, that
$$
\sum_{n\in \mathfrak{B}}\frac{1}{n}<\infty.
$$

\section{Proof of Theorem \ref{thm:2}}

We let $p$ be a large prime and put $M=2^p-1$. Let $k$ be a positive
integer such that $k=o(p)$ holds as $p\to\infty$. Choose positive
integers $a\ge 3$ and $b$ even such that $a+b=k$ and $a-b=1$.
Clearly, $a=(k+1)/2$ and $b=(k-1)/2$, and in order for $a$ and $b$
to be integers with $b$ even we must have $k\equiv  1\pmod 4$. From  now on, we
work under this assumption. Let ${\mathcal I}=\lfloor M/(2p^2),
M/p^2\rfloor$. We choose $a-3$ distinct primes in ${\mathcal I}$
which are $1$ modulo $p$ and $b$ distinct primes in ${\mathcal I}$
which are $-1$ modulo $p$. By the Siegel-Walfisz Theorem (note that
that the inequality $p<2\log(M/(2p^2))$ holds for large enough
values of $p$ so we may apply the Siegel-Walfisz Theorem to estimate
the number of primes congruent to either $1$ or $-1$ modulo $p$ in
${\mathcal I}$), it follows that the inequality
$$
U_{\eta}=\pi(M/p^2;p,\eta)-\pi(M/(2p^2);p,\eta)\ge \frac{M}{3p^3\log
M}\qquad {\text{\rm for}}~\eta\in \{\pm 1\}
$$
holds for large values of $p$. Recall that $\pi(x;v,u)$ means the
number of primes $p\le x$ congruent to $u$ modulo $v$. The number of
 choices of pairs of primes as above is
\begin{eqnarray}
\label{eq:UV} & = & \binom{U_1}{a-3}\binom{U_{-1}}{b}\ge
\left(\frac{U_1}{a-3}\right)^{a-3}\left(\frac{U_1}{b}\right)^b\nonumber\\
& \ge &
\left(\frac{U_1}{a}\right)^{a-3}\left(\frac{U_{-1}}{b}\right)^{b}\left(1+O\left(\frac{kp^3}{M}\right)
\right)^k\nonumber\\
& \gg & \frac{M^{k-3}}{(3(\log 2)kp^4)^{k-3}}\gg
\frac{M^{k-3}}{p^{5k-15}}
\end{eqnarray}
since $3(\log 2)k<p$ for large $p$. Here, we also used the fact that
$\log M<p(\log 2)$. Let $p_1<\cdots<p_{a-3}$ and $q_1<\cdots<q_b$ be
such primes. Put
$$
N=p_1+\cdots+p_{a-3}+q_1+\cdots+q_b<(a-3+b)\frac{M}{p^2}<\frac{kM}{p^2}<\frac{M}{p}
$$
for large values of $p$. Note also that since $a+b=k-3$ is even and
all the above primes are odd (because $M/(2p^2)>2$ for large values
of $p$), it follows that $N$ is even. Furthermore, $N\equiv
a-3-b\pmod p\equiv -2\pmod p$. Thus, $M-N>M-M/p$ is a large odd
number which is congruent to
$$
2^p-1-N\equiv 2-1-(-2)\equiv 3\pmod p.
$$
By a Theorem of Ayoub \cite{Ay} (see also \cite{Ba}), it follows
that for large $p$ the number $M-N$ can be written as
$$
M-N=r_1+r_2+r_3,
$$
where $r_1<r_2<r_3$ are distinct primes all congruent to $1$ modulo
$p$. Moreover, the number of such representations is
\begin{equation}
\label{eq:Ay} \sim \frac{pC_{M-N}M^2}{6((p-1)^3+1)(\log
M)^3}(1+o(1))
\end{equation}
as $p\to\infty$, where
$$
C_{M-N}=\prod_{\ell\mid M-N}\left(1-\frac{\ell}{(\ell-1)^3+1}\right)
\prod_{\ell>2} \left(1+\frac{1}{(\ell-1)^3}\right).
$$
Observe that $C_{M-N}\gg 1$. In what follows, we will see that at
least half of the above representations will have $r_1>M/p^2$.
Indeed, assume that this is not so. Then $r_1\le M/p^2$ is a prime
congruent to $1$ modulo $p$ and $r_2\le M$ is a prime congruent to
$1$ modulo $p$, and once $r_1$ and $r_2$ are chosen then $r_3$ is
fixed by the equation $r_3=M-N-r_1-r_2$. The number of such pairs
$(r_1,r_2)$ is
$$
\le \pi(M/p^2;p,1)\pi(M;p,1)\ll \frac{M^2}{p^4(\log M)^2}\ll
\frac{M^2}{p^3(\log M)^3}
$$
and the above upper bound is of a smaller order of magnitude then
the function appearing at \eqref{eq:Ay}. Thus, for large $p$, there
are
\begin{equation}
\label{eq:r} \gg \frac{M^2}{p^2(\log M)^3}\gg \frac{M^2}{p^5}
\end{equation}
such representations where $r_1>M/p^2$. From now on we work with
such representations. Now observe that
$\{p_1,\ldots,p_{a-3},q_1,\ldots,q_b,r_1,r_2,r_3\}$ are distinct
primes because $r_1>p_{a-3}$. Let $n$ be the product of the above
$a+b=k$ primes. Then
$$
\beta(n)=\sum_{i=1}^{a-3} p_i+\sum_{j=1}^b q_j+r_1+r_2+r_3=2^p-1
$$
and $n\equiv 1\cdot (-1)^b\equiv 1\pmod p$, therefore $p\mid n-1$,
so $\beta(n)\mid 2^p-1\mid 2^{n-1}-1$. Thus, $n\in \mathfrak{B}$.
The size of $n$ is
$$
n<M^k<2^{pk}.
$$
We write $x=2^{pk}$. Thus, $pk=(\log x)/(\log 2)$. By unique
factorization, it follows that positive integers $n$ arising from
distinct sets of primes
$$
\{p_1,\ldots,p_{a-3},q_1,\cdots,q_b,r_1,r_2,r_3\}
$$
are distinct.
The number of such sets is obtained by multiplying the bounds
\eqref{eq:UV} and \eqref{eq:r}. Thus,
$$
\#\mathfrak{B}(x)\gg \frac{M^{k-1}}{p^{5k}}\gg \frac{x}{\exp(p\log
2+5k\log p)}.
$$
Thus, with $kp=(\log x)/(\log 2)$, our task is to choose $k$ and $p$
such that $p(\log 2)+5k\log p$ is minimal. This suggests to choose
$k$ and $p$ such that $k=(c_5+o(1)) p/\log p$ as $p\to\infty$, where $c_5=(\log
2)/5$. Since $kp=(\log x)/\log 2$, we need to choose $p$ such that
$p^2/\log p=(c_6+o(1))(\log x)$, where $c_6=5/(\log 2)^2$. This
shows shows that we should choose $p$ close to $y=c_7(\log x\log\log
x)^{1/2}$, where $c_7=(2.5)^{1/2}/\log 2$. A recent result of Baker,
Harman and Pintz (see \cite{BHP}) says that for large $x$ it is
always possible to choose a prime $p$ in $[c_7(\log x\log\log
x)^{1/2}, c_7(\log x\log\log x)^{1/2}+O((\log x)^{0.26})]$, which is
good enough for our purposes. In fact, the statement that for large $x$ there exists a prime in an interval 
like the above with the exponent $0.26$ replaced by any exponent
$<1/2$ is good enough for our purposes. Once such $p$ is chosen, we choose
$k\equiv 1\pmod 4$ such that $k=(\log x)/(p\log 2)+O(1)$, which is
obviously possible. Since $k\ll p/\log p$, it follows that the
condition $k=o(p)$ is indeed fulfilled as $p\to\infty$. This
argument shows that
\begin{equation}
\label{eq:lowB} \#\mathfrak{B}(x)\ge x\exp((-c_8+o(1))(\log
x\log\log x)^{1/2})
\end{equation}
holds as $x\to\infty$, where $c_8=2(\log 2)c_7={\sqrt{10}}$. This
finishes the proof of Theorem \ref{thm:2}.

\medskip

\noindent {\bf Remark.} Obviously, our arguments for the upper bound
\eqref{eq:upB} and lower bound \eqref{eq:lowB} are not tight and at
least the involved multiplicative constants inside the exponentials
can easily be improved. We leave it to the reader as an open problem
to bring the upper and lower bounds \eqref{eq:upB} and
\eqref{eq:lowB} substantially closer.

\section{Acknowledgements} 

We thank the referee for a careful reading of the manuscript and for suggestions that improved the quality of our paper. This paper started during a pleasant visit
of the second author at the Mathematical Institute of the UNAM in
Morelia, Mexico in November of 2007. He thanks the people of this
Institute for their hospitality. During the preparation of this
paper, F.~L. was supported in part by Grant SEP-CONACyT 79685 and
PAPIIT 100508.

\begin{thebibliography}{9999}

\bibitem{Ay} R.~ Ayoub, On Rademacher's extension of the Goldbach-Vinogradov
theorem, {\it Canad. J. Math.\/} {\bf 5} (1953), 482--491.

\bibitem{BHP} R.~C.~Baker, G.~ Harman and J.~ Pintz,
The difference between consecutive primes. II., {\it Proc. Lond.
Math. Soc.\/} III Ser. {\bf 83} (2001), 532--562.

\bibitem{BaLu} W.~D.~Banks and F.~Luca, Sums of prime divisors and Mersenne numbers,
{\it Houston J. Math.\/}  {\bf 33}  (2007), 403--413.

\bibitem{Ba} C.~Bauer, On Goldbach's conjecture in arithmetic progressions,
{\it Studia Sci. Math. Hungar.\/} {\bf 37}  (2001), 1--20.


\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{KoLu1} J.-M.~ De ~Koninck and F.~ Luca, On positive integers $n$
which are divisible by the sum of their prime factors, {\it
Mathematika\/} {\bf 52} (2005), 69--77.

\bibitem{KoLu2} J.-M. ~De ~Koninck and F. ~Luca, Integers divisible by sums of
powers of their prime factors, {\it J. Number Theory\/} {\bf 128}
(2008), 557--563.

\bibitem{KoLu3} J.-M.~ De~ Koninck and F.~ Luca, On sums of powers of prime
factors of an integer, {\it Ann. Univ. Sci. Budapest Sect.
Comput.\/}, to appear.

\bibitem{ErPom} P.~Erd\H os and C. Pomerance, On the largest prime factors of $n$ and $n+1$,
{\it Aequationes Math.\/} {\bf 17} (1978), 311--321.

\bibitem{LuPo} F.~Luca and C.~Pomerance, Irreducible radical
extensions and Euler-function chains, in {\it Combinatorial Number
Theory}, de Gruyter, Berlin, 2007, pp.\ 351--361.

\bibitem{Pom1} C.~Nelson, D.~E.~Penney and C.~Pomerance, 714 and 715,
{\it J. Rec. Math.\/} {\bf 7} (1974), 87--89.

\bibitem{Pom2} C.~Pomerance, Ruth-Aaron numbers revisited, in
{\it Paul Erd\H os and his Mathematics}, Bolyai Soc.
Math. Stud. {\bf 11}, Janos Bolyai Math. Soc., Budapest, 2002,
567--579.


\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A41; Secondary 11N25.

\noindent \emph{Keywords: } primes, sieve methods.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 15 2008;
revised version received February 20 2009.
Published in {\it Journal of Integer Sequences},
February 23 2009.

\bigskip
\hrule
\bigskip

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


\end{document}