A240590 Number of primes between successive powerful numbers (A001694).

2, 2, 0, 2, 3, 0, 2, 0, 4, 3, 2, 2, 3, 3, 2, 0, 1, 3, 5, 5, 2, 1, 1, 5, 1, 7, 0, 5, 2, 4, 5, 1, 5, 2, 7, 3, 2, 2, 6, 9, 4, 4, 0, 7, 8, 2, 7, 4, 4, 8, 1, 1, 4, 4, 9, 7, 2, 1, 9, 10, 6, 1, 0, 2, 0, 9, 12, 7, 4, 12, 6, 5, 4, 5, 12, 0, 8, 3, 3, 10, 8, 0, 2, 13, 2, 13, 10, 10, 1, 15, 0, 7, 9, 9, 3, 13, 7, 4, 0, 7, 5, 4, 13, 2

Offset: 1

Author

Antonio Roldán, Apr 08 2014

Keywords

• nonn

Examples

			a(9) = 4 because A001694(9) = 36, A001694(10) = 49, and there are 4 primes between them: 37, 41, 43 and 47.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001694, A240591.

Programs

PARI

ispowerful(n)={local(h);if(n==1,h=1,h=(vecmin(factor(n)[, 2])>1));return(h)}
proxpowerful(n)={local(k);k=n+1;while(!ispowerful(k),k+=1);return(k)}
{for(i=1,5000,if(ispowerful(i),m=proxpowerful(i);p=primepi(m)-primepi(i);print1(p, ", ")))}

Python

from math import isqrt
from sympy import mobius, integer_nthroot, primepi
def A240590(n):
    def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
    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
    def f(x):
        c, l = n+x, 0
        j = isqrt(x)
        while j>1:
            k2 = integer_nthroot(x//j**2,3)[0]+1
            w = squarefreepi(k2-1)
            c -= j*(w-l)
            l, j = w, isqrt(x//k2**3)
        c -= squarefreepi(integer_nthroot(x,3)[0])-l
        return c
    return -primepi(a:=bisection(f,n,n))+primepi(bisection(lambda x:f(x)+1,a,a)) # Chai Wah Wu, Sep 15 2024