A367642 - OEIS

%I #24 Sep 10 2024 00:25:30

%S 2,5,5,9,10,10,10,17,28,33,33,33,33,33,33,37,50,50,50,50,50,50,50,50,

%T 65,82,101,122,122,122,122,126,129,129,129,145,170,170,170,170,170,

%U 170,170,170,170,170,170,170,197,217,217,217,217,217,217,217,217,217

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

%e a(1) = 2 as there are no perfect powers less than 1, and none between 1 and 2.

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

%o (PARI) ispp(n) = {ispower(n) || n==1}; \\ A001597

%o f(n) = sum(k=1, n-1, ispp(k));

%o a(n) = my(k=n, nb=f(n)); while(f(k)-f(n+1) != f(n), k++); k; \\ _Michel Marcus_, Nov 30 2023

%o (Python)

%o from sympy import mobius, integer_nthroot, perfect_power

%o def A367642(n):

%o     if n == 1: return 2

%o     def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))

%o     m = (f(n)<<1)-bool(perfect_power(n))

%o     def g(x): return m+x-f(x)

%o     def bisection(f,kmin=0,kmax=1):

%o         while f(kmax) > kmax: kmax <<= 1

%o         while kmax-kmin > 1:

%o             kmid = kmax+kmin>>1

%o             if f(kmid) <= kmid:

%o                 kmax = kmid

%o             else:

%o                 kmin = kmid

%o         return kmax

%o     return bisection(g,m,m)+1 # _Chai Wah Wu_, Sep 09 2024

%Y Cf. A001597, A069623.

%K nonn

%O 1,1

%A _Tanmaya Mohanty_, Nov 25 2023