A062298 - OEIS

%I #56 Sep 08 2022 08:45:03

%S 1,1,1,2,2,3,3,4,5,6,6,7,7,8,9,10,10,11,11,12,13,14,14,15,16,17,18,19,

%T 19,20,20,21,22,23,24,25,25,26,27,28,28,29,29,30,31,32,32,33,34,35,36,

%U 37,37,38,39,40,41,42,42,43,43,44,45,46,47,48,48,49,50,51,51,52,52,53

%N Number of nonprimes <= n.

%C a(n) = n - A000720(n). This is asymptotic to n - Li(n). Note that a(n) + A095117(n) = 2*n. - _Jonathan Vos Post_, Nov 22 2004

%C Same as number of primes between n and prime(n+1) and between n and prime(n)+1 (end points excluded); n prime -> a(n)=a(n-1), n composite-> a(n)=1+a(n-1). - _David James Sycamore_, Jul 23 2018

%C There exists at least one prime number between a(n) and n for n >= 3 (see the paper by Ya-Ping Lu attached in the links). - _Ya-Ping Lu_, Nov 27 2020

%H Harry J. Smith, <a href="/A062298/b062298.txt">Table of n, a(n) for n = 1..1000</a>

%H Ya-Ping Lu, <a href="/A337788/a337788.pdf">Lower Bounds for the Number of Primes in Some Integer Intervals</a>

%F a(n) = n - A000720(n).

%F a(n) = 1 + A065855(n). - _David James Sycamore_, Jul 23 2018

%e a(19) = 11 as there are 8 primes up to 19 (inclusive).

%p NumComposites := proc(N::posint) local count, i:count := 0:for i from 1 to N do if not isprime(i) then count := count + 1 fi:od: count;end:seq(NumComposites(binomial(k+1,k)), k=0..73); # _Zerinvary Lajos_, May 26 2008

%p A062298 := proc(n) n-numtheory[pi](n) ; end: seq(A062298(n),n=1..120) ; # _R. J. Mathar_, Sep 27 2009

%t Table[n-PrimePi[n],{n,80}] (* _Harvey P. Dale_, May 10 2012 *)

%t Accumulate[Table[If[PrimeQ[n],0,1],{n,100}]] (* _Harvey P. Dale_, Feb 15 2017 *)

%o (PARI) a(n) = n-primepi(n); \\ _Harry J. Smith_, Aug 04 2009

%o (Haskell)

%o a062298 n = a062298_list !! (n-1)

%o a062298_list = scanl1 (+) $ map (1 -) a010051_list

%o -- _Reinhard Zumkeller_, Oct 10 2013

%o (Magma) [n - #PrimesUpTo(n): n in [1..100]]; // _Vincenzo Librandi_, Aug 05 2015

%o (Python)

%o from sympy import primepi

%o print([n - primepi(n) for n in range(1, 101)]) # _Indranil Ghosh_, Mar 29 2017

%Y Cf. A000720, A101203, A010051, A065855.

%K nonn

%O 1,4

%A _Amarnath Murthy_, Jun 19 2001

%E Corrected and extended by _Vladeta Jovovic_, Jun 22 2001