3
$\begingroup$

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$?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • 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$ Feb 8, 2011 at 3:48
  • 1
    $\begingroup$ Is there any 'quick and dirty' way of seeing that asymptotic? $\endgroup$ 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$ 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$ Feb 8, 2011 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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