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

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, 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, 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

Offset: 1

Author

Walter Nissen, Mar 10 2003

Keywords

• easy
• nonn

Examples

			a(1) = 2 because there are 2 primes between 1^2 and 2^2, viz., 2 and 3.
a(2) = 2 because there are 2 primes between 2^2 and 2^3, viz., 5 and 7.
a(3) = 0 because there are no primes between 2^3 and 3^2.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10001

Crossrefs

Cf. A001597, A053289, A000720, A000040.

Programs

Mathematica

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

Python

from sympy import mobius, integer_nthroot, primepi
def A080769(n):
    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())))
    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 int(-primepi(a:=bisection(f,n,n))+primepi(bisection(lambda x:f(x)+1,a,a))) # Chai Wah Wu, Sep 09 2024

Formula

a(n) = A000720(A001597(n+1)) - A000720(A001597(n)). - Jianing Song, Nov 19 2019

Extensions

Offset corrected by Jianing Song, Nov 19 2019