OFFSET
1,1
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
KEYWORD
nonn
AUTHOR
Tanmaya Mohanty, Nov 25 2023
STATUS
approved