L−1 X k=1 (−1)k+1 X 2≤i1<···<ik≤L ⌊x1/lcm(i1,...,ik

Problem 11117

(American Mathematical Monthly, Vol.111, December 2004) Proposed by M. Nyblom (Australia).

An integer n is a positive power if there exist integers a and k such that a≥ 1, m ≥ 2, and n = a^m. Let N(x) denote the number of positive powers n such that 1 ≤ n ≤ x. For real x ≥ 4 and with L= ⌊log₂x⌋, show that

N(x) =

L−1

X

k=1

(−1)^k+1 X

2≤i₁<···<ik≤L

⌊x^{1/lcm(i1,...,ik)}⌋.

Solution proposed by Giulio Francot and Roberto Tauraso,

Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

For m ≥ 2 and for x ≥ 4, let Am(x) be the set of m-powers contained in the interval [1, x]. Since

|Am(x)| = ⌊x^1/m⌋ then Am(x) = {1} for m > L = ⌊log₂x⌋ ≥ 2 and by the inclusion-exclusion principle

N(x) =     

L

[

m=2

Am(x)     

=

L−1

X

k=1

(−1)^k+1 X

2≤i₁<···<ik≤L

|Ai₁(x) ∩ · · · ∩ Aik(x)|

Let p^α₁¹p^α₂²· · · p^α_r^r be the prime factorization of n then n ∈ Am(x) if and only if 1 ≤ n ≤ x and m| αsfor all s = 1, . . . , r. Hence

Ai₁(x) ∩ · · · ∩ Aik(x) = Alcm(i₁,...,ik)(x), and therefore

N(x) =

L−1

X

k=1

(−1)^k−1 X

2≤i₁<···<ik≤L

A_lcm(i1,...,ik)(x) =

L−1

X

k=1

(−1)^k+1 X

2≤i₁<···<ik≤L

⌊x^{1/lcm(i1,··· ,ik)}⌋.