A367642 a(n) is the smallest natural number such that the number of perfect powers less than n equals the number of perfect powers between n and a(n) (exclusive).

2, 5, 5, 9, 10, 10, 10, 17, 28, 33, 33, 33, 33, 33, 33, 37, 50, 50, 50, 50, 50, 50, 50, 50, 65, 82, 101, 122, 122, 122, 122, 126, 129, 129, 129, 145, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 197, 217, 217, 217, 217, 217, 217, 217, 217, 217

Offset: 1

Author

Tanmaya Mohanty, Nov 25 2023

Keywords

• nonn

Examples

			a(1) = 2 as there are no perfect powers less than 1, and none between 1 and 2.
a(9) = 28 as there are 3 perfect powers less than 9 (1, 4 and 8), and between 9 and 28 (16, 25 and 27).
		

Crossrefs

Cf. A001597, A069623.

Programs

PARI

ispp(n) = {ispower(n) || n==1}; \\ A001597
f(n) = sum(k=1, n-1, ispp(k));
a(n) = my(k=n, nb=f(n)); while(f(k)-f(n+1) != f(n), k++); k; \\ Michel Marcus, Nov 30 2023

Python

from sympy import mobius, integer_nthroot, perfect_power
def A367642(n):
    if n == 1: return 2
    def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    m = (f(n)<<1)-bool(perfect_power(n))
    def g(x): return m+x-f(x)
    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
    return bisection(g,m,m)+1 # Chai Wah Wu, Sep 09 2024