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.

1, 2, 10, 15495, 151165506066

Offset: 0

Author

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

Keywords

• nonn
• hard
• more

Comments

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

Examples

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

Links

• 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.

Crossrefs

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.

Programs

Mathematica

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

Extensions

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

Edited by Peter Munn, Dec 17 2022