cp's OEIS Frontend

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

%I A367642 #24 Sep 10 2024 00:25:30
%S A367642 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 A367642 65,82,101,122,122,122,122,126,129,129,129,145,170,170,170,170,170,
%U A367642 170,170,170,170,170,170,170,197,217,217,217,217,217,217,217,217,217
%N 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).
%e A367642 a(1) = 2 as there are no perfect powers less than 1, and none between 1 and 2.
%e A367642 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 A367642 (PARI) ispp(n) = {ispower(n) || n==1}; \\ A001597
%o A367642 f(n) = sum(k=1, n-1, ispp(k));
%o A367642 a(n) = my(k=n, nb=f(n)); while(f(k)-f(n+1) != f(n), k++); k; \\ _Michel Marcus_, Nov 30 2023
%o A367642 (Python)
%o A367642 from sympy import mobius, integer_nthroot, perfect_power
%o A367642 def A367642(n):
%o A367642     if n == 1: return 2
%o A367642     def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
%o A367642     m = (f(n)<<1)-bool(perfect_power(n))
%o A367642     def g(x): return m+x-f(x)
%o A367642     def bisection(f,kmin=0,kmax=1):
%o A367642         while f(kmax) > kmax: kmax <<= 1
%o A367642         while kmax-kmin > 1:
%o A367642             kmid = kmax+kmin>>1
%o A367642             if f(kmid) <= kmid:
%o A367642                 kmax = kmid
%o A367642             else:
%o A367642                 kmin = kmid
%o A367642         return kmax
%o A367642     return bisection(g,m,m)+1 # _Chai Wah Wu_, Sep 09 2024
%Y A367642 Cf. A001597, A069623.
%K A367642 nonn
%O A367642 1,1
%A A367642 _Tanmaya Mohanty_, Nov 25 2023