cp's OEIS Frontend

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

%I A072613 #55 Feb 16 2025 08:32:46
%S A072613 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 A072613 10,10,10,11,12,12,12,12,12,12,12,13,13,13,13,13,14,14,14,14,15,15,16,
%U A072613 17,17,17,17,18,18,18,19,19,19,19,20,20,20,20,20,21,21,21,22,22,22,22
%N A072613 Number of numbers of the form p*q (p, q distinct primes) less than or equal to n.
%C A072613 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 A072613 Number of squarefree semiprimes not exceeding n. - _Wesley Ivan Hurt_, May 25 2015
%D A072613 G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics, 1995.
%H A072613 N. J. A. Sloane, <a href="/A072613/b072613.txt">Table of n, a(n) for n = 1..10000</a>
%H A072613 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Semiprime.html">Semiprime</a>.
%F A072613 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 A072613 Asymptotically a(n) ~ (n/log(n))log(log(n)) [G. Tenenbaum pp. 200--].
%F A072613 a(n) = Sum_{i<=n | Omega(i)=2} mu(i). - _Wesley Ivan Hurt_, Jan 05 2013, revised May 25 2015
%F A072613 a(n) = Sum_{i<=n | tau(i)=4} mu(i). - _Wesley Ivan Hurt_, May 25 2015
%e A072613 a(6) = 1 since 2*3 is the only number of the form p*q less than or equal to 6.
%p A072613 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 A072613 fPi[n_] := Sum[ PrimePi[n/ Prime@i] - i, {i, PrimePi@ Sqrt@ n}]; Array[ fPi, 81] (* _Robert G. Wilson v_, Jul 22 2008 *)
%t A072613 Accumulate[Table[If[PrimeOmega[n] MoebiusMu[n]^2 == 2, 1, 0], {n, 100}]] (* _Wesley Ivan Hurt_, Jun 01 2017 *)
%t A072613 Accumulate[Table[If[SquareFreeQ[n]&&PrimeOmega[n]==2,1,0],{n,100}]] (* _Harvey P. Dale_, Aug 05 2019 *)
%o A072613 (PARI) a(n)=sum(k=1,n,if(abs(omega(k)-2)+(1-issquarefree(k)),0,1))
%o A072613 (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 A072613 (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 A072613 (Python)
%o A072613 from math import isqrt
%o A072613 from sympy import prime, primepi
%o A072613 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 A072613 Cf. A072000.
%Y A072613 Partial sums of A280710.
%K A072613 easy,nonn
%O A072613 1,10
%A A072613 _Benoit Cloitre_, Aug 11 2002