On the Sum of Iterations of the Euler Function

Igor E. Shparlinski Department of Computing Macquarie University Sydney, NSW 2109 Australia

                      igor@ics.mq.edu.au

Abstract

We study the sum

F (n) = ∑_{k=1}^{κ(n)} φ^{(k)}(n).

of consecutive iterations of the Euler function φ(n) (where the last iteration satisfies φ^{(κ(n))}(n) = 1). We show that for almost all n, the difference |F (n) − n| is not too small, and the ratio n/F (n) is not an integer. The latter result is related to a question about the so-called perfect totient numbers, for which F (n) = n.

1 Introduction

Let φ denote the Euler function, which, for an integer n ≥ 1, is defined as usual by

φ(n) = #{j ∈ ℤ | 1 ≤ j ≤ n, gcd(j, n) = 1}.

Moreover, for an integer k ≥ 1, we use φ^{(k)} to denote the kth iteration of φ, that is, the function defined recursively as φ^{(1)}(n) = φ(n) and φ^{(k+1)}(n) = φ^{k}(φ(n)), k = 1, 2, . . ..

Clearly for every n there exists a uniquely defined integer κ(n) such that φ^{(κ(n))}(n) = 1. Accordingly, we define the function

F (n) = ∑_{k=1}^{κ(n)} φ^{(k)}(n),

which is an additive analogue of the function

G(n) = ∏_{k=1}^{κ(n)} φ^{(k)}(n)

considered in the paper [1]. (In fact, the results of [1] are formulated for nG(n) but one can easily reformulate them for G(n).)

The function F (n) also appears in the definition of perfect totient numbers, which are the integers n ≥ 2 with F (n) = n; see [4, 6] and references therein. Here we use some very elementary arguments to establish several properties of this function, which seem to be new.

Let

V(x) = {φ(n) ≤ x | n = 1, 2, …}, U(x) = {F (n) ≤ x | n = 1, 2, …}.

We start with the observation that

U(x) ⊆ {v + F (v) | v ∈ V(x)},

therefore

#U(x) ≤ #V(x).

There are several very tight bounds on the value set of the Euler function (see [2, 5]). These immediately imply that

#U(x) ≤ \frac{x}{log x} exp ((C + o(1))(log log log x)^{2}) ,  x → ∞,  (1)

for some absolute constant C = 0.8178 · · ·. This, in turn, implies that the set of perfect totient numbers is of density zero. On the other other hand, it is easy to check that F (3^{s}) = 3^{s}, s = 1, 2, . . .. Thus there are infinitely many perfect totient numbers, and in fact #U(x) ≥ log x/ log 3−1. Here we show that in fact one can get a better bound by considering integers of the form 2^{r}3^{s}, r, s = 1, 2, . . ..

As in the case of the classical perfect numbers, see [3], one can consider multiply perfect totient numbers for which F (n)|n. We show that multiply perfect totient numbers form a zero density set.

We also show that

|F (n) − n| ≥ (log n)^{log 2+o(1)}

for almost all n. Hence such “approximately” perfect totient numbers form a set of density zero, too.

Throughout the paper, the implied constants in the symbols “O”, “≫” and “≪” are absolute. (We recall that the notation U ≪ V and V ≫ U is equivalent to the statement that U = O(V) for positive functions U and V). We also use the symbol “o” with its usual meaning: the statement U = o(V) is equivalent to U/V → 0.

Finally, for any real number z > 0 and any integer ν ≥ 1, we write log_{ν} z for the function defined inductively by log_{1} z = max{log z, 1}, where log z is the natural logarithm of z and log_{ν} z = log_{1}(log_{ν−1} z) for ν > 1. When ν = 1, we omit the subscript in order to simplify the notation; however, we continue to assume that log z ≥ 1 for any z > 0.

2 Main Results

Theorem 2.1. The following bound holds:

#U(x) ≫ (log x)^{2}.

Proof. For positive integer r and s, we have

F (2^{2r}3^{2s}) = ∑_{i=1}^{2s} 3^{2s−i}2^{2r} + ∑_{j=0}^{2r} 2^{2r−j}
= 2^{2r−1}(3^{2s} − 1) + 2^{2r} − 1 = 2^{2r−1}3^{2s} + 2^{2r−1} − 1.

Assume that

2^{2r−1}3^{2s} + 2^{2r−1} − 1 = 2^{2u−1}3^{2v} + 2^{2u−1} − 1

for some positive integers u and v. Then

(3^{2s} + 1) = 2^{2u−2r}(3^{2v} + 1)

which is impossible unless u = r, v = s, since

3^{2s} + 1 ≡ 3^{2v} + 1 ≡ 2 (mod 4).

This means that the values of F (2^{2r}3^{2s}) are pairwise distinct and the result follows.

Denoting by M(x) the number of multiply perfect totient numbers n ≤ x, we have the following result. Theorem 2.2. For all positive integers n ≤ x except possibly o(x) of them, the bound

M(x) ≪ \frac{x}{log x} exp ((C + o(1))(log_{3} x)^{2})

holds. Proof. Let

Δ = max_{n≤x} \frac{n}{φ(n)}.

Since φ(n) ≫ n/ log_{2} n (see [7, Theorem 4, Chapter I.5]) we conclude that Δ = O(log_{2} x). Clearly, every n with F (n)|n must be of the form n = du with an positive integer d ≤ Δ and u ∈ U(x/d). Therefore, using (1), we deduce,

M(x) ≤ ∑_{1≤d≤Δ} #U(x/d)

≤ x ∑_{1≤d≤Δ} \frac{1}{d log(x/d)} exp ((C + o(1))(log_{3}(x/d))^{2})

≤ \frac{x}{log x} exp ((C + o(1))(log_{3} x)^{2}) ∑_{1≤d≤Δ} \frac{1}{d}
≪ \frac{x}{log x} exp ((C + o(1))(log_{3} x)^{2}) log Δ
= \frac{x}{log x} exp ((C + o(1))(log_{3} x)^{2}) ,

which finishes the proof.

Theorem 2.3. For all positive integers n ≤ x, except possibly o(x) of them, the bound

|F (n) − n| ≥ (log x)^{log 2+o(1)}

holds.

Proof. Let ν(m) denote the largest power of 2 that divides m. We start with an observation that if m is not a power of 2 itself, we have ν(φ(m)) ≥ ν(m). It is also clear that ν(φ(m)) ≥ ω(m) − 1 where ω(m) is the number of distinct prime divisors of n. This implies that

F (n) ≡ 2^{ω(n)−1} + ⋯ + 1 ≡ −1 (mod 2^{ω(n)−1}).

From the classical Hardy-Ramanujan inequality, for any y ≥ 1,

|ω(n) − log_{2} x| ≤ y\sqrt{log_{2} x}

for at most O(xy^{−2}) positive integers n ≤ x (see [7, Theorem 4, Chapter III.3]). Take y = (log_{2} x)^{1/6} and put

r = ⌊log_{2} x − y\sqrt{log_{2} x} − 1⌋ , s = ⌊log_{2} x − 2y\sqrt{log_{2} x}⌋ .

We see that

F (n) ≡ −1 (mod 2^{r})

for all but O(x(log_{2} x)^{−1/3}) positive integers n ≤ x. Therefore, for every of the remaining integers n we see that if |F (n) − n| < 2^{s} then n belongs to one of the O(2^{s}) residue classes modulo 2^{r}. Thus this is possible for at most O (2^{s}(x/2^{r} + 1)) = O(x2^{s−r}) positive integers n ≤ x, which finishes the proof.

3 Open Questions

It seems quite plausible that considering integers n composed out of more fixed primes, for example, n = 2^{r}3^{s}5^{t} one can improve the lower bound of Theorem 2.1. We however do not see how to create a more generic argument, which would lead to, say, the estimate

\frac{log #U(x)}{log_{2} x} → ∞, x → ∞,

which, no doubt, is correct.

It is also natural to expect that the bounds of Theorems 2.2 and 2.3 are not tight and can be improved.

One can easily derive from [1, Theorem 4.2] that

\frac{1}{x} ∑_{n≤x} F (n) ∼ \frac{3}{π^{2}} x.

In fact, using the full strength of [1, Theorem 4.2], one can obtain a more precise asymptotic expansion for the average value of F (n).

Finally, one can also ask similar questions for the sums of iterations of other number theoretic functions, such as the the sum of divisors function σ(n) or the Carmichael functions λ(n).

References

[1] P. Erdős, A. Granville, C. Pomerance and C. Spiro, On the normal behaviour of the iterates of some arithmetic functions, in Analytic Number Theory, Birkhäuser, Boston, 1990, pp. 165–204.

[2] K. Ford, The distribution of totients, Ramanujan J., 2 (1998), 67–151.

[3] B. Hornfeck and E. Wirsing, Über die Häufigkeit vollkommener Zahlen, Math. Ann., 133 (1957), 431–438.

[4] D. E. Iannucci, D. Moujie and G. L. Cohen, On perfect totient numbers, J. Integer Sequences, 6 (2003), Article 03.4.5.

[5] H. Maier and C. Pomerance, On the number of distinct values of Euler’s φ function, Acta Arith., 49 (1988), 263–275.

[6] A. L. Mohan and D. Suryanarayana, Perfect totient numbers, in Number Theory (Proc. 3rd Matscience Conf., Mysore, 1981), Lect. Notes in Math., vol. 938, Springer-Verlag, New York, 1982, pp. 101–105.

[7] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge University Press, 1995.

2000 Mathematics Subject Classification: Primary 11N37; Secondary 11N60. Keywords: Euler function, iterations, congruences.

(Concerned with sequence \underline{A082897}.)

Received July 27 2005; revised version received January 18 2006. Published in Journal of Integer Sequences, January 23 2006.

Return to Journal of Integer Sequences home page.