A024621 Positions of nonprimes among the powers of primes (A000961).

1, 4, 7, 8, 11, 15, 16, 19, 24, 28, 33, 42, 43, 45, 54, 69, 71, 79, 87, 92, 118, 121, 137, 153, 171, 188, 199, 245, 248, 293, 314, 341, 360, 361, 364, 393, 446, 483, 526, 559, 605, 651, 699, 719, 750, 857, 894, 930, 935, 1050, 1079, 1215, 1305, 1348, 1436, 1479, 1514

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Crossrefs

Complement of A024620.

Programs

PARI

lista(nn) = {vec = vector(nn, i, i); powpr = select((i->((omega(i)==1) || (i==1))), vec); for (i = 1, #powpr, if (! isprime(powpr[i]), print1(i, ", ")););} \\ Michel Marcus, Oct 02 2013

Python

from sympy import primepi, integer_nthroot
def A024621(n):
    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): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(2,x.bit_length())))
    return n+primepi(bisection(f,n,n)) # Chai Wah Wu, Nov 05 2024