Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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
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$. –  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
add comment

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.