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

%I #46 Sep 02 2024 13:03:38

%S 1,3,9,20,54,112,240,648,1344,2816,5760,12800,26624,62208,129024,

%T 270336,552960,1114112,2293760,4915200,9961472,20447232,47775744,

%U 96468992,198180864,411041792,830472192,1698693120,3422552064,7046430720

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

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

%H Chai Wah Wu, <a href="/A078841/b078841.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..228 from Robert G. Wilson v)

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

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

%e a(0) = 1 since one is the multiplicative identity,

%e a(1) = 2nd 1-almost prime is the second prime number = A000040(2) = 3,

%e a(2) = 3rd 2-almost prime = 3rd semiprime = A001358(3) = 9 = {3*3}.

%e a(3) = 4th 3-almost prime = A014612(4) = 20 = {2*2*5}.

%e a(4) = 5th 4-almost prime = A014613(5) = 54 = {2*3*3*3},

%e a(5) = 6th 5-almost prime = A014614(6) = 112 = {2*2*2*2*7}, ....

%t 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 *)

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

%o (Python)

%o from math import prod, isqrt

%o from sympy import primerange, integer_nthroot, primepi

%o def A078841(n):

%o if n <= 1: return (n<<1)+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 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)))

%o kmin, kmax = 1,2

%o while f(kmax) >= kmax:

%o kmax <<= 1

%o while True:

%o kmid = kmax+kmin>>1

%o if f(kmid) < kmid:

%o kmax = kmid

%o else:

%o kmin = kmid

%o if kmax-kmin <= 1:

%o break

%o return kmax # _Chai Wah Wu_, Aug 23 2024

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

%K nonn

%O 0,2

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

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