THE AVERAGE LARGEST PRIME FACTOR
Eric Naslund
Department of Mathematics, Princeton University, Princeton, New Jersey [email protected]
Received: 2/18/13, Revised: 7/17/13, Accepted:12/5/13 , Published: 12/13/13
Abstract
LetP(n) denote the largest prime factor of an integern. In this paper we look at the average of P(n), and prove that
1 x
X
nx
P(n) = lig(x) +O✏
⇣
xe c(logx)3/5 ✏⌘ , where lig(x) = Rx
2 t x
[x/t]
logtdt. This improves a result of De Koninck and Iv´ıc and allows us to deduce their asymptotic expansion
1 x
X
nx
P(n) =c0 x
logx+c1 1!x
(logx)2 +· · ·+ck 1(k 1)!x
(logx)k +O x (logx)k+1
!
as a corollary, with the advantage that we can give the constants explicitly as cn = 1
2n+1 Xn j=0
2j( 1)j⇣(j)(2)
j! .
1. Introduction
Let P(n) denote the largest prime factor of an integern. The moments of P(n) were first looked at in 1976 by Knuth and Pardon [4], and concerning the average, they proved that
X
nx
P(n)⇠⇡2 12
x2
logx. (1)
The above asymptotic also appeared in Erd˝os and Alladi’s 1977 paper [1] on additive arithmetic functions. Later, De Koninck and Ivi´c [2] proved that P
nxP(n) has an asymptotic expansion of the form
X
nx
P(n) =x2
✓ d1
logx+ d2
log2x+· · ·+ dm logmx+O
✓ 1 logm+1x
◆◆
where the constants di are computable, but not given explicitely. This expansion appears again in [3], where Ivi´c finds a similar formula for the kth largest prime factor. In this paper, we calculate the average of P(n) up to an error of the form O✏
⇣
xe c(logx)3/5 ✏⌘
, like that of the prime number theorem. This allows us to deduce De Koninck and Ivi´c’s expansion as a corollary, as well as give the constants di explicitely. Our main result is:
Theorem 1. Letting lig(x) =Rx 2 t
x [x/t]
logtdt, we have that 1
x X
nx
P(n) =lig(x) +O✏⇣
xe c(logx)3/5 ✏⌘
. (2)
For any integerk, lig(x)has the asymptotic expansion lig(x) =c0 x
logx+c1 1!x
(logx)2 +· · ·+ck 1(k 1)!x
(logx)k +O x (logx)k+1
! (3) where
cn = 1 2n+1
Xn j=0
2j( 1)j⇣(j)(2)
j! . (4)
These constantscn satisfy cn = 1 +O 2nn .
Notice in particular thatc0= ⇡122, so we deduce that X
nx
P(n) = ⇡2 12
x2
logx+O x2 (logx)2
! .
Although this expansion has previously been presented in [2], and again in [3], there are some advantages to the result above. We are able to give the constants cn explicitely in terms of the zeta function without much additional work, and our proof is basic requiring only an application of the hyperbola method. Furthermore, we give the explicit integral form which has an error term like that of the prime number theorem, paralleling how⇡(x) is approximated by the function li(x).
2. The Main Theorem
For each integernx, there is at most one primep >pxsuch thatp|n, and for each primepthere will be exactlyh
x p
i
integers less thanxwhich are divisible byp.
Combining these two facts, we see that X
px<px
p
x
p X
nx
P(n)X
px
p
x p ,
and sinceP
pp xph
x p
ixP
pp
x1 =O⇣
x3/2 logx
⌘, it follows that X
nx
P(n) =X
px
p
x p +O
✓x3/2 logx
◆
. (5)
By writingh
x p
i=P
nx:p|n1, and rearranging the order of summation, we obtain X
px
p
x
p =X
px
p X
nx:p|n
1 =X
nx
X
pxn
p. (6)
LettingK(x) =P
pxp, we have the estimate K(x) =
Z x 2
t
logtdt+O✏⇣
x2e c(logx)3/5 ✏⌘
, (7)
which follows from the prime number theorem (See [5]) along with partial summa- tion. Using (7) along with equations (5), and (6), we have that
X
nx
P(n) = X
nx
Z nx
2
t
logtdt+X
nx
O✏
✓x2
n2e c(logxn)3/5 ✏◆
+O x32 logx
!
= Z x
2
t⇥x
t
⇤
logtdt+O✏⇣
x2e c(logx)3/5 ✏⌘
(8)
= xlig(x) +O✏⇣
x2e c(logx)3/5 ✏⌘
, (9)
which proves (2). To recover the asymptotic expansion in (3), we turn our attention to this integral function and make the substitutiont= xu to obtain
lig(x) = 1 x
Z x 2
t⇥x
t
⇤ logtdt=x
Z x/2 1
[u]
u3log ux du. (10) We can rewrite the integral above as
Z x/2 1
[u]
u3log xu du= 1 logx
Z x/2 1
[u]
u3
✓
1 logu logx
◆ 1
du, and for any integerk 1, by the geometric series expansion
✓
1 logu logx
◆ 1
= 1 +logu
logx+· · ·+
✓logu logx
◆k 1
+
✓logu logx
◆k✓
1 logu logx
◆ 1
, we have that
Z x/2 1
[u]
u3log xu du =
kX1 n=0
1 (logx)n+1
Z x/2 1
[u]
u3(logu)ndu
+ 1
(logx)k+1 Z x/2
1
[u]
u3 (logu)k
✓
1 logu logx
◆ 1
du.
Each of these integrals is absolutely convergent on [1,1), and so the last term con- tributes an error term of at most Ok⇣
1 logk+1x
⌘. Settingck = k!1 R1
1 [u]
u3 (logu)kdu, and applying the bound
Z 1
x/2
[u]
u3 (logu)ndu Z 1
x/2
(logu)n u2 du=O
✓(logx)n x
◆ , it follows that
lig(x) = x logx
k 1
X
n=0
n!cn (logx)n +Ok
✓ x logk+1x
◆
. (11)
To evaluate these constants cn, we use exponential generating series. Integration by parts tells us that fors >1
⇣(s) = X1 n=1
n s= Z 1
1
x sd[x] =s Z 1
1
[x]x s 1dx, and so
X1 k=0
ckzk = Z 1
1
[x]xz 3dx=⇣(2 z) 2 z . Multiplying the power series expansions for⇣(2 z) and 21z yields
0
@X1
j=0
( 1)j⇣(j)(2)zj j!
1 A 1
2 X1 k=0
zk 2k
!
=1 2
X1 n=0
zn 0
@ X
k+j=n
( 1)j⇣(j)(2) j!
1 2k
1 A, and hence
cn = 1 2n+1
Xn j=0
2j( 1)j⇣(j)(2)
j! .
To find the size ofcn we note that ( 1)j⇣(j)(2)
j! = 1
j!
X1 k=1
(logk)j k2
= 1
j!
Z 1
1
(logx)j x2 dx+ 1
j!
Z 1
1
(j 2 logx) logj 1x
x3 {x}dx.
Substitutingx=eu, the first integral becomes (j+ 1), and the second isO⇣
j!
2j
⌘ , which implies that
( 1)j
j! ⇣(j)(2) 1 =O
✓1 2j
◆ , and so cn= 1 +O 2nn . This establishes all of Theorem 1.
Acknowledgment I am grateful to Greg Martin for his suggestions and encour- agement.
References
[1] K. Alladi and P. Erd˝os. On an additive arithmetic function.Pacific J. Math.71(2):275–294, 1977.
[2] Jean-Marie De Koninck and Aleksandar Ivi´c. The distribution of the average prime divisor of an integer. Arch. Math. (Basel)43(1)(1984), 37–43.
[3] Aleksandar Ivi´c. On thekth prime factor of an integer.Zb. Rad. Prirod.-Mat. Fak. Ser. Mat.
20(1)(1990), 63–73.
[4] Donald E. Knuth and Luis Trabb Pardo. Analysis of a simple factorization algorithm.Theoret.
Comput. Sci.3(3)(1976/77), 321–348.
[5] Hugh L. Montgomery and Robert C. Vaughan. Multiplicative number theory. I. Classical theory, volume 97 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2007.