9
$\begingroup$

Let $ \pi(x) $ be the prime counting function: the number of numbers $\leq x$ with just one prime factor. Let $ \pi_n(x) $ count the number of numbers $\leq x$ with exactly $n$ prime factors (counted with multiplicity).

When plotting the values for different $n$ up to large $x$, it seems that for every $n$ there will be a point from where on $ \pi_n(x) > \pi(x) $. I'm conflicted about my intuition on this. On one hand, it seem's to be plausible because numbers with more and more prime factors become more and more common. On the other hand, numbers with, say, 100 prime factors seem like they are so rare that they will be always less than $ \approx \frac{x}{\log x}$

My question is: Will there at some point be more numbers with $n$ factors than prime numbers for any $n$?

Bonus question for positive answer: Is there a way to find the point this happens for a given $n$ other than the naive approach?

Bonus question for negative answer: What is the largest $n$ which surpasses the prime counting function?

Chart $\pi_n(x)$ for $x \lt 100$, at $\approx 25$ there are more numbers with $2$ factors than prime numbers.

Chart $\pi_n(x)$ for $x \lt 100.000$, at $\approx 40000$ there are more numbers with $5$ factors than prime numbers.

Chart $\pi_n(x)$ for $x \lt 10.000.000$, at $\approx 4.000.000$ there are more numbers with $6$ factors than prime numbers.

(Please ignore the 'Divisors' in the chart legend, it should read 'Factors')

$\endgroup$
  • 2
    $\begingroup$ $\pi_n(x)$ is the number of numbers $≤x$ with exactly $n$ prime factors or at least $n$ prime factors? $\endgroup$ – Conifold Feb 3 at 23:58
  • 1
    $\begingroup$ @Conifold with exactly $n$ prime factors $\endgroup$ – SmallestUncomputableNumber Feb 4 at 0:01
  • $\begingroup$ @Barry Cipra: two, I'll edit the question $\endgroup$ – SmallestUncomputableNumber Feb 4 at 7:17
5
$\begingroup$

Interesting question. My intuition is that $\pi_n(x)>\pi(x)$ for large $x$.

Heuristic argument: We note that, for each $n$, the sum of the reciprocals of the $n-$primes diverges. (here, of course, an $n-$prime means a natural number with exactly $n$ prime divisors). This is clear since we can just pick some $(n-1)-$prime $A$ and then note that every number of the form $Ap$ for prime $p$ is an $n-$prime, and of course $\sum_{\text {p prime}}\frac 1{Ap}$ diverges.

Now let $\{A_1, A_2,\cdots \}$ be the $(n-1)-$primes. Then we can write (speaking roughly) $$\pi_n(x)≥\pi\left(\frac x{A_1}\right) +\pi\left(\frac x{A_2}\right)+\cdots$$

And for any $A$ we have $$\pi\left(\frac x{A}\right)\sim \frac 1{A}\frac x{\ln x-\ln A}≥\frac 1{A}\frac x{\ln x}\sim \frac 1A\times \pi(x)$$

Thus for large $x$ :$$\pi_n(x)≥\pi(x)\times \left(\frac 1{A_1}+\frac 1{A_2}+\cdots\right)$$ And we just need to use enough of the $A_i$ to get that sum over $1$.

I think that for large enough $x$ it shouldn't be too hard to make this argument more solid. As to getting a good estimate of the crossing point, well that sounds tougher. If you need $A_1, \cdots, A_N$ to get the sum over $1$ then I'd start to look around $x=A_N$ but, of course, the estimates we are relying on are very unreliable for small arguments so it's hard to imagine that this will work terribly well. The argument will be on much surer ground when $\frac x{A_N}$ is large.

Worth noting: these divergent series do not diverge rapidly. For $3-$primes I note that you need to go out to $A_{96}=402$ before the sum of the reciprocals exceeds $1$.

$\endgroup$
  • $\begingroup$ just naively, the number of semiprimes up to $n$ is always greater than $({\sqrt{n}\over \ln\sqrt{n}})^2$ $\endgroup$ – user645636 Feb 4 at 1:00
  • $\begingroup$ @RoddyMacPhee Again, you mean for large enough $n$. And you can get a similar formula for $n-$primes. But I think that you get sharper bounds out of terms like $\lambda x$ then out of terms like $x^{1/n}$, but of course I could have that wrong. $\endgroup$ – lulu Feb 4 at 1:08
  • $\begingroup$ all I know is I plugged it into the prime number theorem. if you look at sundaram, and apply a few things you might be able to coax things out. I know $$\sqrt{n\over 4}\approx a, (2a+1)^2\approx n$$ by that. $\endgroup$ – user645636 Feb 4 at 1:19
  • 1
    $\begingroup$ @RoddyMacPhee Not sure I see where you are going with that. I don't immediately see how to turn your sort of lower bound into a heuristic argument. Your expression is $\frac {4n}{(\ln n)^2}$ which is not greater than $\frac n{\ln n}$ except for very small $n$. But of course I might be missing something. $\endgroup$ – lulu Feb 4 at 1:32
  • $\begingroup$ you can sieve them using sundaram. it's a lower bound. $\endgroup$ – user645636 Feb 4 at 1:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.