A116430 The number of n-almost primes less than or equal to 10^n, starting with a(0)=1.

1, 4, 34, 247, 1712, 11185, 68963, 409849, 2367507, 13377156, 74342563, 407818620, 2214357712, 11926066887, 63809981451, 339576381990, 1799025041767, 9494920297227, 49950199374227, 262036734664892

Offset: 0

Author

Robert G. Wilson v, Feb 10 2006, Jun 01 2006

Keywords

• nonn

Comments

If instead we asked for those less than or equal to 2^n, then the sequence is A000012.

Crossrefs

Cf. A036352, A114106, A114453.

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

Cf. A006880, A036352, A109251, A114106, A114453, A120047 - A120053.

Programs

Mathematica

AlmostPrimePi[k_Integer, n_] := Module[{a, i}, a[0] = 1; If[k == 1, PrimePi[n], Sum[PrimePi[n/Times @@ Prime[Array[a, k - 1]]] - a[k - 1] + 1, Evaluate[ Sequence @@ Table[{a[i], a[i - 1], PrimePi[(n/Times @@ Prime[Array[a, i - 1]])^(1/(k - i + 1))]}, {i, k - 1}]]]]]; (* Eric W. Weisstein, Feb 07 2006 *)
Table[ AlmostPrimePi[n, 10^n], {n, 0, 13}]

PARI

almost_prime_count(N, k) = if(k==1, return(primepi(N))); (f(m, p, k, j=0) = my(c=0, s=sqrtnint(N\m, k)); if(k==2, forprime(q=p, s, c += primepi(N\(m*q))-j; j += 1), forprime(q=p, s, c += f(m*q, q, k-1, j); j += 1)); c); f(1, 2, k);
a(n) = if(n == 0, 1, almost_prime_count(10^n, n)); \\ Daniel Suteu, Jul 10 2023

Python

from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A116430(n):
    if n<=1: return 3*n+1
    def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))
    return int(sum(primepi(10**n//prod(c[1] for c in a))-a[-1][0] for a in g(10**n,0,1,1,n))) # Chai Wah Wu, Aug 23 2024

Extensions

Edited by N. J. A. Sloane, Aug 08 2008 at the suggestion of R. J. Mathar

a(15)-a(16) from Donovan Johnson, Oct 01 2010

a(17)-a(19) from Daniel Suteu, Jul 10 2023