Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
1  
The On-Line Encyclopedia of Integer Sequences ( oeis.org/A001358) agrees with your estimate for the nth almost prime, and gives sources. –  Michael Lugo Feb 8 '11 at 3:48
1  
Is there any 'quick and dirty' way of seeing that asymptotic? –  Stanley Yao Xiao Feb 8 '11 at 4:02
1  
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$. –  Péter Komjáth Feb 8 '11 at 6:33
    
@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? –  Gerry Myerson Feb 8 '11 at 23:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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