Skip to main content
1 of 3
Milo Moses
  • 2.9k
  • 12
  • 36

Asymptotic for the probability that a number has $k$ prime factors less than $Q$

If we let $\omega_Q(n)$ denote the number of distinct prime factors of $n$ less than a bound $Q$, then what asymptotic formulas exist for $\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]$ as $Q\to\infty$ if $k$ remains fixed (or perhaps very small with respect to n)?

I am asking this question since my study led me to want to bound the quantity

$$\mathbf{E}_{n\in\mathbb{N}}\left[\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}\right]$$

as $Q\to\infty$. Since

$$\mathbf{E}_{n\in\mathbb{N}}\left[\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}\right]=\sum_{n=1}^{\pi(Q)}\left(\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]\right)\left(\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}\right)$$

and

$$\sum_{n=1}^{\pi(Q)}\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]2^{\omega_Q(n)}\sim_{Q\to\infty} c\log(Q)$$

is well understood, good (upper) bounds on $\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]$ could help me in my effort.

For small values of $k$ computations can be done directly, like

$$\Pr_{n\in\mathbb{N}}[\omega_Q(n)=0]\sim\frac{c}{\log(Q)}$$

and

$$\Pr_{n\in\mathbb{N}}[\omega_Q(n)=1]\sim c\frac{\log(\log(Q))}{\log(Q)}$$

The main approach I have been using is noting that $\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]$ is exactly the coefficient of $x^k$ in the polynomial

$$\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)$$

Asymptotics of this full polynomial are easy to come by, for instance as $Q\to\infty$ we have that

$$\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\sim c \log^{x-1}(Q)$$

Heuristically this would suggest that

$$\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]=\frac{1}{k!}\left.\frac{d^k}{dx^k}\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\right|_{x=0}\sim \frac{c}{k!}\left.\frac{d^k}{dx^k}\log^{x-1}(Q)\right|_{x=0}$$

This argument is however by no means rigorous so I would appreciate true assymptotics.

Milo Moses
  • 2.9k
  • 12
  • 36