login
A116430
The number of n-almost primes less than or equal to 10^n, starting with a(0)=1.
16
1, 4, 34, 247, 1712, 11185, 68963, 409849, 2367507, 13377156, 74342563, 407818620, 2214357712, 11926066887, 63809981451, 339576381990, 1799025041767, 9494920297227, 49950199374227, 262036734664892
OFFSET
0,2
COMMENTS
If instead we asked for those less than or equal to 2^n, then the sequence is A000012.
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}]
PROG
(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
KEYWORD
nonn
AUTHOR
Robert G. Wilson v, Feb 10 2006, Jun 01 2006
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
STATUS
approved