%I #31 Nov 08 2024 07:21:20
%S 1,3,9,30,90,269,788,2249,6340,17526,47911,129639,348251,929714,
%T 2469499,6532869,17219031,45246630,118572805,309998131,808746993,
%U 2105893899,5474080107,14207001052,36818679828,95292132897,246327403310
%N Where 5^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) = 9 since 5^2 is the 9th 2-almost-prime: {4,6,9,10,14,15,21,22,25,...}.
%t l = Table[0, {30}]; e = 0; Do[f = Plus @@ Last /@ FactorInteger[n]; l[[f+1]]++; If[n == 5^e, Print[l[[f+1]]]; e++ ], {n, 1, 5^10}] (* _Ryan Propper_, Aug 08 2005 *)
%t 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 *)
%t Join[{1},Table[ AlmostPrimePi[n, 5^n], {n, 1, 25}]] (* _Robert G. Wilson v_, Feb 10 2006 *)
%o (Python)
%o from math import isqrt, prod
%o from sympy import primerange, integer_nthroot, primepi
%o def almostprimepi(n, k):
%o if k==0: return int(n>=1)
%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 def A078844(n): return almostprimepi(5**n, n) if n else 1 # _Chai Wah Wu_, Nov 07 2024
%Y Cf. A078840, A078841, A078842, A078843, A078845, A078846.
%K nonn
%O 0,2
%A _Benoit Cloitre_ and _Paul D. Hanna_, Dec 10 2002
%E a(8)-a(10) from _Ryan Propper_, Aug 08 2005
%E a(11)-a(25) from _Robert G. Wilson v_, Feb 10 2006
%E a(26) from _Donovan Johnson_, Sep 27 2010