experimental-projects/oeis-research/Robert G. Wilson v/The number of n-almost primes less than or equal to 10^n, starting with a(0)=1/prog.sf

#!/usr/bin/ruby

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

# Known terms:
#   1, 4, 34, 247, 1712, 11185, 68963, 409849, 2367507, 13377156, 74342563, 407818620, 2214357712, 11926066887, 63809981451, 339576381990, 1799025041767

# New terms:
#   a(17) = 9494920297227
#   a(18) = 49950199374227
#   a(19) = 262036734664892

#`{
# PARI/GP program:

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)); \\ ~~~~

}

#for n in (0..100) {
for n in (0..100) {
    say [n, n.almost_prime_count(10**n)]
}

__END__
[0, 1]
[1, 4]
[2, 34]
[3, 247]
[4, 1712]
[5, 11185]
[6, 68963]
[7, 409849]
[8, 2367507]
[9, 13377156]
[10, 74342563]
[11, 407818620]
[12, 2214357712]
[13, 11926066887]
[14, 63809981451]
[15, 339576381990]
[16, 1799025041767]
[17, 9494920297227]
[18, 49950199374227]
[19, 262036734664892]