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

Comments

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

Links

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

Formula

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

Example

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

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A239105 A302255 A218446 * A102548 A343174 A340205

Adjacent sequences: A362962 A362963 A362964 * A362966 A362967 A362968

Keyword

nonn

Author

Max Alekseyev, Jun 03 2023

Status

approved