A126279 -id:A126279 - cp's OEIS frontend

A125527 Number of semiprimes <= 2^n.

0, 1, 2, 6, 10, 22, 42, 82, 157, 304, 589, 1124, 2186, 4192, 8110, 15658, 30253, 58546, 113307, 219759, 426180, 827702, 1608668, 3129211, 6091437, 11868599, 23140878, 45150717, 88157689, 172235073, 336717854, 658662065, 1289149627, 2524532330

Offset: 1

Robert G. Wilson v, Dec 29 2006

nonn

Robert G. Wilson v, Table of n, a(n) for n = 1..63 (using data from A120033, terms n=48, 50..57 from Dana Jacobsen)
Eric Weisstein's World of Mathematics, Semiprime.

Cf. A126279, A066265, A007053, A120033, A127396.

SemiPrimePi[n_] := Sum[ PrimePi[ n/Prime@i] - i + 1, {i, PrimePi@ Sqrt@n}]; Table[ SemiPrimePi[2^n], {n, 47}]

a(n)=my(s,i,N=2^n); forprime(p=2, sqrtint(N), s+=primepi(N\p); i++); s - i * (i-1)/2 \\ Charles R Greathouse IV, May 12 2013

use ntheory ":all"; print "$ ",semiprime_count(1 << $),"\n" for 1..48; # Dana Jacobsen, Sep 10 2018

a(n) = A072000(2^n). - R. J. Mathar, Aug 26 2011

A052130 a(n) is the number of numbers between 1 and 2^m with m-n prime factors (counted with multiplicity), for m sufficiently large.

Original entry on oeis.org

1, 2, 7, 15, 37, 84, 187, 421, 914, 2001, 4283, 9184, 19611, 41604, 87993, 185387, 389954, 817053, 1709640, 3567978, 7433670, 15460810, 32103728, 66567488, 137840687, 285076323, 588891185, 1215204568, 2505088087, 5159284087

Offset: 0

Bernd-Rainer Lauber (br.lauber(AT)surf1.de), Jan 21 2000

a(n) = number of products of half-odd-primes <= 2^n. E.g., a(2) = 7 since 1, 3/2, (3/2)^2, (3/2)^3, (3/2)*(5/2), 5/2, 7/2 are all <= 2^2. - David W. Wilson, Feb 01 2000
m is sufficiently large precisely when 2^m > 3^(m-n), i.e., when m >= floor(n*log(3)/log(1.5)) = A117630(n+1) = A126281(n) for n > 1. (Robert G. Wilson v asks if this conjecture holds in a comment to A126281.) - David A. Corneth, Apr 09 2015
From Robert G. Wilson v, Apr 13 2020: (Start)
This sequence shows a sufficiently large row of A126279 read backwards or a sufficiently large column of A126279 read vertically.
log(y) ~ a + b*x + c*x^2, where a=1.1422, b=0.7419, and c=-0.00035, with an r^2 of 1.0. (End)
[But what is y? - Editors, Jun 15 2021]

			Between 1 and 2^m there is just one number with m prime factors, namely 2^m, so a(0) = 1.
For m >= 3, up to 2^m there are 2 numbers with m-1 prime factors, 2^(m-1) and 3*2^(m-2), so a(1) = 2.

Martin Raab, Table of n, a(n) for n = 0..41 (Terms 0..35 from Robert G. Wilson v)
Index entries for sequences related to numbers of primes in various ranges

Cf. A117630, A126279, A126281.

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[Floor[n(1 + 1/Sqrt@2)] + 2, 2^(n + Floor[n(1 + 1/Sqrt@2)]) + 2], {n, 2, 30}] (* Robert G. Wilson v, Feb 21 2006 *)

from math import prod, isqrt
from sympy import primepi, primerange, integer_nthroot
def A052130(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)))
    k = 1
    while 3**k<(r:=1<Chai Wah Wu, Dec 03 2024

More terms from David W. Wilson, Feb 01 2000

a(24)-a(29) from Robert G. Wilson v, Feb 21 2006

A125149 a(n) is the least k such that the n-almost prime count is positive and equal to the (n-1)-almost prime count. a(0) = 1.

Original entry on oeis.org

1, 2, 10, 15495, 151165506066

Offset: 0

Jonathan Vos Post and Robert G. Wilson v, Jan 07 2007

Unlike any of the prime number races in which any particular form may lead or trail, this sequence demonstrates that although the count of numbers having k prime factors begins by trailing the count for k-1 prime factors, eventually they exchange positions in the race. This can be seen by looking at A126279 or A126280.
The fundamental theorem of arithmetic, or unique factorization theorem, states that every natural number greater than 1 either is itself a prime number, or can be written as a unique product of prime numbers. It had a proof sketched by Euclid, then corrected and completed in "Disquisitiones Arithmeticae" [Carl Friedrich Gauss, 1801]. It fails in many rings of algebraic integers [Ernst Kummer, 1843], a discovery initiating algebraic number theory. Counting the elements in the unique product of prime numbers classifies natural numbers into primes, semiprimes, 3-almost primes and so on. This sequence quantifies a previously undescribed structure to that classification.
We took the first k where the two relevant counts are the same. If instead we took the least k such that the n-almost prime count from k onwards exceeds the (n-1)-almost prime count, the sequence would begin: 3, 34, 15530, ... [see A180126].
The prime count and the semiprime count are identical for 1, 10, 15, 16, 22, 25, 29, 30, 33.
The semiprime count and the 3-almost prime count are identical for 1, 2, 3, 15495, 15496, 15497, 15498, 15508, 15524, 15525, 15529.
The numbers of 3-almost primes and 4-almost primes are equal at 151165506066 and 731 larger numbers, the last one being 151165607041. See A180126. - T. D. Noe, Aug 11 2010
Landau's asymptotic formula suggests that a(n) is about exp(exp(n-1)). - Charles R Greathouse IV, Mar 14 2011

			a(1) = 2 since 1 has no prime factors and 2 has one prime factor, therefore prime factor counts of 0 and 1 occur equally often in the first 2 integers.
a(2) = 10 since there are 4 primes {2, 3, 5 & 7} and 4 semiprimes {4, 6, 9 & 10} less than or equal to 10.
a(4) = 151165506066 since there are 32437255807 4-almost primes and 3-almost primes <= a(4).

Andrew Granville and Greg Martin, Prime Number Races, arXiv:math/0408319 [math.NT], Aug 24 2004.
Eric Weisstein's World of Mathematics, Fundamental Theorem of Arithmetic.
Eric Weisstein's World of Mathematics, Modular Prime Counting Function.
Eric Weisstein's World of Mathematics, Prime Factor.

Cf. A126279, A126280, A117526.
Sequences listing r-almost primes, that is, k such that A001222(k) = r: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13), A069275 (r = 14), A069276 (r = 15), A069277 (r = 16), A069278 (r = 17), A069279 (r = 18), A069280 (r = 19), A069281 (r = 20).
Cf. A180126.

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 *)
f[n_] := Block[{k = 2^n}, While[AlmostPrimePi[n, k] < AlmostPrimePi[n - 1, k], k++ ]; k];

Changed 33 to 34 in a comment. - T. D. Noe, Aug 11 2010

Edited by Peter Munn, Dec 17 2022

A127396 Number of 3-almostprimes <= 2^n.

Original entry on oeis.org

0, 0, 1, 2, 7, 13, 30, 60, 125, 256, 513, 1049, 2082, 4214, 8401, 16771, 33427, 66550, 132405, 262865, 522296, 1036033, 2055256, 4075039, 8078110, 16008485, 31720903, 62847087, 124501149, 246638355, 488559079, 967785236, 1917099175, 3797688543

Offset: 1

Robert G. Wilson v, Dec 29 2006

Robert G. Wilson v, Table of n, a(n) for n = 1..53
Eric Weisstein's World of Mathematics, Semiprime.

Cf. A126279, A109251, A125527.

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[2^n], {n, 30}]

a(n) = A072114(2^n). - R. J. Mathar, Aug 26 2011

A126280 Triangle read by rows: T(k,n) is number of numbers <= 10^n that are products of k primes.

Original entry on oeis.org

4, 4, 1, 25, 34, 22, 12, 4, 2, 168, 299, 247, 149, 76, 37, 14, 7, 2, 1229, 2625, 2569, 1712, 963, 485, 231, 105, 47, 22, 7, 3, 1, 9592, 23378, 25556, 18744, 11185, 5933, 2973, 1418, 671, 306, 138, 63, 25, 11, 4, 2, 78498, 210035, 250853, 198062, 124465, 68963

Offset: 1

Jonathan Vos Post & Robert G. Wilson v, Dec 22 2006

The n-th row's sum is 10^n - 1.

			4 4 1
25 34 22 12 4 2
168 299 247 149 76 37 14
7 2
1229 2625 2569 1712 963 485 231
105 47 22 7 3 1
9592 23378 25556 18744 11185 5933 2973
1418 671 306 138 63 25 11 4 2
78498 210035 250853 198062 124465 68963 35585 17572
8491 4016 1878 865 400 179 79 35 14 7 2
664579 1904324 2444359 2050696 1349779 774078 409849 207207
101787 49163 23448 11068 5210 2406 1124 510 233 102 45 21 7 3 1

Robert G. Wilson v, Table of n, a(n) for n = 1..342
Eric Weisstein's World of Mathematics, Semiprime.
Eric Weisstein's World of Mathematics, Almost Prime.

By columns: A006880, A036352, A109251, A114106, A114453, A120047, A120048, A120049, A120050, A120051, A120052, A120053.

The n-th row's sum: A002283 = 10^n -1, A116430, A126279: same array but for powers of two.

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[m, 10^n], {n, 6}, {m, Floor[Log[2, 10^n]] }] // Flatten

A334069 Number of numbers <= 2^n that are the product of exactly four primes, not necessarily distinct.

Original entry on oeis.org

0, 0, 0, 1, 2, 7, 14, 34, 71, 152, 325, 669, 1405, 2866, 5931, 12139, 24782, 50444, 102458, 207945, 420511, 850518, 1716168, 3460304, 6968639, 14022029, 28189833, 56631732, 113697179, 228115641, 457456902, 916899721, 1836996851, 3678943569, 7365141297, 14740076678, 29490954290

Offset: 1

Robert G. Wilson v, Apr 13 2020

nonn

			a(6) = 7 because
  16 = 2 * 2 * 2 * 2,
  24 = 2 * 2 * 2 * 3,
  36 = 2 * 2 * 3 * 3,
  40 = 2 * 2 * 2 * 5,
  54 = 2 * 3 * 3 * 3,
  56 = 2 * 2 * 2 * 7, and
  60 = 2 * 2 * 3 * 5
are the seven numbers less than 2^6 = 64 that are each the product of four primes.

Robert G. Wilson v, Table of n, a(n) for n = 1..53
Eric Weisstein's World of Mathematics, Almost Prime.
Eric Weisstein's World of Mathematics, Semiprime.

Cf. A007053, A014613, A082996, A125527, A127396, A126279.

Partial sums of A120035.

FourAlmostPrimePi[n_] := Sum[ PrimePi[n/(Prime@i*Prime@j*Prime@k)] - k + 1, {i, PrimePi[n^(1/4)]}, {j, i, PrimePi[(n/Prime@i)^(1/3)]}, {k, j, PrimePi@Sqrt[n/(Prime@i*Prime@j)]}]; Array[FourAlmostPrimePi[2^#] &, 37]

a(n) = A082996(2^n).

A126281 a(n) is the least m to satisfy the requirements of A052130.

Original entry on oeis.org

1, 2, 5, 8, 10, 13, 16, 18, 21, 24, 27, 29, 32, 35, 37, 40, 43, 46, 48, 51, 54, 56, 59, 62, 65, 67, 70, 73

Offset: 1

Robert G. Wilson v, Dec 24 2006

A052130: For m very large, a(n) = number of numbers between 1 and 2^m with m-n prime factors (counted with multiplicity).
In observing the triangular array of A126279, the array T(k,n) defined as the k-th almost prime count of n-th power of two, it is noticed that the k-th term from the right converges to a fixed value beginning with the n-th power of two.
Will this sequence continue to match A117630: floor(n*log(3)/log(3/2)) ?

J. H. Smith, Perfect Numbers.

Cf. A052130, A126279.

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}]] ]]]; f[n_] := Block[{a = 0, m = n}, While[ b = AlmostPrimePi[m-n+1, 2^m]; b > a, m++; a = b]; m--; m]; Array[f, 24] (* Eric W. Weisstein, Feb 07 2006 *)

a(25)-a(28) from Robert G. Wilson v, Sep 07 2012

Expression in comment corrected by L. Edson Jeffery, Apr 03 2015

A125288 a(n) = least integer k such that for all integers m greater than k, 2Pi(n,m) is greater than Pi(n,2m).

Original entry on oeis.org

10, 297, 49650, 180701087317

Offset: 1

Jonathan Vos Post and Robert G. Wilson v, Jan 22 2007

Pi(n, m) is the number of integers <= m that have n prime factors counting multiplicity, also known as n-almost-primes (A078840).

			a(1) = 10 since the first term relates to 1-almost-primes, which are the primes themselves; and there are 4 primes <= 10, and 2*4 = 8 primes <= 2*10 = 20; but for m = 11 and all larger integers, the number of primes <= 2*m is less than twice the number of primes <= m. - _Peter Munn_, Dec 23 2022

Cf. A078840, A092097, A117526, A126279, A125149.

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

a(4) from Donovan Johnson, Nov 13 2010

Edited by Peter Munn, Jan 05 2023

cp's OEIS Frontend

A125527 Number of semiprimes <= 2^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Formula

A052130 a(n) is the number of numbers between 1 and 2^m with m-n prime factors (counted with multiplicity), for m sufficiently large.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A125149 a(n) is the least k such that the n-almost prime count is positive and equal to the (n-1)-almost prime count. a(0) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A127396 Number of 3-almostprimes <= 2^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A126280 Triangle read by rows: T(k,n) is number of numbers <= 10^n that are products of k primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A334069 Number of numbers <= 2^n that are the product of exactly four primes, not necessarily distinct.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A126281 a(n) is the least m to satisfy the requirements of A052130.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A125288 a(n) = least integer k such that for all integers m greater than k, 2*Pi(n,m) is greater than Pi(n,2*m).

Views

Author

Keywords

Comments

Examples

A125288 a(n) = least integer k such that for all integers m greater than k, 2Pi(n,m) is greater than Pi(n,2m).