login
Where 11^n occurs in n-almost-primes, starting at a(0)=1.
16

%I #28 Sep 01 2024 13:45:02

%S 1,5,40,328,2556,18452,126096,827901,5276913,32887213,201443165,

%T 1217389949,7279826998,43168558912,254258462459,1489291941733,

%U 8683388113017,50433408838966

%N Where 11^n occurs in n-almost-primes, starting at a(0)=1.

%C A k-almost-prime is a positive integer that has exactly k prime factors, counted with multiplicity.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/AlmostPrime.html">Almost Prime.</a>

%e a(2) = 40 since 11^2 is the 40th 2-almost-prime: A001358(40) = 121.

%t AlmostPrimePi[k_Integer /; k > 1, n_] := Module[{a, i}, a[0] = 1; 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 *)

%t Table[ AlmostPrimePi[n, 11^n], {n, 2, 11}] (* _Robert G. Wilson v_, Feb 09 2006 *)

%o (PARI)

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

%o a(n) = if(n == 0, 1, almost_prime_count(11^n, n)); \\ _Daniel Suteu_, Jul 10 2023

%o (Python)

%o from math import isqrt, prod

%o from sympy import primerange, integer_nthroot, primepi

%o def A078846(n):

%o def almostprimepi(n, k):

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

%o return int(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n, 0, 1, 1, k)) if k>1 else primepi(n))

%o return almostprimepi(11**n, n) if n else 1 # _Chai Wah Wu_, Sep 01 2024

%Y Cf. A078840, A078841, A078842, A078843, A078844, A078845.

%K more,nonn

%O 0,2

%A _Benoit Cloitre_ and _Paul D. Hanna_, Dec 10 2002

%E a(6)-a(11) from _Robert G. Wilson v_, Feb 09 2006

%E a(12)-a(15) from _Donovan Johnson_, Sep 27 2010

%E a(16)-a(17) from _Daniel Suteu_, Jul 10 2023