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

Links

Table of n, a(n) for n=1..58.

Example

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

Prog

(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

Crossrefs

Cf. A001597, A069623.

Sequence in context: A126357 A377809 A070243 * A050175 A243333 A059797

Adjacent sequences: A367639 A367640 A367641 * A367643 A367644 A367645

Keyword

nonn

Author

Tanmaya Mohanty, Nov 25 2023

Status

approved