A Study of a Curious Arithmetic Function

Bakir Farhi Department of Mathematics University of Béjaia Béjaia Algeria

                     bakir.farhi@gmail.com

Abstract In this note, we study the arithmetic function f : ℤ_{+}^{∗} → ℚ_{+}^{∗} defined by f(2^{k}ℓ) = ℓ^{1−k} (∀k, ℓ ∈ ℕ, ℓ odd). We show several important properties about this function, and we use them to obtain some curious results involving the 2-adic valuation. In the last section of the paper, we generalize those results to any other p-adic valuation.

1 Introduction and notation

The purpose of this paper is to study the arithmetic function f : ℤ_{+}^{∗} → ℚ_{+}^{∗} defined by

f(2^{k}ℓ) = ℓ^{1−k} (∀k, ℓ ∈ ℕ, ℓ odd).

We have, for example, f(1) = 1, f(2) = 1, f(3) = 3, f(12) = \frac{1}{3}, f(40) = \frac{1}{25}, …, so it is clear that f(n) is not always an integer. However, we will show in what follows that f satisfies the property that the product of the f(r) for 1 ≤ r ≤ n is always an integer, and it is a multiple of all odd prime numbers not exceeding n. Further, we exploit the properties of f to establish some curious properties concerning the 2-adic valuation. In the last section of the paper, we give (without proof) the analogous properties for other p-adic valuations.

The study of f requires introducing the two auxiliary arithmetic functions g : ℚ_{+}^{∗} → ℤ_{+}^{∗} and h : ℤ_{+}^{∗} → ℚ_{+}^{∗}, defined by:

g(x) := \begin{cases}x, & if x ∈ ℕ; \\ 1, & otherwise. \end{cases}  (∀x ∈ ℚ_{+}^{∗})  (1)
h(r) := \frac{r}{g(\frac{r}{2})g(\frac{r}{4})g(\frac{r}{8}) ⋯}  (∀r ∈ ℤ_{+}^{∗})  (2)

Notice that the product in the denominator of the right-hand side of (2) is actually finite, because g(\frac{r}{2^{i}}) = 1 for any sufficiently large i. So h is well-defined.

1.1 Some notation and terminology

Throughout this paper, we let ℕ^{∗} denote the set ℕ \ {0} of positive integers. For a given prime number p, we let ν_{p} denote the usual p-adic valuation. We define the odd part of a positive rational number α as the positive rational number, denoted Odd(α), so that we have α = 2^{ν_{2}(α)} · Odd(α). Finally, we denote by ⌊.⌋ the integer-part function and we often use in this paper the following elementary well-known property of that function:

∀a, b ∈ ℕ^{∗}, ∀x ∈ ℝ : ⌊\frac{⌊\frac{x}{a}⌋}{b}⌋ = ⌊\frac{x}{ab}⌋ .

2 Results and proofs

Theorem 1. Let n be a positive integer. Then the product ∏_{r=1}^{n} f(r) is an integer.

Proof. For a given r ∈ ℕ^{∗}, let us write f(r) in terms of h(r). By writing r in the form r = 2^{k}ℓ (k, ℓ ∈ ℕ, ℓ odd), we have by the definition of g:

g (\frac{r}{2}) g (\frac{r}{4}) g (\frac{r}{8}) ⋯ = (2^{k−1}ℓ) (2^{k−2}ℓ) × ⋯ × (2^{0}ℓ) = 2^{\frac{k(k−1)}{2}} ℓ^{k}.

So, it follows that:

h(r) := \frac{r}{g(\frac{r}{2})g(\frac{r}{4})g(\frac{r}{8}) ⋯} = \frac{2^{k}ℓ}{2^{\frac{k(k−1)}{2}} ℓ^{k}} = 2^{\frac{k(3−k)}{2}} ℓ^{1−k} = 2^{\frac{k(3−k)}{2}} f(r).

Hence

f(r) = 2^{\frac{ν_{2}(r)(ν_{2}(r)−3)}{2}} h(r).  (3)

Using (3), we get for all n ∈ ℕ^{∗} that:

∏_{r=1}^{n} f(r) = 2^{∑{n \atop r=1} \frac{ν_{2}(r)(ν_{2}(r)−3)}{2}} ∏_{r=1}^{n} h(r).  (4)

By taking the odd part of each side of this last identity, we obtain

∏_{r=1}^{n} f(r) = Odd (∏_{r=1}^{n} h(r)) (∀n ∈ ℕ^{∗}).  (5)

So, to confirm the statement of the theorem, it suffices to prove that the product ∏_{r=1}^{n} h(r) is an integer for any n ∈ ℕ^{∗}. To do so, we lean on the following sample property of g:

g (\frac{1}{a}) g (\frac{2}{a}) ⋯ g (\frac{r}{a}) = ⌊\frac{r}{a}⌋! (∀r, a ∈ ℕ^{∗}).

Using this, we have

∏_{r=1}^{n} h(r) = ∏_{r=1}^{n} \frac{r}{g (\frac{r}{2}) g (\frac{r}{4}) g (\frac{r}{8}) ⋯}
= \frac{n!}{∏_{r=1}^{n} g (\frac{r}{2}) · ∏_{r=1}^{n} g (\frac{r}{4}) · ∏_{r=1}^{n} g (\frac{r}{8}) ⋯}

= \frac{n!}{⌊\frac{n}{2}⌋!⌊\frac{n}{4}⌋!⌊\frac{n}{8}⌋! ⋯}.

Hence

∏_{r=1}^{n} h(r) = \frac{n!}{⌊\frac{n}{2}⌋!⌊\frac{n}{4}⌋!⌊\frac{n}{8}⌋! ⋯}  (6)

(Notice that the product in the denominator of the right-hand side of (6) is actually finite because ⌊\frac{n}{2^{i}} ⌋ = 0 for any sufficiently large i). Now, since ⌊\frac{n}{2}⌋ + ⌊\frac{n}{4}⌋ + ⌊\frac{n}{8}⌋ + ⋯ ≤ \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + ⋯ = n then \frac{n!}{⌊ \frac{n}{2} ⌋!⌊ \frac{n}{4} ⌋!⌊ \frac{n}{8} ⌋!···} is a multiple of

the multinomial coefficient \binom{⌊ \frac{n}{2} ⌋+⌊ \frac{n}{4} ⌋+⌊ \frac{n}{8} ⌋+...}{⌊ \frac{n}{2} ⌋ ⌊ \frac{n}{4} ⌋ ⌊ \frac{n}{8} ⌋ ...} which is an integer. Consequently \frac{n!}{⌊ \frac{n}{2} ⌋!⌊ \frac{n}{4} ⌋!⌊ \frac{n}{8} ⌋!···} is an integer, which completes this proof.

Here is a table of the values of f(n), h(n), ∏_{1≤i≤n} f(i),and ∏_{1≤i≤n} h(i). The sequences ∏_{1≤i≤n} f(i) and ∏_{1≤i≤n} h(i) are sequences \underline{A185275} and \underline{A185021}, respectively, in Sloane’s Encyclopedia of Integer Sequences.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ f(n) & 1 & 1 & 3 & 1 & 5 & 1 & 7 & 1 & 9 & 1 & 11 & \frac{1}{3} \\ h(n) & 1 & 2 & 3 & 2 & 5 & 2 & 7 & 1 & 9 & 2 & 11 & \frac{2}{3} \\ ∏_{1≤i≤n} f(i) & 1 & 1 & 3 & 3 & 15 & 15 & 105 & 105 & 945 & 945 & 10395 & 3465 \\ ∏_{1≤i≤n} h(i) & 1 & 2 & 6 & 12 & 60 & 120 & 840 & 840 & 7560 & 15120 & 166320 & 110880 \end{matrix}

Theorem 2. Let n be a positive integer. Then ∏_{r=1}^{n} f(r) is a multiple of Odd(lcm(1, 2, …, n)).

In particular, ∏_{r=1}^{n} f(r) is a multiple of all odd prime numbers not exceeding n.

Proof. According to the relations (5) and (6) obtained during the proof of Theorem 1, it suffices to show that \frac{n!}{⌊ \frac{n}{2} ⌋!⌊ \frac{n}{4} ⌋!⌊ \frac{n}{8} ⌋!···} is a multiple of lcm(1, 2, …, n). Equivalently, it suffices to prove that for all prime number p, we have

ν_{p} (\frac{n!}{⌊\frac{n}{2}⌋!⌊\frac{n}{4}⌋!⌊\frac{n}{8}⌋! ⋯}) ≥ α_{p},  (7)

where α_{p} is the p-adic valuation of lcm(1, 2, …, n), that is the greatest power of p not exceeding n. Let us show (7) for a given arbitrary prime number p. Using Legendre’s formula (see e.g., [1]), we have

ν_{p} (\frac{n!}{⌊\frac{n}{2}⌋!⌊\frac{n}{4}⌋!⌊\frac{n}{8}⌋! ⋯}) = ∑_{i=1}^{∞} ⌊\frac{n}{p^{i}} ⌋ − ∑_{j=1}^{∞} ∑_{i=1}^{∞} ⌊\frac{n}{2^{j}p^{i}} ⌋

= ∑_{i=1}^{α_{p}} (⌊\frac{n}{p^{i}} ⌋ − ∑_{j=1}^{α_{2}} ⌊\frac{n}{2^{j}p^{i}} ⌋)  (8)

Next, for all i ∈ {1, 2, …, α_{p}}, we have

∑_{j=1}^{α_{2}} ⌊\frac{n}{2^{j}p^{i}} ⌋ = ∑_{j=1}^{α_{2}} ⌊\frac{⌊\frac{n}{p^{i}} ⌋}{2^{j}} ⌋ ≤ ∑_{j=1}^{α_{2}} \frac{⌊\frac{n}{p^{i}} ⌋}{2^{j}} < ⌊\frac{n}{p^{i}} ⌋ .

But since (⌊\frac{n}{p^{i}} ⌋ − ∑_{j=1}^{α_{2}}⌊\frac{n}{2^{j}p^{i}} ⌋) (i ∈ \{1, 2, …, α_{p}\}) is an integer, it follows that:

⌊\frac{n}{p^{i}} ⌋ − ∑_{j=1}^{α_{2}} ⌊\frac{n}{2^{j}p^{i}} ⌋ ≥ 1 (∀i ∈ \{1, 2, …, α_{p}\}).

By inserting those last inequalities in (8), we finally obtain

ν_{p} (\frac{n!}{⌊\frac{n}{2}⌋!⌊\frac{n}{4}⌋!⌊\frac{n}{8}⌋! ⋯}) ≥ α_{p},

which confirms (7) and completes this proof.

Theorem 3. For all positive integers n, we have

∏_{r=1}^{n} h(r) ≤ c^{n},

where c = 4.01055487 . . .. In addition, the inequality becomes an equality for n = 1023 = 2^{10} − 1.

Proof. First, we use the relation (6) to prove by induction on n that:

∏_{r=1}^{n} h(r) ≤ n^{log_{2} n}4^{n}  (9)

• For n = 1, (9) is clearly true.

• For a given n ≥ 2, suppose that (9) is true for all positive integer < n and let us show that (9) is also true for n. To do so, we distinguish the two following cases:

1^{st} case: (if n is even, that is n = 2m for some m ∈ ℕ^{∗}). In this case, by using (6) and the induction hypothesis, we have

∏_{r=1}^{n} h(r) = \binom{2m}{m} ∏_{r=1}^{m} h(r)

≤ \binom{2m}{m}m^{log_{2} m}4^{m}
≤ m^{log_{2} m}4^{2m}  (since \binom{2m}{m} ≤ 4^{m})
≤ n^{log_{2} n}4^{n},

as claimed. 2^{nd} case: (if n is odd, that is n = 2m + 1 for some m ∈ ℕ^{∗}). By using (6) and the induction hypothesis, we have

∏_{r=1}^{n} h(r) = (2m + 1)\binom{2m}{m} ∏_{r=1}^{m} h(r)

≤ (2m + 1)\binom{2m}{m}m^{log_{2} m}4^{m}
≤ m^{log_{2} m+1}4^{2m+1}  (since 2m + 1 ≤ 4m and \binom{2m}{m} ≤ 4^{m})
≤ n^{log_{2} n}4^{n},

as claimed. The inequality (9) thus holds for all positive integer n. Now, to establish the inequality of the theorem, we proceed as follows:

— For n ≤ 70000, we simply verify the truth of the inequality in question (by using the Visual Basic language for example).

— For n > 70000, it is easy to see that n^{log_{2} n} ≤ (c/4)^{n} and by inserting this in (9), the inequality of the theorem follows. The proof is complete.

Now, since any positive integer n satisfies ∏_{r=1}^{n} f(r) ≤ ∏_{r=1}^{n} h(r) (according to (5) and the fact that ∏_{r=1}^{n} h(r) is an integer), then we immediately derive from Theorem 3 the following:

Corollary 4. For all positive integers n, we have

∏_{r=1}^{n} f(r) ≤ c^{n},

where c is the constant given in Theorem 3. □

To improve Corollary 4, we propose the following optimal conjecture which is very probably true but it seems difficult to prove or disprove it!

Conjecture 5. For all positive integers n, we have

∏_{r=1}^{n} f(r) < 4^{n}.

Using the Visual Basic language, we have checked the validity of Conjecture 5 up to n = 100000. Further, by using elementary estimations similar to those used in the proof of Theorem 3, we can easily show that:

lim_{n→+∞} (∏_{r=1}^{n} f(r))^{1/n} = lim_{n→+∞} (∏_{r=1}^{n} h(r))^{1/n} = 4,

which shows in particular that the upper bound of Conjecture 5 is optimal.

Now, by exploiting the properties obtained above for the arithmetic function f, we are going to establish some curious properties concerning the 2-adic valuation.

Theorem 6. For all positive integers n and all odd prime numbers p, we have

∑_{r=1}^{n} ν_{2}(r)ν_{p}(r) ≤ ∑_{r=1}^{n} ν_{p}(r) − ⌊\frac{log n}{log p}⌋ .

Proof. Let n be a positive integer and p be an odd prime number. Since (according to Theorem 2), the product ∏_{r=1}^{n} f(r) is a multiple of the positive integer Odd(lcm(1, 2, …, n)) whose the p-adic valuation is equal to ⌊\frac{log n}{log p}⌋, then we have

ν_{p} (∏_{r=1}^{n} f(r)) = ∑_{r=1}^{n} ν_{p} (f(r)) ≥ ⌊\frac{log n}{log p}⌋ .

But by the definition of f, we have for all r ≥ 1:

ν_{p}(f(r)) = (1 − ν_{2}(r))ν_{p}(r).

So, it follows that:

∑_{r=1}^{n}(1 − ν_{2}(r))ν_{p}(r) ≥ ⌊\frac{log n}{log p}⌋ ,

which gives the inequality of the theorem.

Theorem 7. Let n be a positive integer and let a_{0}+a_{1}2^{1}+a_{2}2^{2}+⋯+a_{s}2^{s} be the representation of n in the binary system. Then we have

∑_{r=1}^{n} \frac{ν_{2}(r)(3 − ν_{2}(r))}{2} = ∑_{i=1}^{s} ia_{i}.

In particular, we have for all m ∈ ℕ:

∑_{r=1}^{2^{m}} \frac{ν_{2}(r)(3 − ν_{2}(r))}{2} = m.

Proof. By taking the 2-adic valuation in the two hand-sides of the identity (4) and then using (6), we obtain

∑_{r=1}^{n} \frac{ν_{2}(r)(3 − ν_{2}(r))}{2} = ν_{2} (∏_{r=1}^{n} h(r)) = ν_{2} (\frac{n!}{⌊\frac{n}{2}⌋!⌊\frac{n}{4}⌋!⌊\frac{n}{8}⌋! ⋯}) .

It follows by using Legendre’s formula (see e.g., [1]) that:

∑_{r=1}^{n} \frac{ν_{2}(r)(3 − ν_{2}(r))}{2} = ∑_{i=1}^{∞} ⌊\frac{n}{2^{i}} ⌋ − ∑_{j=1}^{∞} ∑_{i=1}^{∞} ⌊\frac{n}{2^{i+j}} ⌋

= ∑_{i=1}^{∞} ⌊\frac{n}{2^{i}} ⌋ − ∑_{u=2}^{∞}(u − 1) ⌊\frac{n}{2^{u}} ⌋

= ∑_{i=1}^{∞} ⌊\frac{n}{2^{i}} ⌋ − ∑_{i=1}^{∞} i ⌊\frac{n}{2^{i+1}} ⌋ .

By adding to the last series the telescopic series ∑_{i=1}^{∞} ((i − 1) ⌊\frac{n}{2^{i}} ⌋ − i ⌊\frac{n}{2^{i+1}} ⌋) which is convergent with sum zero, we derive that:

∑_{r=1}^{n} \frac{ν_{2}(r)(3 − ν_{2}(r))}{2} = ∑_{i=1}^{∞} i (⌊\frac{n}{2^{i}} ⌋ − 2 ⌊\frac{n}{2^{i+1}} ⌋) .

But according to the representation of n in the binary system, we have

⌊\frac{n}{2^{i}} ⌋ − 2 ⌊\frac{n}{2^{i+1}} ⌋ = \begin{cases}a_{i}, & for i = 1, 2, …, s; \\ 0, & for i > s. \end{cases}

Hence

∑_{r=1}^{n} \frac{ν_{2}(r)(3 − ν_{2}(r))}{2} = ∑_{i=1}^{s} ia_{i},

as required. The second part of the theorem is an immediate consequence of the first one. The proof is finished.

3 Generalization to the other p-adic valuations

The generalization of the previous results by replacing the 2-adic valuation by a p-adic valuation (where p is an odd prime) is possible but it doesn’t yield results as interesting as those concerning the 2-adic valuation. Actually, the particularity of the prime number p = 2 which have permit us to obtain the previous interesting results is the fact that we have \frac{1}{p} + \frac{1}{p^{2}} + \frac{1}{p^{3}} + ⋯ = 1 for p = 2.

For the following, let p be an arbitrary prime number. We consider more generally the arithmetic function f_{p} : ℕ^{∗} → ℚ_{+}^{∗} defined by:

f_{p}(p^{k}ℓ) = ℓ^{1−k}

for any k ∈ ℕ, ℓ ∈ ℕ^{∗}, ℓ non-multiple of p. So we have clearly f_{2} = f. Using the same method and the same arguments as those used in Section 2, we obtain the followings:

Theorem 8. Let n be a positive integer. Then the product ∏_{r=1}^{n} f_{p}(r) is an integer.

For x ∈ ℚ^{∗}, set φ_{p}(x) := xp^{−ν_{p}(x)}.

Theorem 9. Let n be a positive integer. Then ∏_{r=1}^{n} f_{p}(r) is a multiple of φ_{p}(lcm(1, 2, …, n)).

In particular, ∏_{r=1}^{n} f_{p}(r) is a multiple of all prime number, different from p, not exceeding n.

In addition, ∏_{r=1}^{n} f_{p}(r) is a multiple of the rational number φ_{p}(n!^{\frac{p−2}{p−1}} ).

Remark 10. For p ≠ 2, because the rational number n!^{\frac{p−2}{p−1}} cannot bounded from above by c^{n} (c an absolute constant) then according to the second part of Theorem 9, there is no inequality of the type ∏_{r=1}^{n} f_{p}(r) < c^{n} (c an absolute constant). So, Corollary 4 cannot be generalized to the arithmetic functions f_{p} (p ≠ 2).

Theorem 11. For all positive integers n and all prime numbers q ≠ p, we have

∑_{r=1}^{n} ν_{p}(r)ν_{q}(r) ≤ ∑_{r=1}^{n} ν_{q}(r) − ⌊\frac{log n}{log q}⌋ .

We have also

∑_{r=1}^{n} ν_{p}(r)ν_{q}(r) ≤ ∑_{r=1}^{n} ν_{q}(r) − \frac{p − 2}{p − 1} ∑_{i=1}^{∞} ⌊\frac{n}{q^{i}} ⌋ .

Theorem 12. Let n be a positive integer and let a_{0} + a_{1}p^{1} + a_{2}p^{2} + ⋯ + a_{s}p^{s} be the representation of n in the base-p system. Then we have

∑_{r=1}^{n} \frac{ν_{p}(r)(3 − ν_{p}(r))}{2} = ∑_{i=1}^{s} \{\frac{p(p − 2)p^{i−1} + 1 + (i − 1)(p − 1)}{(p − 1)^{2}}\} a_{i}.

In particular, we have for all m ∈ ℕ:

∑_{r=1}^{p^{m}} \frac{ν_{p}(r)(3 − ν_{p}(r))}{2} = \frac{p(p − 2)p^{m−1} + 1 + (m − 1)(p − 1)}{(p − 1)^{2}}.

References

[1] G. H. Hardy and E. M. Wright. The Theory of Numbers, 5th ed., Oxford Univ. Press, 1979.

2010 Mathematics Subject Classification: Primary 11A05. Keywords: Arithmetic function, least common multiple, 2-adic valuation.

(Concerned with sequences \underline{A185021} and \underline{A185275}.)

Received April 27 2011; revised version received October 15 2011; January 25 2012. Published in Journal of Integer Sequences, January 28 2012.

Return to Journal of Integer Sequences home page.