0
$\begingroup$

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!

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ i hope you do understand that your way of direct counting isn't quite right because you have many double counting - you can however use your argument in addition to PIE to get the wanted result $\endgroup$
    – ned grekerzberg
    Sep 21, 2018 at 19:47
  • $\begingroup$ @nedgrekerzberg: I had thought that using primes was enough, but you are right. Most of the doublecount is eliminated by only using prime powers. There are only two left. $\endgroup$
    – Ross Millikan
    Sep 21, 2018 at 19:55
0
$\begingroup$

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]

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .