On Sums of Powers of the p-adic Valuation of n!

Rafael Jakimczuk División Matemática Universidad Nacional de Luján Buenos Aires Argentina

                   jakimczu@mail.unlu.edu.ar

Abstract We study sums where the multiplicities of the primes in the prime factorization of n! appear, and obtain a strong connection between these sums and the Riemann zeta function.

1 Introduction

Consider the prime factorization of a positive integer a,

a = p_{1}^{s_{1}}p_{2}^{s_{2}} ⋯ p_{k}^{s_{k}},

where p_{1}, p_{2}, …, p_{k} are the distinct prime factors of a and s_{1}, s_{2}, …, s_{k} are their multiplicities. We let Ω(a) denote the total number of prime factors [3], that is,

Ω(a) = s_{1} + s_{2} + ⋯ + s_{k}.

Consider the prime factorization of n!. We let E(p) denote the multiplicity of a prime p appearing in this factorization. Consequently, we can write the prime factorization of n! as follows:

n! = ∏_{2≤p≤n} p^{E(p)}.

The following asymptotic formula is well-known: (e.g., [3, 5])

Ω(n!) = ∑_{2≤p≤n} E(p) = n log log n + An + o (\frac{n}{log n}) ,  (1)

where the constant A is

A = M + ∑_{p} \frac{1}{p(p − 1)} ≈ 1.034653,

and M is Mertens’s constant.

Let k ≥ 1 an arbitrary but fixed positive integer. We study the sequences

∑_{2≤p≤n} \frac{1}{E(p)^{k}} ,

and prove a strong connection between these sequences and the Riemann zeta function ζ(s). We also study the sequences

∑_{2≤p≤n} E(p)^{k} (k ≥ 2).

2 Main Results

Theorem 1. Let k ≥ 1 be an arbitrary but fixed positive integer. For any sufficiently large integer n we have

∑_{2≤p≤n} \frac{1}{E(p)^{k}} = C_{k} \frac{n}{log n} + O_{k} (\frac{n}{log^{2} n}) ,  (2)

where

C_{k} = (−1)^{k} + ∑_{j=2}^{k+1}(−1)^{k+j−1}ζ(j).  (3)

Proof. By the prime number theorem, we have

π(x) = ∑_{2≤p≤x} 1 = \frac{x}{log x} + O (\frac{x}{log^{2} x}) .  (4)

Consider the prime factorization of n!. The multiplicity E(p) of the prime p is, by Legendre’s theorem, equal to

E(p) = ∑_{j=1}^{∞} ⌊\frac{n}{p^{j}} ⌋ .

If p satisfies the inequality

\frac{n}{j + 1} < p ≤ \frac{n}{j},

where j is a fixed positive integer, and the inequality

p > \sqrt{n},

then we obtain

E(p) = ∑_{j=1}^{∞} ⌊\frac{n}{p^{j}} ⌋ = ⌊\frac{n}{p}⌋ = j.

Now we have

∑_{p≤n} \frac{1}{E(p)^{k}} = ∑_{p≤\sqrt{n}} \frac{1}{E(p)^{k}} + ∑_{\sqrt{n}<p≤n} \frac{1}{E(p)^{k}} ,  (5)

where

∑_{p≤\sqrt{n}} \frac{1}{E(p)^{k}} = O (π (\sqrt{n})) = O (\frac{\sqrt{n}}{log n}) = O (\frac{n}{log^{2} n}) .  (6)

Let J = ⌊\sqrt{n}⌋. If p > \sqrt{n} then E(p) = ⌊\frac{n}{p}⌋. Hence, we have

∑_{\sqrt{n}<p≤n} \frac{1}{E(p)^{k}} = ∑_{j=1}^{J−1} \frac{1}{j^{k}} ∑_{\frac{n}{j+1} <p≤ \frac{n}{j}} 1 = ∑_{j=1}^{J−1} \frac{1}{j^{k}} (π (\frac{n}{j}) − π (\frac{n}{j + 1})) .  (7)

Note that, by Eq. (4), we have

π (\frac{n}{j}) = \frac{n}{j log \frac{n}{j}} + O (\frac{n}{j log^{2} \frac{n}{j}} ) = \frac{n}{j log n} + O (\frac{log j}{j} \frac{n}{log^{2} n}) + O (\frac{n}{j log^{2} \frac{n}{j}} ) ,  (8)

where we use the formula

\frac{1}{1 − f(n)} = 1 + (\frac{1}{1 − f(n)}) f(n).

In the same way, we find that

π (\frac{n}{j + 1}) = \frac{n}{(j + 1) log n} + O (\frac{log(j + 1)}{(j + 1)} \frac{n}{log^{2} n}) + O (\frac{n}{(j + 1) log^{2} \frac{n}{(j+1)}} )  (9)

Eqs. (8) and (9) give

\frac{1}{j^{k}} (π (\frac{n}{j}) − (π (\frac{n}{j + 1}))) = \frac{1}{j^{k}} (\frac{1}{j} − \frac{1}{j + 1}) \frac{n}{log n} + O (\frac{log j}{j^{k+1}} \frac{n}{log^{2} n})

− O (\frac{log(j + 1)}{j^{k}(j + 1)} \frac{n}{log^{2} n}) + O (\frac{n}{j^{k+1} log^{2} \frac{n}{j}} ) − O (\frac{n}{j^{k}(j + 1) log^{2} \frac{n}{j+1}} ) .  (10)

Note that

∑_{j=1}^{J−1} \frac{1}{j^{k}} (\frac{1}{j} − \frac{1}{j + 1}) \frac{n}{log n} = C_{k} \frac{n}{log n} + O (\frac{n}{log^{2} n}) ,  (11)

where

C_{k} = ∑_{j=1}^{∞} \frac{1}{j^{k}} (\frac{1}{j} − \frac{1}{j + 1}) .  (12)

On the other hand, we have

∑_{j=1}^{J−1} O (\frac{log j}{j^{k+1}} \frac{n}{log^{2} n}) = O (\frac{n}{log^{2} n} ∑_{j=1}^{J−1} \frac{log j}{j^{k+1}} ) = O (\frac{n}{log^{2} n}) ,  (13)

Analogously, we find that

∑_{j=1}^{J−1} O (\frac{log(j + 1)}{j^{k}(j + 1)} \frac{n}{log^{2} n}) = O (\frac{n}{log^{2} n}) .  (14)

Besides, we have

∑_{j=1}^{J−1} O (\frac{n}{j^{k+1} log^{2} \frac{n}{j}} ) = O (∑_{j=1}^{J−1} \frac{n}{j^{k+1} log^{2} \frac{n}{j}} ) = O (\frac{n}{log^{2} n}) ,  (15)

since

∑_{j=1}^{J−1} \frac{n}{j^{k+1} log^{2} \frac{n}{j}} = O (∑_{j=1}^{J−1} \frac{n}{j^{k+1} log^{2} \frac{n}{J}} ) = O (\frac{n}{log^{2} n}) .

In the same manner, we obtain

∑_{j=1}^{J−1} O (\frac{n}{j^{k}(j + 1) log^{2} \frac{n}{j+1}} ) = O (\frac{n}{log^{2} n}) .  (16)

Substituting equations (11), (13), (14), (15) and (16) into (10) (see (7)) we find that

∑_{\sqrt{n}<p≤n} \frac{1}{E(p)^{k}} = C_{k} \frac{n}{log n} + O (\frac{n}{log^{2} n}) .  (17)

Equations (5), (6), and (17) give (2).

We have the equation

\frac{1}{j^{k}} (\frac{1}{j} − \frac{1}{(j + 1)}) = \frac{1}{j^{k+1}} − (\frac{1}{j^{k−1}} (\frac{1}{j} − \frac{1}{j + 1})) .

Therefore, by (12)

C_{k} = ζ(k + 1) − C_{k−1}.  (18)

On the other hand, we have

C_{1} = ∑_{j=1}^{∞} (\frac{1}{j^{2}} − \frac{1}{j(j + 1)}) = ζ(2) − 1,  (19)

since

∑_{j=1}^{∞} \frac{1}{j(j + 1)} = ∑_{j=1}^{∞} (\frac{1}{j} − \frac{1}{j + 1}) = 1.

Equations (18) and (19) give (3).

Example 2. If k = 1 then Theorem 1 is

∑_{2≤p≤n} \frac{1}{E(p)} = (\frac{π^{2}}{6} − 1) \frac{n}{log n} + O (\frac{n}{log^{2} n}) .

Theorem 3. The sequence of positive numbers C_{k} is strictly decreasing and

C_{k} = \frac{1}{2} + O (2^{−k}) .

Besides, we have the following limit

lim_{k→∞} C_{k} = \frac{1}{2}.

Proof. Clearly the sequence of positive numbers C_{k} is strictly decreasing (see Eq. (12)). Therefore the limit of this sequence exists and is either positive or zero. Eq. (18) then implies that the limit is 1/2, since lim_{k→∞} ζ(k) = 1.

To obtain a more precise result we need the following formula [4]:

∑_{j=2}^{∞}(−1)^{j} (ζ(j) − 1) = \frac{1}{2}.

Therefore, we have, for k ≥ 1, that

C_{k} = (−1)^{k} (1 − ∑_{j=2}^{k+1}(−1)^{j}ζ(j)) = (−1)^{k} (1 − ∑_{j=2}^{k+1}(−1)^{j} − ∑_{j=2}^{k+1}(−1)^{j} (ζ(j) − 1))

= (−1)^{k} (1 − \frac{1}{2} (1 − (−1)^{k}) − ∑_{j=2}^{∞}(−1)^{j} (ζ(j) − 1) + ∑_{j>k+1}(−1)^{j} (ζ(j) − 1))

= (−1)^{k} (\frac{1}{2} − \frac{1}{2} (1 − (−1)^{k}) + ∑_{j>k+1}(−1)^{j} (ζ(j) − 1)) = \frac{1}{2} + O (2^{−k})

Theorem 4. Let k ≥ 2 a fixed but arbitrary positive integer. For every sufficiently large integer we have

∑_{p≤n} E(p)^{k} = n^{k} ∑_{p} \frac{1}{(p − 1)^{k}} + O_{k} (n^{k−1} log n) .

Proof. The following equation is well-known [1]. If p ≤ n then

E(p) = \frac{n}{p − 1} + O (\frac{log n}{log p}) .

Therefore, we have

∑_{p≤n} E(p)^{k} = ∑_{p≤n} (\frac{n}{p − 1} + O (\frac{log n}{log p}))^{k} = n^{k} ∑_{p≤n} \frac{1}{(p − 1)^{k}} (1 + O (\frac{p log n}{n log p}))^{k}

= n^{k} ∑_{p} \frac{1}{(p − 1)^{k}} + O (n^{k} ∑_{p>n} \frac{1}{p^{k}} ) + O (n^{k−1} log n ∑_{p≤n} \frac{1}{p^{k−1} log p})

To complete the proof we need the bounds

∑_{p>n} \frac{1}{p^{k}} ≪_{k} \frac{1}{n^{k−1} log n}

and

∑_{p≤n} \frac{1}{p^{k−1} log p} ≪_{k} 1,

since k ≥ 2.

Remark 5.

1. Theorem 4 is a natural generalization of Eq. (1), since we have the well-known formula

∑_{p≤n} \frac{1}{p − 1} = log log n + A + O (\frac{1}{log n}) (n ≥ 2).

2. In the case k = 2, the constant in Theorem 4 is closely related to the constant A in Eq. (1), since

∑_{p} \frac{1}{(p − 1)^{2}} = ∑_{n=2}^{∞} \frac{J_{2}(n) − φ(n)}{n} log ζ(n)

= ∑_{n=2}^{∞} \frac{J_{2}(n)}{n} log ζ(n) + γ − A ≈ 1, 375064994748635 …

where J_{2}(n) = n^{2} ∏_{p|n}(1 − p^{−2}) is the second Jordan arithmetic function [2].

3 Acknowledgments

The author would like to thank the anonymous referee for his/her valuable comments and suggestions for improving the original version of this article. The better error terms in Theorem 1 and Theorem 3 are due to the referee. Theorem 4, together with Remark 5, are also results of the referee. The author is also very grateful to Universidad Nacional de Luján.

References

[1] O. Bordellès, Arithmetic Tales, Springer, 2012.

[2] J. W. L. Glaisher, On the sums of the inverse powers of the prime numbers, Quart. J. Pure Appl. Math. 25 (1891), 347–362.

[3] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford, 1960.

[4] H. M. Srivastava, Sums of certain series of the Riemann zeta function, J. Math. Anal. Appl. 134 (1988), 129–140.

[5] G. Tenenbaum, Introduction à la Théorie Analytique et Probabiliste des Nombres, Belin, 2008.

2000 Mathematics Subject Classification: Primary 11A99; Secondary 11B99. Keywords: factorial, prime factorization, Riemann zeta function.

(Concerned with sequence \underline{A0xxxxx}.)

Received February 10 2017; revised version received April 9 2017. Published in Journal of Integer Sequences, May 1 2017.

Return to Journal of Integer Sequences home page.