A positive integer $n$ is called squarefree, if no square of a prime divides $n$, thus $1, 2, 3, 5, 6, 7, 10, 11$ are squarefree, but not $4, 8, 9, 12$.
How many squarefree numbers are there below $2^{50}$?
To count the number of squarefree numbers less than $2^{50}$, it’s best to use the principle of inclusion and exclusion.
This is based on the fact that a number is square-free if and only if it’s divisible by no square number greater than $1$. So, for a number less than $2^{50}$ to be square-free, it cannot be divisible by $p^2$ for any prime $p$ less than $\sqrt{2^{50}}$ (since if $p \geq \sqrt{2^{50}}$, $p^2 \geq 2^{50}$).
First, note that there are $2^{50}$ total numbers less than $2^{50}$.
Next, let’s count the numbers that are divisible by $p^2$ for some prime $p$ less than $\sqrt{2^{50}} = 2^{25}$. It will simplify things if we notice that there are $9$ primes less than $32$, which is just more than $2^5$:
These 9 primes are $2,3,5,7,11,13,17,19,23$ and $29$.
Consider the subsets of these 9 prime numbers. There are $2^9 = 512$ total subsets. For each subset, we can multiply the primes in that set to get a square, and then look at the set of all numbers less than $2^{50}$ that are divisible by that square.
By inclusion-exclusion, the number of squarefree numbers less than $2^{50}$ is then given by the alternating sum:
$2^{50} -\sum_{p\ prime} \lfloor \frac{2^{50}}{p^2} \rfloor +\sum_{p,q\ primes} \lfloor \frac{2^{50}}{p^2q^2} \rfloor – \ldots $
Adding up these terms individually requires some computation, but doing so should give you the final answer: the number of squarefree numbers less than $2^{50}$.
As the computation can be very laborious, it’s advisable to use a computer to calculate the final number.
More Answers:
Maximising a Weighted ProductPrize Strings
Best Approximations