On the Distribution of Perfect Powers

Rafael Jakimczuk División Matemática Universidad Nacional de Luján Buenos Aires Argentina

                   jakimczu@mail.unlu.edu.ar

In memory of my sister Fedra Marina Jakimczuk (1970–2010)

Abstract Let N(x) be the number of perfect powers that do not exceed x. In this article we

obtain asymptotic formulae for the counting function N(x).

1 Introduction

A natural number of the form m^{n} where m is a positive integer and n ≥ 2 is called a perfect power. The first few terms of the integer sequence of perfect powers are

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, …,

and they are sequence \underline{A001597} in Sloane’s Encylopedia. Let N(x) be the number of perfect powers that do not exceed x. M. A. Nyblom [3] proved the following asymptotic formula,

N(x) ∼ \sqrt{x}.

M. A. Nyblom [4] also obtained a formula for the exact value of N(x) using the inclusionexclusion principle (also called the principle of cross-classification).

In this article we obtain more precise asymptotic formulae for the counting function N(x). For example, we prove

N(x) = \sqrt{x} + \sqrt[3]{x} + \sqrt[5]{x} − \sqrt[6]{x} + \sqrt[7]{x} + o (\sqrt[7]{x}) .

Consequently

\sqrt{x} + \sqrt[3]{x} < N(x) < \sqrt{x} + \sqrt[3]{x} + \sqrt[5]{x}.

2 Preliminary Results

Let A be a set. The number of elements in A we denote in the form |A|.

We need the following results.

Lemma 1. (Inclusion-exclusion principle) Let us consider a given finite collection of sets A_{1}, A_{2}, …, A_{n}. The number of elements in ∪_{i=1}^{n}A_{i} is

|∪_{i=1}^{n}A_{i}| = ∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} |A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}}| ,

where the expression 1 ≤ i_{1} < ⋯ < i_{k} ≤ n indicates that the sum is taken over all the k-element subsets {i_{1}, …, i_{k}} of the set {1, 2, …, n}.

Proof. See for example either [1, page 233] or [2, page 84].

Let A_{n}(x) (n ≥ 2) be the set {k^{n} : k ∈ N, k^{n} ≤ x}, that is, the set of perfect powers whose exponent is n that do not exceed x.

Lemma 2. We have

|A_{n}(x)| = ⌊\sqrt[n]{x}⌋ ,

where ⌊.⌋ denotes the integer-part function.

Proof. We have

k^{n} ≤ x ⇔ k ≤ \sqrt[n]{x}.

M. A. Nyblom [4] proved the following Lemma and the following Theorem.

Lemma 3. For any set consisting of m ≥ 2 positive integers {n_{1}, …, n_{m}} all greater than unity, we have the set equality

⋂_{i=1}^{m} A_{n_{i}}(x) = A_{[n_{1},...,n_{m}]}(x),

where [n_{1}, …, n_{m}] denotes the least common multiple of the m integers n_{1}, …, n_{m}.

Let p_{n} be the n-th prime. Consequently we have,

p_{1} = 2, p_{2} = 3, p_{3} = 5, p_{4} = 7, p_{5} = 11, p_{6} = 13, …

Theorem 4. If x ≥ 4 and p_{1}, p_{2}, …, p_{m} denote the prime numbers that do not exceed ⌊log_{2} x⌋, then for k ≥ m the number of perfect powers that do not exceed x is

N(x) = |⋃_{i=1}^{k} A_{p_{i}}(x)| .

Besides A_{p_{i}}(x) = {1} for i ≥ m + 1.

We also need the following two well-known results.

The binomial formula

(a + b)^{n} = ∑_{k=0}^{n} \binom{n}{k}a^{n−k}b^{k},  (1)

and the following property of the absolute value

|a_{1} + a_{2} + ⋯ + a_{r}| ≤ |a_{1}| + |a_{2}| + ⋯ + |a_{r}| ,  (2)

where a_{1}, a_{2}, …, a_{r} are real numbers.

3 Main Results

Theorem 5. Let p_{n} be the n-th prime number with n ≥ 2, where n is an arbitrary but fixed positive integer. Then

N(x) = ∑_{k=1}^{n−1}(−1)^{k+1} ∑_{p_{i_{1}}···p_{i_{k}} <p_{n}^{1≤i_{1}<···<i_{k}≤n−1}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} + g(x)x^{\frac{1}{pn}} ,  (3)

where lim_{x→∞} g(x) = 1 and the inner sum is taken over the k-element subsets {i_{1}, …, i_{k}} of the set {1, 2, …, n − 1} such that the inequality p_{i_{1}} ⋯ p_{i_{k}} < p_{n} holds.

Proof. Let k = ⌊log_{2} x⌋ + 1 = ⌊\frac{log x}{log 2}⌋ + 1, where x ≥ 4. If p_{1}, p_{2}, …, p_{m} denote the prime numbers that do not exceed ⌊log_{2} x⌋, then we have

p_{1} < ⋯ < p_{m} ≤ ⌊log_{2} x⌋ < ⌊log_{2} x⌋ + 1 = k ≤ p_{m+1} < p_{m+2} < ⋯  (4)

Note that if i ≥ m + 1 we have 1 < x^{\frac{1}{p_{i}}} ≤ x^{\frac{1}{k}} < x^{\frac{1}{\frac{log x}{log 2}}} = 2. That is, 1 < x^{\frac{1}{p_{i}}} < 2. Consequently if i ≥ m + 1 (see Lemma 2) |A_{p_{i}}(x)| = 1. That is, A_{p_{i}}(x) = {1}. Note also that k and m are increasing functions of x. On the other hand n ≥ 2 is an arbitrary but fixed positive integer.

Equation (4) gives

p_{m} < k.  (5)

On the other hand

m < p_{m}.  (6)

Therefore (5) and (6) give

m < k,  (7)

and consequently

p_{m} < p_{k}.  (8)

There exist three possible relations between m, k, n and n + 1 and consequently between p_{m}, p_{k}, p_{n} and p_{n+1}.

First relation.

m < k ≤ n < n + 1

and hence

p_{m} < p_{k} ≤ p_{n} < p_{n+1}.

Second relation.

m ≤ n < n + 1 ≤ k

and hence

p_{m} ≤ p_{n} < p_{n+1} ≤ p_{k}.

Third relation.

n < n + 1 ≤ m < k

and hence

p_{n} < p_{n+1} ≤ p_{m} < p_{k}.

If we define S(x) = max{n + 1, k} then these three relations, Theorem 4 and Lemma 2 give us (x ≥ 4)

|⋃_{i=1}^{n} A_{p_{i}}(x)| ≤ N(x) < |⋃_{i=1}^{n} A_{p_{i}}(x)| + ∑_{i=n+1}^{S(x)} |A_{p_{i}}(x)|

= |⋃_{i=1}^{n} A_{p_{i}}(x)| + ∑_{i=n+1}^{S(x)} ⌊x^{\frac{1}{p_{i}}} ⌋

≤ |⋃_{i=1}^{n} A_{p_{i}}(x)| + (S(x) − n) ⌊x^{\frac{1}{p_{n+1}}} ⌋ .  (9)

Note that there exists x_{0} such that if x ≥ x_{0} the third relation holds.

Note also that S(x) − n is either equal to 1 or k − n < k − 1 = ⌊\frac{log x}{log 2}⌋ ≤ \frac{log x}{log 2}, and so in either case

S(x) − n ≤ \frac{log x}{log 2}  (10)

as x ≥ 4. Consequently (9) and (10) give

|⋃_{i=1}^{n} A_{p_{i}}(x)| ≤ N(x) < |⋃_{i=1}^{n} A_{p_{i}}(x)| + \frac{log x}{log 2}x^{\frac{1}{p_{n+1}}} .  (11)

Lemma 1 gives

|⋃_{i=1}^{n} A_{p_{i}}(x)| = ∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} |A_{p_{i_{1}}}(x) ∩ ⋯ ∩ A_{p_{i_{k}}} (x)| .  (12)

On the other hand, Lemma 3 gives

A_{p_{i_{1}}}(x) ∩ ⋯ ∩ A_{p_{i_{k}}} (x) = A_{[p_{i_{1}},...,p_{i_{k}}]}(x) = A_{p_{i_{1}}···p_{i_{k}}} (x).

Therefore (Lemma 2) we obtain

|A_{p_{i_{1}}}(x) ∩ ⋯ ∩ A_{p_{i_{k}}} (x)| = |A_{p_{i_{1}}···p_{i_{k}}} (x)| = ⌊x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ⌋ .  (13)

Substituting (13) into (12) we find that

|⋃_{i=1}^{n} A_{p_{i}}(x)| = ∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} ⌊x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ⌋

= ∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}}

− ∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} (x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} − ⌊x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ⌋) .  (14)

Now

0 ≤ x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} − ⌊x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ⌋ < 1.  (15)

Consequently (see (1) and (2))

|∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} (x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} − ⌊x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ⌋)| ≤ ∑_{k=1}^{n} ∑_{1≤i_{1}<···<i_{k}≤n} 1

= ∑_{k=1}^{n} \binom{n}{k} ≤ ∑_{k=0}^{n} \binom{n}{k} = (1 + 1)^{n} = 2^{n}.  (16)

That is,

∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} (x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} − ⌊x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ⌋) = O(1).  (17)

Equations (14) and (17) give

|⋃_{i=1}^{n} A_{p_{i}}(x)| = ∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} + O(1)  (18)

If

B(x) = ∑_{k=1}^{n}(−1)^{k+1} ∑_{p_{i_{1}}···p_{i_{k}} <p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}}  (19)

and

C(x) = ∑_{k=1}^{n}(−1)^{k+1} ∑_{p_{i_{1}}···p_{i_{k}} >p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} = o (x^{\frac{1}{p_{n+1}}} )  (20)

then

∑_{k=1}^{n}(−1)^{k+1} ∑_{1≤i_{1}<···<i_{k}≤n} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} = B(x) + C(x).  (21)

Equations (18) and (21) give

|⋃_{i=1}^{n} A_{p_{i}}(x)| = B(x) + C(x) + O(1).  (22)

Equations (22) and (11) give

B(x) + C(x) + O(1) ≤ N(x) < B(x) + C(x) + O(1) + \frac{log x}{log 2}x^{\frac{1}{p_{n+1}}} .

Therefore,

C(x) + O(1) ≤ N(x) − B(x) < C(x) + O(1) + \frac{log x}{log 2}x^{\frac{1}{p_{n+1}}} .  (23)

Equations (23) and (20) give

−ϵ < \frac{N(x) − B(x)}{log x x^{\frac{1}{p_{n+1}}}} < \frac{1}{log 2} + ϵ (ϵ > 0).

That is,

N(x) = B(x) + O (log x x^{\frac{1}{p_{n+1}}} ) .  (24)

Note that (see (19)) if k = 1, …, n then,

∑_{p_{i_{1}}···p_{i_{k}} <p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} = ∑_{p_{i_{1}}···p_{i_{k}} <p_{n}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} + ∑_{p_{n}≤p_{i_{1}}···p_{i_{k}} <p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} .  (25)

Now, if k = 1, …, n − 1 then

∑_{p_{i_{1}}···p_{i_{k}} <p_{n}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} = ∑_{p_{i_{1}}···p_{i_{k}} <p_{n}^{1≤i_{1}<···<i_{k}≤n−1}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} ,  (26)

and if k = 2, …, n then

∑_{p_{n}≤p_{i_{1}}···p_{i_{k}} <p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}} = ∑_{p_{n}<p_{i_{1}}···p_{i_{k}} <p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}}  (27)

On the other hand, if k = 1 then

∑_{p_{n}≤p_{i_{1}}<p_{n+1}^{1≤i_{1}≤n}} x^{\frac{1}{p_{i_{1}}}} = x^{\frac{1}{pn}}  (28)

Equations (19), (25), (26), (27) and (28) give

B(x) = ∑_{k=1}^{n−1}(−1)^{k+1} ∑_{p_{i_{1}}···p_{i_{k}} <p_{n}^{1≤i_{1}<···<i_{k}≤n−1}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}}

+ x^{\frac{1}{pn}} + ∑_{k=2}^{n}(−1)^{k+1} ∑_{p_{n}<p_{i_{1}}···p_{i_{k}} <p_{n+1}^{1≤i_{1}<···<i_{k}≤n}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}}

That is,

B(x) = ∑_{k=1}^{n−1}(−1)^{k+1} ∑_{p_{i_{1}}···p_{i_{k}} <p_{n}^{1≤i_{1}<···<i_{k}≤n−1}} x^{\frac{1}{p_{i_{1}} ···p_{i_{k}}}}

+ x^{\frac{1}{pn}} + o (x^{\frac{1}{pn}} )  (29)

Finally, equations (29) and (24) give (3).

4 Examples

If n = 2 then Theorem 5 becomes

N(x) = \sqrt{x} + g(x)\sqrt[3]{x},  (30)

where lim_{x→∞} g(x) = 1.

If n = 3 then Theorem 5 becomes

N(x) = \sqrt{x} + \sqrt[3]{x} + g(x)\sqrt[5]{x},

where lim_{x→∞} g(x) = 1.

If n = 4 then Theorem 5 becomes

N(x) = \sqrt{x} + \sqrt[3]{x} + \sqrt[5]{x} − \sqrt[6]{x} + g(x)\sqrt[7]{x},

where lim_{x→∞} g(x) = 1. Consequently

\sqrt{x} + \sqrt[3]{x} < N(x) < \sqrt{x} + \sqrt[3]{x} + \sqrt[5]{x}

If n = 5 then Theorem 5 becomes

N(x) = \sqrt{x} + \sqrt[3]{x} + \sqrt[5]{x} − \sqrt[6]{x} + \sqrt[7]{x} − \sqrt[10]{x} + g(x) \sqrt[11]{x},

where lim_{x→∞} g(x) = 1.

To finish, we shall establish two simple theorems.

Theorem 6. Let us consider the n open intervals (0, 1^{2}), (1^{2}, 2^{2}), …, ((n−1)^{2}, n^{2}). Let S(n) be the number of these n open intervals that contain some perfect power. Then

lim_{n→∞} \frac{S(n)}{n} = 0.

Therefore, almost all the open intervals are empty.

Proof. We have (Nyblom’s asymptotic formula)

N(x) = \sqrt{x} + f(x)\sqrt{x},

where lim_{x→∞} f(x) = 0. Consequently

N(n^{2}) = n + f(n^{2})n,

where n are the n squares 1^{2}, 2^{2}, …, n^{2}. Therefore

0 ≤ S(n) ≤ N(n^{2}) − n = f(n^{2})n.

That is

0 ≤ \frac{S(n)}{n} ≤ f(n^{2}).

Using equation (30) we can obtain a more strong result.

Theorem 7. Let us consider the n open intervals (0, 1^{2}), (1^{2}, 2^{2}), …, ((n−1)^{2}, n^{2}). Let F (n) be the number of perfect powers in these n open intervals. Then F (n) ∼ n^{\frac{2}{3}} .

Proof. Equation (30) gives

N(n^{2}) = n + g(n^{2})n^{\frac{2}{3}} ,

where n are the n squares 1^{2}, 2^{2}, …, n^{2}. Therefore

F (n) = N(n^{2}) − n = g(n^{2})n^{\frac{2}{3}} ∼ n^{\frac{2}{3}} .

5 Acknowledgements

The author would like to thank the anonymous referee for his/her valuable comments and suggestions for improving the original version of this article. The author is also very grateful to Universidad Nacional de Luján.

References

[1] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford, 1960.

[2] W. J. LeVeque, Topics in Number Theory, Addison-Wesley, 1958.

[3] M. A. Nyblom, A counting function for the sequence of perfect powers, Austral. Math. Soc. Gaz. 33 (2006), 338–343.

[4] M. A. Nyblom, Counting the perfect powers, Math. Spectrum 41 (2008), 27–31.

2000 Mathematics Subject Classification: Primary 11A99; Secondary 11B99. Keywords: Perfect powers, counting function, asymptotic formulae.

(Concerned with sequence \underline{A001597}.)

Received May 28 2011; revised version received August 16 2011. Published in Journal of Integer Sequences, September 25 2011.

Return to Journal of Integer Sequences home page.