cp's OEIS Frontend

A080769 Number of primes between consecutive integer powers with exponent > 1.

%I A080769 #21 Sep 10 2024 00:24:27
%S A080769 2,2,0,2,3,0,2,0,4,3,4,3,5,0,1,3,5,5,3,1,5,1,7,5,2,4,6,7,7,5,2,6,9,8,
%T A080769 7,8,9,8,8,6,4,9,10,9,10,7,2,9,12,11,12,6,5,9,12,11,3,10,8,0,2,13,15,
%U A080769 10,11,15,7,9,12,13,11,0,12,17,2,11,16,16,13,17,15,14,16,15,15,17,13,2,19
%N A080769 Number of primes between consecutive integer powers with exponent > 1.
%H A080769 Michael De Vlieger, <a href="/A080769/b080769.txt">Table of n, a(n) for n = 1..10001</a>
%F A080769 a(n) = A000720(A001597(n+1)) - A000720(A001597(n)). - _Jianing Song_, Nov 19 2019
%e A080769 a(1) = 2 because there are 2 primes between 1^2 and 2^2, viz., 2 and 3.
%e A080769 a(2) = 2 because there are 2 primes between 2^2 and 2^3, viz., 5 and 7.
%e A080769 a(3) = 0 because there are no primes between 2^3 and 3^2.
%t A080769 Count[#, _?PrimeQ] & /@ Range @@@ # &@ Partition[#, 2, 1] &@ Select[Range@ 5000, # == 1 || GCD @@ FactorInteger[#][[All, 2]] > 1 &] (* _Michael De Vlieger_, Jun 30 2016, after _Ant King_ at A001597 *)
%o A080769 (Python)
%o A080769 from sympy import mobius, integer_nthroot, primepi
%o A080769 def A080769(n):
%o A080769     def f(x): return int(n-1+x+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
%o A080769     def bisection(f,kmin=0,kmax=1):
%o A080769         while f(kmax) > kmax: kmax <<= 1
%o A080769         while kmax-kmin > 1:
%o A080769             kmid = kmax+kmin>>1
%o A080769             if f(kmid) <= kmid:
%o A080769                 kmax = kmid
%o A080769             else:
%o A080769                 kmin = kmid
%o A080769         return kmax
%o A080769     return int(-primepi(a:=bisection(f,n,n))+primepi(bisection(lambda x:f(x)+1,a,a))) # _Chai Wah Wu_, Sep 09 2024
%Y A080769 Cf. A001597, A053289, A000720, A000040.
%K A080769 easy,nonn
%O A080769 1,1
%A A080769 _Walter Nissen_, Mar 10 2003
%E A080769 Offset corrected by _Jianing Song_, Nov 19 2019