A072613 Number of numbers of the form p*q (p, q distinct primes) less than or equal to n.

0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 9, 10, 10, 10, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 16, 17, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22

Offset: 1

Author

Benoit Cloitre, Aug 11 2002

Keywords

• easy
• nonn

Comments

There was an old comment here that said a(n) was equal to A070548(n) - 1, but this is false (e.g. at n=210). - N. J. A. Sloane, Sep 10 2008

Number of squarefree semiprimes not exceeding n. - Wesley Ivan Hurt, May 25 2015

Examples

			a(6) = 1 since 2*3 is the only number of the form p*q less than or equal to 6.
		

References

• G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics, 1995.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Semiprime.

Crossrefs

Cf. A072000.

Partial sums of A280710.

Programs

Maple

f:=proc(n) local c,i,j,p,q; c:=0; for i from 1 to n do p:=ithprime(i); if p^2 >= n then break; fi; for j from i+1 to n do q:=ithprime(j); if p*q > n then break; fi; c:=c+1; od: od; RETURN(c); end; # N. J. A. Sloane, Sep 10 2008

Mathematica

fPi[n_] := Sum[ PrimePi[n/ Prime@i] - i, {i, PrimePi@ Sqrt@ n}]; Array[ fPi, 81] (* Robert G. Wilson v, Jul 22 2008 *)
Accumulate[Table[If[PrimeOmega[n] MoebiusMu[n]^2 == 2, 1, 0], {n, 100}]] (* Wesley Ivan Hurt, Jun 01 2017 *)
Accumulate[Table[If[SquareFreeQ[n]&&PrimeOmega[n]==2,1,0],{n,100}]] (* Harvey P. Dale, Aug 05 2019 *)

PARI

a(n)=sum(k=1,n,if(abs(omega(k)-2)+(1-issquarefree(k)),0,1))

PARI

a(n) = my(t=0,i=0); forprime(p = 2, sqrtint(n), i++; t+=primepi(n\p)); t-binomial(i+1,2) \\ David A. Corneth, Jun 02 2017

PARI

upto(n) = {my(l=List(), res=[0, 0, 0, 0, 0], j=1, t=0); forprime(p = 2, n, forprime(q=nextprime(p+1), n\p, listput(l, p*q))); listsort(l); for(i=2, #l, t++;res=concat(res, vector(l[i]-l[i-1], j, t))); res} \\ David A. Corneth, Jun 02 2017

Python

from math import isqrt
from sympy import prime, primepi
def A072613(n): return int(sum(primepi(n//prime(k))-k+1 for k in range(1,primepi(isqrt(n))+1))) - primepi(isqrt(n)) # Chai Wah Wu, Jul 23 2024

Formula

a(n) = Sum_{pA000720, and the sum is over all primes less than sqrt(n). [N-E. Fahssi, Mar 05 2009]

Asymptotically a(n) ~ (n/log(n))log(log(n)) [G. Tenenbaum pp. 200--].

a(n) = Sum_{i<=n | Omega(i)=2} mu(i). - Wesley Ivan Hurt, Jan 05 2013, revised May 25 2015

a(n) = Sum_{i<=n | tau(i)=4} mu(i). - Wesley Ivan Hurt, May 25 2015