2
$\begingroup$

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}$ ?

  • 2
    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.2012-06-12
  • 0
    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 ?2012-06-12
  • 2
    (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$.2012-06-12
  • 0
    we've just reached this exact solution as well! :D2012-06-12
  • 0
    It is always best when you discover things yourself.2012-06-12

1 Answers 1

4

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