On Positive Integers n with a Certain Divisibility Property

Florian Luca Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58089 Morelia, Michoacán México

                     fluca@matmor.unam.mx

Vicentiu Tipu Department of Mathematics University of Toronto Toronto, Ontario, Canada M5S 2E4

                    vtipu@math.toronto.edu

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.

1 Introduction

For every positive integer n with factorization n = ∏_{p|n} p^{a_{p}}, we put β(n) = ∑_{p|n} p. Several authors have considered this function or one of the closely related functions B(n) = ∑_{p|n} p^{a_{p}}, or f(n) = ∑_{p|n} a_{p}p, or β_{k}(n) = ∑_{p|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ős and Pomerance ([9], [11] and [12]) studied the set of positive integers n such that f(n) = f(n+1), referred to as Ruth-Aaron numbers. De Koninck and Luca [6, 7] studied positive integers n with at least two distinct prime factors for which β_{k}(n) divides n. De Koninck and Luca [8] studied positive integers n with at least two distinct prime factors such that B(n) = β(n)^{2}, while Banks and Luca [3] studied positive integers n such that β(n) | 2^{n} − 1.

Here, we add to the literature on this topic and study positive integers n such that β(n) | 2^{n−1} − 1. Note that if n = p is an odd prime, then

β(n) = p | 2^{p−1} − 1 = 2^{n−1} − 1.

In particular, by the Prime Number Theorem, there are at least π(x) ∼ x/ log x such positive integers n not exceeding x as x → ∞. Hence, to make our problem more interesting, we look at the set

𝔅 = {n is not a prime and β(n) | 2^{n−1} − 1}.

For any subset A of positive integers and a positive real number x we put A(x) = A ∩ [1, x]. Our first result shows that the counting function #𝔅(x) is of a smaller order of magnitude then the counting function of the primes.

Theorem 1. The estimate #𝔅(x) = o(x/ log x) holds as x → ∞.

Thus, if a “random” number n satisfies β(n) | 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 ∈ 𝔅. Thus,

again by the Prime Number Theorem, #𝔅(x) ≥ ∑_{k≥2} π(x^{1/k}) ≥ (2 + o(1))x^{1/2}/ log x as x → ∞. A quick computation with Mathematica revealed that 𝔅(10^{6}) has 3871 elements of which only 236 are prime powers. So, one would guess that the main contribution to #𝔅(x) should not come from prime powers for large x. Our next result shows that this is indeed so.

Theorem 2. The estimate 𝔅(x) = x^{1+o(1)} holds as x → ∞.

Our proofs of both Theorem 1 and 2 are effective in that in both cases specific functions bounding #𝔅(x) from above and from below and which have the indicated orders of magnitude are provided. In fact, for Theorem 2, we show that there are at least x^{1+o(1)} squarefree numbers in 𝔅(x) as x → ∞. 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 ≫ and ≪ with the usual meanings. The constants implied by the symbols O, ≫ and ≪ are absolute. We recall that U = O(V), U ≪ V and V ≫ U are all equivalent to the statement that |U| < cV holds with some positive constant c, while U = o(V) means that U/V → 0. We write c_{1}, c_{2}, … for positive constants which are labeled increasingly throughout the paper.

2 Proof of Theorem 1

In [3], it was shown that the counting function of the set positive integers n ≤ x such that β(n) | 2^{n} − 1 is O(x log log x/ log x). Here, we follow the basic approach of [3], 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 β(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} ≡ 1 (mod n). Finally, we write ω(n) and Ω(n) for the number of prime and prime power divisors of n (of exponent ≥ 1), respectively.

We let x be a large positive number. We let α > β ≥ γ be numbers in (0, 1). Let y, z and Ω be functions of x of growth

y = exp ((log x)^{α+o(1)}) , z = exp ((log x)^{β+o(1)}) , Ω = (log x)^{γ+o(1)}

as x → ∞. We shall make these functions more precise later. We split the set 𝔅(x) into six subsets as follows:

𝔅_{1} = {n ∈ 𝔅(x) : P ≤ y};
𝔅_{2} = {n ∈ 𝔅(x)\𝔅_{1} : p^{2} | n for some prime p ≥ y};
𝔅_{3} = {n ∈ 𝔅(x)\(𝔅_{1} ∪ 𝔅_{2}) : Ω(n) ≥ Ω};
𝔅_{4} = {n ∈ 𝔅(x)\(∪_{j=1}^{3}𝔅_{j}) : Q ≤ z};
𝔅_{5} = {n ∈ #𝔅(x)\(∪_{j=1}^{4}𝔅_{j}) : t(Q) ≥ Q^{1/3} and Ω(t(Q)) ≤ Ω};
𝔅_{6} = 𝔅(x)\(∪_{j=1}^{5}𝔅_{j}).

We now bound the cardinalities of each of the sets 𝔅_{i} for i = 1, …, 6.

The set 𝔅_{1}. Numbers in 𝔅_{1} are called y-smooth. Well-known results concerning the number of y-smooth numbers n ≤ x (see [5]) show that in our range the estimate

#𝔅_{1} = xu^{−u+o(u)}

holds as u → ∞, where u = log x/ log y (= (log x)^{1−α+o(1)} as x → ∞). Thus,

#𝔅_{1} ≤ x exp(−(1 + o(1))u log u) as x → ∞.  (1)

The set 𝔅_{2}. If p ∈ [y, x^{1/2}] is a fixed prime, then there are ⌊x/p^{2}⌋ ≤ x/p^{2} positive integers n ≤ x divisible by p^{2}. Summing up over all the possible values for p, we get that

#𝔅_{2} ≤ ∑_{y≤p≤x^{1/2}} \frac{x}{p^{2}} ≤ x ∑_{y≤m} \frac{1}{m^{2}} ≤ x ∫_{y−1}^{∞} \frac{dt}{t} ≪ \frac{x}{y}.  (2)

The set 𝔅_{3}. Lemma 13 in [10] shows that uniformly for all integers k ≥ 1 we have

∑_{\begin{matrix}n≤x \\ Ω(n)≥k \end{matrix}} 1 ≪ \frac{kx log x}{2^{k}}.  (3)

Applying this with k = ⌊Ω⌋, we get that

#𝔅_{3} ≤ x exp (−(log 2 + o(1))Ω)  as x → ∞.  (4)

From now on until the end of the argument, we consider n ∈ 𝔅(x)\(∪_{j=1}^{3}𝔅_{j}). Write n = P m and observe that P (m) < P and that y ≤ P ≤ x/m. Thus, m ≤ x/y. Note also that m ≥ 2 since n is not prime.

The set 𝔅_{4}. Let us fix a positive integer m ≤ x/y. Note that β(n) = P + β(m) < P Ω(n) < xΩ/m and that if m is fixed and β(n) is known, then P = β(n)−β(m) is determined uniquely; thus, n is also determined uniquely. Since n ∈ 𝔅_{4}, it follows that β(n) ≤ xΩ/m is a z-smooth number. As in the argument for 𝔅_{1}, it follows from the results from [5] that for a fixed m, the number of possibilities for n is

≤ \frac{xΩ}{m}v_{m}^{−v_{m}+o(v_{m})},

as v_{m} → ∞, where v_{m} = log(xΩ/m)/ log z. Since x/m ≥ y, we get that v_{m} ≥ v = log y/ log z (= (log x)^{α−β+o(1)} as x → ∞). Thus, for large x, it follows that uniformly in m ≤ x/y, the number of possibilities for n ∈ 𝔅_{4} is

≤ \frac{x}{m} exp(−(1 + o(1))v log v)

as x → ∞. Summing up now over all the possible values for m ≤ x/y, we get that

#𝔅_{4} ≤ x exp(−(1 + o(1))v log v) ∑_{2≤m≤x/y} \frac{1}{m}
≤ x(log x) exp(−(1 + o(1))v log v)

as x → ∞, which implies that

#𝔅_{4} ≤ x exp(−(1 + o(1))v log v)  (5)

as x → ∞.

The set 𝔅_{5}. This is by far the most interesting set. We fix again m ≤ x/y. Since Q | β(n), we have that P ≡ −β(m) (mod Q). Further, since Q | β(n) | 2^{n−1} − 1, we get that n − 1 ≡ 0 (mod t(Q)), so P m ≡ 1 (mod t(Q)). By the Chinese Remainder Theorem (note that t(Q) | 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 ≤ x/m (without even accounting for the fact that P is prime) is

≤ 1 + \frac{x}{mQt(Q)}.  (6)

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) ≥ Q^{1/3} > z^{1/3}.

Case 1. Qt(Q) ≤ x/m. Let us write 𝔅_{5,1} for the subset of 𝔅_{5} formed by such numbers n. In this instance, the second term in equation (6) dominates and the number of possibilities for P when m and Q are fixed is

≤ \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 ≡ 1 (mod d), it follows that Q = 1 + dℓ for some positive integer ℓ ≤ xΩ/(md) < xΩ (the case ℓ = 0 is not accepted since Q = 1 is not prime). Thus, the number of possibilities for n ∈ 𝔅_{5,1} when m and d are fixed does not exceed

\frac{2x}{md} ∑_{1≤ℓ<xΩ} \frac{1}{1 + dℓ} < \frac{2x}{md^{2}} ∑_{1≤ℓ<xΩ} \frac{1}{ℓ} ≪ \frac{x log x}{md^{2}}.

Summing up the above bound over all m ≤ x/y and d ≥ z^{1/3}, we get that

#𝔅_{5,1} ≪ x log x ∑_{m≤x/y} \frac{1}{m} ∑_{z^{1/3}≤d≤xΩ} \frac{1}{d^{2}}

≪ x(log x)^{2} ∫_{z^{1/3}}^{∞} \frac{dt}{t^{2}} ≪ \frac{x(log x)^{2}}{z^{1/3}} .  (7)

Case 2. Qt(Q) > x/m. We write 𝔅_{5,2} for the subset of 𝔅_{5} consisting of these numbers. We write also β(n) = P + β(m) = Qδ, where 1 ≤ δ < xΩ/m is some positive integer. Since P ≤ 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 δ and observe that Q ≤ xΩ/(mδ). Note also that

P = β(n) − β(m) = Qδ − β(m) ≡ δ − β(m) (mod d).

Since also P m ≡ 1 (mod d), we get that d divides m(β(m) − δ) + 1. This last number is not zero since m ≥ 2 (if it were zero, then m(δ − β(m)) = 1, which is impossible for m ≥ 2). Since δ ≥ 1, the size of this number is

|m(β(m) − δ) + 1| < max{mδ, mP (m)Ω(m)}
< max{xmΩ, m^{2}Ω}
< xmΩ < \frac{x^{2}Ω}{y} < x^{2}

for large values of x. Thus,

Ω(|m(β(m) − δ) + 1|) < \frac{log(x^{2})}{log 2} < 3 log x.

Since d is a divisor of the fixed integer m(β(m) − δ) + 1 having Ω(d) < Ω, it follows that d can be chosen in at most

(3 log x)^{Ω} < exp ((log log x + log 3)Ω)  (8)

ways for large values of x. Now Q ≤ xΩ/(mδ) is a prime with Q ≡ 1 (mod d), so the number of possibilities for Q (hence, for P) is

≤ \frac{xΩ}{mδd}.

Keeping m and δ fixed and summing up over all the possible values of d (the number of which is indicated by upper bound (8)) we conclude that once m and δ are fixed, then Q (hence, P; so also n) can be fixed in at most

\frac{xΩ exp ((log log x + log 3)Ω)}{z^{1/3}mδ}

ways. Summing up over all the possibilities for δ < xΩ and m ≤ x/y, we get that

#𝔅_{5,2} ≤ \frac{x}{z^{1/3}} exp ((log log x + log 3)Ω) ∑_{m≤x/y} \frac{1}{m} ∑_{δ≤xΩ} \frac{1}{δ}
≪ \frac{x}{z^{1/3}} (log x)^{2} exp ((log log x + log 3)Ω)  (9)

as x → ∞. Comparing estimates (7) and (9), we conclude that for large x we have

#𝔅_{5} ≤ #𝔅_{5,1} + #𝔅_{5,2}
< x exp (−\frac{log z}{3} + (log log x + log 3)Ω + O(log log x))  (10)

as x → ∞.

The set 𝔅_{6}. Suppose that n ∈ 𝔅_{6}. Then either t(Q) < Q^{1/3}, or Ω(d) > Ω. Let 𝔅_{6,1} and 𝔅_{6,2} be the subsets of 𝔅_{6} such that the first and second inequality holds, respectively.

We first deal with 𝔅_{6,1}. Let Q be the set of primes such that t(Q) < Q^{1/3}, and let Q(t) = Q ∩ [1, t]. The first few elements of the set Q are {8191, 43691, 65537, …}. We first show that Q is sparse. Let t be large and let k = #Q(t). Let 8191 = q_{1} < ⋯ < q_{k} be all the numbers in Q(t). Then

8191^{k} < ∏_{i=1}^{k} q_{i} | ∏_{j≤t^{1/3}}(2^{j} − 1) < 2^{∑_{j≤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 ≤ t, we have

∑_{\begin{matrix}s≤q≤t \\ q∈Q \end{matrix}} \frac{1}{q} = ∫_{s}^{t} \frac{d#Q(u)}{u} = \frac{#Q(u)}{u}|_{u=s}^{u=t} + ∫_{s}^{t} \frac{#Q(u)}{u^{2}}du ≪ \frac{1}{s^{1/3}} .  (11)

Returning to our problem, let n ∈ 𝔅_{6,1}. To count such n, write again n = P m and β(n) = Qδ and assume that m ≤ x/y and Q ∈ [z, xΩ] are fixed. Then δ can be chosen in at most

\frac{xΩ}{mQ}

ways. Note that Q ∈ Q. Summing up the above bound over m ≤ x/y and Q ∈ Q ∩ [z, xΩ], we get that

#𝔅_{6,1} ≪ xΩ ∑_{m≤x/y} \frac{1}{m} ∑_{\begin{matrix}z≤Q≤xΩ \\ Q∈Q \end{matrix}} \frac{1}{Q}

≪ \frac{x(log x)Ω}{z^{1/3}} = \frac{x}{z^{1/3+o(1)}}  (12)

as x → ∞, where in the above estimate we used the upper bound (11) with s = z and t = xΩ.

We now deal with 𝔅_{6,2}. Note that for such numbers, Q − 1 is a multiple of d, so Ω(Q − 1) ≥ Ω(d) > Ω. Fix m and Q < xΩ. Then δ (hence, P; so, n) can be fixed in at most

\frac{xΩ}{Q} < \frac{xΩ}{Q − 1}  (13)

ways. It follows easily by partial summation from formula (3) that uniformly in k ≥ 1 and t, we have

∑_{\begin{matrix}n≤t \\ Ω(n)≥k \end{matrix}} \frac{1}{n} ≪ \frac{k(log t)^{2}}{2^{k}} .  (14)

Summing up bounds (13) over all primes Q with Ω(Q − 1) > Ω and using bound (14) for t = xΩ and k = ⌊Ω⌋, we get that

#𝔅_{6,2} ≪ \frac{x(log x)^{2}Ω^{2}}{2^{Ω}} = x exp(−(log 2 + o(1))Ω)  (15)

as x → ∞. From estimates (12) and (15), we get

#𝔅_{6} ≤ \frac{x}{z^{1/3+o(1)}} + \frac{x}{exp ((log 2 + o(1))Ω)}  (16)

as x → ∞.

Comparing bounds (1), (2), (4), (5), (10) and (16), we see that the optimal bounds are obtained when the parameters y, z and Ω are chosen such that

Ω log 2 = \frac{log z}{3} − (log log x + log 3)Ω = v log v = u log u.

This gives

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},
Ω = (c_{3} + o(1))(log x)^{1/3}(log log x)^{1/3}

as x → ∞, 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, Ω with α = 2/3, β = γ = 1/3. Therefore we have just shown that

#𝔅(x) ≤ x exp (−(c_{4} + o(1))(log x log log x)^{1/3})  (17)

as x → ∞, where c_{4} = (log 2)^{1/3}/3. This finishes the proof of Theorem 1.

Remark. Notice that as a byproduct of our effort we conclude immediately, by partial summation, that

∑_{n∈𝔅} \frac{1}{n} < ∞.

3 Proof of Theorem 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 → ∞. Choose positive integers a ≥ 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 ≡ 1 (mod 4). From now on, we work under this assumption. Let I = ⌊M/(2p^{2}), M/p^{2}⌋. We choose a − 3 distinct primes in I which are 1 modulo p and b distinct primes in 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 I), it follows that the inequality

U_{η} = π(M/p^{2}; p, η) − π(M/(2p^{2}); p, η) ≥ \frac{M}{3p^{3} log M} for η ∈ \{±1\}

holds for large values of p. Recall that π(x; v, u) means the number of primes p ≤ x congruent to u modulo v. The number of choices of pairs of primes as above is

= \binom{U_{1}}{a − 3}\binom{U_{−1}}{b} ≥ (\frac{U_{1}}{a − 3})^{a−3} (\frac{U_{1}}{b} )^{b}
≥ (\frac{U_{1}}{a} )^{a−3} (\frac{U_{−1}}{b} )^{b} (1 + O (\frac{kp^{3}}{M} ))^{k}
≫ \frac{M^{k−3}}{(3(log 2)kp^{4})^{k−3}} ≫ \frac{M^{k−3}}{p^{5k−15}}  (18)

since 3(log 2)k < p for large p. Here, we also used the fact that log M < p(log 2). Let p_{1} < ⋯ < p_{a−3} and q_{1} < ⋯ < q_{b} be such primes. Put

N = p_{1} + ⋯ + p_{a−3} + q_{1} + ⋯ + 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 ≡ a − 3 − b (mod p) ≡ −2 (mod p). Thus, M − N > M − M/p is a large odd number which is congruent to

2^{p} − 1 − N ≡ 2 − 1 − (−2) ≡ 3 (mod p).

By a Theorem of Ayoub [1] (see also [4]), 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

∼ \frac{pC_{M−N}M^{2}}{6((p − 1)^{3} + 1)(log M)^{3}} (1 + o(1))  (19)

as p → ∞, where

C_{M−N} = ∏_{ℓ|M−N} (1 − \frac{ℓ}{(ℓ − 1)^{3} + 1}) ∏_{ℓ>2} (1 + \frac{1}{(ℓ − 1)^{3}} ) .

Observe that C_{M−N} ≫ 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} ≤ M/p^{2} is a prime congruent to 1 modulo p and r_{2} ≤ 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

≤ π(M/p^{2}; p, 1)π(M; p, 1) ≪ \frac{M^{2}}{p^{4}(log M)^{2}} ≪ \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 (19). Thus, for large p, there are

≫ \frac{M^{2}}{p^{2}(log M)^{3}} ≫ \frac{M^{2}}{p^{5}}  (20)

such representations where r_{1} > M/p^{2}. From now on we work with such representations. Now observe that {p_{1}, …, p_{a−3}, q_{1}, …, 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

β(n) = ∑_{i=1}^{a−3} p_{i} + ∑_{j=1}^{b} q_{j} + r_{1} + r_{2} + r_{3} = 2^{p} − 1

and n ≡ 1 · (−1)^{b} ≡ 1 (mod p), therefore p | n − 1, so β(n) | 2^{p} − 1 | 2^{n−1} − 1. Thus, n ∈ 𝔅. 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}, …, p_{a−3}, q_{1}, ⋯, q_{b}, r_{1}, r_{2}, r_{3}}

are distinct. The number of such sets is obtained by multiplying the bounds (18) and (20). Thus,

#𝔅(x) ≫ \frac{M^{k−1}}{p^{5k}} ≫ \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 → ∞, 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 [2]) 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 ≡ 1 (mod 4) such that k = (log x)/(p log 2)+O(1), which is obviously possible. Since k ≪ p/ log p, it follows that the condition k = o(p) is indeed fulfilled as p → ∞. This argument shows that

#𝔅(x) ≥ x exp((−c_{8} + o(1))(log x log log x)^{1/2})  (21)

holds as x → ∞, where c_{8} = 2(log 2)c_{7} = \sqrt{10}. This finishes the proof of Theorem 2.

Remark. Obviously, our arguments for the upper bound (17) and lower bound (21) 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 (17) and (21) substantially closer.

4 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.

References

[1] R. Ayoub, On Rademacher’s extension of the Goldbach-Vinogradov theorem, Canad. J. Math. 5 (1953), 482–491.

[2] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes. II., Proc. Lond. Math. Soc. III Ser. 83 (2001), 532–562.

[3] W. D. Banks and F. Luca, Sums of prime divisors and Mersenne numbers, Houston J. Math. 33 (2007), 403–413.

[4] C. Bauer, On Goldbach’s conjecture in arithmetic progressions, Studia Sci. Math. Hungar. 37 (2001), 1–20.

[5] E. R. Canfield, P. Erdős and C. Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), 1–28.

[6] J.-M. De Koninck and F. Luca, On positive integers n which are divisible by the sum of their prime factors, Mathematika 52 (2005), 69–77.

[7] J.-M. De Koninck and F. Luca, Integers divisible by sums of powers of their prime factors, J. Number Theory 128 (2008), 557–563.

[8] J.-M. De Koninck and F. Luca, On sums of powers of prime factors of an integer, Ann. Univ. Sci. Budapest Sect. Comput., to appear.

[9] P. Erdős and C. Pomerance, On the largest prime factors of n and n + 1, Aequationes Math. 17 (1978), 311–321.

[10] F. Luca and C. Pomerance, Irreducible radical extensions and Euler-function chains, in Combinatorial Number Theory, de Gruyter, Berlin, 2007, pp. 351–361.

[11] C. Nelson, D. E. Penney and C. Pomerance, 714 and 715, J. Rec. Math. 7 (1974), 87–89.

[12] C. Pomerance, Ruth-Aaron numbers revisited, in Paul Erdős and his Mathematics, Bolyai Soc. Math. Stud. 11, Janos Bolyai Math. Soc., Budapest, 2002, 567–579.

2000 Mathematics Subject Classification: Primary 11A41; Secondary 11N25. Keywords: primes, sieve methods.

(Concerned with sequence \underline{A156787}.)

Received December 15 2008; revised version received February 20 2009. Published in Journal of Integer Sequences, February 23 2009.

Return to Journal of Integer Sequences home page.