cp's OEIS Frontend

A161170 Least integer k such that the n-almost prime count is equal to the prime count.

%I A161170 #23 Mar 18 2025 01:38:44
%S A161170 10,125,1809,37820,2722768,1037849736,4204496515890,476649763963226416
%N A161170 Least integer k such that the n-almost prime count is equal to the prime count.
%C A161170 Related to sequence A125149, but we compare the prime count to the semiprime count, then the product-of-three-primes count, and so on.
%C A161170 We start with a the number two, and a prime count of 1.
%C A161170 Then the prime count and semiprime count are first identical when k = 10, the prime count is 4 ({2, 3, 5, 7}) and the semiprime count is also 4 ({4, 6, 9, 10}).
%C A161170 Next, when k = 125 the prime count of 30 and product-of-three-primes count of 30 are first identical.
%C A161170 Based on the write up for A125149 and examination of the factor counts as k increases, we believe this sequence is infinite, but have not proved this.
%e A161170 a(2) = 10 since there are now 4 primes ({2, 3, 5, 7}) and 4 semiprimes ({4, 6, 9, 10}) <= 10.
%e A161170 a(3) = 125 with 30 primes and 30 products of 3 primes.
%e A161170 a(4) = 1809 with 279 primes and 279 products of 4 primes.
%e A161170 a(5) = 37820 with 4000 primes and 4000 products of 5 primes.
%e A161170 a(6) = 2722768 with 198183 primes and 198183 products of 6 primes.
%e A161170 a(7) = 1037849736 with 52672391 primes and 52672391 products of 7 primes.
%e A161170 a(8) = 4204496515890 with 150007470826 primes and 150007470826 products of 8 primes.
%e A161170 a(9) = 476649763963226416 with 12012658440940682 primes and 12012658440940682 products of 9 primes.
%o A161170 (Ruby) # A slow program to generate sequence
%o A161170 # Faster C code is available by request
%o A161170 # Tallies number of primes, semiprimes, trieneprimes ...
%o A161170 tally = Hash.new { |h,k| h[k] = 0}
%o A161170 # Returns number of factors of num
%o A161170 def factors(num)
%o A161170 (2..(Math.sqrt(num).to_i)).each{ |i|
%o A161170 return factors(num/i) + 1 if num % i == 0
%o A161170 }
%o A161170 1
%o A161170 end
%o A161170 # Testing number of primes against composites with num_factors
%o A161170 num_factors = 2
%o A161170 2.upto( 1.0/0.0 ) { |i|
%o A161170 tally[factors(i)] +=1
%o A161170 if tally[1] == tally[num_factors]
%o A161170 puts "k: #{i} Primes: #{tally[1]} Composites with #{num_factors} factors: #{tally[num_factors]}"
%o A161170 num_factors += 1
%o A161170 end
%o A161170 }
%o A161170 (Perl) use ntheory ":all"; my($k,@S)=(0,map{0}1..20); forfactored { $S[@_]++; while ($S[1] == $S[$k]) { print "$k $_\n" if $k>1; $k++; } } 3e6; # _Dana Jacobsen_, Jan 18 2019
%Y A161170 Cf. A125149.
%K A161170 hard,more,nonn
%O A161170 2,1
%A A161170 _Andy Martin_, Jun 04 2009
%E A161170 Edited example and a(8) from _Donovan Johnson_, Mar 10 2010
%E A161170 a(9) from _Henri Lifchitz_, Mar 17 2025