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

%I #54 Jul 23 2024 18:51:10

%S 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,

%T 10,10,10,11,12,12,12,12,12,12,12,13,13,13,13,13,14,14,14,14,15,15,16,

%U 17,17,17,17,18,18,18,19,19,19,19,20,20,20,20,20,21,21,21,22,22,22,22

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

%C 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

%C Number of squarefree semiprimes not exceeding n. - _Wesley Ivan Hurt_, May 25 2015

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

%H N. J. A. Sloane, <a href="/A072613/b072613.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Semiprime.html">Semiprime</a>.

%F a(n) = Sum_{p<sqrt(n)} (Pi(x/p)-Pi(p)), where Pi(n) is the prime counting function, A000720, and the sum is over all primes less than sqrt(n). [_N-E. Fahssi_, Mar 05 2009]

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

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

%F a(n) = Sum_{i<=n | tau(i)=4} mu(i). - _Wesley Ivan Hurt_, May 25 2015

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

%p 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

%t fPi[n_] := Sum[ PrimePi[n/ Prime@i] - i, {i, PrimePi@ Sqrt@ n}]; Array[ fPi, 81] (* _Robert G. Wilson v_, Jul 22 2008 *)

%t Accumulate[Table[If[PrimeOmega[n] MoebiusMu[n]^2 == 2, 1, 0], {n, 100}]] (* _Wesley Ivan Hurt_, Jun 01 2017 *)

%t Accumulate[Table[If[SquareFreeQ[n]&&PrimeOmega[n]==2,1,0],{n,100}]] (* _Harvey P. Dale_, Aug 05 2019 *)

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

%o (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

%o (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

%o (Python)

%o from math import isqrt

%o from sympy import prime, primepi

%o 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

%Y Cf. A072000.

%Y Partial sums of A280710.

%K easy,nonn

%O 1,10

%A _Benoit Cloitre_, Aug 11 2002