A036351 Number of numbers <= 10^n that are products of two distinct primes.
2, 30, 288, 2600, 23313, 209867, 1903878, 17426029, 160785135, 1493766851, 13959963049, 131125938680, 1237087821006, 11715901643501, 111329815346924, 1061057287065814, 10139482896634686, 97123037634329553, 932300026078297246, 8966605849186166511, 86389956292394285653, 833671466547121873095, 8056846659972421004731
Offset: 1
Keywords
Programs
-
Mathematica
f[n_] := Sum[ PrimePi[n/Prime[i]] - i, {i, PrimePi[ Sqrt[ n]] }]; Table[ f[10^n], {n, 14}] (* Robert G. Wilson v, Feb 07 2012 and modified Dec 28 2016 *) -
PARI
a(n)=my(s);forprime(p=2,sqrt(10^n),s+=primepi(10^n\p)); s-binomial(primepi(sqrt(10^n))+1,2) \\ Charles R Greathouse IV, Apr 23 2012
-
Python
from math import isqrt from sympy import primepi, primerange def A036351(n): return -(t:=primepi(s:=isqrt(m:=10**n)))-(t*(t-1)>>1)+sum(primepi(m//k) for k in primerange(1, s+1)) # Chai Wah Wu, Aug 15 2024
Formula
a(n) = (1/2)*(pi(10^(n/2)) + Sum_{i=1..pi(10^n)} pi((10^n-1)/P_i)) -1 = Sum_{i=1..pi(sqrt(10^n))} (pi((10^n-1)/P_i) -1) - binomial(pi(sqrt(10^n)), 2). - Robert G. Wilson v, May 19 2005
Extensions
a(14) from Robert G. Wilson v, May 19 2005
a(15)-a(16) from Donovan Johnson, Oct 16 2010
Corrected a(15) and a(16) by Henri Lifchitz, Nov 11 2012
a(17)-a(19) from Henri Lifchitz, Nov 11 2012
a(20)-a(21) from Henri Lifchitz, Jul 03 2015
a(22)-a(23) from Henri Lifchitz, Nov 09 2024