How many positive integers from set $\{1,2...,10^{30}\}$ can't be represented as 2nd, 3rd, or 5th power of some positive integer?

Question

An interesting problem I ran across. My guess is that it can be solved somehow using inclusion-exclusion principle. It would be a fun thing to learn how to do this, so I could use that knowledge in solving some other problems. Tried searching the internet, but didn't find any tutorial or similar problem like this one. I hope that this post will help someone in the future who needs to solve this type of problems.

So, it goes like:

How many positive integers from set $\{1,2...,10^{30}\}$ can't be represented as 2nd, 3rd, or 5th power of some positive integer?

Answer 1

Since $10^{30}=(10^{15})^2=(10^{10})^3=(10^{6})^5=(10^5)^6=(10^3)^{10}=(10^2)^{15}$.

Thus, the number of square is $10^{15}$, the number of cubes is $10^{10}$, the number of 5-th power is $10^6$, the number of 6-th power is $10^5$, the number of 10-th power is $10^3$, the number of 15-th power is $10^2$, and the number of 30-th power is $10$.

Thus, there are $10^{30}-10^{15}-10^{10}-10^6+10^5+10^3+10^2-10$ numbers cannot be represented as 2-nd, 3rd, or 5-th powers.

Answer 2

There are $10^{15}$ squares.

There are $10^{10}$ cubes.

There are $10^6$ quints.

There are $10^5$ powers to the 6 which are both squares and cubes.

There are $10^3$ powers to the 10 which are both squares and quints.

There are $10^2$ powers to the 15 which are both cubes and quints.

And there are $10$ powers to the 30 which are all three.

Apply Exclusion/Inclusion.

Total that cant be are ALL numbers - (ALL squares,cubes, and quints) + (Those that can be two of the property as these were double counted) - (those that are all three as these were triple counted).

So answer is $10^{30} - (10^{15}+10^{10} + 10^6)+(10^5+10^3+10^2) - 10$