In the famous Chen's Theorem which states that every sufficiently large even positive integer $n$ can be written as $n = p + q$, where $p$ is a prime and $q$ is a product of at most two primes. This is the precise 'almost prime' definition we use, where it's either a prime or a product of two primes. Now from the prime number theorem we have a crude estimate for the size of the $n$th prime, namely $p_n \sim n \log(n)$. Are there any similar estimates for the set of almost primes? To be more precise, let $\mathcal{P}$ denote the set of primes, and let $\mathcal{P}^2$ denote the set {$pq : p,q$ primes}. Set $Q = \mathcal{P} \cup \mathcal{P}^2$ and enumerate the elements of $Q$as $a_1, a_2, \cdots$ The question is do we have an approximation for $a_n$?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The number of almost-primes up to $x$ is asymptotic to $x\log\log x/\log x$. It doesn't matter whether you include the primes or not, as there are only $x/\log x$ of them. I think this gives $n\log n/\log\log n$ as a crude estimate for the $n$th almost prime.
-
1$\begingroup$ The On-Line Encyclopedia of Integer Sequences ( oeis.org/A001358) agrees with your estimate for the nth almost prime, and gives sources. $\endgroup$Michael Lugo– Michael Lugo2011-02-08 03:48:45 +00:00Commented Feb 8, 2011 at 3:48
-
1$\begingroup$ Is there any 'quick and dirty' way of seeing that asymptotic? $\endgroup$2011-02-08 04:02:22 +00:00Commented Feb 8, 2011 at 4:02
-
1$\begingroup$ Yes. For a prime $p\leq x$ the number of number of the form $pq\leq x$ where $q$ is prime is roughly $(x/p)/\log (x/p)$, which, when added up, is around $Sx/\log x$ where $S$ is the sum of the reciprocals of the primes up to $x$, which is $\log \log x$. $\endgroup$Péter Komjáth– Péter Komjáth2011-02-08 06:33:15 +00:00Commented Feb 8, 2011 at 6:33
-
$\begingroup$ @Peter, I thought of that argument, but doesn't it count each almost prime twice? leading to an estimate that's off by a factor of 2? $\endgroup$Gerry Myerson– Gerry Myerson2011-02-08 23:32:35 +00:00Commented Feb 8, 2011 at 23:32