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

#!/usr/bin/ruby

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

# Known terms:
#   1, 4, 22, 125, 669, 3410, 16677, 78369, 359110, 1612613, 7133274, 31185350, 135062165, 580556958, 2480278767, 10542976739, 44626102826, 188215850830, 791374442571

# New terms:
#   a(19) = 3318478309647
#   a(20) = 13882441625034
#   a(21) = 57952990683107

#`{
# 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(8^n, n)); \\ ~~~~

}

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

__END__
[0, 1]
[1, 4]
[2, 22]
[3, 125]
[4, 669]
[5, 3410]
[6, 16677]
[7, 78369]
[8, 359110]
[9, 1612613]
[10, 7133274]
[11, 31185350]
[12, 135062165]
[13, 580556958]
[14, 2480278767]
[15, 10542976739]
[16, 44626102826]
[17, 188215850830]
[18, 791374442571]
[19, 3318478309647]
[20, 13882441625034]
[21, 57952990683107]