A059396 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.

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, 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, 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

Offset: 1

Author

Henry Bottomley, Jan 29 2001

Keywords

• nonn
• easy

Comments

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

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

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000

Programs

Maple

a:= proc(n) option remember;
      numtheory[pi](floor(sqrt(ithprime(n))))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Sep 05 2011

Mathematica

Table[PrimePi[Sqrt[Prime[n]]],{n,110}] (* Harvey P. Dale, Sep 06 2015 *)

PARI

a(n) = primepi(sqrtint(prime(n))); \\ Altug Alkan, Sep 05 2018

Formula

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