How many numbers below $n$ with a square number of distinct prime factors?

Question

Is there a nice closed-form expression for, or asymptotic formula for the number of numbers below $n$ with a square number of distinct prime factors?

Motivation:

As a student who studies mathematics in my spare time, I encountered some questions asking about the number of numbers below certain limits that adhere to certain elementary factor properties and later was thinking about it, when it occurred to me that there were many, seemingly simple or natural, questions to ask about "counting functions" that nothing I know can help with...

So, more generally, on top of an answer to the above, are there nice toolkits or pieces of machinery that can, with some property, tell me the number of numbers below $n$ with that property? (even if this toolkit only works for a specific subset of properties, I would be interested)

Answer 1

Let $\pi_k(n)$ be the number of integers $\le n$ with exactly $k$ distinct prime factors. You are looking for $\sum_{m=1}^{\infty}\pi_{m^2}(n)=\pi(n)+\pi_4(n)+\pi_9(n)+\ldots$. Hardy and Ramanujan proved the upper bound $$ \pi_k(n) < c(n/\log n) \cdot (\log\log n + d)^{k-1}/(k-1)!$$ for some constants $c$ and $d$, and Erdös and Pillai (independently) proved the lower bound $$ \pi_k(n) > c'(n/\log n) \cdot (\log\log n)^{k-1}/(k-1)! $$ for some constant $c'$. So, putting things together, you have $$ \frac{c'(\log\log n)^{k-1}}{(k-1)!}<\frac{\pi_{k}(n)}{n/\log n}<\frac{c(\log\log n+d)^{k-1}}{(k-1)!}. $$ Taking $g(z)=\sum_{m=1}^{\infty}\frac{z^{m^2-1}}{(m^2-1)!}$, you have $$ c'g(\log \log n)<\frac{\sum_{m=1}^{\infty}\pi_{m^2}(n)}{n/\log n}<cg(\log\log n + d). $$ Update:

After spending some time looking into the asymptotic growth of functions like $g(z)$, analytic with every derivative at the origin equalling zero or one... which seems interesting and may be worth its own question... I think that $g(z)$ is $\Theta(e^z / \sqrt{z})$ for large $z$. If that's correct, then in fact $$ \sum_{m=1}^{\infty}\pi_{m^2}(n)\in\Theta\left(\frac{n}{\sqrt{\log\log n}}\right). $$

Answer 2

Let $\omega(n)$ be the number of distinct prime factors of $n$. Distribution of the numbers satisfying $\omega(n)=k$ is well-known. The method is discussed in Montgomery & Vaughan 'Multiplicative Number Theory' volume 1, chapter 7, exercise 3. Denote by $$ F(s,z)=\prod_p \left(1+\frac z{p^s-1}\right)\left(1-\frac1{p^s}\right)^z. $$ The product is taken over prime numbers. This product converges for $\Re(s)=\sigma>1/2$, uniformly for $|z|\leq R<\infty$.

Let $\rho_k(x)$ be the number of $n\leq x$ for which $\omega(n)=k$. Then $$ \rho_k(x)=G\left(\frac{k-1}{\log\log x}\right)\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\left(1+O_R\left(\frac k{(\log\log x)^2}\right)\right) $$ uniformly for $1\le k\le R\log\log x$. Here, $G(z)=F(1,z)/\Gamma(z+1)$, and $G(0)=G(1)=1$. Also, $G(z)\asymp 1$ on $0\leq z\leq R$.

It is okay to have $R=e+1$ since we have the number $B(x,R)$ for which $\omega(n)\geq R\log\log x$ is $$ B(x,R)=O\left( x(\log x)^{R-1-R\log R} \right) $$ and $R-1-R\log R<-1$.

Then it remains summing over the ones with $k=l^2$. Let $y=\log\log x$.

First, note by Stirling's formula that $$ \frac{y^{l^2-1}}{(l^2-1)!} \sim \frac1{\sqrt{2\pi(l^2-1)}}\left( \frac{ey}{l^2-1}\right)^{l^2-1}\sim \frac1{l\sqrt{2\pi} }\left( \frac{ey}{l^2-1}\right)^{l^2-1}. $$ Let $n=l^2-1$. We have $$ \left( \frac{ey}{l^2-1}\right)^{l^2-1}=\exp\left(n\log\left(\frac{ey}n \right) \right) =\exp\left( n \left(1+\log(\frac yn -1 +1) \right)\right). $$ We sum over $\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}$, so that $-1<\frac1R -1 \leq \frac yn-1\leq \frac1{0.6}-1<1$. Over $\frac1R-1\leq x\leq \frac1{0.6}-1$, we have $$ \log(1+x)\leq x - \frac16 x^2. $$ This gives $$ \exp\left( n \left(1+\log(\frac yn -1 +1) \right)\right)\leq \exp\left(n(1+\frac yn -1 - \frac16 (\frac yn -1)^2)\right) $$ $$ =e^y\exp\left(-\frac16 n(\frac yn -1)^2 \right)=e^y \exp\left(-\frac16 (\frac y{\sqrt n} - \sqrt n)^2 \right). $$ Thus, $$ \sum_{\substack{{\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}}\\{n=l^2-1}}}\exp\left(-\frac16 (\frac y{\sqrt n} - \sqrt n)^2 \right)\asymp 1. \ \ \ \ (*) $$ Then $$ \sum_{\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}} \frac1{l\sqrt{2\pi} }\left( \frac{ey}{l^2-1}\right)^{l^2-1}\asymp \frac{e^y}{\sqrt y}. $$ Hence $$ \sum_{\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}} \frac{y^{l^2-1}}{(l^2-1)!} \asymp \frac{e^y}{\sqrt y}.$$

We sum over the remaining $l$ with $\asymp \log y$ intervals of the type $[\sqrt{1+\alpha^{t+1} y},\sqrt{1+\alpha^t y}]$ with $0<\alpha<1$ and varying $t$.

By the same method above, we have $$\sum_{\sqrt{1+\alpha^{t+1}y}\leq l \leq \sqrt{1+\alpha^t y}}\frac{y^{l^2-1}}{(l^2-1)!}\ll \frac{e^{\alpha^t y}}{\sqrt{\alpha^t y}}\left(\frac1{\alpha^t}\right)^{\alpha^t y}\ll \exp\left((\alpha - \alpha\log \alpha)y\right). $$ Since $0<\alpha - \alpha\log \alpha <1$, the sum over whole remaining range contribute to $$ \ll (\log y)\exp\left((\alpha - \alpha\log \alpha)y\right) \ll \frac{e^y}{\sqrt y}. $$ Therefore, by combining all estimates, we have $$ \sum_{l\leq \sqrt{1+Ry}} \frac{y^{l^2-1}}{(l^2-1)!}\asymp \frac{e^y}{\sqrt y}. $$ This proves that the conjectured answer by @mjqxxxx is true.