login
Number of primes less than square root of n-th prime; i.e., number of trial divisions by smaller primes to show that n-th prime is indeed prime.
3

%I #28 Sep 23 2018 22:20:41

%S 0,0,1,1,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,

%T 5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,

%U 7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9

%N Number of primes less than square root of n-th prime; i.e., number of trial divisions by smaller primes to show that n-th prime is indeed prime.

%C Asymptotic to 2*(n/log(n))^(1/2):

%C Since p_n ~ n * log n, a(n) ~ sqrt(n * log n) / (log (sqrt(n * log n))) ~ 2 * sqrt(n) * sqrt(log n) / (log n + log log n) ~ 2 * sqrt(n / log n). - _Daniel Forgues_, Sep 04 2018

%H Alois P. Heinz, <a href="/A059396/b059396.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A000720(A000196(A000040(n))).

%e a(32) = 5 since the 32nd prime is 131 which is not divisible by 2, 3, 5, 7 or 11 (and does not need to be tested against 13, 17, 19 etc. since 13^2 = 169 > 131).

%p a:= proc(n) option remember;

%p numtheory[pi](floor(sqrt(ithprime(n))))

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Sep 05 2011

%t Table[PrimePi[Sqrt[Prime[n]]],{n,110}] (* _Harvey P. Dale_, Sep 06 2015 *)

%o (PARI) a(n) = primepi(sqrtint(prime(n))); \\ _Altug Alkan_, Sep 05 2018

%K nonn,easy

%O 1,5

%A _Henry Bottomley_, Jan 29 2001