A072114 Number of 3-almost primes (A014612) <= n.

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

Offset: 0

Author

Benoit Cloitre, Jun 19 2002

Keywords

• easy
• nonn

Comments

Number of k <= n such that bigomega(k) = 3.

Let A be a positive integer then card{ x <= n : bigomega(x) = A } ~ (n/Log(n))*Log(Log(n))^(A-1)/(A-1)!. For which n, card{ x <= n : bigomega(x) = 3 } >= card{ x <= n : bigomega(x) = 2 } ?

15530 is the first number for which there are more 3-almost primes than 2-almost primes. See A125149.

References

• E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1, Teubner, Leipzig; third edition : Chelsea, New York (1974).
• G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, p. 203, Publications de l'Institut Cartan, 1990.

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
• E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.

Crossrefs

Cf. A014612, A109251, A001358, A072000.

Partial sums of A101605.

Cf. A125149.

Programs

Mathematica

Table[Sum[KroneckerDelta[PrimeOmega[i], 3], {i, n}], {n, 0, 50}] (* Wesley Ivan Hurt, Oct 07 2014 *)

PARI

for(n=1,100,print1(sum(i=1,n,bigomega(i)==3),","))

PARI

a(n)=my(j,s);forprime(p=2,(n+.5)^(1/3),j=primepi(p)-2;forprime(q=p,sqrtint(n\p),s+=primepi(n\(p*q))-j++));s \\ Charles R Greathouse IV, Mar 21 2012

Python

from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A072114(n): return int(sum(primepi(n//(k*m))-b for a,k in enumerate(primerange(integer_nthroot(n,3)[0]+1)) for b,m in enumerate(primerange(k,isqrt(n//k)+1),a))) # Chai Wah Wu, Aug 17 2024

Formula

a(n) = card{ x <= n : bigomega(x) = 3 }, asymptotically : a(n) ~ (n/log(n))*log(log(n))^2/2 [Landau, p. 211].