Problem 3 · Perfect powers up to 2025
Counting squares, cubes and higher powers without repeats.
Integer answer, at most 4 digitsHow many natural numbers between $1$ and $2025$ can be written as $a^b$ with $a$ and $b$ natural numbers greater than (not equal to) $1$?
Copa Cangur · SCM
Hard
Closed answer
Reasoned solution
Key idea: prime exponents suffice ($4 = 2^2$ already falls among the squares, etc.); then subtract the numbers counted twice.
Squares: from $2^2 = 4$ to $45^2 = 2025$: $44$. Cubes: from $2^3$ to $12^3 = 1728$: $11$. Fifth powers: $32, 243, 1024$: $3$. Sevenths: $128$: $1$. Sum: $59$.
Repeats: $64$ and $729$ (sixth powers: both square and cube) and $1024 = 2^{10} = 32^2 = 4^5$ (square and fifth power): $3$ duplicates.
$$44 + 11 + 3 + 1 - 2 - 1 = 56.$$
Answer: 56