On Some Products Taken over Prime Numbers

Abdelmalek Bedhouche Laboratoire des Mathématiques Appliquées Faculté des Sciences Exactes et Informatique Université de Jijel 18000 Jijel Algeria

          abdelmalek.bedhouche@univ-bejaia.dz

Bakir Farhi Laboratoire de Mathématiques Appliquées Faculté des Sciences Exactes Université de Bejaia 06000 Bejaia Algeria

              bakir.farhi@univ-bejaia.dz

Abstract

We study expressions of the type ∏_{p} p^{⌊ \frac{x}{f(p)} ⌋}, where x is a nonnegative real number, f is an arithmetic function satisfying some conditions, and the product is over the primes p. We begin by proving that such expressions can be expressed by using the lcm function, without reference to prime numbers; we illustrate this result with several examples. The rest of the paper is devoted to studying two particular cases related to f(m) = m and f(m) = m − 1. In both cases, we find arithmetic properties and analytic estimates for the underlying expressions.

1 Introduction and notation

Throughout this paper, we let ℕ^{∗} denote the set of positive integers and 𝒫 the set of prime numbers. The letter p is reserved for primes. For a given prime number p, we let ϑ_{p} denote the usual p-adic valuation. For x ∈ ℝ, we let ⌊x⌋ denote the integer part of x. For N, b ∈ ℕ, with b ≥ 2, the expansion of N in base b is denoted by N = \overline{a_{k}a_{k−1} ⋯ a_{1}a_{0}}_{(b)}, meaning that N = a_{0} + ba_{1} + b^{2}a_{2} + ⋯ + b^{k}a_{k} (with k ∈ ℕ, a_{0}, a_{1}, …, a_{k} ∈ {0, 1, …, b − 1} and a_{k} ≠ 0). In such a context, we let S_{b}(N) denote the sum of base-b digits of N; that is, S_{b}(N) := a_{0} + a_{1} + ⋯ + a_{k}. Further, we let τ, π, and θ, respectively, denote the divisorcounting function, the prime-counting function, and the Chebyshev theta function, defined as follows:

τ(n) := ∑_{d|n} 1 , π(x) := ∑_{p≤x} 1 , and θ(x) := ∑_{p≤x} log p (∀n ∈ ℕ^{∗}, ∀x ∈ ℝ^{+}).

It is known that for n ≥ 3, we have τ(n) = n^{O(1/ log log n)} (see e.g., [5, Proposition 7.12, page 101]). So, a fortiori,

τ(n) = O(n^{1/3}).  (1)

On the other hand, the prime number theorem states that π(x) ∼_{+∞} \frac{x}{log x}. Other equivalent statements are θ(x) ∼_{+∞} x and log lcm(1, 2, …, n) ∼_{+∞} n (see e.g., [5, Chapter 4]). The weaker estimates π(x) = O(x/log x), θ(x) = O(x), and log lcm(1, 2, …, n) = O(n) are called Chebyshev’s estimates.

In number theory, it is common that a prime factorization of some special numbers N produces, as exponents of each prime p, expressions of the form ⌊\frac{u_{N}}{f(p)}⌋ or a sum of such expressions. The most famous example is perhaps the Legendre formula, stating that for natural numbers n, we have

n! = ∏_{p} p^{⌊ \frac{n}{p} ⌋+⌊ \frac{n}{p^{2}} ⌋+⌊ \frac{n}{p^{3}} ⌋+···},  (2)

which may be also reformulate in terms of base expansions as follows:

n! = ∏_{p} p^{\frac{n−Sp(n)}{p−1}} .  (3)

See e.g., [6, pages 76-77]. Another famous example is the formula of the least common multiple of the first consecutive positive integers:

lcm(1, 2, …, n) = ∏_{p} p^{⌊ \frac{log n}{log p} ⌋}  (∀n ∈ ℕ).  (4)

Among other examples which are less known, we can cite the following

lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{k} ≤ n\} = ∏_{p} p^{⌊ \frac{n}{p} ⌋},  (5)

which is pointed out in the book of Cahen and Chabert [2, page 246] and also by Farhi [3] in the context of the integer-valued polynomials. Basing on the remark that in Formulas (2), (4), and (5), the right-hand side (which is a product taken over the primes) is interpreted without reference to prime numbers, we may naturally ask if an expression of a general type ∏_{p} p^{⌊ \frac{x}{f_{1}(p)} ⌋+⌊ \frac{x}{f_{2}(p)} ⌋+···}, where x ∈ ℝ^{+} and (f_{i})_{i} is a sequence of positive functions satisfying some regularity conditions, possesses the same property; that is, it has an interpretation without reference to the primes. In this paper, we study only the case of the products

π_{f}(x) := ∏_{p} p^{⌊ \frac{x}{f(p)} ⌋},

for which we affirmatively answer the previous question under some hypotheses on f. After giving several applications of our result, we focus our study on the two particular cases f(p) = p and f(p) = p − 1. Because in both cases, there is no loss of generality to take x an integer, we are led define

ρ_{n} := ∏_{p} p^{⌊ \frac{n}{p} ⌋} and σ_{n} := ∏_{p} p^{⌊ \frac{n}{p−1} ⌋}

for n ∈ ℕ. These are, respectively, the sequences \underline{A048803} and \underline{A091137} of [7].

We begin with the arithmetic study of ρ_{n} and σ_{n} by establishing several arithmetic properties concerning them; in particular, we obtain a nontrivial divisor and a nontrivial multiple for σ_{n}. Moreover, we determine the p-adic valuations of the integers \frac{σ_{n}}{n!} when the prime p is large enough compared to \sqrt{n}; we discover that the prime numbers of the form ⌊\frac{n}{k} + 1⌋ (k ∈ ℕ^{∗}, k < \sqrt{n + 1} + 1) play a vital role in the arithmetic nature of the σ_{n}’s. In another direction, we find asymptotic estimates for log ρ_{n} and log σ_{n}.

2 An expression of π_{f} using the least common multiple

Our result of expressing π_{f} in terms of the lcm’s without reference to prime numbers is the following:

Theorem 1. Let f : ℕ^{∗} → ℝ_{+} be an arithmetic function such that f(ℕ^{∗} \ {1}) ⊂ ℝ_{+}^{∗} (i.e., f does not vanish except at 1 eventually). Consider the set ℕ^{∗} \ {1} equipped with the partial order relation “ |” of divisibility (a | b ⇔ a divides b) and the set ℝ_{+}^{∗} equipped with the usual total order relation “ ≤”, and suppose that the map

\begin{matrix}f̃: ℕ^{∗} \ \{1\} & ⟶ & ℝ_{+}^{∗} \\ n & ⟼ & \frac{f(n)}{log n} \end{matrix}

is nondecreasing with respect to these two orders. Then for x ∈ ℝ^{+} we have

∏_{p} p^{⌊ \frac{x}{f(p)} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, f(i_{1}) + f(i_{2}) + ⋯ + f(i_{k}) ≤ x\}.

In order to present a clean proof of Theorem 1, we use the following lemma: Lemma 2. Let f : ℕ^{∗} → ℝ_{+} as in Theorem 1. Then, for prime numbers p and positive integers a, we have

ϑ_{p}(a) ≤ \frac{f(a)}{f(p)}.

Proof. Let p be a prime number and a be a positive integer. Since the inequality of the lemma is trivial when ϑ_{p}(a) = 0, we may suppose that ϑ_{p}(a) ≥ 1; that is p | a. So according to our assumptions on f, we have that \frac{f(p)}{log p} ≤ \frac{f(a)}{log a}, which translates into \frac{log a}{log p} ≤ \frac{f(a)}{f(p)}. Hence, ϑ_{p}(a) ≤ \frac{log a}{log p} ≤ \frac{f(a)}{f(p)}, as required.

Proof of Theorem 1. Let x ∈ ℝ_{+} be fixed. For a given prime number p, the p-adic valuation of the left-hand side of the identity of Theorem 1 is equal to ⌊\frac{x}{f(p)}⌋, while the p-adic valuation of the right-hand side of the same identity is equal to ℓ_{p} := max{ϑ_{p}(i_{1}i_{2} … i_{k}); k ∈ ℕ, i_{1}, …, i_{k} ∈ ℕ^{∗}, f(i_{1}) + ⋯ + f(i_{k}) ≤ x\}. So, we have to show that ℓ_{p} = ⌊\frac{x}{f(p)}⌋ for primes p. To do so, we prove the two inequalities ℓ_{p} ≥ ⌊\frac{x}{f(p)}⌋ and ℓ_{p} ≤ ⌊\frac{x}{f(p)}⌋.

First, for a given prime number p, let us show that ℓ_{p} ≥ ⌊\frac{x}{f(p)}⌋. By considering the particular natural number k = ⌊\frac{x}{f(p)}⌋ and the particular positive integers i_{1} = i_{2} = ⋯ = i_{k} = p, we get f(i_{1}) + f(i_{2}) + ⋯ + f(i_{k}) = kf(p) = ⌊\frac{x}{f(p)}⌋f(p) ≤ x. Thus, according to the definition of ℓ_{p} we have ℓ_{p} ≥ ϑ_{p} (i_{1}i_{2} ⋯ i_{k}) = ϑ_{p}(p^{k}) = k = ⌊\frac{x}{f(p)}⌋, as required.

Now, for a given prime number p, let us show that ℓ_{p} ≤ ⌊\frac{x}{f(p)}⌋. For k ∈ ℕ and i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, with f(i_{1}) + f(i_{2}) + ⋯ + f(i_{k}) ≤ x, we have

ϑ_{p} (i_{1}i_{2} ⋯ i_{k}) = ϑ_{p}(i_{1}) + ϑ_{p}(i_{2}) + ⋯ + ϑ_{p}(i_{k})

≤ \frac{f(i_{1})}{f(p)} + \frac{f(i_{2})}{f(p)} + ⋯ + \frac{f(i_{k})}{f(p)} (according to Lemma 2)

= \frac{f(i_{1}) + f(i_{2}) + ⋯ + f(i_{k})}{f(p)}

≤ \frac{x}{f(p)};

but since ϑ_{p}(i_{1}i_{2} ⋯ i_{k}) ∈ ℕ, it follows that: ϑ_{p} (i_{1}i_{2} ⋯ i_{k}) ≤ ⌊\frac{x}{f(p)}⌋. The definition of ℓ_{p} concludes that ℓ_{p} ≤ ⌊\frac{x}{f(p)}⌋, as required. This completes the proof.

Remark 3. Let us put ourselves in the situation of Theorem 1.

1. If the map f̃ is nondecreasing in the usual sense; i.e., with respect to the usual orders of the two sets ℕ^{∗} \{1} and ℝ_{+}^{∗}, then it remains nondecreasing in the sense imposed by Theorem 1. This immediately follows from the implication: a | b ⇒ a ≤ b, ∀a, b ∈ ℕ^{∗}.

2. More generally than the previous item, if the restriction of the map f̃ on ℕ^{∗} \ {1, 2} is nondecreasing in the usual sense and f̃(2) ≤ f̃(4), then f̃ is nondecreasing in the sense imposed by Theorem 1.

Now, from Theorem 1, we derive the following corollary in which the condition imposed on f is made simpler.

Corollary 4. Let f : ℕ^{∗} → ℝ_{+} be an arithmetic function satisfying f(ℕ^{∗} \ {1}) ⊂ ℝ_{+}^{∗}. Suppose that the map

\begin{matrix}ℕ^{∗} \ \{1\} & ⟶ & ℝ_{+}^{∗} \\ n & ⟼ & \frac{f(n)}{n} \end{matrix}

is nondecreasing in the usual sense (i.e., with respect to the usual order of ℝ). Then for x ∈ ℝ_{+} we have

∏_{p} p^{⌊ \frac{x}{f(p)} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, f(i_{1}) + f(i_{2}) + ⋯ + f(i_{k}) ≤ x\}.

Proof. We use Theorem 1 together with Item 2 of Remark 3. We remark that f̃(defined as in Theorem 1) is the product of the two functions: n ↦ \frac{f(n)}{n} (assumed to be nondecreasing in the usual sense on ℕ^{∗} \ \{1\}) and n ↦ \frac{n}{log n}, which is nondecreasing on ℕ^{∗} \ \{1, 2\} = \{3, 4, 5, … \}. So, f̃ is nondecreasing on ℕ^{∗} \ {1, 2} in the usual sense. In addition, we have

f̃(2) = \frac{f(2)}{log 2} = \frac{f(2)}{2} · \frac{2}{log 2} = \frac{f(2)}{2} · \frac{4}{log 4} ≤ \frac{f(4)}{4} · \frac{4}{log 4}

(since n ↦ \frac{f(n)}{n} is assumed to be nondecreasing in the usual sense on ℕ^{∗} \ \{1\}). That is, we have f̃(2) ≤ \frac{f(4)}{log 4} = f̃(4). The conclusion follows from Item 2 of Remark 3 and Theorem 1.

2.1 Some applications

1. By applying Theorem 1 for f(m) = log m, we obtain that for x ∈ ℝ_{+}, we have

∏_{p} p^{⌊ \frac{x}{log p} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, log i_{1} + log i_{2} + ⋯ + log i_{k} ≤ x\}
= lcm{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1}i_{2} ⋯ i_{k} ≤ e^{x}}
= lcm (1, 2, …, ⌊e^{x}⌋) .

In particular, by taking x = log n (n ∈ ℕ^{∗}), we obtain the following well-known formula:

∏_{p} p^{⌊ \frac{log n}{log p} ⌋} = lcm (1, 2, …, n) .

2. By applying Corollary 4 for the function f(m) = m, we obtain in particular that for all n ∈ ℕ, we have

∏_{p} p^{⌊ \frac{n}{p} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{k} ≤ n\}, (6)

which is already pointed out by Cahen and Chabert [2] and by Farhi [3].

3. (Generalization of (6)). Let α ≥ 1. By applying Corollary 4 for the function f(m) = m^{α}, we obtain in particular that for all n ∈ ℕ, we have

∏_{p} p^{⌊ \frac{n}{p^{α}} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1}^{α} + i_{2}^{α} + ⋯ + i_{k}^{α} ≤ n\}.

4. For all n, k ∈ ℕ, with n ≥ k, let us define, as in [3],

q_{n,k} := lcm{i_{1}i_{2} ⋯ i_{k} ; i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{k} ≤ n}.

These numbers were studied by Farhi [3] in a context related to integer-valued polynomials. By applying Corollary 4 for the function f(m) = m − 1, we obtain that for all n ∈ ℕ, we have

∏_{p} p^{⌊ \frac{n}{p−1} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗},
(i_{1} − 1) + (i_{2} − 1) + ⋯ + (i_{k} − 1) ≤ n}

= lcm{i_{1}i_{2} ⋯ i_{k} ; k ∈ ℕ, i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{k} ≤ n + k}

= lcm{q_{n+k,k} ; k ∈ ℕ},  (7)

which remarkably represents the least common multiple of the n^{th} diagonal of the arithmetic triangle of the q_{i,j}’s, beginning as follows (see [3])

1

1 1
1 2 1
1 6 2 1
1 12 12 2 1
1 60 12 12 2 1
1 60 360 24 12 2 1
1 420 360 360 24 12 2 1

Table 1: The triangle of the q_{n,k}’s for 0 ≤ k ≤ n ≤ 7.

For a given n ∈ ℕ, let D_{n} = (d_{n,k})_{k∈ℕ} denote the sequence of the n^{th} diagonal of the above triangle, that is

d_{n,k} := q_{n+k,k} = lcm{i_{1}i_{2} ⋯ i_{k} ; i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{k} ≤ n + k}. (8)

In order to simplify Formula (7), we show that the sequences D_{n} (n ∈ ℕ) are all nondecreasing in the divisibility sense and eventually constant. More precisely, we have the following proposition:

Proposition 5. For all n, k ∈ ℕ, we have

d_{n,k} divides d_{n,k+1}.

If in addition k ≥ n, then we have

d_{n,k} = d_{n,n}.

Proof. Let n, k ∈ ℕ be fixed. If i_{1}i_{2} ⋯ i_{k} is a member of the list of lcm defining d_{n,k}, then 1 · i_{1}i_{2} ⋯ i_{k} satisfies 1 + (i_{1} + i_{2} + ⋯ + i_{k}) ≤ 1 + (n + k) = n + (k + 1), so the same element is a member of the list of the lcm defining d_{n,k+1}. Hence, d_{n,k} divides d_{n,k+1}, as required.

Now, let us prove the second part of the proposition. So, suppose that k ≥ n and let us prove that d_{n,k} = d_{n,n}. It follows from an immediate induction leaning on the result of the first part of the proposition (proved above) that d_{n,n} | d_{n,k}. So, it remains to prove that d_{n,k} | d_{n,n}. Let i_{1}, i_{2}, …, i_{k} ∈ ℕ^{∗} such that i_{1} + i_{2} + ⋯ + i_{k} ≤ n + k. Let ℓ ∈ ℕ denote the number of indices i_{r} (1 ≤ r ≤ k) which are equal to 1; so we have exactly (k − ℓ) indices i_{r} which are ≥ 2. Thus, we have

i_{1} + i_{2} + ⋯ + i_{k} ≥ ℓ + 2(k − ℓ) = 2k − ℓ.

But since i_{1} +i_{2} +⋯+i_{k} ≤ n+k, we derive that 2k −ℓ ≤ n+k, which gives ℓ ≥ k −n. This proves that we have at least (k − n) indices i_{r} which are equal to 1. By assuming, without loss of generality, that those indices are i_{n+1}, i_{n+2}, …, i_{k} (i.e., i_{n+1} = i_{n+2} = ⋯ = i_{k} = 1), we get

i_{1}i_{2} ⋯ i_{n} = i_{1}i_{2} ⋯ i_{k}

and

i_{1} + i_{2} + ⋯ + i_{n} = (i_{1} + i_{2} + ⋯ + i_{k}) − (k − n) ≤ (n + k) − (k − n) = 2n.

This shows that each product i_{1}i_{2} ⋯ i_{k} occurring in the definition of d_{n,k} reduces (by permuting the i_{r}’s and eliminate those of them which are equal to 1) to a product j_{1}j_{2} ⋯ j_{n} which occurs in the definition of d_{n,n}. Consequently d_{n,k} | d_{n,n}, as required. This completes the proof of the proposition.

Using Proposition 5, for n ∈ ℕ we have

lcm{q_{n+k,k} ; k ∈ ℕ} = lcm{d_{n,k} ; k ∈ ℕ}
= d_{n,n}
= lcm{i_{1}i_{2} ⋯ i_{n} ; i_{1}, i_{2}, …, i_{n} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{n} ≤ 2n}.

This proves the following interesting corollary, simplifying Formula (7):

Corollary 6. For n ∈ ℕ, we have

∏_{p} p^{⌊ \frac{n}{p−1} ⌋} = lcm\{i_{1}i_{2} ⋯ i_{n} ; i_{1}, i_{2}, …, i_{n} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{n} ≤ 2n\}.  □

3 Arithmetic results on the numbers ρ_{n} and σ_{n}

A certain number of arithmetic properties concerning the numbers ρ_{n} and σ_{n} are either immediate or quite easy to prove. We have gathered them in the following proposition:

Proposition 7. For natural numbers n, we have

(i) ρ_{n} | ρ_{n+1}, σ_{n} | σ_{n+1}, and ρ_{n} | σ_{n};

(ii) ρ_{n} | n!;

(iii) n! | σ_{n} and σ_{n} | (2n)!;

(iv) σ_{2n+1} = 2σ_{2n}.

Proof. Let n ∈ ℕ be fixed. The properties of Item (i) are trivial.

Item (ii) follows because for primes p, the term ⌊n/p⌋ is the first term of ⌊n/p⌋+⌊n/p^{2}⌋+ ⋯, which is the exact exponent of p in n!, which is also \frac{n−S_{p}(n)}{p−1} ≤ \frac{n}{p−1}; so in particular ≤ ⌊\frac{n}{p−1}⌋, giving at the same time the first part of (iii).

Let us prove the second part of (iii). To do so, we use Corollary 6. For i_{1}, i_{2}, …, i_{n} ∈ ℕ^{∗} satisfying i_{1}+i_{2}+⋯+i_{n} ≤ 2n, we have that i_{1}i_{2} ⋯ i_{n} | i_{1}!i_{2}! ⋯ i_{n}! | (i_{1}+i_{2}+⋯+i_{n})! | (2n)!. Thus, lcm{i_{1}i_{2} ⋯ i_{n} ; i_{1}, i_{2}, …, i_{n} ∈ ℕ^{∗}, i_{1} + i_{2} + ⋯ + i_{n} ≤ 2n} | (2n)!; that is, according to Corollary 6, σ_{n} | (2n)!.

Finally, Item (iv) follows from the fact that ϑ_{p}(σ_{2n+1}) = ϑ_{p}(2σ_{2n}) for primes p (distinguish the two cases “p odd” and “p = 2”). This completes the proof of the proposition.

In the following proposition, we shall improve Item (iii) of Proposition 7.

Proposition 8. For natural numbers n, we have

(n + 1)! | σ_{n} and σ_{n} | n! lcm(1, 2, …, n, n + 1).

Proof. Let n ∈ ℕ be fixed. We have to show that for primes p, one has

ϑ_{p} ((n + 1)!) ≤ ϑ_{p} (σ_{n}) ≤ ϑ_{p} (n! lcm(1, 2, …, n, n + 1)) .  (9)

Let p be a fixed prime number and let us prove (9). By setting e the greatest nonnegative integer satisfying p^{e} ≤ n + 1, we obtain

ϑ_{p}(n!) = ∑_{i=1}^{e}⌊\frac{n}{p^{i}} ⌋

and

ϑ_{p}((n + 1)!) = ∑_{i=1}^{e}⌊\frac{n + 1}{p^{i}}⌋

(according to the Legendre formula),

ϑ_{p}(σ_{n}) = ⌊\frac{n}{p − 1}⌋

(by definition of σ_{n}), and

ϑ_{p}(lcm(1, 2, …, n + 1)) = e.

So (9) reduces to

∑_{i=1}^{e} ⌊\frac{n + 1}{p^{i}}⌋ ≤ ⌊\frac{n}{p − 1}⌋ ≤ ∑_{i=1}^{e} ⌊\frac{n}{p^{i}} ⌋ + e.  (10)

On the one hand, we have

∑_{i=1}^{e} ⌊\frac{n + 1}{p^{i}}⌋ ≤ ∑_{i=1}^{e} \frac{n + 1}{p^{i}} = \frac{n + 1}{p − 1} (1 − \frac{1}{p^{e}} ) ≤ \frac{n}{p − 1}

(since p^{e} ≤ n + 1). But since ∑_{i=1}^{e}⌊\frac{n+1}{p^{i}}⌋ is an integer, we derive the inequality

∑_{i=1}^{e} ⌊\frac{n + 1}{p^{i}}⌋ ≤ ⌊\frac{n}{p − 1}⌋ ,

confirming the left inequality in (10). On the other hand, by using the refined inequality ⌊\frac{a}{b}⌋ ≥ \frac{a+1}{b} − 1, which holds for all positive integers a, b, we have

⌊\frac{n}{p − 1}⌋ − ∑_{i=1}^{e} ⌊\frac{n}{p^{i}} ⌋ ≤ \frac{n}{p − 1} − ∑_{i=1}^{e} (\frac{n + 1}{p^{i}} − 1)

= \frac{n}{p − 1} − \frac{n + 1}{p − 1} (1 − \frac{1}{p^{e}} ) + e

= \frac{1}{p − 1} (\frac{n + 1}{p^{e}} − 1) + e.

But from the definition of e, we have p^{e+1} > n + 1; that is, \frac{n+1}{p^{e}} < p. By inserting this into the last estimate, we get

⌊\frac{n}{p − 1}⌋ − ∑_{i=1}^{e} ⌊\frac{n}{p^{i}} ⌋ < e + 1.

Next, since ⌊\frac{n}{p−1}⌋ − ∑_{i=1}^{e}⌊\frac{n}{p^{i}} ⌋ ∈ ℤ, we conclude

⌊\frac{n}{p − 1}⌋ − ∑_{i=1}^{e} ⌊\frac{n}{p^{i}} ⌋ ≤ e,

confirming the right inequality of (10). This completes this proof.

From Proposition 8, we derive an asymptotic estimate for the number log σ_{n} when n tends to infinity.

Corollary 9. We have

log σ_{n} ∼_{+∞} n log n.

Proof. According to Proposition 8, for n ∈ ℕ^{∗} we have

log (n + 1)! ≤ log σ_{n} ≤ log (n!) + log lcm(1, 2, …, n, n + 1).

Then the asymptotic estimate of the corollary follows from the facts

log (n + 1)! ∼_{+∞} log(n!) ∼_{+∞} n log n

according to Stirling’s formula, and

log lcm(1, 2, …, n, n + 1) ∼_{+∞} n

according to the prime number theorem.

Note that the asymptotic estimate of the above corollary will be specified in Section 4. We now turn to establish a result evaluating the p-adic valuations of the positive integers

\frac{σ_{n}}{n!} (n ∈ ℕ^{∗}) for sufficiently large prime numbers. We discover as a remarkable phenomenon that primes of a special type play a vital role. We have the following theorem:

Theorem 10. Let n be a positive integer and p be a prime number such that

\sqrt{n + 1} < p ≤ n + 1.

Then we have

ϑ_{p} (\frac{σ_{n}}{n!} ) = ⌊\frac{S_{p}(n)}{p − 1}⌋ ∈ \{0, 1\}.

Furthermore, the equality ϑ_{p}(\frac{σ_{n}}{n!} ) = 1 holds if and only if S_{p}(n) ≥ p − 1, which holds if and only if p has the form

p = ⌊\frac{n}{k} + 1⌋ ,

with k ∈ ℕ^{∗} and k < \sqrt{n + 1} + 1.

Proof. By the definition of σ_{n} and the Legendre formula (3), we have that

ϑ_{p} (\frac{σ_{n}}{n!} ) = ϑ_{p} (σ_{n}) − ϑ_{p} (n!)

= ⌊\frac{n}{p − 1}⌋ − \frac{n − S_{p}(n)}{p − 1}

= ⌊\frac{n}{p − 1} − \frac{n − S_{p}(n)}{p − 1}⌋ (since \frac{n − S_{p}(n)}{p − 1} = ϑ_{p}(n!) ∈ ℤ)

= ⌊\frac{S_{p}(n)}{p − 1}⌋ .  (11)

Next, let us prove that ⌊\frac{S_{p}(n)}{p−1}⌋ ∈ \{0, 1\}. The hypothesis on p insures that n < p^{2} − 1, which implies that the representation of the positive integer n in base p has the form n = \overline{a_{1}a_{0}}_{(p)}, with a_{0}, a_{1} ∈ \{0, 1, …, p − 1\} and (a_{0}, a_{1}) ≠ (p − 1, p − 1). Consequently, we have

S_{p}(n) = a_{0} +a_{1} < 2(p−1), implying that \frac{S_{p}(n)}{p−1} < 2; hence ⌊\frac{S_{p}(n)}{p−1}⌋ ∈ \{0, 1\}, as required. This achieves the proof of the first part of the theorem, which immediately gives the equivalence between ϑ_{p}(\frac{σ_{n}}{n!} ) = 1 and S_{p}(n) ≥ p − 1. Now, let us prove the last part of the theorem.

Suppose that S_{p}(n) ≥ p − 1. As seen above, the representation of n in base p has the form n = \overline{a_{1}a_{0}}_{(p)} = a_{0} + pa_{1}, where a_{0}, a_{1} ∈ \{0, 1, …, p − 1\} and (a_{0}, a_{1}) ≠ (p − 1, p − 1). We will show that k = a_{1} + 1 is suitable for the required form of p. By supposition, we have a_{0} + a_{1} ≥ p − 1, implying that

p − 1 ≤ \frac{a_{0} + a_{1}p}{a_{1} + 1} < p,

which is equivalent to

⌊\frac{n}{a_{1} + 1}⌋ = p − 1.

Thus,

p = ⌊\frac{n}{a_{1} + 1} + 1⌋ .

Furthermore, we have a_{1} = ⌊\frac{n}{p}⌋ ≤ \frac{n}{p} < \sqrt{n + 1} (since p > \sqrt{n + 1} > \frac{n}{\sqrt{n+1}}). Thus, k = a_{1} + 1 satisfies the required properties; i.e., p = ⌊\frac{n}{k} + 1⌋ and k < \sqrt{n + 1} + 1.

Conversely, suppose that there exists k ∈ ℕ^{∗}, with k < \sqrt{n + 1}+1, such that p = ⌊\frac{n}{k} +1⌋, and let us show that S_{p}(n) ≥ p − 1. Setting a_{0} := n − (k − 1)p and a_{1} := k − 1, we first show that the representation of n in base p is n = \overline{a_{1}a_{0}}_{(p)}. Since it is immediate that n = a_{0} + pa_{1}, it just remains to prove that a_{0}, a_{1} ∈ \{0, 1, …, p − 1\}. Since k < \sqrt{n + 1} + 1 < p + 1 then k − 1 < p; that is a_{1} ∈ \{0, 1, …, p − 1\}. Next, since p = ⌊\frac{n}{k} + 1⌋ then

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

implying that

p − k ≤ n − (k − 1)p < p.

Hence

p − k ≤ a_{0} < p.

But p − k = (p − 1) − a_{1} ≥ 0; thus a_{0} ∈ {0, 1, …, p − 1}. We have confirmed that the representation of n in base p is n = \overline{a_{1}a_{0}}_{(p)}. Consequently, we have

S_{p}(n) = a_{0} + a_{1} = n − (k − 1)(p − 1).

Then, since n ≥ k(p − 1) (because \frac{n}{k} + 1 ≥ ⌊\frac{n}{k} + 1⌋ = p), it follows that S_{p}(n) ≥ p − 1, as required. This completes the proof of the theorem.

4 Analytic estimates of the numbers log ρ_{n} and log σ_{n}

Throughout this section, we let c denote the absolute positive constant given by

c := ∑_{p} \frac{log p}{p(p − 1)} = 0.755 ….

Our goal is to find asymptotic estimates for log ρ_{n} and log σ_{n} as n tends to infinity. The obtained main results are the following:

Theorem 11. We have

log ρ_{n} = n log n − (c + 1)n + O (\sqrt{n}) .

Theorem 12. We have

log σ_{n} = n log n − n + 2\sqrt{n} + o(\sqrt{n}).

To establish Theorem 11, we need the auxiliary results below. Theorem 12 is derived from Theorem 10 and a result of Bordellès et al. [1].

Lemma 13. For x ≥ 1, we have

∑_{p>x} \frac{log p}{p(p − 1)} = O (\frac{1}{x}) .

Proof. Since \frac{log p}{p(p−1)} ≤ 2\frac{log p}{p^{2}} (for primes p), then it suffices to show that ∑_{p>x} \frac{log p}{p^{2}} = O(\frac{1}{x}). According to the Abel summation formula (see e.g., [5, Proposition 1.4]), for positive real numbers x, y, with x < y we have

∑_{x<p≤y} \frac{log p}{p^{2}} = ( ∑_{x<p≤y} log p) \frac{1}{y^{2}} − ∫_{{y \atop x}} ( ∑_{x<p≤t} log p) (\frac{1}{t^{2}} )′ dt

= \frac{θ(y) − θ(x)}{y^{2}} + 2 ∫_{x}^{y} \frac{θ(t) − θ(x)}{t^{3}} dt.

Then, by setting y to infinity, it follows (since θ(y) = O(y)) that

∑_{p>x} \frac{log p}{p^{2}} = 2 ∫_{x}^{+∞} \frac{θ(t) − θ(x)}{t^{3}} dt = 2 ∫_{x}^{+∞} \frac{θ(t)}{t^{3}} dt − \frac{θ(x)}{x^{2}}.

Using finally θ(t) = O(t), we get

∑_{p>x} \frac{log p}{p^{2}} = O (∫_{x}^{+∞} \frac{dt}{t^{2}}) + O (\frac{1}{x}) = O (\frac{1}{x}) ,

as required. The proof is complete.

Lemma 13 above is used in the proof of the following proposition:

Proposition 14. For positive integers n we have

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p = c · n + O (\sqrt{n}) .

Proof. Let n be a fixed positive integer. For primes p, let e_{p} denote the greatest nonnegative integer satisfying p^{e_{p}} ≤ n; explicitly e_{p} = ⌊\frac{log n}{log p}⌋. So we have p^{e_{p}+1} > n. On the one hand, we have

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p ≤ ∑_{p} (\frac{n}{p^{2}} + \frac{n}{p^{3}} + ⋯) log p = ∑_{p} \frac{n}{p(p − 1)} log p;

that is

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p ≤ c · n.  (12)

On the other hand, we have (according to the definition of the e_{p}’s)

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p = ∑_{p≤\sqrt{n}} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯ + ⌊\frac{n}{p^{e_{p}}} ⌋) log p

≥ ∑_{p≤\sqrt{n}} ((\frac{n}{p^{2}} − 1) + (\frac{n}{p^{3}} − 1) + ⋯ + (\frac{n}{p^{e_{p}}} − 1)) log p

= n ∑_{p≤\sqrt{n}} (\frac{1}{p^{2}} + \frac{1}{p^{3}} + ⋯ + \frac{1}{p^{e_{p}}} ) log p − ∑_{p≤\sqrt{n}} (e_{p} − 1) log p

= n ∑_{p≤\sqrt{n}} (\frac{1}{p(p − 1)} − \frac{1}{p^{e_{p}}(p − 1)}) log p − ∑_{p≤\sqrt{n}} (e_{p} − 1) log p

= n ∑_{p≤\sqrt{n}} \frac{log p}{p(p − 1)} − n ∑_{p≤\sqrt{n}} \frac{log p}{p^{e_{p}}(p − 1)} − ∑_{p≤\sqrt{n}} (e_{p} − 1) log p

= n (c − ∑_{p>\sqrt{n}} \frac{log p}{p(p − 1)}) − n ∑_{p≤\sqrt{n}} \frac{log p}{p^{e_{p}}(p − 1)} − ∑_{p≤\sqrt{n}} (e_{p} − 1) log p;

that is,

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p ≥ c n − n ∑_{p>\sqrt{n}} \frac{log p}{p(p − 1)} − n ∑_{p≤\sqrt{n}} \frac{log p}{p^{e_{p}}(p − 1)}

− ∑_{p≤\sqrt{n}} (e_{p} − 1) log p. (13)

But, by using Lemma 13, we have

∑_{p>\sqrt{n}} \frac{log p}{p(p − 1)} = O (\frac{1}{\sqrt{n}}) .  (14)

Next, by using the fact p^{e_{p}} > \frac{n}{p} (for primes p), we have

∑_{p≤\sqrt{n}} \frac{log p}{p^{e_{p}}(p − 1)} < \frac{1}{n} ∑_{p≤\sqrt{n}} \frac{p}{p − 1} log p ≤ \frac{2}{n} ∑_{p≤\sqrt{n}} log p = \frac{2}{n}θ (\sqrt{n}) = O (\frac{1}{\sqrt{n}}) ,  (15)

and by using the fact e_{p} − 1 < e_{p} := ⌊\frac{log n}{log p}⌋ ≤ \frac{log n}{log p}, we have

∑_{p≤\sqrt{n}} (e_{p} − 1) log p < ∑_{p≤\sqrt{n}} log n = (log n)π(\sqrt{n}) = O (\sqrt{n}) .  (16)

Then, by substituting (14), (15), and (16) into (13), we get

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p ≥ c n + O (\sqrt{n}) .  (17)

Finally, (12) and (17) conclude to

∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p = c · n + O (\sqrt{n}) ,

as required.

We are now able to prove Theorem 11. Proof of Theorem 11. For sufficiently large integers n, we have, according to Legendre’s formula,

log ρ_{n} = ∑_{p} ⌊\frac{n}{p}⌋ log p = ∑_{p} (⌊\frac{n}{p}⌋ + ⌊\frac{n}{p^{2}} ⌋ + ⋯) log p

− ∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p

= log(n!) − ∑_{p} (⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯) log p.

The weaker form of Stirling’s approximation formula log(n!) = n log n − n + O(log n) and Proposition 14 imply that

log ρ_{n} = n log n − (c + 1)n + O(\sqrt{n}),

as required.

We now turn to estimate log σ_{n}. To do so, we rely on Theorem 10 and a result of Bordellès et al. [1] (already conjectured by Kellner [4]), part of which is recalled below:

Theorem 15 (Corollary 1.6 of [1]). We have

∑_{\begin{matrix}p>\sqrt{n} \\ S_{p}(n)≥p \end{matrix}} 1 = \frac{2\sqrt{n}}{log n} + o (\frac{\sqrt{n}}{log n})

as n → +∞.

Proof of Theorem 12. For a given positive integer n, according to Theorem 10 we have

\frac{σ_{n}}{n!} = ∏_{\begin{matrix}\sqrt{n+1}<p≤n+1 \\ S_{p}(n)≥p−1 \end{matrix}}p = ∏_{\begin{matrix}\sqrt{n+1}<p≤n+1 \\ S_{p}(n)=p−1 \end{matrix}}p · ∏_{\begin{matrix}p>\sqrt{n+1} \\ S_{p}(n)≥p \end{matrix}} p

(remark that S_{p}(n) ≥ p implies p ≤ n). Thus,

log σ_{n} = log(n!) + ∑_{\begin{matrix}\sqrt{n+1}<p≤n+1 \\ S_{p}(n)=p−1 \end{matrix}}log p + ∑_{\begin{matrix}p>\sqrt{n+1} \\ S_{p}(n)≥p \end{matrix}} log p.  (18)

Now, on the one hand, we remark that n ≡ S_{p}(n) (mod (p−1)) (for primes p), so for a prime p satisfying \sqrt{n + 1} < p ≤ n + 1, the condition S_{p}(n) = p − 1 is equivalent to (p − 1) | n. Consequently,

∑_{\begin{matrix}\sqrt{n+1}<p≤n+1 \\ S_{p}(n)=p−1 \end{matrix}}log p ≤ ∑_{d|n} log(d + 1) ≤ τ(n) log(n + 1) = O (n^{1/3} log n)  (19)

(by (1)). On the other hand, by using Theorem 15, we have

∑_{\begin{matrix}p>\sqrt{n+1} \\ S_{p}(n)≥p \end{matrix}} log p = ∑_{\begin{matrix}p>\sqrt{n} \\ S_{p}(n)≥p \end{matrix}} log p+O (log n) = ( ∑_{\begin{matrix}p>\sqrt{n} \\ S_{p}(n)≥p \end{matrix}} 1) log n+O (log n) = 2\sqrt{n}+o (\sqrt{n}) . (20)

Then, by inserting (19) and (20) together with the Stirling approximation formula log(n!) = n log n − n + O(log n) into (18), we conclude that

log σ_{n} = n log n − n + 2\sqrt{n} + o(\sqrt{n}),

as required.

5 Acknowledgment

The authors acknowledge support from the Algerian DGRSDT (Direction Générale de la Recherche Scientifique et du Développement Technologique). The authors are also grateful to the anonymous reviewer for indicating them the two references [1] and [4] and for having shown them the argument of proving Theorem 12, which they initially stated in the form of a conjecture.

References

[1] O. Bordellès, F. Luca, P. Moree, and I. E. Shparlinski, Denominators of Bernoulli polynomials, Mathematika 64 (2018), 519–541.

[2] P.-J. Cahen and J.-L. Chabert, Integer-Valued Polynomials, Mathematical Surveys and Monographs, 48, American Mathematical Society, 1997.

[3] B. Farhi, On the derivatives of the integer-valued polynomials, Funct. Approx. Comment. Math. 61 (2019), 227–241.

[4] B. C. Kellner, On a product of certain primes, J. Number Theory 179 (2017), 149–164.

[5] 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.

[6] Victor H. Moll, Numbers and Functions. From a Classical-Experimental Mathematician’s Point of View, Student Mathematical Library, Vol. 65, American Mathematical Society, 2012.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available

    at https://oeis.org/.

2020 Mathematics Subject Classification: Primary 11A41; Secondary 11A05, 11N37. Keywords: prime factorization, least common multiple, prime number of a special form, asymptotic estimate of arithmetic functions.

(Concerned with sequences \underline{A048803} and \underline{A091137}.)

Received July 26 2022; revised version received November 1 2022; December 15 2022. Published in Journal of Integer Sequences, January 2 2023.

Return to Journal of Integer Sequences home page.