%I #21 Sep 10 2024 00:24:27

%S 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 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 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 Number of primes between consecutive integer powers with exponent > 1.

%H Michael De Vlieger, <a href="/A080769/b080769.txt">Table of n, a(n) for n = 1..10001</a>

%F a(n) = A000720(A001597(n+1)) - A000720(A001597(n)). - _Jianing Song_, Nov 19 2019

%e a(1) = 2 because there are 2 primes between 1^2 and 2^2, viz., 2 and 3.

%e a(2) = 2 because there are 2 primes between 2^2 and 2^3, viz., 5 and 7.

%e a(3) = 0 because there are no primes between 2^3 and 3^2.

%t 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 (Python)

%o from sympy import mobius, integer_nthroot, primepi

%o def A080769(n):

%o 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 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 int(-primepi(a:=bisection(f,n,n))+primepi(bisection(lambda x:f(x)+1,a,a))) # _Chai Wah Wu_, Sep 09 2024

%Y Cf. A001597, A053289, A000720, A000040.

%K easy,nonn

%O 1,1

%A _Walter Nissen_, Mar 10 2003

%E Offset corrected by _Jianing Song_, Nov 19 2019