INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A33

ON FACTORIZATION OF INTEGERS WITH RESTRICTIONS ON THE EXPONENTS

Simon Litsyn^{1}

School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978 Israel

                          litsyn@eng.tau.ac.il

Vladimir Shevelev^{2}

Department of Mathematics, Ben Gurion University of the Negev, Beer Sheva 84105 Israel

                           shevelev@bgu.ac.il

Received: 1/19/07, Accepted: 6/24/07, Published: 7/20/07

Abstract

For a fixed k ∈ ℕ we consider a multiplicative basis in ℕ such that every n ∈ ℕ has the unique factorization as product of elements from the basis with the exponents not exceeding k. We introduce the notion of k-multiplicativity of arithmetic functions, and study several arithmetic functions naturally defined in k-arithmetics. We study a generalized Euler function and prove analogs of the Wirsing and Delange theorems for k-arithmetics.

MSC: Primary 11A51, 11A25; Secondary 11N37

1. Introduction

Let

n = ∏_{p∈P} p^{n_{p}}  (1)

be the canonical factorization of an integer n to prime powers. In other words, the set {p ∈ P} constitutes a multiplicative basis in ℕ and n_{p} can take any non-negative integer values. In the paper we consider other multiplicative bases such that any integer has a unique factorization with the exponents not exceeding some prescribed value k. For example, if k = 1, then the only such basis is

Q^{(1)} = {p^{2^{j}}, p ∈ P, j = 0, 1, …, ∞},

1Partly supported by ISF Grant 033-06

2Partly supported by the Kamea program of the Israeli Ministry of Absorption

and every integer n has the unique factorization

n = ∏_{q∈Q^{(1)}} q^{n_{q}}, n_{q} ∈ {0, 1}.

For arbitrary k, the basis is

Q^{(k)} = {p^{(k+1)^{j}}, p ∈ P, j = 0, 1, …, ∞},

and the corresponding k-factorization is

n = ∏_{q∈Q^{(k)}} q^{n_{q}}, n_{q} ∈ {0, 1, …, k}.  (2)

Example 1 For k = 2 we have the ordered basis

Q^{(2)} = {2, 3, 5, 7, 8, 11, 13, 17, 19, 23, 27, 29, …, 512, …},

and, for example, 35831808 = 2^{2} · 3^{1} · 8^{1} · 27^{2} · 512^{1}.

Notice that the standard prime basis P is the limiting for k tending to ∞, and, by definition, P = Q^{(∞)}.

For a fixed k we use the term k-primes for the elements of Q^{(k)}. We say that a number d is k-divisor of n if the exponents in the k-factorization of d, d_{q}, do not exceed n_{q}.

In this paper we study some non-trivial generalizations of classical arithmetic functions for the introduced k-factorization. It is organized as follows. We start with some basic relations in Section 2. In Section 3 we define k-unitary and k-polynitary divisors and demonstrate that in contrast to the standard ∞-arithmetics in k-arithmetics the maximal divisors are (k − 1)-ary divisors. In Section 4 we study the k-integer part of ratios and provide an explicit and asymptotic expressions for it. A k-equivalent of the Euler totient function is introduced in Section 5, and an explicit and asymptotic formula for it is given. The classical asymptotic Mertens formula is generalized in Section 6. In Section 7 we study the average of the sums of k-divisors and some other generalized number-theoretic functions. In Section 8 we prove some results about relations between the classical Euler totient function and its k-generalization. In Section 9 we develop k-analogs of the classical Delange and Wirsing theorems for k-multiplicative functions. Generalizations of the perfect numbers are considered in Section 10. In Section 11 we study bases associated with k-prime numbers for different k’s. Open problems are summarized in Section 12.

Particular cases of the described problems were considered earlier. The case of k = 1 was introduced in 1981 in [16]. Later in [18] a class of multiplicative functions for k = 1 was addressed. In 1990 G. L. Cohen [5] introduced the so-called infinitary arithmetics coinciding with the considered situation when k = 1. In the same paper Cohen treated infinitary perfect numbers coinciding with harmonic numbers from [17]. These numbers were also considered in [12, 18, 23]. Cohen and Hagis [6] analyzed some arithmetic functions associated with infinitary divisors. A survey of unitary and infinitary analogs of arithmetic functions is by Finch [10], see also Weisstein [23]. Notice that D. Suryanarayana [20] introduced a definition of k-ary divisors different from the one considered in this paper.

2. Basic Relations

Let k ∈ ℕ. Consider the factorization of n_{p}, see (1), in the basis of (k + 1),

n_{p} = ∑_{i≥0} a_{i}(k + 1)^{i},  (3)

where a_{i} = a_{i}(n_{p}) are integers belonging to [0, k]. Substituting (3) into (1) we find

n = ∏_{p∈P} ∏_{i≥0} p^{a_{i}(k+1)^{i}} = ∏_{p∈P} ∏_{i≥0} (p^{(k+1)^{i}})^{a_{i}} .  (4)

The uniqueness of (1) and (3) yields the uniqueness of factorization (4). Therefore, the unique multiplicative basis in k-arithmetic consists of k-primes

Q^{(k)} = {p^{(k+1)^{j−1}} : p ∈ P, j ∈ ℕ} ,  (5)

and by (4) the canonical factorization of an integer n is

n = ∏_{q∈Q^{(k)}} q^{n_{q}^{(k)}},  (6)

with n_{q}^{(k)} ≤ k.

To every n we associate the finite multi-set Q_{n}^{(k)} of k-primes of multiplicity defined by (6). For every k ≥ 1 we assume Q_{1}^{(k)} = ∅.

Definition 1 A number d is called a k-divisor of n if Q_{d}^{(k)} ⊆ Q_{n}^{(k)}.

We write d{| \atop k}n if d is a k-divisor of n. Set

(n_{1}, n_{2})_{k} = max_{d {| \atop k} n_{1},d {| \atop k} n_{2}} d.  (7)

It is easy to see that Q_{(n_{1},n_{2})_{k}}^{(k)} = Q_{n_{1}}^{(k)} ∩ Q_{n_{2}}^{(k)}.

Definition 2 Numbers n_{1} and n_{2} are called mutually k-prime if (n_{1}, n_{2})_{k} = 1.

Notice that the mutual k-primality for k ≥ 1 is weaker than the mutual primality in the ordinary arithmetics. Indeed, (n_{1}, n_{2}) = 1 yields (n_{1}, n_{2})_{k} = 1 for any k > 1. However, the last equality could be valid also when (n_{1}, n_{2}) > 1. For example, (2^{(k+1)^{2}}, 3 · 2^{k+2})_{k} = 1 for every k.

Definition 3 A function θ(n) is called k-multiplicative if it is defined for all natural n in such a way that θ(n) ≠ 0, and for mutually k-prime n_{1} and n_{2} we have

θ(n_{1}n_{2}) = θ(n_{1})θ(n_{2}).  (8)

From the definition it follows that θ(1) = 1. In the conventional arithmetics the k-multiplicative functions can be positioned in between the multiplicative functions and strongly-multiplicative functions (for which (8) holds for any n_{1} and n_{2}). Let us list several examples of k-analogs following from (6) for generalizations of well-known properties of multiplicative functions, see e.g. [4, 13].

Let θ(n) be a k-multiplicative function. Then, using q to denote k-primes, we have

∑_{d {| \atop k} n} θ(d) = ∏_{q {| \atop k} n} (1 + ∑_{i=1}^{n_{q}^{(k)}} θ(q^{i})) and  (9)

∑_{d {| \atop k} n} μ_{k}(d)θ(d) = ∏_{q {| \atop k} n}(1 − θ(q)),  (10)

where

μ_{k}(n) = \{ \begin{matrix}0, & if there exists q ∈ Q^{(k)} : q^{2} {| \atop k}n, \\ (−1)^{∑_{q {| \atop k} n} 1}, & otherwise. \end{matrix}  (11)

The function μ_{k}(n) is the analog of the Möbius function in k-arithmetics. A distinction of μ_{k}(n) from μ(n) is, for example, in that when μ_{k}(n) ≠ 0 then n is not necessary square-free in the conventional sense.

When θ(q) = 1 it follows from (10) that

∑_{d {| \atop k} n} μ_{k}(d) = \{ \begin{matrix}0, & if n > 1, \\ 1, & if n = 1. \end{matrix}  (12)

Furthermore, (see, e.g., [4] for the absolutely converging series ∑_{n=1}^{∞} θ(n)) we have

∑_{n=1}^{∞} θ(n) = ∏_{q∈Q^{(k)}}(1 + θ(q) + ⋯ + θ(q^{k})).  (13)

Considering here μ_{k}(n)θ(n) instead of θ(n), by (11), we find

∑_{n=1}^{∞} μ_{k}(n)θ(n) = ∏_{q∈Q^{(k)}}(1 − θ(q)).  (14)

On the other hand, for θ(n) = n^{−s}, ℜ(s) > 1, an analog of the Euler identity in karithmetics follows:

ζ(s) = ∏_{q∈Q^{(k)}} \frac{1 − q^{−(k+1)s}}{1 − q^{−s}} .  (15)

3. Unitary and Polynitary Divisors

Recall that a unitary divisor of a number n in classical arithmetics is a divisor d of n for which (\frac{n}{d}, d) = 1. Let (n, m)^{(1)} stand for the greatest unitary divisor of n and m. Then a divisor d is called bunitary if (\frac{n}{d}, d)^{(1)} = 1. Analogously we may inductively define ℓ-ary divisors of n satisfying (\frac{n}{d}, d)^{(ℓ−1)} = 1. We write in this case d|^{(ℓ)}n. The infinitary divisors are limiting in this process (ℓ = ∞). As it was mentioned, they were introduced by G. L. Cohen [5].

Definition 4 If d{| \atop k}n, then d is called k-unitary, or a (1)_{k}-ary divisor of n, if (\frac{n}{d}, d)_{k} = 1.

Let us denote by (n, m)_{k}^{(1)} the greatest common k-unitary divisor of n and m.

Definition 5 If d{| \atop k}n then d is called k-bunitary, or a (2)_{k}-ary divisor, if (\frac{n}{d}, d)_{k}^{(1)} = 1. Furthermore, if (n, m)_{k}^{(ℓ−1)} is the greatest common (ℓ − 1)_{k}-ary divisor of n and m, then a divisor d of n is called (ℓ)_{k}-ary if (\frac{n}{d}, d)_{k}^{(ℓ−1)} = 1. □

By convention, d is called a (0)_{k}-ary divisor if d{| \atop k}n. We will write d{| \atop k}^{(ℓ)} when we wish to indicate that d is an (ℓ)_{k}-ary divisor of n.

Let us show that, in contrast to the classical arithmetics, in k-arithmetics, k < ∞, there exist divisors of maximal index ℓ. Such are (k − 1)_{k}-ary divisors. The following iterations of the considered process do not change the (k − 1)_{k}-arity of the divisors. In other words, whenever ℓ ≥ k − 1, the (ℓ)_{k}-ary divisors are (k − 1)_{k}-ary divisors.

For the proof we employ the following statement due to Cohen [5]:

If p is a prime, then for an integer y ∈ [0, ℓ], and an integer x ∈ [0, y], we have

p^{x}|^{(ℓ−1)}p^{y} ⇔ p^{x}|^{(y−1)}p^{y}.  (16)

To prove it one should use a trivial fact that the only factors of p^{y} are 1, p, …, p^{y}. For y ≤ k this is true for any k-prime q ∈ Q^{(k)}. Therefore, analogously to (16) for y ∈ [0, k], we have

p^{x} {| \atop k}^{(k−1)}p^{y} ⇔ p^{x} {| \atop k}^{(y−1)}p^{y}.  (17)

Analogously, by (16), for y ∈ [0, k + 1], we obtain

p^{x}|^{(k)}p^{y} ⇔ p^{x}|^{(y−1)}p^{y}.  (18)

However, the last identity is valid in both, the conventional and k-arithmetics. Indeed, for y ≤ k by (17) and (18),

p^{x} {| \atop k}^{(k−1)}p^{y} ⇔ p^{x} {| \atop k}^{(k)}p^{y},

and for y = k + 1, (18) becomes a tautology. Therefore, in k-arithmetics we have for all y,

p^{x} {| \atop k}^{(k)}p^{y} ⇔ p^{x} {| \atop k}^{(k−1)}p^{y},

and the claim easily follows.

In particular,

p^{x} {| \atop 1}^{(1)}p^{y} ⇔ p^{x} {| \atop 1}^{(0)}p^{y},

or p^{x} {| \atop 1}p^{y}, i.e. in 1-arithmetics all the divisors are 1-unitary.

4. The Function ⌊\frac{x}{m}⌋^{(k)}

Let us introduce the function ⌊\frac{x}{m}⌋^{(k)} being a natural generalization of the function ⌊\frac{x}{m}⌋ as a function in x for a fixed m. We use ⌊\frac{x}{m}⌋^{(k)} to denote the number of integers not exceeding x for which m is a k-divisor. In contrast to ⌊\frac{x}{m}⌋, as will be seen from what follows, there is in principle no algorithm for computing ⌊\frac{x}{m}⌋^{(k)}, if the canonical factorization of m in k-arithmetics is not known. Moreover, without such factorization it is impossible even to compute the main asymptotical term of ⌊\frac{x}{m}⌋^{(k)} for x → ∞. The following theorem gives an explicit expression for ⌊\frac{x}{m}⌋^{(k)}.

4.1. An Exact Formula for ⌊\frac{x}{m}⌋^{(k)}

Theorem 1 Let m = q_{1}^{ℓ_{1}}q_{2}^{ℓ_{2}} … q_{r}^{ℓ_{r}}, 1 ≤ ℓ_{i} ≤ k, be the k-factorization of m (notice, that the indices of q_{i}’s are not necessary their consecutive numbers in the ordered sequence of Q^{(k)}). Then for positive real x ≥ m,

⌊\frac{x}{m}⌋^{(k)} = ∑_{j_{1}≥ℓ_{1}} ∑_{j_{2}≥ℓ_{2}} … ∑_{j_{r}≥ℓ_{r}} ((∏_{i=1}^{r} a_{j_{i}}^{(ℓ_{i})}) ⌊\frac{x}{∏_{i=1}^{r} q_{i}^{j_{i}}} ⌋) ,  (19)

where for fixed ℓ > 0,

a_{j}^{(ℓ)} = \{ \begin{matrix}1 & if j ≡ ℓ mod(k + 1), \\ −1 & if j ≡ 0 mod(k + 1), \\ 0 & otherwise. \end{matrix}  (20)

To prove the theorem we will need the following lemma.

Lemma 1 Let m and n be positive integers, and m = q_{1}^{ℓ_{1}}q_{2}^{ℓ_{2}} … q_{r}^{ℓ_{r}}, 1 ≤ ℓ_{i} ≤ k, be the factorization of m to powers of k-prime numbers. Let, moreover, ν_{j} ≥ 1 be the maximal power of k-prime q_{j} dividing n, j = 1, …, r. Then m{| \atop k}n if and only if

ν_{j} ≥ ℓ_{j}, ν_{j} ≡ ℓ_{j}, ℓ_{j} + 1, …, k mod(k + 1), j = 1, 2, …, r.  (21)

Proof. Denote by i_{j} the maximal power of q_{j}^{k+1} dividing n, j = 1, 2, …, r. Notice that q_{j}^{ℓ_{j}} {| \atop k}n if and only if

q_{j}^{ℓ_{j}} | \frac{n}{(q_{j}^{k+1})^{i_{j}}} .

Thus q_{j}^{ℓ_{j}} {| \atop k}n if and only if q_{j}^{(k+1)i_{j}+ℓ_{j}}|n. Since 1 ≤ ℓ_{j} ≤ k,

ν_{j} ∈ [(k + 1)i_{j} + ℓ_{j}, (k + 1)i_{j} + k] , j = 1, 2, …, r.

Indeed, increasing ν_{j} we violate the assumption about maximality of i_{j}. □

Proof of Theorem 1. Let x be a positive real. Consider all possible collections of r non-negative integers α_{1}, α_{2}, …, α_{r}, satisfying q_{1}^{α_{1}}q_{2}^{α_{2}} … q_{r}^{α_{r}} ≤ x. Let us partition the sequence 1, 2, …, ⌊x⌋ into non-intersecting classes T_{α_{1},...,α_{r}} according to the rule:

h ∈ T_{α_{1},...,α_{r}} if

max \{τ ≥ 0 : q_{i}^{τ} {| \atop k} h\} = α_{i}, i = 1, 2, …, r.

Using inclusion-exclusion for the cardinalities of the classes we obtain

|T_{α_{1},...,α_{r}}| = ⌊λ⌋ − ∑_{1≤i≤r} ⌊\frac{λ}{q_{i}} ⌋ + ∑_{1≤i<j≤r} ⌊\frac{λ}{q_{i}q_{j}} ⌋ −

− ∑_{1≤i<j<ℓ≤r} ⌊\frac{λ}{q_{i}q_{j}q_{ℓ}} ⌋ + … + (−1)^{r} ⌊\frac{λ}{q_{1}q_{2} … q_{r}} ⌋ ,  (22)

where

λ = \frac{x}{q_{1}^{α_{1}}q_{2}^{α_{2}} … q_{r}^{α_{r}}} .

By Lemma 1, m{| \atop k}q_{1}^{α_{1}}q_{2}^{α_{2}} … q_{r}^{α_{r}} if and only if α_{j} ≡ ℓ_{j}, ℓ_{j} + 1, …, k mod(k + 1), j = 1, 2, …, r. Therefore,

⌊\frac{x}{m}⌋^{(k)} = ∑_{α_{j}≡ℓ_{j},ℓ_{j}+1,...,k mod(k+1), j=1,2,...,r} |T_{α_{1},...,α_{r}}| .  (23)

Specifically, let us consider the summands with ℓ_{j} ≤ α_{j} ≤ k + 1 (other groups of summands mod(k +1) are considered analogously). Let us correspond to every summand of form ⌊\frac{λ}{q_{i_{1}}q_{i_{2}}...q_{is}} ⌋ in (22) the monomial x_{1}^{α_{1}}x_{2}^{α_{2}} … x_{r}^{α_{r}}· x_{i_{1}}x_{i_{2}} … x_{i_{s}}. Clearly it is a one-to-one correspondence. Assuming that for a linear combination of summands we correspond the same linear combination of the images, we find that to |T_{α_{1},...,α_{r}}|, see (22), corresponds the polynomial

P_{α_{1},...,α_{r}}(x_{1}, …, x_{r}) = x_{1}^{α_{1}}x_{2}^{α_{2}} … x_{r}^{α_{r}} ∑_{s=0}^{r}(−1)^{s} ∏_{1≤i_{1}<i_{2}<...<i_{s}≤r} x_{i_{1}}x_{i_{2}} … x_{i_{s}},

and to the considered subsum of (23) corresponds the polynomial

R(x_{1}, …, x_{r}) = ∑_{α_{j}=ℓ_{j},ℓ_{j}+1,...,k;j=1,2,...,r} x_{1}^{α_{1}}x_{2}^{α_{2}} … x_{r}^{α_{r}}·

· ∑_{s=0}^{r}(−1)^{s} ∏_{1≤i_{1}<i_{2}<...<i_{s}≤r} x_{i_{1}}x_{i_{2}} … x_{i_{s}}.  (24)

The statement of the theorem is true if we manage to prove that

R(x_{1}, …, x_{r}) = ∑_{ℓ_{1}≤i_{1}≤k+1} ∑_{ℓ_{2}≤i_{2}≤k+1} … ∑_{ℓ_{r}≤i_{r}≤k+1} (∏_{s=1}^{r} a_{i_{s}}^{(ℓ_{s})}) x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{r}^{i_{r}}.  (25)

Since

∑_{s=0}^{r}(−1)^{s} ∏_{1≤i_{1}<i_{2}<...<i_{s}≤r} x_{i_{1}}x_{i_{2}} … x_{i_{s}} = ∏_{j=1}^{r}(1 − x_{j}),

we find from (24) that

R(x_{1}, …, x_{r}) = ∏_{j=1}^{r} ∑_{α_{j}=ℓ_{j}}^{k}(x_{j}^{α_{j}} − x_{j}^{α_{j}+1}) = ∏_{j=1}^{r}(x_{j}^{ℓ_{j}} − x_{j}^{k+1}),

and (25) follows. □

Example 2 Let k = 2, m = 12, x = 100. Then q_{1} = 2, q_{2} = 3, ℓ_{1} = 2, ℓ_{2} = 1, and by (19) we have

⌊\frac{100}{12}⌋^{(2)} = ∑_{j_{1}≥2} ∑_{j_{2}≥1} a_{j_{1}}^{(2)}a_{j_{2}}^{(1)} ⌊\frac{100}{2^{j_{1}}3^{j_{2}}} ⌋ ,

where

a_{j_{1}}^{(2)} = \{ \begin{matrix}1, & if j_{1} ≡ 2 mod 3 \\ −1, & if j_{1} ≡ 0 mod 3 \\ 0, & otherwise \end{matrix}

and

a_{j_{2}}^{(1)} = \{ \begin{matrix}1, & if j_{2} ≡ 1 mod 3 \\ −1, & if j_{2} ≡ 0 mod 3 \\ 0, & otherwise \end{matrix}

Therefore, we have

⌊\frac{100}{12}⌋^{(2)} = a_{2}^{(2)}a_{1}^{(1)} ⌊\frac{100}{2^{2}3}⌋ + a_{3}^{(2)}a_{1}^{(1)} ⌊\frac{100}{2^{3}3}⌋ + a_{4}^{(2)}a_{1}^{(1)} ⌊\frac{100}{2^{4}3}⌋
+a_{5}^{(2)}a_{1}^{(1)} ⌊\frac{100}{2^{5}3}⌋ + a_{2}^{(2)}a_{2}^{(1)} ⌊\frac{100}{2^{2}3^{2}} ⌋ + a_{3}^{(2)}a_{2}^{(1)} ⌊\frac{100}{2^{3}3^{2}} ⌋
= ⌊\frac{100}{2^{2}3}⌋ − ⌊\frac{100}{2^{3}3}⌋ + ⌊\frac{100}{2^{5}3}⌋
= 8 − 4 + 1 = 5.

Indeed, we have five numbers not exceeding 100, which are 2-multiples of 12: 12, 36, 60, 84,

96. □

Notice that when x = n, the value ⌊\frac{n}{m}⌋^{(k)} is a complicated arithmetic function in two variables which, in contrast to the conventional function ⌊\frac{n}{m}⌋ = ⌊\frac{n}{m}⌋^{(∞)}, is not homogeneous, i.e., in general ⌊\frac{n}{m}⌋^{(k)} ≠ ⌊\frac{nt}{mt}⌋^{(k)}.

Example 3 Though \frac{25}{3} = \frac{50}{6} = \frac{600}{72} = \frac{100}{12} = \frac{300}{36}, we have

⌊\frac{25}{3}⌋^{(2)} = 8, ⌊\frac{50}{6}⌋^{(2)} = 7, ⌊\frac{600}{72}⌋^{(2)} = 6, ⌊\frac{100}{12}⌋^{(2)} = 5, ⌊\frac{300}{36}⌋^{(2)} = 4.

The question about the minimum of ⌊\frac{nt}{mt}⌋^{(k)} in t is an interesting open problem in k-arithmetics.

4.2. Asymptotic Formula for ⌊\frac{x}{m}⌋^{(k)}

Theorem 2 a) If m = q_{1}^{ℓ_{1}}q_{2}^{ℓ_{2}} … q_{r}^{ℓ_{r}}, 1 ≤ ℓ_{i} ≤ k, q_{i} ∈ Q^{(k)}, then

⌊\frac{x}{m}⌋^{(k)} = x ∏_{i=1}^{r} \frac{q_{i}^{k+1−ℓ_{i}} − 1}{q_{i}^{k+1} − 1} + θ ln^{r} x,  (26)

such that

|θ| ≤ ∏_{i=1}^{r} \frac{1}{ln q_{i}} .

b) For any ε > 0 there exists a constant a_{ε} > 0 depending only on ε, such that uniformly in m ≤ x the following inequality holds:

|⌊\frac{x}{m}⌋^{(k)} − x ∏_{i=1}^{r} \frac{q_{i}^{k+1−ℓ_{i}} − 1}{q_{i}^{k+1} − 1}| ≤ a_{ε}x^{ε}.  (27)

Proof. a) Omitting in the right-hand side of (19) the floor function and taking into account that by (20),

∑_{j≥ℓ} a_{j}^{(ℓ)} \frac{1}{q^{j}} = ∑_{i≥1} (\frac{1}{q^{(k+1)(i−1)+ℓ}} − \frac{1}{q^{(k+1)i}} ) = \frac{q^{k+1−ℓ} − 1}{q^{k+1} − 1},  (28)

we obtain instead of the right-hand side of (19) the following value:

x ∏_{i=1}^{r} \frac{q_{i}^{k+1−ℓ_{i}} − 1}{q_{i}^{k+1} − 1}.

The remainder in (26) is an evident estimate for the number of non-zero summands in (19).

b) Notice that the number of divisors m is at least 2^{r}, which, by the Wiman-Ramanujan theorem (see e.g. [14]), for large enough n > n_{δ} does not exceed

2^{(1+δ) \frac{ln x}{ln ln x}}  (29)

uniformly in m ≤ x. Therefore,

r ≤ (1 + δ)\frac{ln x}{ln ln x}.  (30)

Furthermore, the number of non-zero summands in the right-hand side of (19) does not exceed the number of solutions in natural numbers k_{1}, k_{2}, …, k_{r} of the inequality

∏_{i=1}^{r} 2^{k_{i}} ≤ x,  (31)

or, which is the same, the number of solutions to the inequality

k_{1} + k_{2} + … + k_{r} ≤ ⌊log_{2} x⌋.  (32)

Denote by c(r, n) the number of compositions of n with exactly r parts. It is well known [1] that c(r, n) = \binom{n−1}{r−1}. Therefore, the number N_{x} of solutions to (32) is

∑_{i=1}^{⌊log_{2} x⌋} c(r, i) = ∑_{i=1}^{⌊log_{2} x⌋} \binom{i − 1}{r − 1} = \binom{⌊log_{2} x⌋ + 1}{r} − δ_{r,1} ≤ \binom{⌊log_{2} 2x⌋}{r} ≤ \binom{⌊log_{2} 2x⌋}{(1 + δ)\frac{ln x}{ln ln x}}, (33)

where the last inequality follows from (30). Now using the Stirling approximation we obtain

N_{x} ≤ x^{\frac{ln ln ln x}{ln ln x}} (1 + o(x)).  (34)

Therefore, for x > x_{ε},

N_{x} ≤ x^{ε}.  (35)

It is only left to choose the constant a_{ε} in such a way that (35) will hold as well for x ≤ x_{ε}. □

Remark 1 It is known [14] that estimate (29) cannot be essentially improved, i.e. there are infinitely many n ≤ x for which the number of divisors exceeds 2^{(1−δ) \frac{ln x}{ln ln x}}. Let us show that also in the case k < ∞, (29) cannot be essentially improved when k-divisors are used instead of the conventional divisors.

Indeed, ∏_{p≤N,p∈P} p ∼ e^{N+o(N)}. Let us consider the most distinct from the conventional case k = 1. For r large enough consider n = ∏_{p≤p_{r}} p. We have

n ≤ e^{p_{r}(1+ε)} ⇒ p_{r} ≥ \frac{ln n}{1 + ε}, r ≥ π (\frac{ln n}{1 + ε}) ≥ \frac{\frac{ln n}{1+ε}(1 − ε)}{ln ln n − ln(1 + ε)}.

Therefore, for 2^{r} divisors of n (coinciding with 1-divisors) we have

2^{r} ≥ 2^{\frac{(ln n)(1−2ε)}{ln ln n−ln(1+ε)}} ≤ 2^{(1−δ) \frac{ln n}{ln ln n}}

for a relevant small enough δ. It is easy to check that (34) cannot be essentially improved by a more accurate estimate of the number of summands in the right-hand side of (19), i.e., the number

k_{1} ln q_{1} + ⋯ + k_{r} ln q_{r} ≤ ⌊ln x⌋,  (36)

instead of the estimate (31). It is known [3] that the number of solutions to (36) in natural numbers is O (\frac{ln^{r} x}{r! ∏_{i≤r} ln q_{i}} ). This by more cumbersome calculations using (30) also yields (34). □

Example 4 The obtained asymptotics provide accurate enough estimates even for small numbers. For example, using the main term (27), we get (with rounding)

⌊\frac{25}{3}⌋^{(2)} = 7.7, ⌊\frac{50}{6}⌋^{(2)} = 6.6, ⌊\frac{600}{72}⌋^{(2)} = 5.7, ⌊\frac{100}{12}⌋^{(2)} = 4.4, ⌊\frac{300}{36}⌋^{(2)} = 3.3.

This can be compared to the exact values 8, 7, 6, 5, and 4 appearing in Example 3. □

5. A k-analog of the Euler Function

Let us consider a k-analog of the Euler function in k-arithmetics:

φ_{k}(n) = ∑_{1≤j≤n:(j,n)_{k}=1} 1.  (37)

Example 5 It is easy to check that

φ_{1}(100) = 77, φ_{2}(100) = 46, φ_{3}(100) = 43, φ_{4}(100) = 42, φ_{5}(100) = 41,

and φ_{k}(100) = 40 for k ≥ 6.

Notice that it is convenient considering the Euler function along with the more general function

φ_{k}(x, n) = ∑_{1≤j≤x:(j,n)_{k}=1} 1,  (38)

such that φ_{k}(n) = φ_{k}(n, n).

Theorem 3

φ_{k}(x, n) = ∑_{d {| \atop k} n} μ_{k}(d) ⌊\frac{x}{d}⌋^{(k)} .  (39)

Remark 2 Consider a structurally close to φ(n), but not having a clear arithmetic sense, multiplicative function

φ̃_{k}(n) = ∑_{d {| \atop k} n} μ_{k}(d)\frac{n}{d}.  (40)

Notice, that in contrast to φ̃_{k}(n) the function φ_{k}(n) is not multiplicative. In particular the equality

∑_{d {| \atop k} n} φ_{k}(d) = n,

is not valid here (though is correct for (40)). Therefore, and as well since ⌊\frac{n}{d}⌋^{(k)} is not a function of the ratio \frac{n}{d}, apparently there is no way to use here the k-analog of the Möbius inversion:

∑_{d {| \atop k} n} f(d) = F (n) ⇒ ∑_{d {| \atop k} n} μ_{k}(d)F (\frac{n}{d}) = f(n).

Moreover, it follows from (40) that

φ̃_{k}(n) = n ∏_{q {| \atop k} n, q∈Q^{(k)}} (1 − \frac{1}{q}) .  (41)

We will see later that this means that φ̃_{k}(n) even asymptotically does not approximate φ_{k}(n). Nevertheless we will demonstrate that φ_{k}(n) is accurately approximated by some simple enough multiplicative function.

Proof of Theorem 3. For every fixed n let us consider the k-multiplicative function λ_{n}^{(k)}(m) defined on the powers of k-primes as

λ_{n}^{(k)}(q^{ℓ}) = \{ \begin{matrix}1, & if q^{ℓ} {| \atop k}n; \\ 0, & otherwise, \end{matrix} 1 ≤ ℓ ≤ k.

Then for every m ≤ n we have

λ_{n}^{(k)}(m) = \{ \begin{matrix}1, & if m{| \atop k}n; \\ 0, & otherwise. \end{matrix}  (42)

It follows from (38) and (42) that

φ_{k}(x, n) = ∑_{1≤j≤x} ∏_{q {| \atop k} n} (1 − λ_{j}^{(k)}(q)) .  (43)

Indeed, if there is no k-prime, which simultaneously k-divides n and k-divides j, then (j, n)_{k} = 1 and

∏_{q {| \atop k} n} (1 − λ_{j}^{(k)}(q)) = 1.

If there is at least one k-prime q that k-divides simultaneously n and j, then

∏_{q {| \atop k} n} (1 − λ_{j}^{(k)}(q)) = 0.

This gives (43). Let us rewrite now (10) for θ(d) = λ_{j}^{(k)}(d). We have

∏_{q {| \atop k} n} (1 − λ_{j}^{(k)}(q)) = ∑_{d {| \atop k} n} μ_{k}(d)λ_{j}^{(k)}(d).  (44)

We deduce from (43) and (44)

φ_{k}(x, n) = ∑_{1≤j≤x} ∑_{d {| \atop k} n} μ_{k}(d)λ_{j}^{(k)}(d) = ∑_{d {| \atop k} n} μ_{k}(d) ∑_{1≤j≤x} λ_{j}^{(k)}(d).  (45)

However, it follows from (42) that

∑_{1≤j≤x} λ_{j}^{(k)}(d) = ⌊\frac{x}{d}⌋^{(k)} ,  (46)

and (45) and (46) yield (39). □

Now we are in a position to present an explicit expression for φ_{k}(n).

Theorem 4 Let q_{1}, q_{2}, …, q_{r}, be all k-prime k-divisors of n. Then

φ_{k}(x, n) = ∑(−1)^{τ_{1}+τ_{2}+...+τ_{r}} ⌊\frac{x}{q_{1}^{t_{1}}q_{2}^{t_{2}} … q_{r}^{t_{r}}} ⌋ ,  (47)

where the summation is over all non-negative t_{1}, t_{2}, …, t_{r}, for which t_{i} ≡ 0 mod(k + 1) or t_{i} ≡ 1 mod(k + 1), and

τ_{i} = \{ \begin{matrix}0, & if t_{i} ≡ 0 mod(k + 1), \\ 1, & if t_{i} ≡ 1 mod(k + 1), \end{matrix}  (48)

i = 1, 2, …, r.

Proof. According to Theorem 3 it is sufficient to consider the divisors of n having the form d = q_{i_{1}}q_{i_{2}} … q_{i_{h}}, 1 ≤ i_{1} < i_{2} < … < i_{h} ≤ r. By Theorem 1 in this case

⌊\frac{x}{d}⌋^{(k)} = ∑_{j_{1}≥1} ∑_{j_{2}≥1} … ∑_{j_{h}≥1} (∏_{i=1}^{h} a_{j_{i}}^{(1)}) ⌊\frac{x}{q_{i_{1}}^{j_{1}}q_{i_{2}}^{j_{2}} … q_{i_{h}}^{j_{h}}} ⌋ ,  (49)

where

a_{j}^{(1)} = \{ \begin{matrix}1, & if j ≡ 1 mod(k + 1), \\ −1, & if j ≡ 0 mod(k + 1), \\ 0, & otherwise. \end{matrix}  (50)

Set

θ(j) = \{ \begin{matrix}0, & if j ≡ 0 mod(k + 1), \\ 1, & if j ≡ 1 mod(k + 1). \end{matrix}  (51)

Then by (49)-(50) we have

⌊\frac{x}{d}⌋^{(k)} = ∑(−1)^{θ(j_{1})+θ(j_{2})+...+θ(j_{h})+h} ⌊\frac{x}{q_{i_{1}}^{j_{1}}q_{i_{2}}^{j_{2}} … q_{i_{h}}^{j_{h}}} ⌋ ,

where the summation is over all j_{i} ≥ 1 for which j_{i} ≡ 0 mod(k +1) or j_{i} ≡ 1 mod(k +1). Hence for d = q_{i_{1}}q_{i_{2}} … q_{i_{h}},

μ_{k}(d) ⌊\frac{x}{d}⌋^{(k)} = ∑(−1)^{θ(j_{1})+θ(j_{2})+...+θ(j_{h})} ⌊\frac{x}{q_{i_{1}}^{j_{1}}q_{i_{2}}^{j_{2}} … q_{i_{h}}^{j_{h}}} ⌋ .

By Theorem 3 then

φ_{k}(x, n) = ∑_{1≤i_{1}<i_{2}<...<i_{h}≤r} ∑(−1)^{θ(j_{1})+θ(j_{2})+...+θ(j_{h})} ⌊\frac{x}{q_{i_{1}}^{j_{1}}q_{i_{2}}^{j_{2}} … q_{i_{h}}^{j_{h}}} ⌋ ,  (52)

where the internal summation is over all j_{i} ≥ 1 satisfying either j ≡ 0 mod(k + 1) or j ≡ 1 mod(k + 1). Clearly (47) follows from (52) and (51). □

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A33 15

Example 6 For n = x = 100 (r = 2, q_{1} = 2, q_{2} = 5) we have by (47) and (48),

φ_{2}(100) = ∑_{t_{1}≥0, t_{1}≡0 or 1 mod 3} ∑_{t_{2}≥0, t_{2}≡0 or 1 mod 3}(−1)^{τ_{1}+τ_{2}} ⌊\frac{100}{2^{t_{1}}5^{t_{2}}} ⌋ =

= 100 − \frac{100}{2} + ⌊\frac{100}{8}⌋ − ⌊\frac{100}{16}⌋ + ⌊\frac{100}{64}⌋ −

−\frac{100}{5} + \frac{100}{2 · 5} − ⌊\frac{100}{8 · 5}⌋ + ⌊\frac{100}{16 · 5}⌋ = 46.

Now we treat the asymptotic behavior of φ_{k}(n). Theorem 5

φ_{k}(x, n) = κ_{k}(n)x + O ((nx)^{ε}) ,  (53)

where

κ_{k}(n) = ∏_{q {| \atop k} n} (1 + \frac{1}{q} + … + \frac{1}{q^{k}} )^{−1} ,

and the implied constant only depends on ε. Proof. Set

n^{∗} = ∏_{q {| \atop k} n} \frac{q^{k+1} − 1}{q^{k} − 1}.  (54)

Using Theorem 3 and the uniform estimate (27) for ℓ_{i} = 1, i = 1, 2, …, r, we find

|φ_{k}(x, n) − x ∑_{d {| \atop k} n} \frac{μ_{k}(d)}{d^{∗}} | = |∑_{d {| \atop k} n} μ_{k}(d) (⌊\frac{x}{d}⌋^{(k)} − \frac{x}{d^{∗}} )| ≤

≤ ∑_{d {| \atop k} n} |⌊\frac{x}{d}⌋^{(k)} − \frac{x}{d^{∗}} | ≤ a_{ε}x^{ε} ∑_{d {| \atop k} n} 1 = a_{ε}x^{ε}τ^{(k)}(n) ≤ a_{ε}x^{ε}τ(n),  (55)

where τ^{(k)}(n) is the number of k-divisors of n, and τ(n) is the number of conventional divisors of n. By the Wiman-Ramanujan theorem (see e.g. [14]) for δ > 0 and n > n_{0}(δ),

τ(n) < n^{\frac{(1+δ) ln 2}{ln ln n}} < n^{ε}, n ≥ n_{ε}.

By (55) and (53) this means that it is sufficient to demonstrate that

∑_{d {| \atop k} n} \frac{μ_{k}(d)}{d^{∗}} = ∏_{q {| \atop k} n} (1 + \frac{1}{q} + … + \frac{1}{q^{k}} )^{−1} .  (56)

This easily follows from (10) if one sets θ(n) = (n^{∗})^{−1}. □

Theorem 5 is a generalization of the main result of [16] which can be deduced from it setting k = 1, x = n. As well Theorem 14 of [6] is a particular case of our theorem when k = 1.

Notice that for the values φ_{k}(n) presented in Example 5, using the main term (53) for x = n we obtain the following approximations: φ_{1}(100) ≈ 76.9 (the exact value 77), φ_{2}(100) ≈ 46.1(46), φ_{3}(100) ≈ 42.7(43), φ_{4}(100) ≈ 41.3(42), φ_{5}(100) ≈ 40.6(41), and φ_{k}(100) ≈ 40.3(40) for k ≥ 6. Thus the approximation is quite accurate even for small n’s.

6. Sums of the Values of the k-Euler Function

The following double summation formula due to Mertens (see e.g. [9]) is well known:

∑_{i=1}^{n} φ(i) = \frac{3}{π^{2}} n^{2} + O(n ln n).  (57)

Consider ∑_{i=1}^{n} φ_{k}(n). We will need an estimate for the following sum:

ν_{k}(x, d) = ∑_{1≤i≤x:d {| \atop k} i} i  (58)

for the numbers of the form

d = q_{1}q_{2} … q_{r}, q_{1} < q_{2} < … < q_{r}, q_{i} ∈ Q^{(k)}, i = 1, 2, …, r.  (59)

Lemma 2 Let d be of the form (59). Then for any ε > 0 there exists a b_{ε} > 0, such that

|ν_{k}(x, d) − \frac{x^{2}}{2d^{∗}} | ≤ b_{ε}x^{1+ε},  (60)

where

d^{∗} = ∏_{i=1}^{r} \frac{q_{i}^{k+1} − 1}{q_{i}^{k} − 1}.  (61)

Proof. By (27) when ℓ_{i} = 1 uniformly in d ≤ x we have

⌊\frac{x}{d}⌋^{(k)} = ∑_{1≤i≤x:d {| \atop k} i} 1 = \frac{x}{d^{∗}} + O(x^{ε}).  (62)

Using the Stieltjes integration with the integrator ⌊\frac{x}{d}⌋^{(k)} (assuming d is a constant) we obtain the sought results from (62). □

Theorem 6 We have for any ε > 0,

∑_{n≤x} φ_{k}(n) = \frac{x^{2}}{2} ∏_{q∈Q^{(k)}} (1 − (\frac{q^{k} − 1}{q^{k+1} − 1})^{2}) + o(x^{1+ε}).

Proof. Using (39) and (62) for x = n we find

∑_{n≤x} φ_{k}(n) = ∑_{n≤x} ∑_{d {| \atop k} n} μ_{k}(d) ⌊\frac{n}{d}⌋^{(k)} =

= ∑_{n≤x} n ∑_{d {| \atop k} n} \frac{μ_{k}(d)}{d^{∗}} + o(x^{1+ε}) = ∑_{d≤x} \frac{μ_{k}(d)}{d^{∗}} ∑_{n≤x: d {| \atop k} n} n + o(x^{1+ε}).

From Lemma 2 now we get

∑_{n≤x} φ_{k}(n) = ∑_{d≤x} \frac{μ_{k}(d)}{d^{∗}} (\frac{x^{2}}{2d^{∗}} + o(x^{1+ε})) =

= \frac{x^{2}}{2} ∑_{d≤x} \frac{μ_{k}(d)}{(d^{∗})^{2}} + o (x^{1+ε} ∑_{d≤x} \frac{μ_{k}(d)}{d^{∗}}) .  (63)

Notice that since

d^{∗} = ∏_{i=1}^{r} \frac{q_{i}^{k+1} − 1}{q_{i}^{k} − 1} > ∏_{i=1}^{r} q_{i} = d,

we have

|∑_{d≤x} \frac{μ_{k}(d)}{d^{∗}} | ≤ ∑_{d≤x} \frac{1}{d} = O(log x).

Moreover,

|∑_{d≥x} \frac{μ_{k}(d)}{(d^{∗})^{2}} | ≤ ∑_{d>x} \frac{1}{d^{2}} ≤ \frac{1}{x − 1}.

Therefore, by (63),

∑_{n≤x} φ_{k}(n) = \frac{x^{2}}{2} ∑_{i=1}^{∞} \frac{μ_{k}(i)}{(i^{∗})^{2}} + o(x^{1+ε}),

where by (61) n^{∗} is a k-multiplicative function.

Finally, using (14) for θ(n) = (n^{∗})^{−2} we obtain the claim. □ In particular, when k = 1, a result from [6] follows from the theorem:

∑_{n≤x} φ_{1}(n) = \frac{x^{2}}{2} ∏_{q∈Q^{(1)}} (1 − \frac{1}{(q + 1)^{2}} ) + o(x^{1+ε}) = 0.3666252769 … x^{2} + o(x^{1+ε}).

Here (and in what follows) the constant was computed in [10], see also [7, 11] for efficient computational methods.

When k → ∞ we find from the theorem that

∑_{n≤x} φ(n) ∼ \frac{x^{2}}{2} ∏_{p∈P} (1 − \frac{1}{p^{2}} ) = \frac{3}{π^{2}} x^{2}.  (64)

7. Other Functions

Let us consider several natural arithmetical functions.

1. The function φ̃_{k}(n) has been defined above in (40) and (41) as a second (formal) generalization of the Euler totient function. For k = 1, φ̃_{1}(n) was considered in [6] and [10]. For it we analogously deduce:

∑_{n≤x} φ̃_{k}(n) = ∑_{n≤x} ∑_{d {| \atop k} n} μ_{k}(d)\frac{n}{d} = ∑_{n≤x} n ∑_{d {| \atop k} n} \frac{μ_{k}(d)}{d} =

= ∑_{d≤x} \frac{μ_{k}(d)}{d} ∑_{n≤x: d {| \atop k} n} n = ∑_{d≤x} \frac{μ_{k}(d)}{d}ν_{k}(x, d) =

= ∑_{d≤x} \frac{μ_{k}(d)}{d} (\frac{x^{2}}{2d^{∗}} + o(x^{1+ε})) = \frac{x^{2}}{2} ∑_{i=1}^{∞} \frac{μ_{k}(i)}{ii^{∗}} + o(x^{1+ε}) =

= \frac{x^{2}}{2} ∏_{q∈Q^{(k)}} (1 − \frac{q^{k} − 1}{(q^{k+1} − 1)q} ) + o(x^{1+ε}).

In particular, when k = 1,

∑_{n≤x} φ_{1}(n) ∼ \frac{x^{2}}{2} ∏_{q∈Q^{(1)}} (1 − \frac{1}{q(q + 1)}) = 0.3289358388 … x^{2},

like in [6], the constant has been computed in [10]. If k → ∞ we arrive again at the classical expression (64).

2. The summatory function for sums of k-divisors.

Consider ∑_{n≤x} σ_{k}(n) where σ_{k}(n) is the sum of k-divisors of n. Analogously to Lemma 2 we obtain from (27) the following result for the function ν_{k}(x, d) from (58):

ν_{k}(x, d) = \frac{x^{2}}{2d^{∗}} + o(x^{1+ε}),  (65)

where

d^{∗} = ∏_{q {| \atop k} d} \frac{q^{k+1} − 1}{q^{k+1−d_{q}^{(k)}} − 1},  (66)

and d_{q}^{(k)} is defined by the factorization (6) for n = d. Furthermore,

∑_{n≤x} σ_{k}(n) = ∑_{n≤x} ∑_{d {| \atop k} n} \frac{n}{d} = ∑_{n≤x} n ∑_{d {| \atop k} n} \frac{1}{d} =

= ∑_{d≤x} \frac{1}{d} ∑_{n≤x: d {| \atop k} n} n = ∑_{d≤x} \frac{ν_{k}(x, d)}{d} =

= ∑_{d≤x} \frac{1}{d} (\frac{x^{2}}{2d^{∗}} + o(x^{1+ε})) = \frac{x^{2}}{2} ∑_{i=1}^{∞} \frac{1}{ii^{∗}} + o(x^{1+ε}).

Setting in (13), θ(n) = \frac{1}{nn^{∗}} and noticing that by (66),

θ(q^{j}) = \frac{q^{k−j+1} − 1}{(q^{k+1} − 1)q^{j}} , j = 1, 2, …, k,

we find

∑_{n≤x} σ_{k}(n) = \frac{x^{2}}{2} ∏_{q∈Q^{(k)}} (1 + \frac{q^{k+1}}{q^{k+1} − 1} ∑_{j=1}^{k} \frac{1}{q^{2j}} − \frac{1}{q^{k+1} − 1} ∑_{j=1}^{k} \frac{1}{q^{j}} ) + o(x^{1+ε}) =

= \frac{x^{2}}{2} ∏_{q∈Q^{(k)}} (1 + \frac{q^{k} − 1}{q^{k}(q^{2} − 1)}) + o(x^{1+ε}).

In particular, when k = 1,

∑_{n≤x} σ_{1}(n) ∼ \frac{x^{2}}{2} ∏_{q∈Q^{(1)}} (1 + \frac{1}{q(q + 1)}) = 0.7307182421 … x^{2},

coinciding with [6, 10]. When k → ∞ we obtain a result from [10],

∑_{n≤x} σ(n) ∼ \frac{x^{2}}{2} ∏_{p∈P} (1 + \frac{1}{p^{2} − 1}) = \frac{ζ(2)}{2}x^{2} = \frac{π^{2}}{12}x^{2}.

3. The numbers k-free from the (i + 1)-st powers.

Consider the sequence S_{k}(i) of numbers in k-arithmetics for which in the canonical representation (6) only the powers not exceeding i are allowed, i ≤ k − 1. Let us find the asymptotics for the sum, ∑_{n∈S_{k}^{(i)}} 1. Using inclusion-exclusion we have

∑_{n∈S_{k}^{(i)}} 1 = ⌊x⌋ − ∑_{q≤x} ⌊\frac{x}{q^{i+1}} ⌋^{(k)} + ∑_{q_{1}<q_{2}≤x} ⌊\frac{x}{q_{1}^{i+1}q_{2}^{i+1}} ⌋^{(k)} − … =

= ∑_{n≤x} ∑_{d^{i+1} {| \atop k} n} μ_{k}(d) = ∑_{d≤x^{\frac{1}{i+1}}} μ_{k}(d) ∑_{n≤x: d^{i+1} {| \atop k} n} 1 =

= ∑_{d≤x^{\frac{1}{i+1}}} μ_{k}(d) ⌊\frac{x}{d^{i+1}} ⌋^{(k)} = ∑_{d≤x^{\frac{1}{i+1}}} μ_{k}(d) (\frac{x}{(d^{i+1})^{∗}} + o(x^{ε})) ,

where the last equality is by Theorem 2. Therefore,

∑_{n∈S_{k}^{(i)}} 1 = x ∑_{d≤x^{\frac{1}{i+1}}} \frac{μ_{k}(d)}{(d^{i+1})^{∗}} + o (x^{\frac{1}{i+1} +ε}) = x ∑_{d=1}^{∞} \frac{μ_{k}(d)}{(d^{i+1})^{∗}} + o (x^{\frac{1}{i+1} +ε}) .

Since \frac{1}{(n^{i+1})^{∗}} is a k-multiplicative function for a fixed i, by (14) we conclude that

∑_{n∈S_{k}^{(i)}} 1 = x ∏_{q∈Q^{(k)}} (1 − \frac{q^{k−i} − 1}{q^{k+1} − i}) + o (x^{\frac{1}{i+1} +ε}) .

In particular, when k → ∞ we obtain the known result, cf. [21],

∑_{n∈S_{∞}^{(i)}} 1 ∼ x ∏_{p∈P} (1 − \frac{1}{p^{i+1}} ) = \frac{x}{ζ(i + 1)}.

4. k-complete numbers.

A number n is called k-complete if in its factorization (6) at least one k-prime has power k. Let F_{k}(x) be the number of k-complete numbers not exceeding x. For k = 1 clearly F_{1}(x) = ⌊x⌋ − 1. Using inclusion-exclusion, for k ≥ 2, we deduce

F_{k}(x) = − ∑_{n≤x^{\frac{1}{k}}} ∑_{d>1: d^{k} {| \atop k} n} μ_{k}(d) = ⌊x^{\frac{1}{k}} ⌋ − ∑_{n≤x^{\frac{1}{k}}} ∑_{d≥1: d^{k} {| \atop k} n} μ_{k}(d) =

= ⌊x^{\frac{1}{k}} ⌋ − ∑_{1≤d≤x^{\frac{1}{k}}} μ_{k}(d) ∑_{n≤x^{\frac{1}{k}}: d^{k} {| \atop k} n} 1 =

= ⌊x^{\frac{1}{k}} ⌋ − ∑_{1≤d≤x^{\frac{1}{k}}} μ_{k}(d) ⌊\frac{x^{\frac{1}{k}}}{d^{k}} ⌋^{(k)} =

= ⌊x^{\frac{1}{k}} ⌋ − ∑_{1≤d≤x^{\frac{1}{k}}} (μ_{k}(d)\frac{x^{\frac{1}{k}}}{(d^{k})^{∗}} + o(x^{ε})) ,

where the last equality is due to Theorem 2. Furthermore,

F_{k}(x) = ⌊x^{\frac{1}{k}} ⌋ − x^{\frac{1}{k}} ∑_{1≤d≤x^{\frac{1}{k}}} \frac{μ_{k}(d)}{(d^{k})^{∗}} + o(x^{\frac{1}{k} +ε}) =

= x^{\frac{1}{k}} (1 − ∑_{d=1}^{∞} \frac{μ_{k}(d)}{(d^{k})^{∗}}) + o(x^{\frac{1}{k} +ε}).

Since (n^{k})^{∗} is k-multiplicative, then by (14) for θ(n) = (n^{k})^{∗} we have finally for k ≥ 2,

F_{k}(x) = x^{\frac{1}{k}} (1 − ∏_{q∈Q^{(k)}} (1 − \frac{q − 1}{q^{k+1} − 1})) + o(x^{\frac{1}{k} +ε}).

8. Relations Between φ_{k}(n) and φ(n)

Since for all n and k we have φ_{k}(n) ≥ φ(n), it is of interest to study the equation

φ_{k}(n) − φ(n) = c,  (67)

for a nonnegative constant c.

Theorem 7 For any nonnegative integer c the equation (67) has an infinite number of solutions.

Proof. 1) Let c = 0. Assume n = p^{a}, where p is a prime, a ≥ 1. Let (k + 1)^{m−1} ≤ a ≤ (k + 1)^{m}, and a has the following representation in the basis k + 1:

a = (α_{m−1}, α_{m−2}, …, α_{0})_{k+1}, 0 ≤ α_{i} ≤ k, α_{m−1} ≥ 1.

Let us demonstrate that φ_{k}(p^{a}) = φ(p^{a}) if and only if all α_{i} ≥ 1, i = 0, 1, …, m − 2. Indeed, let there exist j ≤ m − 2 such that α_{j} = 0. Then p^{(k+1)^{j}} ≤ p^{(k+1)^{m−2}} < p^{a}, but (p^{(k+1)^{j}}, p^{a})_{k} = 1. Therefore, φ_{k}(p^{a}) > φ(p^{a}), and we are done. In the opposite

direction, if φ_{k}(p^{a}) > φ(p^{a}), then there exists j ≤ m − 2, for which (p^{(k+1)^{j}}, p^{a})_{k} = 1, but then α_{j} = 0. In particular, if α_{0} = α_{1} = … = α_{m−1} = 1 then, by the above claim, for the number a = 1 + (k + 1) + (k + 1)^{2} + … + (k + 1)^{m−1} = \frac{(k+1)^{m}−1}{k} we have

φ_{k} (p^{\frac{1}{k} ((k+1)^{m}−1)}) = φ (p^{\frac{1}{k} ((k+1)^{m}−1)})

for every prime p and integer m.

2) Let now c ≥ 1. It is well known, see e.g. [14], that for any ε > 0 there exists x_{0}(ε) such that for every x > x_{0}(ε) between x and (1 + ε)x there is a prime. Set ε = \frac{1}{c}. Choose

a prime p > max (\frac{x_{0}(\frac{1}{c})}{c}, c), and set x = cp. Then x > x_{0} (\frac{1}{c}). Therefore, between cp

and (1 + \frac{1}{c}) cp = (c + 1)p, there is a prime. Let us denote it by q: cp < q < (c + 1)p. We will show now that

φ_{k}(p^{k}q) = φ(p^{k}q) + c.  (68)

Indeed, since c < p, the numbers

p^{k+1}, 2p^{k+1}, …, cp^{k+1},

are mutually k-prime with p^{k}q. Moreover cp^{k+1} < p^{k}q, but (c+1)p^{k+1} > p^{k}q. This implies (68). The theorem is proved since for every c there exists an infinite set of possibilities for the choice of relevant p and q. □

Let us prove another statement about the intermediate position of φ_{k}(n) between φ(n) and n.

Theorem 8

lim inf_{n→∞} \frac{φ_{k}(n)}{n} = 0, lim sup_{n→∞} \frac{φ_{k}(n)}{φ(n)} = ∞.

Proof. Set n = n_{m} = ∏_{i=1}^{m} p_{i}, m ≥ 1, where p_{n} is the n-th prime. By Theorem 5

\frac{φ_{k}(n_{m})}{n_{m}} = ∏_{i=1}^{m} (1 + \frac{1}{p_{i}} + … + \frac{1}{p_{i}^{k}} )^{−1} + o (n_{m}^{−1+ε}) .  (69)

We have

∏_{i=1}^{m} (1 + \frac{1}{p_{i}} + … + \frac{1}{p_{i}^{k}} ) ≥ ∏_{i=1}^{m} (1 + \frac{1}{p_{i}} ) =

= \begin{matrix}∏ & {m \atop i=1} & (1 − \frac{1}{p_{i}^{2}} ) \\ ∏ & {m \atop i=1} & (1 − \frac{1}{p_{i}} ) \end{matrix} = \frac{e^{γ}}{ζ(2)} ln p_{m},

where for the last equality see [14], and γ is the Euler constant. Thus (69) yields the first statement of the theorem.

Furthermore, for n = n_{m}^{k+1} we deduce

\frac{φ_{k}(n_{m}^{k+1})}{φ(n_{m}^{k+1})} = \frac{∏_{i=1}^{m} (1 + \frac{1}{p_{i}^{k+1}} + … + _{\frac{1}{p_{i}^{k(k+1)}}} )^{−1} + o (n_{m}^{(k+1)(−1+ε)})}{∏_{i=1}^{m} (1 − \frac{1}{p_{i}} )}.  (70)

Since

\begin{matrix}∏ & {m \atop i=1} & (1 + \frac{1}{p_{i}^{k+1}} + … + _{\frac{1}{p_{i}^{k(k+1)}}} ) & −1 \\ ∏ & {m \atop i=1} & (1 − \frac{1}{p_{i}} ) \end{matrix} > \begin{matrix}∏ & {m \atop i=1} & (1 − \frac{1}{p_{i}^{k+1}} ) \\ ∏ & {m \atop i=1} & (1 − \frac{1}{p_{i}} ) \end{matrix} = \frac{e^{γ}}{ζ(k + 1)} ln p_{m},

(70) yields the second statement of the theorem. □

Furthermore, let us show that the following result is valid.

Theorem 9 For any natural number k,

lim inf_{n→∞} \frac{φ_{k}(n) ln ln n}{n} = e^{−γ},  (71)

where γ is the Euler constant.

Proof. The statement of the theorem is well known in the conventional case k = ∞. Since for every natural k we have φ_{k}(n) ≥ φ(n), we conclude

lim inf_{n→∞} \frac{φ_{k}(n) ln ln n}{n} ≥ e^{−γ}.

Thus, to prove the theorem it is sufficient to present a sequence {n_{m}} on which the equality holds. We will demonstrate that the sequence

n_{m} = ∏_{q∈Q^{(k)},q≤ln m} q  (72)

satisfies the requirement. Notice that for k-primes we have

∏_{q∈Q^{(k)},q≤n} q ∼ e^{n+o(n)}.  (73)

Consequently for the sequence (72) we have

n_{m} ∼ e^{ln m+o(ln m)} = m^{1+o(1)}.  (74)

Using (74) and Theorem 5 we find

\frac{φ_{k}(n_{m}) ln ln n_{m}}{n_{m}} = (ln ln n_{m}) ∏_{q≤ln m} (1 + \frac{1}{q} + … + \frac{1}{q_{k}} )^{−1} + O(n_{m}^{−1+ε}) =

= (ln ln n_{m}) ∏_{q≤ln m} ((1 − \frac{1}{q^{k+1}} )^{−1} (1 − \frac{1}{q})) + O(n_{m}^{−1+ε}) =

= (ln ln n_{m}) ∏_{q≤ln m} (1 − \frac{1}{q^{k+1}} )^{−1} ∏_{p≤ln m} (1 − \frac{1}{p}) ·

· (\begin{matrix}∏ & q≤ln m & (1 − \frac{1}{q}) \\ ∏ & p≤ln m & (1 − \frac{1}{p}) \end{matrix}) + O(n_{m}^{−1+ε}).

However, from the definition of the set Q^{(k)} we have that

\begin{matrix}∏ & q≤ln m & (1 − \frac{1}{q}) \\ ∏ & p≤ln m & (1 − \frac{1}{p}) \end{matrix} = ∏_{q≤(ln m)^{\frac{1}{k+1}}} (1 − \frac{1}{q^{k+1}} ) .  (75)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A33 24

Thus,

\frac{φ_{k}(n_{m}) ln ln n_{m}}{n_{m}} = (ln ln n_{m}) ∏_{(ln m)^{\frac{1}{k+1}} ≤q≤ln m} (1 − \frac{1}{q^{k+1}} )^{−1} ∏_{p≤ln m} (1 − \frac{1}{p}) + O(n_{m}^{−1+ε}). (76)

It is well known (see e.g. [14]) that

∏_{p≤x} (1 − \frac{1}{p}) = \frac{e^{−γ}}{ln x} (1 + O (e^{−c\sqrt{ln x}})) ,  (77)

where c is a positive constant.

Let us also estimate

∏_{(ln m)^{\frac{1}{k+1}} ≤q≤ln m} (1 − \frac{1}{q^{k+1}} )^{−1} .

Since for 0 < x < 1 we have

− ln(1 − x) = ∫_{0}^{x} \frac{dt}{1 − t} ≤ \frac{x}{1 − x},

for m large enough we deduce

ln ∏_{(ln m)^{\frac{1}{k+1}} ≤q≤ln m} (1 − \frac{1}{q^{k+1}} )^{−1} ≤ ∑_{(ln m)^{\frac{1}{k+1}} ≤q≤ln m} \frac{1}{(q − 1)^{k+1}} ≤

≤ ∫_{(ln m)^{\frac{1}{k+1}} −1}^{ln m−1} \frac{dt}{t^{k+1}} = O ((ln m)^{− \frac{k}{k+1}} ) .

Therefore,

∏_{(ln m)^{\frac{1}{k+1}} ≤q≤ln m} (1 − \frac{1}{q^{k+1}} )^{−1} = 1 + O ((ln m)^{− \frac{k}{k+1}} ) .  (78)

Taking into account that from (74) it follows that

\frac{ln ln n_{m}}{ln ln m} = 1 + o (\frac{1}{ln ln m}) ,

we deduce from (76), (77) for x = ln m, and (78) that

\frac{φ_{k}(n_{m}) ln ln n_{m}}{n_{m}} = e^{−γ} (1 + O (\frac{1}{ln ln m})) .

□

Let us also mention that since

e^{c\sqrt{ln x}} = o (x^{\frac{k}{k+1}} ) ,

i.e., x^{− \frac{k}{k+1}} = o(e^{−c\sqrt{ln x}}), it follows from (75), (77) and (78) that the following equality, being a k-generalization of (77), holds:

∏_{q≤x} (1 − \frac{1}{q}) = \frac{e^{−γ}}{ln x} ( ∏_{q∈Q^{(k)}} (1 − \frac{1}{q^{k+1}} )) (1 + O(e^{−c\sqrt{x}})) .  (79)

Applying ln to (79), after simple transformations we find

∑_{q≤x} \frac{1}{q} = ln ln x+γ − ∑_{q∈Q^{(k)}} ∑_{j≥2} \frac{1}{jq^{j}} + ∑_{q∈Q^{(k)}} ∑_{j≥1} \frac{1}{jq^{(k+1)j}} +O(e^{−c\sqrt{ln x}}) = ln ln x+B_{k} +O(e^{−c\sqrt{ln x}}),

where

B_{k} = γ + ∑_{q∈Q^{(k)}} \frac{1}{q^{k+1}} − ∑_{q∈Q^{(k)}} ∑_{j≥2} \frac{1}{jq^{j}} (1 − \frac{1}{q^{kj}} ) .

The latter for k = ∞ becomes

B = γ − ∑_{p} ∑_{j≥2} \frac{1}{jp^{j}} = 0.2614972128 …

and is known as the prime reciprocal constant, the Mertens constant, the Kronecker constant, or the Hadamard-de La Vallée-Poussin constant.

9. Analogs of the Wirsing and Delange Theorems

Since the k-multiplicative functions are multiplicative as well in the conventional sense, all the theorems about multiplicative functions are formally valid for k-multiplicative functions. However, it is worth noticing that from the point of view of the standard arithmetics the k-multiplicative functions are ”under-defined” since they are defined only on a small subset of the set of prime numbers. For example, when k = 2 this subset is {p, p^{2}, p^{3}, p^{6}, p^{9}, p^{18}, …} and the direct application of known asymptotic theorems about multiplicative functions seems to be impossible. Therefore, the question about k-analogs of such theorems is non-trivial. For this goal we have chosen the well known theorems of Wirzing and Delange. Note that the condition on k-multiplicativity allows an essential simplification of the statements of these theorems.

Theorem 10 a) (Wirzing, see [13]) Let h(n) be a multiplicative function satisfying

1) h(n) ≥ 0, n = 1, 2, …;

2) h(p^{ν}) ≤ c_{1}c_{2}^{ν}, p ∈ P, ν = 1, 2, …, c_{2} < 2;

3) ∑_{p≤x,p∈P} h(p) = (τ + o(1))\frac{x}{ln x}, where τ ≥ 0, is a constant.

Then, for x → ∞,

∑_{n≤x} h(n) = (\frac{e^{−γτ}}{Γ(τ)} + o(1)) \frac{x}{ln x} ∏_{p≤x,p∈P} (1 + \frac{h(p)}{p} + \frac{h(p^{2})}{p^{2}} …)  (80)

where Γ(x) is the gamma-function, and γ is the Euler constant.

b) (k-analog) Let h(n) be a k-multiplicative function satisfying 1) h(n) ≥ 0, n = 1, 2, …;

2) h(q^{r}) ≤ c, q ∈ Q^{(k)}, r = 1, 2, …, k;

3) ∑_{q≤x,q∈Q^{(k)}} h(q) = (τ + o(1))\frac{x}{ln x}, where τ ≥ 0, is a constant. Then,

∑_{n≤x} h(n) = (\frac{e^{−γτ}}{Γ(τ)} + o(1)) \frac{x}{ln x} ∏_{q≤x,q∈Q^{(k)}} (1 + \frac{h(q)}{q} + … + \frac{h(q^{k})}{q^{k}}) .  (81)

Theorem 11 a) (Delange, see [13]) Let h(n) be a multiplicative function such that 1) |h(n)| ≤ 1, n = 1, 2, …;

2) the series ∑_{p∈P} \frac{1−h(p)}{p} converges. Then,

lim_{n→∞} \frac{1}{n} ∑_{m=1}^{n} h(m) = ∏_{p∈P} (1 − \frac{1}{p}) (1 + ∑_{j=1}^{∞} \frac{h(p^{j})}{p^{j}}) .  (82)

b) (k-analog) Let h(n) be a k-multiplicative function satisfying 1) |h(n)| ≤ 1, n = 1, 2, …;

2) the series ∑_{q∈Q^{(k)}} \frac{1−h(q)}{q} converges. Then,

lim_{n→∞} \frac{1}{n} ∑_{m=1}^{n} h(m) = ∏_{q∈Q^{(k)}} \frac{q − 1}{q^{k+1} − 1} ∑_{i=0}^{k} q^{k−i}h(q^{i}).  (83)

Proof. We just prove the k-analog of the Delange theorem, the proof the previous theorem is similar. Notice that under the conditions of b) of Theorem 11, the conditions of a) are also valid. We have

1 − \frac{1}{p} = \frac{1 − \frac{1}{p}}{1 − \frac{1}{p^{k+1}}} · \frac{1 − \frac{1}{p^{k+1}}}{1 − \frac{1}{p^{(k+1)^{2}}}} · \frac{1 − \frac{1}{p^{(k+1)^{2}}}}{1 − \frac{1}{p^{(k+1)^{3}}}} …

= ∏_{ℓ=0}^{∞} (1 + \frac{1}{p^{(k+1)^{ℓ}}} + \frac{1}{p^{2(k+1)^{ℓ}}} + … + \frac{1}{p^{k(k+1)^{ℓ}}} )^{−1}

= ∏_{q∈Q^{(k)}: p|q} (1 + \frac{1}{q} + \frac{1}{q^{2}} + … + \frac{1}{q^{k}} )^{−1} .  (84)

Further, using the k-multiplicativity of h(n) for a fixed p ∈ P we have

1 + ∑_{j=1}^{∞} \frac{h(p^{j})}{p^{j}} = ∏_{q∈Q^{(k)}: p|q} (1 + \frac{h(q)}{q} + … + \frac{h(q^{k})}{q^{k}}) ,

and consequently

∏_{p∈P} (1 + ∑_{j=1}^{∞} \frac{h(p^{j})}{p^{j}}) = ∏_{q∈Q^{(k)}} (1 + \frac{h(q)}{q} + … + \frac{h(q^{k})}{q^{k}}) .  (85)

Substituting (84) and (85) into (82) we find:

lim_{n→∞} \frac{1}{n} ∑_{m=1}^{n} h(m) = ∏_{q∈Q^{(k)}} (1 + \frac{1}{q} + \frac{1}{q^{2}} + … + \frac{1}{q^{k}} )^{−1} (1 + \frac{h(q)}{q} + \frac{h(q^{2})}{q^{2}} + … + \frac{h(q^{k})}{q^{k}}) ,

and (83) follows. □

10. Perfect Numbers

A number n is called k-perfect if it equals to the sum of its proper positive k-divisors. It follows from (6) that any k-perfect number satisfies

σ_{k}(n) = ∏_{q {| \atop k} n} \frac{q^{n_{q}+1} − 1}{q − 1} = 2n,  (86)

where σ_{k}(n) is the sum of k-divisors of n. For example, 28 is k-perfect for all k ≥ 2.

Consider a sequence S = {n_{k}}_{k∈T} , such that n_{k} is a k-perfect number of the form

n_{k} = 2^{k+1}(2l − 1),  (87)

where (2l − 1) possesses the conventional factorization (1) into primes having powers not exceeding k, and T is the set of such k for which there exists at least one k-perfect number of the form (87). We will address such numbers as being of type S. Hence by (86) for n_{k} we have

σ_{k}(n_{k}) = (2^{k+1} + 1) ∏_{p|2l−1} \frac{p^{n_{p}+1} − 1}{p − 1} = 2^{k+2}(2l − 1).

Example 7 In the following table we present examples of k-perfect numbers of type S for every k, 1 ≤ k ≤ 10.

\begin{matrix}k & n \\ 1 & 2^{2} · 3 · 5 \\ 2 & 2^{3} · 3^{2} · 7 · 13 \\ 3 & 2^{4} · 3^{2} · 7 · 13 · 17 \\ 4 & 2^{5} · 3^{2} · 7 · 11 · 13 \\ 5 & 2^{6} · 3 · 5 · 7 · 13 \\ 6 & 2^{7} · 3^{2} · 7 · 11 · 13 · 43 \\ 7 & 2^{8} · 3^{2} · 7 · 11 · 13 · 43 · 257 \\ 8 & 2^{9} · 3^{3} · 5^{2} · 19 · 31 \\ 9 & 2^{10} · 3 · 5^{2} · 7 · 31 · 41 \\ 10 & 2^{11} · 3^{3} · 5^{2} · 19 · 31 · 683 \end{matrix}

Notice that in the examples with the pairs of k-perfect numbers of type S for k_{1} = 2, k_{2} = 3; k_{1} = 2, k_{2} = 4; k_{1} = 4, k_{2} = 6; k_{1} = 6, k_{2} = 7; k_{1} = 8, k_{2} = 10; the ratio of the k-perfect numbers in these pairs are 2^{k_{2}−k_{1}}p where p is a prime not dividing the first number in the pair. The corresponding primes in the examples are 17, 11, 43, 257, and 683. This hints at a general description of all such pairs of type S.

Theorem 12 Let n_{1} be a k-perfect number of type S. For n_{2} to be a (k + m)-perfect number of type S having the form

n_{2} = 2^{m}n_{1}p,

where p is a prime, p does not divide n_{1}, it is necessary and sufficient that one of the following conditions is valid

1. m = 1, p is a Fermat prime of the form 2^{k+2} + 1;

2. m = 2, p is a prime of the form \frac{2^{k+3}+1}{3} for an even k.

Theorem 12 claims that there are no considered pairs of k-perfect numbers of type S if k_{2} − k_{1} ≥ 3. Under validity of the conjecture that there is a finite number of Fermat primes, the number of considered pairs satisfying k_{2} − k_{1} = 1 is also finite. Finally, if k_{2} − k_{1} = 2, notice that \frac{2^{k+3}+1}{3} can be prime only if k + 3 is prime. It is conjectured in [2] that the number of primes having form \frac{2^{p}+1}{3} is infinite and, moreover, the number of such primes not exceeding x is approximately e^{γ} log_{2} x, γ is the Euler constant.

For the proof of Theorem 12 we will need the following result.

Lemma 3 The Diophantine equation

2^{k+m+1} + 1 = n(2^{m} − 1),  (88)

for k ≥ 1, m ≥ 1, n ≥ 1, has only the following solutions:

m = 1, k ∈ ℕ, n = 2^{k+2} + 1,  (89)
m = 2, k = 2r, r ∈ ℕ, n = \frac{2^{k+3} + 1}{3}.  (90)

Proof. The case m = 1 is trivial. Assume m ≥ 2. Let

k = rm + s, 0 ≤ s ≤ m − 1.  (91)

We have

(2^{m} − 1) ∑_{i=0}^{⌊k/m⌋} 2^{k−mi} = 2^{k−rm}(2^{m(r+1)} − 1) = 2^{k+m} − 2^{s}.

Therefore,

2^{k+m} ≡ 2^{s} mod(2^{m} − 1),

and

2^{k+m+1} + 1 ≡ 2^{s+1} + 1 mod(2^{m} − 1).

Now, from (88) it follows that

2^{s+1} + 1 ≡ 0 mod(2^{m} − 1).  (92)

Since 2(2^{m} − 1) > 2^{m} + 1 ≥ 2^{s+1} + 1, (92) is possible only if 2^{s+1} + 1 = 2^{m} − 1, or 2^{m−1} − 2^{s} = 1. The last relation can be valid only if m = 2, s = 0. Therefore, by (91), k = 2r. This gives (90). □

Proof of Theorem 12. Let n_{1} be a k-perfect number of type S, i.e.

n_{1} = 2^{k+1}(2l − 1),  (93)

where the factorization (1) of (2l − 1) has powers of the primes not exceeding k. This means that

σ_{k}(2l − 1) = σ(2l − 1).

By (86) specified for n_{1} and by the k-multiplicativity of σ_{k}(n) we have

(2^{k+1} + 1)σ(2l − 1) = 2^{k+2}(2l − 1).  (94)

Furthermore, by (86), the number

n_{2} = 2^{k+m+1}(2l − 1)p, p |̸n_{1},  (95)

is a (k + m) -perfect number of type S if and only if

(2^{k+m+1} + 1) σ(2l − 1)(p + 1) = 2^{k+m+2}(2l − 1)p.  (96)

Dividing (96) by (94) we find

\frac{(2^{k+m+1} + 1)(p + 1)}{2^{k+1} + 1} = 2^{m}p,

yielding

p = \frac{2^{k+m+1} + 1}{2^{m} − 1}.

By Lemma 3 only two possibilities are relevant:

1) m = 1, p = 2^{k+2} + 1.

Clearly, k + 2 cannot have odd prime factors. Therefore, k + 2 = 2^{ν−1}, ν ∈ ℕ. Thus, p = 2^{2^{ν−1}} + 1, i.e. is a Fermat prime.

2) m = 2, p = \frac{2^{k+3}+1}{3}.

In this case, k + 3 is prime.

Let us demonstrate, in the opposite direction, that if n_{1} from (93) is k-perfect, then n_{2} from (95) for

p = 2^{k+2} + 1  (97)

is (k + 1)-perfect, and for

p = \frac{2^{k+3} + 1}{3}, k even,  (98)

is (k + 2)-perfect.

Indeed, when (97) holds, multiplying (94) by 2(2^{k+2} + 1) = 2p, and noticing that 2(2^{k+1} + 1) = p + 1, we find

(2^{k+2} + 1)(p + 1)σ(2l − 1) = 2^{k+3}(2l − 1)p,

corresponding to (96) for m = 1. Therefore, the number n_{2} is (k + 1)-perfect for m = 1.

Under (98), multiplying (94) by 4\frac{2^{k+3}+1}{3} = 4p, and noticing that \frac{4}{3}(2^{k+1} + 1) = p + 1, we find

(2^{k+3} + 1)(p + 1)σ(2l − 1) = 2^{k+4}(2l − 1)p,

corresponding to (96) for m = 2. Therefore, n_{2} is (k + 2)-perfect for m = 2. □

Example 8 For k = 14 the number 2^{16} + 1 is a Fermat prime. It is easily checked using (86) that

2^{15} · 3^{4} · 7 · 11^{3} · 31 · 61 · 83 · 331  (99)

is 14-prime. Therefore using Theorem 12 with m = 1 we find the following 15-perfect number

2^{16} · 3^{4} · 7 · 11^{3} · 31 · 61 · 83 · 331 · 65537.

When k = 10, the number \frac{2^{13}+1}{3} = 2731, is prime. Using Theorem 12 for m = 2, we have, along with the last number in the table of Example 7, the following 12-perfect number:

2^{13} · 3^{3} · 5^{2} · 19 · 31 · 683 · 2731.  (100)

Furthermore, using 14-perfect number (99), and taking into account that \frac{2^{17}+1}{3} = 43691 is prime, we find analogously the following 16-perfect number:

2^{17} · 3^{4} · 7 · 11^{3} · 31 · 61 · 83 · 331 · 43691,

which in turn yields, since \frac{2^{19}+1}{3} = 174763 is prime, the following 18-perfect number

2^{19} · 3^{4} · 7 · 11^{3} · 31 · 61 · 83 · 331 · 43691 · 174763.

Example 9 Notice that for the same k we may have different k-perfect numbers of type S. For example, when k = 8, along with the number given in Example 7, we have another 8-perfect number

2^{9} · 3^{4} · 7 · 11^{2} · 19^{2} · 127.

Therefore, by Theorem 12, we find a 10-perfect number which differs from the corresponding number in Example 7,

2^{11} · 3^{4} · 7 · 11^{2} · 19^{2} · 127 · 683,

which in turn yields yet another 12-perfect number different from (100),

2^{13} · 3^{4} · 7 · 11^{2} · 19^{2} · 127 · 683 · 2731.

11. Mixed Multiplicative Factorizations

Consider an infinite sequence of positive integers k = (k_{1}, k_{2}, …). Let us introduce the corresponding multiplicative basis

Q^{(k)} = {p_{i}^{(k_{i}+1)^{j−1}} |p_{i} being the i-th prime, i, j ∈ ℕ} .  (101)

Analogously to (6) we find the unique factorization for every n ∈ ℕ in this basis:

n = ∏_{q∈Q^{(k)}} q^{n_{q}^{(k)}},  (102)

where n_{q}^{(k)} ≤ k_{i}, if q is divisible by p_{i}. Note that some of k_{i}’s can be assumed to be ∞.

Analogously we introduce the notion of divisibility m{| \atop k}n, the greatest common divisor

(m, n)_{k} = max_{d {| \atop k} m,d {| \atop k} n} d,

and all the above-defined functions. For example, the Möbius function is defined as

μ_{k}(n) = \{ \begin{matrix}(−1)^{∑_{q {| \atop k} n} 1}, & if all n_{q}^{(k)} = 1 \\ 0, & otherwise. \end{matrix}

Furthermore,

⌊\frac{x}{m}⌋^{(k)} = ∑_{n≤x:m {| \atop k} n} 1,

φ_{k}(x, n) = ∑_{1≤j≤x:(j,n)_{k}=1} 1, φ_{k}(n) = φ_{k}(n, n).

Notice that from the proofs of Theorems 2 and 5 it follows that the asymptotic formula (53) is uniform also in k. Let I_{n} be the set of indices of the primes dividing n. We have the following generalizations of Theorems 5 and 6.

Theorem 13

φ_{k}(x, n) = κ_{k}(n)x + O ((nx)^{ε}) ,

where

κ_{k}(n) = ∏_{i∈I_{n}} ∏_{q {| \atop k_{i}} n: p_{i}|q} (1 + \frac{1}{q} + … + \frac{1}{q^{k_{i}}} )^{−1} .

Theorem 14

∑_{n≤x} φ_{k}(n) = a_{k}x^{2} + o (x^{1+ε}) ,

where

a_{k} = \frac{1}{2} ∏_{i=1}^{∞} ∏_{q∈Q^{(k)}: p_{i}|q} (1 − (\frac{q^{k_{i}} − 1}{q^{k_{i}+1} − 1})^{2}) .  (103)

Note that we have continuum of mixed multiplicative bases.

12. Open Problems

1. Find asymptotics for ∑_{n≤x} d_{k}(n) where d_{k}(n) is the number of k-factors of n (the Dirichlet k-divisors problem). It is well known that for k = ∞ by the classical result due to Dirichlet

∑_{n≤x} d(n) = x ln x + (2γ − 1)x + O (x^{\frac{1}{2}} ) ,  (104)

where γ is the Euler constant. For better estimates of the residual term see [8, 15] and references therein. When k = 1 the only known estimate [6] is

∑_{n≤x} d_{1}(n) = c_{1}x ln x + (2γ_{1} − c_{1})x + o (x^{\frac{1}{2} +ε}) ,

where

c_{1} = ∏_{q∈Q^{(1)}} (1 − \frac{1}{(q + 1)^{2}} ) = 0.73325055 …

and γ_{1} is a constant. It would be natural to conjecture that

∑_{n≤x} d_{k}(n) = c_{k}x ln x + (2γ_{k} − c_{k})x + o (x^{\frac{1}{2} +ε}) ,

so that

lim_{k→∞} c_{k} = 1, lim_{k→∞} γ_{k} = γ.

2. Find the sum of k-complete numbers not exceeding x (see Section 7).

3. A number n is called k-compact if in its k-factorization (6) all k-primes are pairwise mutually prime (in the conventional sense). In particular all natural numbers are ∞- compact. The following are open problems: a) find the number of k-compact numbers not exceeding x; b) find the sum of k-compact numbers not exceeding x.

4. a) Is the size of the union of the sets of k-perfect number of type S, k = 1, 2, … (see Section 10) infinite? In other words, whether the table of Example 7 has an infinite number of rows?

b) Is there a value k for which the set of k-perfect numbers of type S is empty? We conjecture that there is. For instance we do not know if there are 11-perfect and/or 13-perfect numbers of type S.

5. Estimate the least term of the sequence {n_{k}^{(c)}} and the density of this sequence (see Theorem 7).

6. a) Do we have for every k ∈ ℕ an infinite number of n such that φ_{k}(n) = nκ_{k}(n) (see Theorem 5 for x = n)? Notice that for n ≤ 1000 there are only 6 solutions to the equation φ_{1}(n) = nκ_{1}(n) [18], namely, 1, 6, 60, 120, 360, 816. b) For every x ≤ 1000, we have that the number of those n ≤ x for which nκ_{1}(n) > φ_{1}(n) is greater than the number of those not satisfying the inequality. For example, when x = 1000 the number of such n is 565. Is that true for all x?

7. For every pair of mutually prime m and n, find min_{t∈ℕ} ⌊\frac{nt}{mt}⌋ (see Section 4).

8. N. P. Romanov, see [14], proved that

∑_{n=2}^{∞} \frac{φ(n)}{n}x^{n} = \frac{6}{π^{2}} ∑_{n=1}^{∞} \frac{μ(n)}{n^{2}} ∏_{p|n,p∈P} (1 − \frac{1}{p^{2}} )^{−1} S_{n}(x),

where

S_{n}(x) = ∑_{ρ=ρ(n)} \frac{ρ^{2}x^{2}}{1 − ρx},

with the summation over all primitive n-th roots of unity. Find a k-analog of this identity for ∑_{n=2}^{∞} \frac{φ_{k}(n)}{n}x^{n}.

9. Is the set of constants a_{k} (see (103)) everywhere dense in the interval [a_{k_{1}}, a_{k_{2}}], where k_{1} = (∞, ∞, …) and k_{2} = (1, 1, …), i.e., in the interval

[\frac{3}{π^{2}} , \frac{1}{2} ∏_{q∈Q^{(1)}} (1 − \frac{1}{(q + 1)^{2}} )] = [0.303963551 …, 0.3666252769 …]?

13. Acknowledgement

We are grateful to the anonymous referee for valuable comments.

References

[1] G. E. Andrews, Theory of Partitions, Addison-Wesley, 1976.

[2] P. T. Bateman, J. L. Selfridge, amd S. S. Wagstaff, The new Mersenne conjecture, Amer. Math. Monthly, vol. 96, 1989, pp. 125–128.

[3] F. Beukers, The lattice points of n-dimensionl tetrahedra, Indag. Math., vol. 37, 1975, pp. 365–372.

[4] K. Chandrasekharan, Introduction to Analytic Number Theory, Springer-Verlag, 1968.

[5] G. L. Cohen, On an integer’s infinitary divisors, Math. Comput. vol. 54, 1990, pp.395–411.

[6] G. L. Cohen, and P. Hagis, Arithmetic functions associated with the infinitary divisors of an integer, Internat. J. Math. & Math. Sci., vol. 16, no. 2, 1993, pp. 373–384.

[7] H. Cohen, High precision computation of Hardy-Littlewood constants, preprint, see http://www.ufr-mi.u-bordeaux.fr/ ∼cohen/

[8] H. Iwaniec and E. Kowalski, Analytic Number Theory, AMS Colloquium Publications, 2004.

[9] S. R. Finch, Euler totient constants, in Mathematical Constants, Cambridge University Press, 2003, pp. 115–118.

[10] S. R. Finch, Unitarism and infinitarism, on-line http://pauillac.inria.fr/algo/csolve/try.pdf

[11] P. Moree, Approximation of singular series and automata, Manuscripta Math., vol. 101, no. 3, 2000, pp. 385–399.

[12] J. M. Pedersen, Tables of aliquot cycles, 2004, http://amicable.adsl.dk/aliquot/infper.txt

[13] A. G. Postnikov, Introduction to Analytic Number Theory, Translations of Mathematical Monographs, vol. 68, American Mathematical Society, Providence, RI, 1988.

[14] K. Prachar, Primzahlverteilung (The distribution of primes) Reprint of the 1957 original, Grundlehren der Mathematischen Wissenschaften, vol. 91, Springer-Verlag, Berlin-New York, 1978.

[15] D. Redmond, Number Theory, An Introduction, Marcel Dekker, 1996.

[16] V. S. Abramovich-Shevelev, On an analog of the Euler function, Proc. North-Caucasus Center Acad. Sci. USSR, no. 2, 1981, pp. 13–17 (In Russian).

[17] V. S. Shevelev, Factorization with distinct factors, Kvant, no. 5, 1983, p. 37 (In Russian).

[18] V. S. Shevelev, Multiplicative functions in the Fermi-Dirac arithmetic, Izv. VUZov Sev.-Kav. Reg. Est. Nauki, no. 4, 1996, pp. 28–43 (In Russian).

[19] N. J. A. Sloane, Sequence A007357/M4267 in The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/ njas/sequences/A007357.

[20] D. Suryanarayana, The number of k-ary divisors of an integer, Monatschr. Math. vol. 72, 1968, pp. 445–450.

[21] D. Suryanarayana, and V. Siva Rama Prasad, The number of k-free divisors of an integer, Acta Arithm., vol. 17, 1970/1971, pp. 345–354.

[22] E. Trost, Primzahlen, Birkhauser, Basel-Stuttgart, 1953 (In German).

[23] E. W. Weisstein, Infinitary perfect numbers, MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/InfinitaryPerfectNumber.html.