|
%I #39 Feb 10 2022 22:01:42
%S 0,3,34,299,2625,23378,210035,1904324,17427258,160788536,1493776443,
%T 13959990342,131126017178,1237088048653,11715902308080,
%U 111329817298881,1061057292827269,10139482913717352,97123037685177087,932300026230174178,8966605849641219022,86389956293761485464
%N a(n) = number of semiprimes < 10^n.
%C Apart from the first nonzero term the sequence is identical to A036352. - _Hugo Pfoertner_, Jul 22 2003
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Semiprime.html">Semiprime</a>
%H <a href="/index/Pri#primepop">Index entries for sequences related to numbers of primes in various ranges</a>
%F (1/2)*( pi(10^(n/2)) + Sum_{i=1..pi(10^n)} pi( (10^n-1)/P_i) ) = Sum_{i=1..pi(sqrt(10^n))} pi( (10^n-1)/P_i ) - binomial( pi(sqrt(10^n)), 2). - _Robert G. Wilson v_, May 16 2005
%e Below 10 there are three semiprimes: 4 (2*2), 6 (2*3) and 9 (3*3).
%t f[n_] := Sum[ PrimePi[(10^n - 1)/Prime[i]], {i, PrimePi[ Sqrt[10^n]]}] - Binomial[ PrimePi[ Sqrt[10^n]], 2]; Do[ Print[ f[n]], {n, 0, 14}] (* _Robert G. Wilson v_, May 16 2005 *)
%t SemiPrimePi[n_] := Sum[ PrimePi[n/Prime@ i] - i + 1, {i, PrimePi@ Sqrt@ n}]; Array[ SemiPrimePi[10^# - 1] &, 14, 0] (* _Robert G. Wilson v_, Jan 21 2015 *)
%o (PARI) a(n)=my(s);forprime(p=2,sqrt(10^n),s+=primepi((10^n-1)\p)); s-binomial(primepi(sqrt(10^n)),2) \\ _Charles R Greathouse IV_, Apr 23 2012
%o (Perl) use Math::Prime::Util qw/:all/; use integer; sub countsp { my($k,$sum,$pc)=($_[0]-1,0,1); prime_precalc(60_000_000); forprimes { $sum += prime_count($k/$_) + 1 - $pc++; } int(sqrt($k)); $sum; } foreach my $n (0..16) { say "$n: ", countsp(10**$n); } # _Dana Jacobsen_, May 11 2014
%Y Cf. A001358, A064911, A072000, A036352 (identical starting from a(2)), A220262, A292785.
%K nonn
%O 0,2
%A _Patrick De Geest_, Dec 10 2001
%E More terms from _Hugo Pfoertner_, Jul 22 2003
%E a(14) from _Robert G. Wilson v_, May 16 2005
%E a(15)-a(16) from _Donovan Johnson_, Mar 18 2010
%E a(17)-a(18) from _Dana Jacobsen_, May 11 2014
%E a(19)-a(21) from _Henri Lifchitz_, Jul 04 2015
|
