On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions

Colin Defant Department of Mathematics University of Florida Gainesville, FL 32611-8105 USA

                    cdefant@ufl.edu

Abstract

We begin by introducing an interesting class of functions, known as the Schemmel totient functions, that generalizes the Euler totient function. For each Schemmel totient function L_{m}, we define two new functions, denoted R_{m} and H_{m}, that arise from iterating L_{m}. Roughly speaking, R_{m} counts the number of iterations of L_{m} needed to reach either 0 or 1, and H_{m} takes the value (either 0 or 1) that the iteration trajectory eventually reaches. Our first major result is a proof that, for any positive integer m, the function H_{m} is completely multiplicative. We then introduce an iterate summatory function, denoted D_{m}, and define the terms D_{m}-deficient, D_{m}-perfect, and D_{m}-abundant. We proceed to prove several results related to these definitions, culminating in a proof that, for all positive even integers m, there are infinitely many D_{m}-abundant numbers. Many open problems arise from the introduction of these functions and terms, and we mention a few of them, as well as some numerical results.

1 Introduction

Throughout this paper, ℕ, ℕ_{0}, and ℙ will denote the set of positive integers, the set of nonnegative integers, and the set of prime numbers, respectively. For any function f, we will write f^{(1)} = f and f^{(k+1)} = f ∘ f^{(k)} for all k ∈ ℕ. The letter p will always denote a prime number. For any n ∈ ℕ, υ_{p}(n) will denote the unique nonnegative integer k such that p^{k} | n and p^{k+1} ∤ n. Finally, in the canonical prime factorization ∏_{i=1}^{r} p_{i}^{α_{i}} of a positive integer, it is understood that, for all distinct i, j ∈ {1, 2, …, r}, we have p_{i} ∈ ℙ, α_{i} ∈ ℕ, and p_{i} ≠ p_{j}.

The well-known Euler ϕ function is defined to be the number of positive integers less than or equal to n that are relatively prime to n. For each m ∈ ℕ, the Schemmel totient function L_{m}(n) is defined as the number of positive integers k ≤ n such that gcd(k + s, n) = 1 for all s ∈ {0, 1, …, m − 1} [2]. In particular, L_{1} = ϕ. For no reason other than a desire to avoid cumbersome notation and the possibility of dealing with undefined objects such as L_{2}^{(2)}(6), we will define L_{m}(0) to be 0 for all positive integers m.

For any integer n > 1, let p(n) be the smallest prime number that divides n. Schemmel [7] showed that, for any positive integer m, L_{m} is multiplicative. Thus, L_{m}(1) = 1. Furthermore, for n > 1,

L_{m}(n) = \begin{cases}0, & if p(n) ≤ m; \\ n ∏_{p|n} (1 − \frac{m}{p}) , & if p(n) > m. \end{cases}  (1)

Letting ∏_{i=1}^{r} p_{i}^{α_{i}} be the canonical prime factorization of n, we may rewrite the above formula as

L_{m}(n) = \begin{cases}0, & if p(n) ≤ m; \\ ∏_{i=1}^{r} p_{i}^{α_{i}−1}(p_{i} − m), & if p(n) > m \end{cases}  (2)

for n > 1.

In 1929, S. S. Pillai introduced a function that counts the number of iterations of the Euler ϕ function needed to reach 1 [5]. In the following section, we generalize Pillai’s function via the Schemmel totient functions. Then, in the third section, we generalize the concept of perfect totient numbers with the introduction, for each positive integer m, of a function D_{m}, which sums the first R_{m} iterates of L_{m}.

2 The functions R_{m} and H_{m}

We record the following propositions, which follow immediately from (2), for later use.

Proposition 1. For x, y, m ∈ ℕ, if x|y, then L_{m}(x)|L_{m}(y).

Repeatedly applying Proposition 1, we find

Proposition 2. For x, y, m, r ∈ ℕ, if x|y, then L_{m}^{(r)}(x)|L_{m}^{(r)}(y).

Proposition 3. For m, n ∈ ℕ, if m is even and n is odd, then either L_{m}(n) = 0 or L_{m}(n) is odd.

In addition, the following theorem is now quite easy to prove.

Theorem 4. For any prime number p and positive integer x,

L_{p−1}(px) = \begin{cases}L_{p−1}(x), & if p ∤ x; \\ pL_{p−1}(x), & if p|x. \end{cases}

Proof. If p ∤ x, it follows from the multiplicativity of L_{p−1} that L_{p−1}(px) = L_{p−1}(p)L_{p−1}(x) = L_{p−1}(x). If p|x, then we have

L_{p−1}(px) = L_{p−1} (p · p^{υ_{p}(x)} · \frac{x}{p^{υ_{p}(x)}} ) = L_{p−1} (p^{υ_{p}(x)+1}) L_{p−1} (\frac{x}{p^{υ_{p}(x)}} )

= p^{υ_{p}(x)}L_{p−1} (\frac{x}{p^{υ_{p}(x)}} ) = pL_{p−1} (p^{υ_{p}(x)}) L_{p−1} (\frac{x}{p^{υ_{p}(x)}} ) = pL_{p−1}(x).

Notice that, for any positive integers m and n with n > 1, we have L_{m}(n) < n and L_{m}(n) ∈ ℕ_{0}. It is easy to see that, by starting with a positive integer n and iterating the function L_{m} a finite number of times, we must eventually reach either 0 or 1. More precisely, there exists a positive integer k such that L_{m}^{(k)}(n) ∈ {0, 1}. This leads us to the following definitions.

Definition 5. For all m, n ∈ ℕ, let R_{m}(n) denote the least positive integer k such that L_{m}^{(k)}(n) ∈ {0, 1}. Furthermore, we define the function H_{m} by

H_{m}(n) = L_{m}^{(R_{m}(n))}(n).

Though the functions H_{m} only take values 0 and 1, they prove to be surprisingly interesting. For example, we can show that, for each positive integer m, H_{m} is a completely multiplicative function. First, however, we will need some definitions and preliminary results.

Definition 6. For m ∈ ℕ, we define the following sets:

P_{m} = {p ∈ ℙ : H_{m}(p) = 1}
Q_{m} = {q ∈ ℙ : H_{m}(q) = 0}
S_{m} = {n ∈ ℕ : q ∤ n ∀ q ∈ Q_{m}}

We define T_{m} to be the unique set of positive integers defined by the following criteria:

• 1 ∈ T_{m}.

• If p is prime, then p ∈ T_{m} if and only if p − m ∈ T_{m}.

• If x is composite, then x ∈ T_{m} if and only if there exist x_{1}, x_{2} ∈ T_{m} such that x_{1}, x_{2} > 1 and x_{1}x_{2} = x.

Lemma 7. Let k, m ∈ ℕ. If all the prime divisors of k are in T_{m}, then all the positive divisors of k (including k) are in T_{m}. Conversely, if k ∈ T_{m}, then every positive divisor of k is an element of T_{m}.

Proof. First, suppose that all the prime divisors of k are in T_{m}, and let d be a positive divisor of k. Then all the prime divisors of d are in T_{m}. Let d = ∏_{i=1}^{r} w_{i}^{α_{i}} be the canonical prime factorization of d. As w_{1} ∈ T_{m}, the third defining criterion of T_{m} tells us that w_{1}^{2} ∈ T_{m}. Then, by the same token, w_{1}^{3} ∈ T_{m}. Eventually, we find that w_{1}^{α_{1}} ∈ T_{m}. As w_{1}^{α_{1}}, w_{2} ∈ T_{m}, we have w_{1}^{α_{1}}w_{2} ∈ T_{m}. Repeatedly using the third criterion, we can keep multiplying by primes until we find that d ∈ T_{m}. This completes the first part of the proof. Now we will prove that if k ∈ T_{m}, then every positive divisor of k is an element of T_{m}. The proof is trivial if k is prime, so suppose k is composite. We will induct on Ω(k), the number of prime divisors (counting multiplicities) of k. If Ω(k) = 2, then, by the third defining criterion of T_{m}, the prime divisors of k must be elements of T_{m}. Therefore, if Ω(k) = 2, we are done. Now, suppose the result holds whenever Ω(k) ≤ h, where h > 1 is a positive integer. Consider the case in which Ω(k) = h + 1. By the third defining criterion of T_{m}, we can write k = k_{1}k_{2}, where 1 < k_{1}, k_{2} < k and k_{1}, k_{2} ∈ T_{m}. By the induction hypothesis, all of the positive divisors of k_{1} and all of the positive divisors of k_{2} are in T_{m}. Therefore, all of the prime divisors of k are in T_{m}. By the first part of the proof, we conclude that all of the positive divisors of k are in T_{m}.

Theorem 8. If m is a positive integer, then S_{m} = T_{m}.

Proof. Fix m ∈ ℕ. Let u be a positive integer such that, for all k ∈ {1, 2, …, u − 1}, either k ∈ S_{m} and k ∈ T_{m} or k ∉ S_{m} and k ∉ T_{m}. We will show that u ∈ S_{m} if and only if u ∈ T_{m}. First, we must show that if k ∈ {1, 2, …, u − 1}, then k ∈ S_{m} if and only if L_{m}(k) ∈ S_{m}. Suppose, for the sake of finding a contradiction, that L_{m}(k) ∈ S_{m} and k ∉ S_{m}. As k ∉ S_{m}, we have that k > 1 and k ∉ T_{m}. Lemma 7 then guarantees that there exists a prime q such that q|k and q ∉ T_{m}. As q ∉ T_{m}, the second defining criterion of T_{m} implies that q − m ∉ T_{m}. We know that q > m because, otherwise, p(k) ≤ q ≤ m, implying that L_{m}(k) = 0 ∉ S_{m}. Therefore, q − m ∈ {1, 2, …, u − 1} and q − m ∉ T_{m}. By the induction hypothesis, q − m ∉ S_{m}. Therefore, there exists some q_{0} ∈ Q_{m} such that q_{0}|q − m. Because q|k, Proposition 1 implies that L_{m}(q)|L_{m}(k). Thus, q_{0}|q − m = L_{m}(q)|L_{m}(k), which implies that L_{m}(k) ∉ S_{m}. This is a contradiction. Now suppose, so that we may again search for a contradiction, that L_{m}(k) ∉ S_{m} and k ∈ S_{m}. L_{m}(k) ∉ S_{m} implies that k > 1, and k ∈ S_{m} implies (by the induction hypothesis) that k ∈ T_{m}. By Lemma 7, all positive divisors of k are elements of T_{m}. Let k = ∏_{i=1}^{r} p_{i}^{α_{i}} be the canonical prime factorization of k. Then, by (2),

L_{m}(k) = \begin{cases}0, & if p(k) ≤ m; \\ ∏_{i=1}^{r} p_{i}^{α_{i}−1}(p_{i} − m), & if p(k) > m. \end{cases}

If p(k) ≤ m, then H_{m} (p(k)) = 0, which mean that p(k) ∈ Q_{m}. As p(k)|k, we have contradicted k ∈ S_{m}. Therefore, p(k) > m, so L_{m}(k) = ∏_{i=1}^{r} p_{i}^{α_{i}−1}(p_{i} − m). For each i ∈ {1, 2, …, r}, p_{i} is a positive divisor of k, so p_{i} ∈ T_{m}. The second criterion defining T_{m} then implies that p_{i} − m ∈ T_{m}, so all positive divisors (and, specifically, all prime divisors) of p_{i} − m are in T_{m}. This implies that all prime divisors of L_{m}(k) are elements of T_{m}, so Lemma 7 guarantees that L_{m}(k) ∈ T_{m}. However, we have shown that 0 < L_{m}(k) < k, so L_{m}(k) ∈ {1, 2, …, u − 1}. By the induction hypothesis, we have L_{m}(k) ∈ S_{m}, a contradiction. Thus, we have established that if k ∈ {1, 2, …, u − 1}, then k ∈ S_{m} if and only if L_{m}(k) ∈ S_{m}.

We are now ready to establish that u ∈ S_{m} if and only if u ∈ T_{m}. Suppose that u ∈ S_{m} and u ∉ T_{m}. We know that u > m because, otherwise, L_{m} (p(u)) = H_{m} (p(u)) = 0, implying that p(u) ∈ Q_{m} and contradicting u ∈ S_{m}. If u is prime, then u ∈ S_{m} implies that u ∈ P_{m}. Then H_{m}(u) = H_{m}(u − m) = L_{m}^{(R_{m}(u−m))}(u − m) = 1 ∈ S_{m}. As L_{m}^{(R_{m}(u−m))}(u − m) = L_{m} (L_{m}^{(R_{m}(u−m)−1)}(u − m)) ∈ S_{m} (we assume here and in the rest of the proof that

R_{m}(u−m) is large enough so that the notation L_{m}^{(·)} makes sense as we have defined it, but the argument is valid in any case), it follows from the preceding argument that L_{m}^{(R_{m}(u−m)−1)}(u− m) = L_{m} (L_{m}^{(R_{m}(u−m)−2)}(u − m)) ∈ S_{m}. Continuing this pattern, we eventually find that L_{m}(u−m) ∈ S_{m}, so u−m ∈ S_{m}. By the induction hypothesis, u−m ∈ T_{m}. However, by the second criterion defining T_{m}, the primality of u then implies that u ∈ T_{m}, a contradiction. Thus, u must be composite. We assumed that u ∉ T_{m}, so Lemma 7 guarantees the existence of a prime q ∉ T_{m} such that q|u. As u is composite, q ∈ {1, 2, …, u − 1}. The induction hypothesis then implies that q ∉ S_{m}, so q ∈ Q_{m}. However, this contradicts u ∈ S_{m}, so we have shows that if u ∈ S_{m}, then u ∈ T_{m}. Suppose, on the other hand, that u ∉ S_{m} and u ∈ T_{m}. Again, we begin by assuming u is prime. Then, because u ∈ T_{m}, we must have u − m ∈ T_{m}. Therefore, by the induction hypothesis and the fact that u − m ∈ {1, 2, …, u − 1}, it follows that u − m ∈ S_{m}. Now, u ∉ S_{m}, so we must have u ∈ Q_{m}. Therefore, H_{m}(u) = H_{m} (L_{m}(u)) = H_{m}(u − m) = L_{m}^{(R_{m}(u−m))}(u − m) = 0 ∉ S_{m}. However, as L_{m}^{(R_{m}(u−m))}(u−m) = L_{m} (L_{m}^{(R_{m}(u−m)−1)}(u − m)) ∉ S_{m}, it follows that L_{m}^{(R_{m}(u−m)−1)}(u−m) =

L_{m} (L_{m}^{(R_{m}(u−m)−2)}(u − m)) ∉ S_{m}. Again, we continue this pattern until we eventually find that L_{m}(u − m) ∉ S_{m}, which means that u − m ∉ S_{m}. This is a contradiction, and we conclude that u must be composite. From u ∈ T_{m} and Lemma 7, we conclude that all of the prime divisors of u are elements of T_{m}. Furthermore, as u is composite, all of the prime divisors of u are elements of {1, 2, …, u − 1}. Then, by the induction hypothesis, all of the prime divisors of u are in the set S_{m}. This implies that none of the prime divisors of u are in Q_{m}, so u ∈ S_{m}. This is a contradiction, and the induction step of the proof is finally complete. All that is left to check is the base case. However, the base case is trivial because 1 ∈ S_{m} and 1 ∈ T_{m}.

We may now use the sets S_{m} and T_{m} interchangeably. In addition, part of the above proof gives rise to the following corollary.

Corollary 9. Let k, m, n ∈ ℕ. Then L_{m}^{(k)}(n) ∈ S_{m} if and only if n ∈ S_{m}.

Proof. The proof follows from the argument in the above proof that L_{m}(n) ∈ S_{m} if and only if n ∈ S_{m} whenever n ∈ {1, 2, …, u − 1}. As we now know that we can make u as large as we need, it follows that L_{m}(n) ∈ S_{m} if and only if n ∈ S_{m}. Then L_{m}^{(2)}(n) ∈ S_{m} if and only if L_{m}(n) ∈ S_{m}, L_{m}^{(3)}(n) ∈ S_{m} if and only if L_{m}^{(2)}(n) ∈ S_{m}, and, in general, L_{m}^{(r+1)}(n) ∈ S_{m} if and only if L_{m}^{(r)}(n) ∈ S_{m} (r ∈ ℕ). The desired result follows immediately.

Corollary 10. Let m, n ∈ ℕ. Then H_{m}(n) ∈ S_{m} if and only if n ∈ S_{m}.

Proof. It is clear that H_{m}(n) ∈ S_{m} if and only if H_{m}(n) = 1. Therefore, the proof follows immediately from setting k = R_{m}(n) in Corollary 9.

Notice that, for a given positive integer m, Corollary 10, along with Theorem 8 and the defining criteria of T_{m}, provides a simple way to construct the set of all positive integers x that satisfy H_{m}(x) = 1. Corollary 10 also expedites the proof of the following theorem.

Theorem 11. The function n ↦ H_{m}(n) is completely multiplicative for all m ∈ ℕ.

Proof. Choose some m, x, y ∈ ℕ. First, suppose H_{m}(x) = 0. By Corollary 10, x ∉ S_{m}. Therefore, there exists q ∈ Q_{m} such that q|x. This implies that q|xy, so xy ∉ S_{m}. Thus, H_{m}(xy) = 0. A similar argument shows that H_{m}(xy) = 0 if H_{m}(y) = 0. Now, suppose that H_{m}(x) = H_{m}(y) = 1. Then Corollary 10 ensures that x, y ∈ S_{m}. Therefore, xy ∈ S_{m}, so H_{m}(xy) = 1. As the function H_{m} can only take values 0 and 1, the proof is complete.

In concluding this section, we note that if m + 1 is composite, then it is impossible for any integer greater than 1 to be in S_{m}. Therefore, whenever m + 1 is composite, we have H_{m}(1) = 1 and H_{m}(n) = 0 for all integers n > 1.

3 Summing the iterates

A perfect totient number is defined [3] to be a positive integer n > 1 that satisfies (using our previous notation)

n = ∑_{i=1}^{R_{1}(n)} ϕ^{(i)}(n).

In the following definitions, we generalize the concept of perfect totient numbers. We also borrow some other traditional terminology related to perfect numbers.

Definition 12. Let m be a positive integer. We define the arithmetic function D_{m} by D_{m}(1) = 0 and

D_{m}(n) = ∑_{i=1}^{R_{m}(n)} L_{m}^{(i)}(n)

for all integers n > 1. If D_{m}(n) < n, we say that n is D_{m}-deficient. If D_{m}(n) = n, we say that n is D_{m}-perfect. If D_{m}(n) > n, we say that n is D_{m}-abundant. Finally, in the case when D_{m}(n) = 0, we say that n is D_{m}-stagnant.

We now present a series of theorems related to these definitions.

Theorem 13. If m > 1 is odd, then all positive integers are D_{m}-deficient.

Proof. Let m > 1 be an odd integer, and let n be any positive integer. If n = 1 or p(n) ≤ m, then n is D_{m}-stagnant. A fortiori, n is D_{m}-deficient. If p(n) > m, then p(n) − m is even and p(n) − m|L_{m}(n) (by Proposition 1). Thus, 2|L_{m}(n), which implies that L_{m}^{(2)}(n) = 0. Hence, D_{m}(n) = L_{m}(n) < n.

Theorem 14. All positive even integers are D_{m}-deficient for all positive integers m.

Proof. The proof is trivial for m > 1 because, in that case, any positive even integer is clearly D_{m}-stagnant. For m = 1, we use the fact that all totient numbers greater than 1 are even. Therefore,

D_{1}(n) = ϕ(n) + ϕ^{(2)}(n) + ⋯ + ϕ^{(R_{1}(n))}(n) ≤ \frac{1}{2}n + \frac{1}{4}n + ⋯ + \frac{1}{2^{R_{1}(n)}} n < n.

Theorem 14 is nothing revolutionary, but we include it because it fits nicely with the next theorems.

For the next two theorems, which are not quite as trivial as the previous two, we require the following lemma.

Lemma 15. If k > 1 is an odd integer, then at least one element of the set {k, L_{2}(k), L_{2}^{(2)}(k)} is divisible by 3.

Proof. Let k > 1 be an odd integer with prime factor p, and suppose 3 ∤ k and 3 ∤ L_{2}(k). We know that p ≢ 2 (mod 3) because p − 2|L_{2}(k), so p ≡ 1 (mod 3). As p − 2 ≡ 2 (mod 3), p − 2 must have some prime factor p′ such that p′ ≡ 2 (mod 3). But then, using Proposition 2, 3|p′ − 2 = L_{2}(p′)|L_{2}(p − 2) = L_{2}^{(2)}(p)|L_{2}^{(2)}(k).

Theorem 16. For any integer m > 1, all positive multiples of 3 are D_{m}-deficient.

Proof. If m ≥ 3, then any positive multiple of 3 is clearly D_{m}-stagnant. Therefore, we only need to check the case m = 2. Write K = {n ∈ ℕ : 3|n, D_{2}(n) ≥ n}. Suppose K ≠ ∅ and let n_{0} be the smallest element of K. If n_{0} = 3^{α} for some α ∈ ℕ, then D_{2}(n_{0}) =

3^{α−1} + 3^{α−2} + ⋯ + 3 + 1 = \frac{n_{0} − 1}{2} < n_{0}. Therefore, n_{0} must have some prime divisor p ≠ 3.

From Theorem 13, p ≠ 2. Also, by Proposition 2, L_{2}(p)|L_{2}(n_{0}) and L_{2}^{(2)}(p)|L_{2}^{(2)}(n_{0}). By Lemma 15, at least one of L_{2}(p) and L_{2}^{(2)}(p) must be divisible by 3. Suppose 3|L_{2}(p) so that 3|L_{2}(n_{0}). By the choice of n_{0} as the smallest element of K, we have D_{2} (L_{2}(n_{0})) < L_{2}(n_{0}).

This implies that D_{2}(n_{0}) = L_{2}(n_{0}) + D_{2} (L_{2}(n_{0})) < 2L_{2}(n_{0}) < \frac{2}{3}n_{0} because 3|n_{0}. From this contradiction, we conclude that 3|L_{2}^{(2)}(p), so 3|L_{2}^{(2)}(n_{0}). Again, by the choice of n_{0}, we have D_{2} (L_{2}^{(2)}(n_{0})) < L_{2}^{(2)}(n_{0}). However, this implies that D_{2}(n_{0}) = L_{2}(n_{0}) + L_{2}^{(2)}(n_{0}) +

D_{2} (L_{2}^{(2)}(n_{0})) < L_{2}(n_{0})+2L_{2}^{(2)}(n_{0}) < 3L_{2}(n_{0}) < n_{0}, which is a contradiction. It follows that K is empty.

Theorem 17. If m > 1 is a positive integer and m ≠ 4, then all positive multiples of 5 are D_{m}-deficient.

Proof. Let m be a positive integer other than 1 or 4, and let n be a multiple of 5. If m ≥ 5, then n is D_{m}-stagnant. If m = 3, then n is D_{m}-deficient by Theorem 13. We therefore only need to check the case m = 2. Write n = 5^{α}k, where α, k ∈ ℕ. We may assume that 2 ∤ k and 3 ∤ k because, otherwise, the desired result follows immediately from either Theorem 14 or Theorem 16. We now consider two cases.

Case 1: α ≥ 2. Write L_{2}(k) = 3^{α_{1}}5^{α_{2}}t, where t is a positive integer not divisible by 2, 3, or 5 and α_{1}, α_{2} ∈ ℕ_{0} (we use Proposition 3 to conclude that t is odd). Then L_{2}(n) = L_{2}(5^{α})L_{2}(k) = 3^{α_{1}+1}5^{α+α_{2}−1}t and L_{2}^{(2)}(n) = L_{2}(3^{α_{1}+1})L_{2}(5^{α+α_{2}−1})L_{2}(t) = 3^{α_{1}+1}5^{α+α_{2}−2}L_{2}(t). As 3|L_{2}(n), we can use Theorem 16 to write D_{2}(n) = L_{2}(n) + L_{2}^{(2)}(n) + D_{2} (L_{2}^{(2)}(n)) < L_{2}(n)+2L_{2}^{(2)}(n) = 3^{α_{1}+1}5^{α+α_{2}−1}t+2 (3^{α_{1}+1}5^{α+α_{2}−2}L_{2}(t)) ≤ 7 (3^{α_{1}+1}5^{α+α_{2}−2}t) ≤

\frac{21}{25}5^{α}k = \frac{21}{25}n. This completes the proof of the case when α ≥ 2.

Case 2: α = 1. In this case, n = 5k, so L_{2}(n) = 3L_{2}(k). We may assume that k > 1 because the case n = 5 is trivial. First, suppose that 3|L_{2}(k). In this case, L_{2}^{(2)}(k) ≤

\frac{1}{3}L_{2}(k), and, by Theorem 4, L_{2}^{(2)}(n) = 3L_{2}^{(2)}(k). Then, using Theorem 16, we have D_{2}(n) =

L_{2}(n) + L_{2}^{(2)}(n) + D_{2} (L_{2}^{(2)}(n)) = 3L_{2}(k) + 3L_{2}^{(2)}(k) + D_{2} (3L_{2}^{(2)}(k)) < 3L_{2}(k) + 6L_{2}^{(2)}(k) ≤ 5L_{2}(k) ≤ n − 10. Now suppose that 3 ∤ L_{2}(k). By Lemma 15 and our assumption that 3 ∤ k, we have 3|L_{2}^{(2)}(k). Using Theorem 4 and Theorem 16 again, we have D_{2}(n) = L_{2}(n) + L_{2}^{(2)}(n) + D_{2} (L_{2}^{(2)}(n)) = 3L_{2}(k) + L_{2}^{(2)}(k) + D_{2} (L_{2}^{(2)}(k)) < 3L_{2}(k) + 2L_{2}^{(2)}(k) ≤ 3(k − 2) + 2(k − 4) = n − 14. This completes the proof of all cases.

The last few theorems have dealt with D_{m}-deficient numbers, so it is natural to ask questions about D_{m}-abundant numbers. We might wish to know the positive integers m for which D_{m}-abundant numbers even exist. How many D_{m}-abundant numbers exist for a given m? How large can we make D_{m}(n) − n? Theorem 13 deals with these questions for the cases when m is odd and greater than 1. Also, a great deal of literature [3, 4] already exists concerning the case m = 1. In the following theorem, we answer all of the preceding questions for the cases when m is a positive even integer.

Theorem 18. Let m be a positive even integer. For any positive A and δ, there exist infinitely many primes p_{0} such that L_{m}(p_{0}^{α}) + L_{m}^{(2)}(p_{0}^{α}) > p_{0}^{α} + Ap_{0}^{α−δ} for all positive integers α.

Proof. Fix m, A, and δ to be positive real numbers, where m is an even integer. Let p_{1}, p_{2}, …, p_{r} be all the primes that divide m, and let q_{1}, q_{2}, …, q_{t} be all the primes that are less than m and do not divide m. For each j ∈ {1, 2, …, t}, define σ_{j} by

σ_{j} = \begin{cases}1, & if m ≢ 1 (mod q_{j}); \\ −1, & if m ≡ 1 (mod q_{j}). \end{cases}

Write M = ∏_{p≤m} p. By the Chinese remainder theorem, there exists a unique solution modulo

M to the system of congruences defined by

\begin{cases}x ≡ 1 (mod p_{i}) & if i ∈ \{1, 2, …, r\}; \\ x ≡ σ_{j} (mod q_{j}) & if j ∈ \{1, 2, …, t\}. \end{cases}  (3)

It is easy to see that if x_{0} is a solution to (3), then x_{0} and x_{0} − m are each relatively prime to every prime less than or equal to m. By Dirichlet’s theorem concerning the infinitude of primes in arithmetic progressions, there must be infinitely many primes that satisfy the system (3). Let p_{0} be one such prime, and write

β = ∏_{p|p_{0}−m} (1 − \frac{m}{p}) .

As p_{0} is relatively prime to all primes less than or equal to m, we have

∏_{m<p≤p_{0}} (1 − \frac{m}{p}) ≤ β ≤ 1.

It is well-known [6], that, as p_{0} → ∞,

∏_{m<p≤p_{0}} (1 − \frac{m}{p}) ∼ \frac{c_{m}}{(log p_{0})^{m}}

for some constant c_{m} that depends only on m. We find that

βp_{0}^{2} ≥ p_{0}^{2} ∏_{m<p≤p_{0}} (1 − \frac{m}{p}) ∼ \frac{c_{m}p_{0}^{2}}{(log p_{0})^{m}} .

Therefore, we may choose p_{0} to be large enough so that βp_{0}^{2} > Ap_{0}^{2−δ} + 3mp_{0}. With this choice of p_{0}, we may write β(p_{0} − m)^{2} > βp_{0}^{2} − 2βmp_{0} ≥ βp_{0}^{2} − 2mp_{0} > Ap_{0}^{2−δ} + mp_{0}. But β(p_{0} − m) = L_{m}(p_{0} − m) because p(p_{0} − m) > m. Thus,

(p_{0} − m)L_{m}(p_{0} − m) > Ap_{0}^{2−δ} + mp_{0}.  (4)

Let α be an integer, and, for now, assume α ≥ 2. Rearranging and multiplying the inequality (4) by p_{0}^{α−2}, we have −mp_{0}^{α−1} + p_{0}^{α−1}L_{m}(p_{0} − m) > mp_{0}^{α−2}L_{m}(p_{0} − m) + Ap_{0}^{α−δ}. After further algebraic manipulation, we find p_{0}^{α−1}(p_{0} − m) + p_{0}^{α−2}(p_{0} − m)L_{m}(p_{0} − m) > p_{0}^{α} + Ap_{0}^{α−δ}. Noticing that the left-hand side of the preceding inequality is simply L_{m}(p_{0}^{α}) + L_{m}^{(2)}(p_{0}^{α}), we have L_{m}(p_{0}^{α}) + L_{m}^{(2)}(p_{0}^{α}) > p_{0}^{α} + Ap_{0}^{α−δ}. This is the desired result for α ≥ 2. To show that

the result holds when α = 1, it suffices to show that L_{m}(p_{0}) + L_{m}^{(2)}(p_{0}) > \frac{L_{m}(p_{0}^{2}) + L_{m}^{(2)}(p_{0}^{2})}{p_{0}}.

This reduces to p_{0} − m + L_{m}(p_{0} − m) > p_{0} − m + \frac{p_{0} − m}{p_{0}}L_{m}(p_{0} − m), which is obviously

true.

Corollary 19. For any positive even integer m, there exist infinitely many D_{m}-abundant numbers.

We conclude this section with a remark about D_{m}-perfect numbers. Using Mathematica, one may check that for m ∈ {2, 4, 6}, the only D_{m}-perfect number less than 100, 000 is 37, 147, which is D_{2}-perfect. Unfortunately, this data is too scarce to make any reasonable conjecture about the nature or distribution of D_{m}-perfect numbers for positive even integers m.

4 Numerical analysis and concluding remarks

In 1943, H. Shapiro investigated a function C, which counts the number of iterations of the ϕ function needed to reach 2 [8]. Shapiro showed that the function C is additive, and he established bounds for its values. In this paper, we have not gone into much detail exploring the functions R_{m} because they prove, in general, to be either completely uninteresting or very difficult to handle. For example, for any integer n > 1,

R_{3}(n) = \begin{cases}1, & if n ≢ 1, 5 (mod 6); \\ 2, & if n ≡ 1, 5 (mod 6). \end{cases}

On the other hand, the function R_{4} does not seem to obey any nice pattern or exhibit any sort of nice additive behavior. There seems to be some hope in analyzing the function R_{2}, so we make the following conjecture.

Conjecture 20. If x > 3 is an odd integer, then

R_{2}(x) ≥ \frac{log (\frac{49}{15}x)}{log 7}.

We note that it is not difficult to prove, using Lemma 15 and a bit of case work, that

R_{2}(x) ≤ 3\frac{log(x + 2)}{log 3} − 3 for all integers x > 1 (with equality only at x = 7). How-

ever, as Figure 1 shows, this is a very weak upper bound (at least for relatively small Figure 1: A plot of the first 300, 000 values of the function R_{2}, as well as some important curves. Note that the black streaks in the figure are, in actuality, several overlapping dots.

x). It is tempting to think, based on the figure, that R_{2}(x) ≤ 3 + \frac{log x}{log 3} for all posi-

tive integers x. However, setting x = 480, 314, 203 yields a counterexample because 3 +

\frac{log 480, 314, 203}{log 3} ≈ 21.196 < 22 = R_{2}(480, 314, 203).

The author has found that investigating bounds of the function R_{2} naturally leads to a question about the infinitude of twin primes, which hints at the potential difficulty of the problem. Indeed, Harrington and Jones [1] have arrived at the same conclusion while studying the function C_{2}(x) := R_{2}(x) − 1, and they conjecture that the values of C_{2}(x) + C_{2}(y) − C_{2}(xy) can be arbitrarily large. To avoid the unpredictability of the values of the function C_{2}, Harrington and Jones have restricted the domain of C_{2} to the set D of positive integers k with the property that none of the numbers in the set {k, L_{2}(k), L_{2}^{(2)}(k), …} has a prime factor that is congruent to 1 modulo 3. With this restriction of the domain of C_{2}, these two authors have established results analogous to those that Shapiro gave for the function C mentioned earlier. In fact, we speculate that methods analogous to those that Harrington and Jones have used could easily generalize to allow for analogous results concerning functions C_{m}(x) := R_{m}(x) − 1 if one is willing to use a sufficiently restricted domain of C_{m}.

We next remark that, in Theorem 17, the requirement that m ≠ 4 is essential. For example, write p_{1} = 306, 167, p_{2} = 4 + p_{1}^{2}, p_{3} = 4 + p_{2}^{2}, p_{4} = 4 + p_{3}^{2}, and p_{5} = 4 + p_{4}^{2}. Then the number 5p_{5} is a D_{4}-abundant multiple of 5.

Lastly, we have not spent much effort analyzing the “sizes” of the functions D_{m} or searching for D_{m}-perfect numbers. We might inquire about the average order or possible upper and lower bounds for D_{m} for a general positive even integer m. In addition, it is natural to ask if there even are any D_{m}-perfect numbers other than 37, 147 for even positive integers m.

5 Acknowledgments and dedications

Dedicated to my parents Marc and Susan, my brother Jack, and my sister Juliette.

Also dedicated to Mr. Jacob Ford, who wrote a program to find values of the functions L_{m}, R_{m}, and H_{m}. Mr. Ford and my father also sparked my interest in computer programming, which I used to analyze the functions D_{m}.

Finally, I would like to thank the unknown referee for taking the time to read carefully through my work and for his or her valuable suggestions.

References

[1] J. Harrington and L. Jones, On the iteration of a function related to Euler’s ϕ-function. Integers 10 (2010), 497–515.

[2] J. Herzog and P. R. Smith, Lower bounds for a certain class of error functions. Acta Arith. 60 (1992), 289–305.

[3] D. Iannucci, M. Deng, and G. Cohen, On perfect totient numbers. J. Integer Seq. 6 (2003), Article 03.4.5.

[4] F. Luca, On the distribution of perfect totients. J. Integer Seq. 9 (2006), Article 06.4.4.

[5] S. S. Pillai, On a function connected with ϕ(n). Bull. Amer. Math. Soc. 35 (1929), 837–841.

[6] J. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math. 6 (1962), 64–94.

[7] V. Schemmel, Über relative Primzahlen, J. Reine Angew. Math., 70 (1869), 191–192.

[8] H. Shapiro, An arithmetic function arising from the ϕ function. Amer. Math. Monthly 50 (1943), 18–30.

[9] G. K. White, Iterations of generalized Euler functions. Pacific J. Math. 12 (1962), 777– 783.

2010 Mathematics Subject Classification: Primary 11N64; Secondary 11B83.

Keywords: Schemmel totient function, iterated arithmetic function, summatory function, perfect totient number.

(Concerned with sequences \underline{A000010}, \underline{A003434}, \underline{A058026}, \underline{A092693}, \underline{A123565}, \underline{A241663}, \underline{A241664}, \underline{A241665}, \underline{A241666}, \underline{A241667}, and \underline{A241668}.)

Received April 26 2014; revised versions received October 12 2014; November 7 2014; January 8 2015. Published in Journal of Integer Sequences, January 13 2015.

Return to Journal of Integer Sequences home page.