cp's OEIS Frontend

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.

%I A125149 #32 Feb 16 2025 08:33:04
%S A125149 1,2,10,15495,151165506066
%N 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.
%C A125149 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.
%C A125149 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.
%C A125149 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].
%C A125149 The prime count and the semiprime count are identical for 1, 10, 15, 16, 22, 25, 29, 30, 33.
%C A125149 The semiprime count and the 3-almost prime count are identical for 1, 2, 3, 15495, 15496, 15497, 15498, 15508, 15524, 15525, 15529.
%C A125149 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
%C A125149 Landau's asymptotic formula suggests that a(n) is about exp(exp(n-1)). - _Charles R Greathouse IV_, Mar 14 2011
%H A125149 Andrew Granville and Greg Martin, <a href="https://arxiv.org/abs/math/0408319">Prime Number Races</a>, arXiv:math/0408319 [math.NT], Aug 24 2004.
%H A125149 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html">Fundamental Theorem of Arithmetic</a>.
%H A125149 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ModularPrimeCountingFunction.html">Modular Prime Counting Function</a>.
%H A125149 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>.
%e A125149 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.
%e A125149 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.
%e A125149 a(4) = 151165506066 since there are 32437255807 4-almost primes and 3-almost primes <= a(4).
%t 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 *)
%t A125149 f[n_] := Block[{k = 2^n}, While[AlmostPrimePi[n, k] < AlmostPrimePi[n - 1, k], k++ ]; k];
%Y A125149 Cf. A126279, A126280, A117526.
%Y A125149 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).
%Y A125149 Cf. A180126.
%K A125149 nonn,hard,more
%O A125149 0,2
%A A125149 _Jonathan Vos Post_ and _Robert G. Wilson v_, Jan 07 2007
%E A125149 Changed 33 to 34 in a comment. - _T. D. Noe_, Aug 11 2010
%E A125149 Edited by _Peter Munn_, Dec 17 2022