A066265 a(n) = number of semiprimes < 10^n.

0, 3, 34, 299, 2625, 23378, 210035, 1904324, 17427258, 160788536, 1493776443, 13959990342, 131126017178, 1237088048653, 11715902308080, 111329817298881, 1061057292827269, 10139482913717352, 97123037685177087, 932300026230174178, 8966605849641219022, 86389956293761485464, 833671466551239927908, 8056846659984852885191

Offset: 0

Author

Patrick De Geest, Dec 10 2001

Keywords

• nonn

Comments

Apart from the first nonzero term the sequence is identical to A036352. - Hugo Pfoertner, Jul 22 2003

Examples

			Below 10 there are three semiprimes: 4 (2*2), 6 (2*3) and 9 (3*3).
		

Links

• Eric Weisstein's World of Mathematics, Semiprime
• Index entries for sequences related to numbers of primes in various ranges

Crossrefs

Cf. A001358, A064911, A072000, A036352 (identical starting from a(2)), A220262, A292785.

Programs

Mathematica

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

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

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

Python

from math import isqrt
from sympy import primepi, primerange
def A066265(n): return int((-(t:=primepi(s:=isqrt(m:=10**n)))*(t-1)>>1)+sum(primepi(m//k) for k in primerange(1, s+1))) if n>1 else 3*n # Chai Wah Wu, Aug 16 2024

Formula

(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

Extensions

More terms from Hugo Pfoertner, Jul 22 2003

a(14) from Robert G. Wilson v, May 16 2005

a(15)-a(16) from Donovan Johnson, Mar 18 2010

a(17)-a(18) from Dana Jacobsen, May 11 2014

a(19)-a(21) from Henri Lifchitz, Jul 04 2015

a(22)-a(23) from Henri Lifchitz, Nov 09 2024