0,2

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 those which have k-1 prime factors, eventually their numbers will exceed those of the other. 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 one 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 prime, semiprimes, trieneprimes and so on. This sequence quantifies a previously undescribed structure to that classification.

We took the first k where the two almost prime counts are the same. If instead we took the least k such that the n-th-almost prime count always exceeds the (n-1)th-almost prime. That sequence would begin: 3,34,15530,...,.

The prime count and the semiprime count are identical for 1, 10, 15, 16, 22, 25, 29, 30, 33.

The semiprime count and the trieneprime count are identical for 1, 2, 3, 15495, 15496, 15497, 15498, 15508, 15524, 15525, 15529.

The number 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

Table of n, a(n) for n=0..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.

1 has no prime factors. 2 has one prime factor and therefore is tied with those with no prime factor.

a(2) = 10 since there are now 4 primes {2, 3, 5 & 7} and 4 semiprimes {4, 6, 9 & 10} less than or equal to 10.

a(3) = 15495 since there are 3973 products of three prime

a(4) = 151165506066 since there are 32437255807 4-almost primes and 3-almost primes <= a(4).

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

Cf. A126279, A126280, A117526, A000040, A001358, A014612, A014613, A014614, A046306, A046308, A046310, A046312, A046314, A069272, A069273, A069274, A069275, A069276, A069277, A069278, A069279, A069280, A069281.

Sequence in context: A007158 A155733 A080485 * A079180 A027735 A085698

Adjacent sequences:  A125146 A125147 A125148 * A125150 A125151 A125152

hard,more,nonn

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

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

approved