# How many numbers $\in [1 .. 10^9]$ that are not of the form $x^2, x^3$ or $x^5$?

We've started with $x^2$, saying that there are $\sqrt{10^9}$ numbers that are not $\in 10^9$

i'm thinking that if we add $\sqrt[3]{10^9}$ and $\sqrt[5]{10^9}$ to $\sqrt{10^9}$ and subtract them from $10^9$, we would have gone too far and excluded too many numbers due to repeating numbers such as $2^2$,$2^3$ and $2^5$, for example.

does it even make sense to do so? aren't all numbers in $\sqrt[3]{10^9}$ and $\sqrt[5]{10^9}$ $< 10^9$ already in $\sqrt{10^9}$ ?

-
Call a number bad if it is a square or a cube or a fifth power. The squares $1$, $4$, $9$, $16$, and so on are bad. Some cubes are in the above list, like $1$ and $64$, but some cubes are not, like $8$ and $27$. The general device for this kind of counting problem is the Principle of Inclusion/Exclusion. That works nicely here, though there are other ways. – André Nicolas Jun 12 '12 at 16:36
should i then repeat the exclusion process for the other two before adding them to $\sqrt{10^9}$, you think? or am i thinking about this in the wrong way ? – Shokodemon Jun 12 '12 at 16:38
(i) Count the squares, cubes, fifth powers. Add up. Overestimate! (ii) Count the $6$th powers, $10$th powers, $15$th powers, add up, subtract from (i). Now we have an underestimate. (iii) count the $30$th powers. There is only one, since $10^9<2^{30}$. So add $1$. – André Nicolas Jun 12 '12 at 16:45
we've just reached this exact solution as well! :D – Shokodemon Jun 12 '12 at 16:59
It is always best when you discover things yourself. – André Nicolas Jun 12 '12 at 18:57

Let $a=10^9$. There are $\lfloor a^{1/2} \rfloor$ squares, $\lfloor a^{1/3}\rfloor$ cubes and $\lfloor a^{1/5}\rfloor$ $5^{th}$ powers within $1$ to $10^9$. So, the P.I.E. gives the answer to be: $a-(\lfloor a^{1/2}\rfloor+\lfloor a^{1/3}\rfloor+\lfloor a^{1/5}\rfloor-\lfloor a^{1/6}\rfloor-\lfloor a^{1/10}\rfloor-\lfloor a^{1/15}\rfloor+\lfloor a^{1/30}\rfloor)$.