On the Middle Prime Factor of an Integer

Jean-Marie De Koninck Département de Mathématiques

Université Laval Québec G1V 0A6

Canada

 jmdk@mat.ulaval.ca

Florian Luca Fundación Marcos Moshinsky

UNAM Circuito Exterior C.U. Apdo. Postal 70-543 Mexico D.F. 04510

Mexico

fluca@matmor.unam.mx

Abstract

Given an integer n ≥ 2, let p_{m}(n) denote the middle prime factor of n. We obtain an estimate for the sum of the reciprocals of p_{m}(n) for n ≤ x.

1 Introduction

Given an integer n ≥ 2, let P (n) stand for its largest prime factor, writing P (1) = 1. The global behavior of this function is easy to evaluate. For instance, one can easily show that

∑_{n≤x} P (n) = \frac{π^{2}}{12} \frac{x^{2}}{log x} + O (\frac{x^{2}}{log^{2} x}) .

This is a well known result and a proof can be found in our recent book ([4, Thm. 9.2]).

Estimating the global behavior of the reciprocal of P (n) is much harder, and it has been the focus of many papers at the end of the 1970’s and early 1980’s. See, for instance, the book of De Koninck and Ivić [2] and the papers of Erdős and Ivić [5, 6]. The best estimate was finally obtained in 1986 by Erdős, Ivić and Pomerance [7]; they proved that

∑_{n≤x} \frac{1}{P (n)} = xδ(x) (1 + O (\sqrt{\frac{log_{2} x}{log x}})) ,

where δ(x) is some continuous function which decreases to 0 very slowly as x → ∞ and satisfies

δ(x) = exp\{−\sqrt{2 log x log_{2} x}(1 + o(1))\} as x → ∞.

Here and in what follows, for an integer k ≥ 2, we write log_{k} x for the k-th fold iterate of log evaluated at x, and we shall assume that the input x in such an expression is sufficiently large such that the thus defined iterated logarithm is real and positive.

Interestingly the sum of the reciprocals of the second largest prime factor function P_{2}(n) defined for those integers n with at least two prime factors, has a totally different asymptotic value. In fact, the first author proved in 1993 (see De Koninck [1]) that, if Ω(n) stands for the number of prime factors of n counting their multiplicity,

∑_{\begin{matrix}n≤x \\ Ω(n)≥2 \end{matrix}} \frac{1}{P_{2}(n)} = c_{2} \frac{x}{log x} + O (\frac{x}{log^{2} x}) ,

where c_{2} = ∑_{m=1}^{∞} \frac{1}{m} ∑_{p≥P (m)} \frac{1}{p^{2}} ≈ 1.254. In the same paper, it is shown that, if P_{k}(n) stands for

the k-largest prime factor of an integer, then

∑_{\begin{matrix}n≤x \\ Ω(n)≥k \end{matrix}} \frac{1}{P_{k}(n)} = c_{k} \frac{x(log_{2} x)^{k−2}}{log x} (1 + O (\frac{1}{log_{2} x})) ,

where c_{k} = c_{2}/(k − 2)!.

In 1988, De Koninck and Galambos [3] estimated the sum of the reciprocals of a random prime factor of an integer. More precisely, for each integer n ≥ 2, let

p_{1}(n) < p_{2}(n) < ⋯ < p_{ω(n)}(n)

be its k = ω(n) distinct prime factors, and then select at random (with equal probability 1/k) one of these prime factors and call it p_{∗}(n). Then, set

R(x) = ∑_{2≤n≤x} \frac{1}{p_{∗}(n)}.  (1)

Note that the total number of sums of the above form is ω(2)ω(3) ⋯ ω(⌊x⌋). We shall say that a property holds for almost all sums in (1) if the number N(x) of sums with the property in question satisfies

\frac{N(x)}{ω(2)ω(3) ⋯ ω(⌊x⌋)} → 1 as x → ∞.

Then they proved that, for almost all sums in (1),

R(x) = c_{1} \frac{x}{log_{2} x} + O (\frac{x}{(log_{2} x)^{2}} ) ,

where c_{1} = ∑_{p} \frac{1}{p^{2}} ≈ 0.452.

During the 1984 Oberwolfach Conference on Analytic Number Theory, Paul Erdős asked the first author if he had thought of estimating the sum of the reciprocals of the middle prime factor of an integer. After almost 30 years, we can now prove an estimate for this sum.

2 The main result

Given an integer n ≥ 2, write it as n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}}, where p_{1} < p_{2} < ⋯ < p_{k} are its distinct prime factors and α_{1}, α_{2}, …, α_{k} are positive integers. We let p_{m}(n) = p_{max(1,⌊k/2⌋)} and say that p_{m}(n) is the “middle” prime factor of n. We will prove the following estimate.

Theorem 1. As x → ∞,

∑_{n≤x} \frac{1}{p_{m}(n)} = \frac{x}{log x} exp ((c_{0} + o(1))\sqrt{log_{2} x log_{3} x}) ,

where c_{0} = \sqrt{2}.

3 The proof of the upper bound

For the upper bound, we first set

N_{1}(x) = {n ≤ x : Ω(n) > 10 log_{2} x};
N_{2}(x) = {n ≤ x : p_{m}(n) > log x};
N_{3}(x) = {n ≤ x : ω(n) = 1, 2}.

By Luca and Pomerance [9, Lem. 13], we have

#N_{1}(x) ≪ \frac{x log x log_{2} x}{2^{10 log_{2} x}} ≪ \frac{x}{(log x)^{5}} ,

which shows that

∑_{n∈N_{1}(x)} \frac{1}{p_{m}(n)} ≪ #N_{1}(x) ≪ \frac{x}{(log x)^{5}} .  (2)

Clearly,

∑_{n∈N_{2}(x)} \frac{1}{p_{m}(n)} ≤ \frac{#N_{2}(x)}{log x} ≪ \frac{x}{log x}.  (3)

Finally,

#N_{3}(x) ≪ \frac{x log_{2} x}{log x},

so that

∑_{n∈N_{3}(x)} \frac{1}{p_{m}(n)} ≪ \frac{x log_{2} x}{log x}.  (4)

In light of these estimates for the contributions of the members n from N_{1}(x), N_{2}(x) and N_{3}(x) to the sum of the reciprocals of p_{m}(n), from now on we assume that n ∈ N_{4}(x) = {n ≤ x}\ (N_{1}(x) ∪ N_{2}(x) ∪ N_{3}(x)) .

Fix p ∈ [2, log x] and k ∈ [3, 10 log_{2} x] and consider the set

N_{p,k}(x) = {n ∈ N_{4}(x) : p_{m}(n) = p and ω(n) = k}.

Write k = 2k_{0} + δ, where δ ∈ {0, 1}. If n ∈ N_{p,k}(x), then n = ap^{α}b, where P (a) < p, α ≥ 1, all prime factors of b exceed p and ω(a) = k_{0} − 1, and ω(b) = k_{0} + δ. Fix also a. Then b ≤ x/ap^{α}. Note that

ap^{α} ≤ p^{10 log_{2} x} < (log x)^{10 log_{2} x} = x^{o(1)} as x → ∞.

Hence, given a and p^{α}, the number of choices for the number b is, by the Hardy-Ramanujan inequalities (see Hardy and Ramanujan [8] or De Koninck and Luca [4, Thm. 10.1]),

≪ \frac{x}{ap^{α} log(x/ap^{α})} × \frac{1}{(k_{0} + δ − 1)!} × (log_{2}(x/ap^{α}) + O(1))^{k_{0}+δ−1}
≪ \frac{x(log_{2} x)}{ap^{α} log x} × \frac{1}{(k_{0} − 1)!} × (log_{2} x)^{k_{0}−1}.

Thus, since k! ≥ (k/e)^{k}, we have

\frac{1}{p}#N_{p,k}(x) ≤ \frac{1}{p} ∑_{\begin{matrix}a \\ ω(a)=k_{0}−1 \\ Ω(a)<10 log_{2} x \\ P (a)<p \end{matrix}} ∑_{α≥1} \frac{x(log_{2} x)}{ap^{α} log x} × \frac{1}{(k_{0} − 1)!} × (log_{2} x)^{k_{0}−1}

≪ \frac{x(log_{2} x)}{p^{2} log x} × \frac{(log_{2} x)^{k_{0}−1}}{(k_{0} − 1)!} ∑_{\begin{matrix}a \\ ω(a)=k_{0}−1 \\ Ω(a)<10 log_{2} x \\ P (a)<p \end{matrix}} \frac{1}{a}

≪ \frac{x(log_{2} x)}{p^{2} log x} × \frac{(log_{2} x)^{k_{0}−1}}{(k_{0} − 1)!} × \frac{1}{(k_{0} − 1)!} (∑_{\begin{matrix}q<p \\ β≥1 \end{matrix}} \frac{1}{q^{β}} )^{k_{0}−1}

≪ \frac{x(log_{2} x)}{p^{2} log x} × \frac{(log_{2} x)^{k_{0}−1}}{(k_{0} − 1)!} × \frac{(log_{2} p)^{k_{0}−1}}{(k_{0} − 1)!}
≪ \frac{x(log_{2} x)^{2}}{p^{2} log x} (\frac{e^{2} log_{2} x log_{2} p}{k_{0}^{2}})^{k_{0}} .

For fixed A > 1, the maximum of the function f_{A}(t) = (e^{2}A/t^{2})^{t} is attained at t_{0} = \sqrt{A} in which case f_{A}(t_{0}) = exp(2\sqrt{A}). We first take B = exp(2\sqrt{log_{2} x log_{3} x}) and split the range of p into values p ≤ B and p > B. Let N_{5}(n) and N_{6}(n) be the subsets of N_{4}(x) for which p(n) ≤ B and p(n) > B, respectively. Applying the above observation with

A = log_{2} x log_{2} B,

we get that

∑_{n∈N_{5}(x)} \frac{1}{p_{m}(n)} ≤ ∑_{\begin{matrix}p≤B \\ 3≤k<10 log_{2} x \end{matrix}} \frac{1}{p}#N_{p,k}(x)

≪ ∑_{\begin{matrix}p≤B \\ 1≤k_{0}<5 log_{2} x \end{matrix}} \frac{x(log_{2} x)^{2}}{p^{2} log x} (\frac{e^{2} log_{2} x log_{2} B}{k_{0}^{2}} )^{k_{0}}

≪ \frac{x(log_{2} x)^{3}}{log x} exp(2\sqrt{A}) ( ∑_{2≤p≤B} \frac{1}{p^{2}} )
≪ \frac{x}{log x} exp ((c_{0} + o(1))\sqrt{log_{2} x log_{3} x})  (5)

as x → ∞. For N_{6}(x), we use the fact that p ≤ log x, put C = log_{2} x log_{3} x, and use the above argument based on the maximum of the function f_{C}(t) to get that

∑_{n∈N_{6}(x)} \frac{1}{p_{m}(n)} ≪ ∑_{\begin{matrix}B<p<log x \\ 3≤k<10 log_{2} x \end{matrix}} \frac{1}{p}#N_{p,k}(x)

≪ ∑_{\begin{matrix}B<p≤log x \\ 1≤k_{0}<5 log_{2} x \end{matrix}} \frac{x(log_{2} x)^{2}}{p^{2} log x} (\frac{e^{2} log_{2} x log_{3} x}{k_{0}^{2}})^{k_{0}}

≪ \frac{x(log_{2} x)^{3}}{log x} exp(2\sqrt{C}) (∑_{p>B} \frac{1}{p^{2}} ) ≪ \frac{x(log_{2} x)^{3}}{log x} ,  (6)

because B = exp(2\sqrt{C}). Comparing estimates (2), (3), (4), (5) and (6), we get the desired estimate.

4 The proof of the lower bound

We now turn our attention to the lower bound. For this, we shall select a subset of positive integers n ≤ x such that the sum of the reciprocals of p_{m}(n) for n’s in this subset already achieves the desired lower bound. Our n’s will be of the form

n = abpP

such that p ∈ [q_{0}, 2q_{0}], a and b are square free and have k_{0} and k_{0} − 1 prime factors, respectively, with r < p(a) < P (a) ≤ q_{0} and 2q_{0} < p(b) < P (b) < x^{1/(2k_{0})}, and P is a prime in the interval [x/(2pab), x/(pab)]. Here,

q_{0} = exp (\sqrt{\frac{log_{2} x}{log_{3} x}})  and k_{0} = ⌊c_{0}^{−1}\sqrt{log_{2} x log_{3} x}⌋,  r = log_{2} x.

Formally,

A = {a : μ^{2}(a) = 1, P (a) ≤ q_{0}, p(a) > r, ω(a) = k_{0}}.

We need to estimate the sum of reciprocals of the members of A. For this, we set

S = ∑_{r<q≤q_{0}} \frac{1}{q} and S_{1} = ∑_{r<q≤q_{0}} ∑_{β≥1} \frac{1}{q^{β}} .

Clearly,

S = log_{2} q_{0} − log_{2} r + O(1) = \frac{1}{2} log_{3} x + O(log_{4} x),  (7)

and

S_{1} = S + ∑_{r<q≤q_{0}} ∑_{β≥2} \frac{1}{q^{β}} = S + O (∑_{q>r} \frac{1}{q^{2}} ) = S + O (\frac{1}{r}) .

In particular,

S_{1}^{k_{0}} = (S + O (\frac{1}{r}))^{k_{0}} = S^{k_{0}} exp (O (\frac{k_{0}}{rS} )) = S^{k_{0}}(1 + o(1)).

Now it is easy to see that

∑_{a∈A} \frac{1}{a} ≥ \frac{1}{k_{0}!}S^{k_{0}} − ∑_{r<q<p} \frac{1}{q^{2}} \frac{S_{1}^{k_{0}−1}}{(k_{0} − 1)!}

≥ \frac{S^{k_{0}}}{k_{0}!} (1 + O (\frac{k_{0}}{S} ∑_{q>r} \frac{1}{q^{2}} ))

= \frac{S^{k_{0}}}{k_{0}!} (1 + O (\frac{k_{0}}{rS} )) = \frac{S^{k_{0}}}{k_{0}!} (1 + o(1)).  (8)

Observe that if a ∈ A, then ap < (2q_{0})^{k_{0}+1} < (log x)^{log_{2} x} for all sufficiently large x. Now let

B = {b : μ^{2}(b) = 1, p(b) > 2q_{0}, P (b) < x^{1/(2k_{0})}, ω(b) = k_{0} − 1} .

Proceeding as in the estimation of the sum of the reciprocals of a ∈ A, one gets that

∑_{b∈B} \frac{1}{b} ≫ \frac{1}{(k_{0} − 1)!} (T + O(1))^{k_{0}−1} ≫ \frac{1}{\sqrt{log_{2} x}} \frac{T^{k_{0}}}{k_{0}!} ,  (9)

where

T = ∑_{2q_{0}<q<x^{1/2k_{0}}} \frac{1}{q} = log_{2}(x^{1/2k_{0}}) − log_{2}(2q_{0}) + o(1)
= log_{2} x + O(log_{3} x).  (10)

Consider now a ∈ A, b ∈ B. Then

apb < (log x)^{log_{2} x}x^{(k_{0}−1)/(2k_{0})} < x^{1/2}(log x)^{log_{2} x} < x^{2/3}

for all sufficiently large x, so that letting P ∈ [x/(2apb), x/(apb)], it follows that

P ≥ x/(2apb) > x^{1/3} > x^{1/(2k_{0})}

for large x, implying that given n = P apb, the numbers P, a, b are uniquely determined. Observe that the number of choices for P is

π (\frac{x}{abp}) − π (\frac{x}{2abp}) ≫ \frac{x}{apb log(x/apb)} ≫ \frac{x}{apb log x}.  (11)

Thus, in light of (8), (9) and (11), it follows that the number of positive integers n ≤ x such constructed and for which p_{m}(n) = p is

≥ ∑_{a∈A} ∑_{b∈B} (π (\frac{x}{apb}) − π (\frac{x}{2apb}))

≫ \frac{x}{p log x} (∑_{a∈A} \frac{1}{a}) (∑_{b∈B} \frac{1}{b}) ,

so that

\frac{1}{p} ∑_{\begin{matrix}n≤x \\ p_{m}(n)=p \end{matrix}} 1 ≫ \frac{x}{p^{2} log x\sqrt{log log x}} \frac{(ST)^{k_{0}}}{k_{0}!^{2}} ,

which means, in light of (7) and (10), that

\frac{1}{p} ∑_{\begin{matrix}n≤x \\ p_{m}(n)=p \end{matrix}} 1 ≫ \frac{x}{p^{2}(log x)(log_{2} x)^{3/2}}

× (\frac{(e^{2}/2 + o(1)) log_{2} x log_{3} x}{(1/2 + o(1)) log_{2} x log_{3} x})^{(c_{0}^{−1}+o(1))\sqrt{log_{2} x log_{3} x}}

≫ \frac{x exp((c_{0} + o(1))\sqrt{log_{2} x log_{3} x})}{log x} × \frac{1}{p^{2}}

implying that

∑_{n≤x} \frac{1}{p_{m}(n)} ≫ \frac{x}{log x} exp((c_{0} + o(1))\sqrt{log_{2} x log_{3} x}) ∑_{q_{0}<p<2q_{0}} \frac{1}{p^{2}}

≫ \frac{x exp((c_{0} + o(1))\sqrt{log_{2} x log_{3} x})}{log x} (\frac{π(2q_{0}) − π(q_{0})}{4q_{0}^{2}})
≫ \frac{x}{q_{0}(log q_{0})(log x)} exp((c_{0} + o(1))\sqrt{log_{2} x log_{3} x})
≫ \frac{x}{log x} exp((c_{0} + o(1))\sqrt{log_{2} x log_{3} x}) (x → ∞),

as requested.

Remark 2. It would be interesting to obtain bounds on the error terms. One may also ask about variations of this problem in which one considers the median prime, or the middle prime taking into account multiplicities, and so on. We leave all such problems for a future project.

5 Acknowledgments

We thank the referee for suggestions which improved the quality of the manuscript. The work of the first author was supported by a grant from NSERC. The second worked on this paper during a visit to Université Laval in the Fall of 2012 and was supported in part by Projects PAPIIT IN104512, CONACyT Mexico-France 193539, CONACyT Mexico-India 163787, and a Marcos Moshinsky Fellowship.

References

[1] J. M. De Koninck, Sur les plus grands facteurs premiers d’un entier, Monatsh. Math. 116 (1993), 13–37.

[2] J. M. De Koninck and A. Ivić, Topics in Arithmetical Functions, Mathematics Studies 43, North-Holland, Amsterdam, 1980.

[3] J. M. De Koninck and J. Galambos, Some randomly selected arithmetical sums, Acta Math. Hung. 52 (1988), 37–43.

[4] J. M. De Koninck and F. Luca, Analytic Number Theory: Exploring the Anatomy of Integers, Graduate Studies in Mathematics, Vol. 134, American Mathematical Society, 2012.

[5] P. Erdős and A. Ivić, Estimates for sums involving the largest prime factor of an integer and certain related additive functions, Studia Sci. Math. Hungar. 15 (1980), 183–199.

[6] P. Erdős and A. Ivić, On sums involving reciprocals of certain arithmetical functions, Publ. Inst. Math. (Beograd) 32 (1982), 49–56.

[7] P. Erdős, A. Ivić, and C. Pomerance, On sums involving reciprocals of the largest prime factor of an integer, Glas. Mat. Ser. III 21 (1986), 283–300.

[8] G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Quart. J. Math. 48 (1917), 76–92.

[9] F. Luca and C. Pomerance, Irreducible radical extensions and Euler-function chains, Integers 7 (2007), Paper A25.

2010 Mathematics Subject Classification: Primary 11N37. Keywords: largest prime factor, middle prime factor.

Received March 2 2013; revised version received May 13 2013. Published in Journal of Integer Sequences, May 16 2013.

Return to Journal of Integer Sequences home page.