Square Root Smooth Numbers

A positive integer is called square root smooth if all of its prime factors are strictly less than its square root.
Including the number $1$, there are $29$ square root smooth numbers not exceeding $100$.

How many square root smooth numbers are there not exceeding $10\,000\,000\,000$?

Let $\omega(x)$ denote the number of SRSNs $\leq x$. We apply the principle of inclusion and exclusion. For any prime $p$, let $S(p)$ denote the set of positive integers $\leq x$ whose prime factorization includes $p$ as a factor; then by definition $|\cap _{p\leq\sqrt{x}}S(p)|=\omega(x)$.

By the principle of inclusion and exclusion, we see that
\[\left|\bigcap_{p\leq\sqrt{x}}S(p)\right|=\left|\bigcup_{p\leq\sqrt{x}}S(p)\right|-\sum _{p,q\leq\sqrt{x}}\left|S(p)\cap S(q)\right|+\dotsb.\]

Note that $\left|\bigcup_{p\leq\sqrt{x}}S(p)\right|=\sum _{q\leq\sqrt{x}}\lfloor \tfrac{x}{q}\rfloor$ by definition, where $\lfloor a\rfloor$ denotes the greatest integer less than or equal to $a$. We wish to find an expression for $\left|S(p)\cap S(q)\right|$ where $pp$ and $x\geq 1$. Hence $\left|S(p)\cap S(q)\right|=\sum _{r\leq\sqrt[p]{x/p^2}}\lfloor \tfrac{x}{p^2r}\rfloor$.

This process can be repeated to find $\left|S(p)\cap S(q)\cap S(r)\right|$, $\left|S(p)\cap S(q)\cap S(r)\cap S(s)\right|$, and so forth for any given set of primes. We can use this process to estimate $\omega(x)$ when $x=10^{10}$ by computing the following steps for all subset of primes less than $\sqrt{10^{10}} , i.e. $ less than $10^{5}$:

1. Calculate $\sum _{p\leq\sqrt{x}}\lfloor \tfrac{x}{p}\rfloor$ , which is the number of SRSNs with at least one prime factor less than $\sqrt{x}$ .
2. Subtract $\sum _{px/2$, i.e. $2p^{n-1}>x$), in which case the subsequent steps contribute $0$ to $\omega(x)$ .

Under the conditions given, only 5 steps are necessary, hence this is feasible to be calculated by hand or with a calculator, resulting in $\omega(x)$ = 36,247,771.

More Answers: