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 nth-almost prime count always exceeds the (n-1)th-almost prime. That sequence would begin: 3,33,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.

Andrew Granville and Greg Martin, Prime Number Races., Aug. 24, 2004.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1), The Fundamental Theorem Of Arithmetic.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2), Modular Prime Counting Function.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3), Prime Factor (17).

Unity has no prime factors. Two 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 (eww(AT)wolfram.com) Feb 07 2006 *)

f[n_] := Block[{k = 2^n}, While[AlmostPrimePi[n, k] < AlmostPrimePi[n - 1, k], k++ ]; k];

Cf. A126279, A126280, A117526.

Cf. A000040, A001358, A014612, A014613, A014614, A046306, A046308, A046310, A046312, A046314.

Cf. A069272, A069273, A069274, A069275, A069276, A069277, A069278, A069279, A069280, A069281.

Sequence in context: A007158 A155733 A080485 this_sequence A079180 A027735 A085698

Adjacent sequences: A125146 A125147 A125148 this_sequence A125150 A125151 A125152

hard,more,nonn

Jonathan Vos Post (jvospost3(AT)gmail.com) & Robert G. Wilson v (rgwv(AT)rgwv.com), Jan 07 2007