A078841 Main diagonal of the table of k-almost primes (A078840): a(n) = (n+1)-st integer that is an n-almost prime.

1, 3, 9, 20, 54, 112, 240, 648, 1344, 2816, 5760, 12800, 26624, 62208, 129024, 270336, 552960, 1114112, 2293760, 4915200, 9961472, 20447232, 47775744, 96468992, 198180864, 411041792, 830472192, 1698693120, 3422552064, 7046430720

Offset: 0

Author

Benoit Cloitre and Paul D. Hanna, Dec 10 2002

Keywords

• nonn

Comments

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

Examples

			a(0) = 1 since one is the multiplicative identity,
a(1) = 2nd 1-almost prime is the second prime number = A000040(2) = 3,
a(2) = 3rd 2-almost prime = 3rd semiprime = A001358(3) = 9 = {3*3}.
a(3) = 4th 3-almost prime = A014612(4) = 20 = {2*2*5}.
a(4) = 5th 4-almost prime = A014613(5) = 54 = {2*3*3*3},
a(5) = 6th 5-almost prime = A014614(6) = 112 = {2*2*2*2*7}, ....
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 0..1000 (terms 0..228 from Robert G. Wilson v)
• Eric Weisstein's World of Mathematics, Almost Prime.

Crossrefs

Cf. A078840, A078842, A078843, A078844, A078445, A078846, A101695.

Programs

Mathematica

f[n_] := Plus @@ Last /@ FactorInteger@n; t = Table[{}, {40}]; Do[a = f[n]; AppendTo[ t[[a]], n]; t[[a]] = Take[t[[a]], 10], {n, 2, 148*10^8}]; Table[ t[[n, n + 1]], {n, 30}] (* Robert G. Wilson v, Feb 11 2006 *)
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 *)
AlmostPrime[k_, n_] := Block[{e = Floor[ Log[2, n] + k], a, b}, a = 2^e; Do[b = 2^p; While[ AlmostPrimePi[k, a] < n, a = a + b]; a = a - b/2, {p, e, 0, -1}]; a + b/2]; AlmostPrime[1, 1] = 2; lst = {}; Do[ AppendTo[lst, AlmostPrime[n-1, n]], {n, 30}]; lst (* Robert G. Wilson v, Nov 13 2007 *)

Python

from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A078841(n):
    if n <= 1: return (n<<1)+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)))
    def f(x): return int(n+x-sum(primepi(x//prod(c[1] for c in a))-a[-1][0] for a in g(x,0,1,1,n)))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Aug 23 2024

Formula

Conjecture: Lim as n->inf. of a(n+1)/a(n) = 2. - Robert G. Wilson v, Nov 13 2007

Extensions

a(14)-a(29) from Robert G. Wilson v, Feb 11 2006