A078845 -id:A078845 - cp's OEIS frontend

A078843 Where 3^n occurs in n-almost primes, starting at a(0)=1.

1, 2, 3, 5, 8, 14, 23, 39, 64, 103, 169, 269, 427, 676, 1065, 1669, 2628, 4104, 6414, 10023, 15608, 24281, 37733, 58503, 90616, 140187, 216625, 334527, 516126, 795632, 1225641, 1886570, 2901796, 4460359, 6851532, 10518476, 16138642, 24748319

Offset: 0

Benoit Cloitre and Paul D. Hanna, Dec 10 2002

nonn

			a(3) = 5 since 3^3 is the 5th 3-almost-prime: 8,12,18,20,27,....., A014612.

Max Alekseyev, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Almost Prime.

Cf. A078840, A078841, A078842, A078844, A078845, A078846.

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 *)
Table[ AlmostPrimePi[n, 3^n], {n, 2, 37}] (* Robert G. Wilson v, Feb 09 2006 *)

a(n)=sum(i=1,3^n,if(bigomega(i)-n,0,1))

{ appi(k,n,m=2) = local(r=0);
if(k==0,return(1));
if(k==1,return(primepi(n)));
forprime(p=m, floor(sqrtn(n,k)+1e-20),
r+=appi(k-1,n\p,p)-(k==2)*(primepi(p)-1));
r }
{ appi3(k,n) = appi(k,n) - if(k>=1,appi(k-1,n\3)) }
a=1; for(n=1,50, k=ceil(n*log(5/3)/log(5/2)); a+=appi3(n-k,3^n\2^k); print1(a,", "))
\\ Max Alekseyev, Jan 06 2008

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A078843(n):
    def almostprimepi(n,k):
        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(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))
    return almostprimepi(3**n,n) if n else 1 # Chai Wah Wu, Sep 01 2024

a(n) = a(n-1) + appi3(n-k, floor(3^n/2^k)), where k = ceiling(n*c) with c = log(5/3)/log(5/2) = 0.55749295065024006729857073190835923443... and appi3(k,n) is the number of k-almost primes not divisible by 3 and not exceeding n. - Max Alekseyev, Jan 06 2008

a(14)-a(37) from Robert G. Wilson v, Feb 09 2006

A078844 Where 5^n occurs in n-almost-primes, starting at a(0)=1.

Original entry on oeis.org

1, 3, 9, 30, 90, 269, 788, 2249, 6340, 17526, 47911, 129639, 348251, 929714, 2469499, 6532869, 17219031, 45246630, 118572805, 309998131, 808746993, 2105893899, 5474080107, 14207001052, 36818679828, 95292132897, 246327403310

Offset: 0

Benoit Cloitre and Paul D. Hanna, Dec 10 2002

nonn

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

			a(2) = 9 since 5^2 is the 9th 2-almost-prime: {4,6,9,10,14,15,21,22,25,...}.

Eric Weisstein's World of Mathematics, Almost Prime.

Cf. A078840, A078841, A078842, A078843, A078845, A078846.

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 *)
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 *)
Join[{1},Table[ AlmostPrimePi[n, 5^n], {n, 1, 25}]] (* Robert G. Wilson v, Feb 10 2006 *)

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def almostprimepi(n, k):
    if k==0: return int(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(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))
def A078844(n): return almostprimepi(5**n, n) if n else 1 # Chai Wah Wu, Nov 07 2024

a(8)-a(10) from Ryan Propper, Aug 08 2005
a(11)-a(25) from Robert G. Wilson v, Feb 10 2006
a(26) from Donovan Johnson, Sep 27 2010

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

Original entry on oeis.org

1, 5, 40, 328, 2556, 18452, 126096, 827901, 5276913, 32887213, 201443165, 1217389949, 7279826998, 43168558912, 254258462459, 1489291941733, 8683388113017, 50433408838966

Offset: 0

Benoit Cloitre and Paul D. Hanna, Dec 10 2002

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

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

Eric Weisstein's World of Mathematics, Almost Prime.

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

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 *)
Table[ AlmostPrimePi[n, 11^n], {n, 2, 11}] (* Robert G. Wilson v, Feb 09 2006 *)

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(11^n, n)); \\ Daniel Suteu, Jul 10 2023

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A078846(n):
    def almostprimepi(n, k):
        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(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))
    return almostprimepi(11**n, n) if n else 1 # Chai Wah Wu, Sep 01 2024

a(6)-a(11) from Robert G. Wilson v, Feb 09 2006
a(12)-a(15) from Donovan Johnson, Sep 27 2010
a(16)-a(17) from Daniel Suteu, Jul 10 2023

A116430 The number of n-almost primes less than or equal to 10^n, starting with a(0)=1.

Original entry on oeis.org

1, 4, 34, 247, 1712, 11185, 68963, 409849, 2367507, 13377156, 74342563, 407818620, 2214357712, 11926066887, 63809981451, 339576381990, 1799025041767, 9494920297227, 49950199374227, 262036734664892

Offset: 0

Robert G. Wilson v, Feb 10 2006, Jun 01 2006

nonn

If instead we asked for those less than or equal to 2^n, then the sequence is A000012.

Cf. A036352, A114106, A114453.
Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.
Cf. A006880, A036352, A109251, A114106, A114453, A120047 - A120053.

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}]

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

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

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

A078842 Sums of the antidiagonals of the table of k-almost primes (A078840).

Original entry on oeis.org

1, 2, 7, 19, 44, 95, 195, 395, 794, 1583, 3172, 6334, 12665, 25313, 50596, 101180, 202326, 404635, 809227, 1618410, 3236766, 6473474, 12946903, 25893723, 51787365, 103574668, 207149213, 414298342, 828596584, 1657193052, 3314385970

Offset: 0

Benoit Cloitre and Paul D. Hanna, Dec 11 2002

nonn

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

			a(3) = 19 = 5 (3rd prime) + 6 (2nd 2-almost prime) + 8 (first 3-almost prime).

Robert G. Wilson v, Table of n, a(n) for n = 0..140.
Eric Weisstein's World of Mathematics, k-Almost Prime.

Cf. A078840, A078841, A078843, A078844, A078845, A078846.

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}]; Plus @@@ Table[t[[n - k + 1, k]], {n, 30}, {k, n, 1, -1}] (* Or *)
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]; Table[ Sum[ AlmostPrime[k, n - k + 1], {k, n}], {n, 150}] (* Robert G. Wilson v, Feb 11 2006 *)

a(n) = Sum_{i=0..n-1} A078840(i+1, n-i).

a(12)-a(30) from Robert G. Wilson v, Feb 11 2006

A116426 The number of n-almost primes less than or equal to 4^n, starting with a(0)=1.

Original entry on oeis.org

1, 2, 6, 13, 34, 77, 177, 406, 887, 1962, 4225, 9094, 19482, 41414, 87706, 184976, 389357, 816193, 1708412, 3566209, 7431153, 15457234, 32098652, 66560309, 137830562, 285062028, 588871107, 1215176367, 2505048537, 5159228725

Offset: 0

Robert G. Wilson v, Feb 10 2006

nonn

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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 *)
Join[{1},Table[AlmostPrimePi[n, 4^n], {n, 29}]]

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A116426(n):
    if n<=1: return 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((1<<(n<<1))//prod(c[1] for c in a))-a[-1][0] for a in g(1<<(n<<1),0,1,1,n))) # Chai Wah Wu, Oct 02 2024

A116427 The number of n-almost primes less than or equal to 6^n, starting with a(0)=1.

Original entry on oeis.org

1, 3, 13, 50, 200, 726, 2613, 9061, 30779, 102637, 338230, 1102674, 3566001, 11455355, 36597558, 116395587, 368749900, 1164407829, 3666312894, 11515047829, 36085395700, 112857846859, 352329509934, 1098136237818

Offset: 0

Robert G. Wilson v, Feb 10 2006

nonn

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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 *)
Join[{1},Table[AlmostPrimePi[n, 6^n], {n, 21}]]

a(22)-a(23) from Donovan Johnson, Oct 01 2010

A116428 The number of n-almost primes less than or equal to 8^n, starting with a(0)=1.

Original entry on oeis.org

1, 4, 22, 125, 669, 3410, 16677, 78369, 359110, 1612613, 7133274, 31185350, 135062165, 580556958, 2480278767, 10542976739, 44626102826, 188215850830, 791374442571, 3318478309647, 13882441625034, 57952990683107

Offset: 0

Robert G. Wilson v, Feb 14 2006

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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}]]]]];
Table[ AlmostPrimePi[n, 8^n], {n, 14}] (* Eric W. Weisstein, Feb 07 2006 *)

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(8^n, n)); \\ Daniel Suteu, Jul 10 2023

a(15)-a(18) from Donovan Johnson, Oct 01 2010

a(19)-a(21) from Daniel Suteu, Jul 10 2023

A116429 The number of n-almost primes less than or equal to 9^n, starting with a(0)=1.

Original entry on oeis.org

1, 4, 26, 181, 1095, 6416, 35285, 187929, 973404, 4934952, 24628655, 121375817, 592337729, 2868086641, 13798982719, 66043675287, 314715355786, 1494166794434, 7071357084444, 33374079939405

Offset: 0

Robert G. Wilson v, Feb 10 2006

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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, 9^n], {n, 13}]

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(9^n, n)); \\ Daniel Suteu, Jul 10 2023

a(14)-a(16) from Donovan Johnson, Oct 01 2010

a(16) corrected and a(17)-a(19) from Daniel Suteu, Jul 10 2023

A116431 The number of n-almost primes less than or equal to 12^n, starting with a(0)=1.

Original entry on oeis.org

1, 5, 48, 434, 3695, 29165, 218283, 1569995, 10950776, 74621972, 499495257, 3297443264, 21533211312, 139411685398, 896352197825, 5730605551626, 36465861350230

Offset: 0

Robert G. Wilson v, Feb 10 2006

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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, 12^n], {n, 12}]

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(12^n, n)); \\ Daniel Suteu, Jul 10 2023

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A116431(n):
    if n<=1: return 4*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(12**n//prod(c[1] for c in a))-a[-1][0] for a in g(12**n,0,1,1,n))) # Chai Wah Wu, Sep 28 2024

a(13)-a(14) from Donovan Johnson, Oct 01 2010

a(15)-a(16) from Daniel Suteu, Jul 10 2023

cp's OEIS Frontend

A078843 Where 3^n occurs in n-almost primes, starting at a(0)=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A078844 Where 5^n occurs in n-almost-primes, starting at a(0)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A116430 The number of n-almost primes less than or equal to 10^n, starting with a(0)=1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A078842 Sums of the antidiagonals of the table of k-almost primes (A078840).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A116426 The number of n-almost primes less than or equal to 4^n, starting with a(0)=1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Python

A116427 The number of n-almost primes less than or equal to 6^n, starting with a(0)=1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A116428 The number of n-almost primes less than or equal to 8^n, starting with a(0)=1.