A362965 Number of primes <= the n-th prime power.

1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 11, 12, 13, 14, 15, 15, 16, 17, 18, 18, 19, 20, 21, 22, 22, 23, 24, 25, 26, 27, 28, 29, 30, 30, 30, 31, 31, 32, 33, 34, 35, 36, 37, 38, 39, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 53, 54, 54, 55, 56, 57, 58, 59, 60

Offset: 1

Author

Max Alekseyev, Jun 03 2023

Keywords

• nonn

Comments

Also, number of distinct primes among the first n prime powers (cf. A246655).

Examples

			The 4th prime, 7, is followed by prime powers 8 and 9 before the next prime (11), accounting for three consecutive 4s in the sequence (at indices n = 5..7). Similarly, the three 9s (at n = 13..15) show that the 9th prime (23) is followed by two prime powers (25, 27) before the next prime (29). This occurs again at n = 40..42 (a(n) = 30), 358..360 (a(n) = 327) and 3588..3590 (a(n) = 3512). - _M. F. Hasler_, Oct 31 2024
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000961, A000720, A246655, A366833 (run lengths).

Programs

Mathematica

A362965list[upto_]:=PrimePi[Select[Range[upto],PrimePowerQ]];A362965list[500] (* Paolo Xausa, Jun 29 2023 *)

PARI

apply(primepi, [p| p <- [1..300], isprimepower(p)]) \\ Michel Marcus, Jun 04 2023

Python

from sympy import primepi, integer_nthroot
def A362965(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    return int(primepi(bisection(f,n,n))) # Chai Wah Wu, Oct 28 2024

Formula

a(n) = A000720(A246655(n)).