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

%I #42 Aug 17 2024 01:34:16

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

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

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

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

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

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

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

%D E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1, Teubner, Leipzig; third edition : Chelsea, New York (1974).

%D G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, p. 203, Publications de l'Institut Cartan, 1990.

%H Charles R Greathouse IV, <a href="/A072114/b072114.txt">Table of n, a(n) for n = 0..10000</a>

%H E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, <a href="http://name.umdl.umich.edu/ABV2766.0001.001">vol. 1</a> and <a href="http://name.umdl.umich.edu/ABV2766.0002.001">vol. 2</a>, Leipzig, Berlin, B. G. Teubner, 1909.

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

%t Table[Sum[KroneckerDelta[PrimeOmega[i], 3], {i, n}], {n, 0, 50}] (* _Wesley Ivan Hurt_, Oct 07 2014 *)

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

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

%o (Python)

%o from math import isqrt

%o from sympy import primepi, primerange, integer_nthroot

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

%Y Cf. A014612, A109251, A001358, A072000.

%Y Partial sums of A101605.

%Y Cf. A125149.

%K easy,nonn

%O 0,13

%A _Benoit Cloitre_, Jun 19 2002