A066265
a(n) = number of semiprimes < 10^n.
Original entry on oeis.org
0, 3, 34, 299, 2625, 23378, 210035, 1904324, 17427258, 160788536, 1493776443, 13959990342, 131126017178, 1237088048653, 11715902308080, 111329817298881, 1061057292827269, 10139482913717352, 97123037685177087, 932300026230174178, 8966605849641219022, 86389956293761485464, 833671466551239927908, 8056846659984852885191
Offset: 0
Below 10 there are three semiprimes: 4 (2*2), 6 (2*3) and 9 (3*3).
-
f[n_] := Sum[ PrimePi[(10^n - 1)/Prime[i]], {i, PrimePi[ Sqrt[10^n]]}] - Binomial[ PrimePi[ Sqrt[10^n]], 2]; Do[ Print[ f[n]], {n, 0, 14}] (* Robert G. Wilson v, May 16 2005 *)
SemiPrimePi[n_] := Sum[ PrimePi[n/Prime@ i] - i + 1, {i, PrimePi@ Sqrt@ n}]; Array[ SemiPrimePi[10^# - 1] &, 14, 0] (* Robert G. Wilson v, Jan 21 2015 *)
-
a(n)=my(s);forprime(p=2,sqrt(10^n),s+=primepi((10^n-1)\p)); s-binomial(primepi(sqrt(10^n)),2) \\ Charles R Greathouse IV, Apr 23 2012
-
use Math::Prime::Util qw/:all/; use integer; sub countsp { my($k,$sum,$pc)=($[0]-1,0,1); prime_precalc(60_000_000); forprimes { $sum += prime_count($k/$) + 1 - $pc++; } int(sqrt($k)); $sum; } foreach my $n (0..16) { say "$n: ", countsp(10**$n); } # Dana Jacobsen, May 11 2014
-
from math import isqrt
from sympy import primepi, primerange
def A066265(n): return int((-(t:=primepi(s:=isqrt(m:=10**n)))*(t-1)>>1)+sum(primepi(m//k) for k in primerange(1, s+1))) if n>1 else 3*n # Chai Wah Wu, Aug 16 2024
A109251
Number of numbers up to 10^n which are products of three primes.
Original entry on oeis.org
0, 1, 22, 247, 2569, 25556, 250853, 2444359, 23727305, 229924367, 2227121996, 21578747909, 209214982913, 2030133769624, 19717814526785, 191693417109381, 1865380637252270, 18168907486812690, 177123437184971927, 1728190923820610000
Offset: 0
There are 22 numbers with three prime factors up to 10^2: 8, 12, 18, 20, 27, 28, 30, 42, 44, 45, 50, 52, 63, 66, 68, 70, 75, 76, 78, 92, 98, 99.
Cf.
A014612 = numbers with three prime factors,
A036352 = number of numbers up to 10^n which are products of two primes,
A072114.
-
ThreeAlmostPrimePi[n_] := Sum[ PrimePi[n/(Prime@i*Prime@j)] - j + 1, {i, PrimePi[n^(1/3)]}, {j, i, PrimePi@ Sqrt[n/Prime@i]}]; Table[ ThreeAlmostPrimePi[10^n], {n, 0, 14}] (* Robert G. Wilson v *)
-
from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A109251(n):
r = 10**n
return int(sum(primepi(r//(k*m))-b for a,k in enumerate(primerange(integer_nthroot(r,3)[0]+1)) for b,m in enumerate(primerange(k,isqrt(r//k)+1),a))) # Chai Wah Wu, Sep 18 2024
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
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, 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
A120049
Number of 8-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 0, 7, 105, 1418, 17572, 207207, 2367507, 26483012, 291646797, 3173159326, 34192782745, 365561221293, 3882841742380, 41015564702074, 431227959019552, 4515480975731045, 47115876816676830
Offset: 0
There are 7 eight-almost primes up to 1000: 256, 384, 576, 640, 864, 896 & 960.
Cf.
A006880,
A036352,
A109251,
A114106,
A114453,
A120047,
A120048,
A120049,
A120050,
A120051,
A120052,
A120053,
A116430.
-
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[8, 10^n], {n, 12}]
-
from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A120049(n):
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,8))) # Chai Wah Wu, Aug 23 2024
A120047
Number of 6-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 2, 37, 485, 5933, 68963, 774078, 8493366, 91683887, 977694273, 10327249593, 108264085934, 1128049914377, 11694704489580, 120734708167792, 1242063105505230, 12739510126065301, 130330025583399801
Offset: 0
There are 2 six-almost primes up to 100: 64 and 96, so a(2) = 2.
-
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[6, 10^n], {n, 0, 13}]
-
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 A120047(n): return almostprimepi(10**n,6) # Chai Wah Wu, Dec 09 2024
A120048
Number of 7-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 0, 14, 231, 2973, 35585, 409849, 4600247, 50678212, 550454756, 5913771637, 62981797962, 665997804082, 7001087934965, 73232029374751, 762783057783010, 7916319351632036, 81898808371556517
Offset: 0
There are 14 seven-almost primes up to 1000: 128, 192, 288, 320, 432, 448, 480, 648, 672, 704, 720, 800, 832 & 972.
Cf.
A006880,
A036352,
A109251,
A114106,
A114453,
A120047,
A120048,
A120049,
A120050,
A120051,
A120052,
A120053,
A116430.
-
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[7, 10^n], {n, 11}]
A120050
Number of 9-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 0, 2, 47, 671, 8491, 101787, 1180751, 13377156, 148930536, 1636170477, 17787688377, 191742524399, 2052389350029, 21838745177567, 231206458686127, 2437121982958248, 25591920108631224, 267840642082525459
Offset: 0
There are 2 nine-almost primes up to 1000: 512 & 768.
Cf.
A006880,
A036352,
A109251,
A114106,
A114453,
A120047,
A120048,
A120049,
A120050,
A120051,
A120052,
A120053,
A116430.
-
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[9, 10^n], {n, 12}]
A120051
Number of 10-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 0, 0, 22, 306, 4016, 49163, 578154, 6618221, 74342563, 823164388, 9011965866, 97765974368, 1052666075366, 11263041623194, 119864659464824, 1269754732725522, 13396817167474205, 140847445420555406
Offset: 0
There are 22 ten-almost primes up to 10000: 1024, 1536, 2304, 2560, 3456, 3584, 3840, 5184, 5376, 5632, 5760, 6400, 6656, 7776, 8064, 8448, 8640, 8704, 8960, 9600, 9728, and 9984.
Cf.
A006880,
A036352,
A109251,
A114106,
A114453,
A120047,
A120048,
A120049,
A120050,
A120051,
A120052,
A120053,
A116430.
-
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[10, 10^n], {n, 12}]
-
from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A120051(n):
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,10))) # Chai Wah Wu, Nov 03 2024
A120053
Number of 12-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 0, 0, 3, 63, 865, 11068, 133862, 1563465, 17836903, 200051717, 2214357712, 24255601105, 263439785143, 2841076717752, 30457549169277, 324855769153426, 3449587218984911, 36489283363168885
Offset: 0
There are 3 twelve-almost primes up to 10000: 4096, 6144, and 9216.
Cf.
A006880,
A036352,
A109251,
A114106,
A114453,
A120047,
A120048,
A120049,
A120050,
A120051,
A120052,
A120053,
A116430.
-
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[12, 10^n], {n, 11}]
-
from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A120053(n):
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,12))) # Chai Wah Wu, Aug 23 2024
A120052
Number of 11-almost primes less than or equal to 10^n.
Original entry on oeis.org
0, 0, 0, 0, 7, 138, 1878, 23448, 279286, 3230577, 36585097, 407818620, 4490844534, 48972151631, 529781669333, 5693047157230, 60832290450373, 646862625625663, 6849459596884350, 72259172519243461
Offset: 0
There are 7 eleven-almost primes up to 10000: 2048, 3072, 4608, 5120, 6912, 7168, and 7680.
Cf.
A006880,
A036352,
A109251,
A114106,
A114453,
A120047,
A120048,
A120049,
A120050,
A120051,
A120052,
A120053,
A116430.
-
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[11, 10^n], {n, 12}]
Showing 1-10 of 15 results.
Comments