Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
A positive integer $n$ is called a perfect power if and only if there exist two positive integers $p,q$, both are greater than 1, such that $n=p^q$. For example $8=2^3, 36=6^2$ are perfect powers, but $20=2^2*5, 11=11^1$ are not.
Let $A=\{1,2,\dots,1000\}$. How many elements of $A$ is a perfect power?
I hope there exist a beautiful way to solve this, perhaps without calculating the number of primes untill 1000 or considering all the cases. Is there a formula? Thanks in advance!
I don't think there is anything better than counting up each power. There are $\lfloor \sqrt {1000} \rfloor=31$ squares and a similar formula for each power. You are correct that you only need to consider primes as all the fourth powers are squares as well. You also don't need to count any higher than $10$ because $2^{10} \gt 1000$ and you need to only count $1$ once. The sixth powers have been counted twice-once as squares and once as cubes, so need to be subtracted once. This would apply to any number the product of two primes, but six is the only one less than $10$.
If a number is a power then it is a power where the exponent is prime.
Furthermore there is no positive integer less than 1001 that is both (A) a square and a 5th or a 7th power B) a 3rd power and either a 5th or 7th power, (C) a 5th power and a 7th power (D) an 11th (or higher) power.
So the total number of powers no larger than 1001 is # squares + #cubes -#6th powers +#5th powers +#7th powers (besides 1 and 0 that is).
This is 30 + 9 - 2 + 2 + 1 = 40 [if my arithmetic is correct]
