A246547 Prime powers p^e where p is a prime and e >= 2 (prime powers without the primes or 1).

4, 8, 9, 16, 25, 27, 32, 49, 64, 81, 121, 125, 128, 169, 243, 256, 289, 343, 361, 512, 529, 625, 729, 841, 961, 1024, 1331, 1369, 1681, 1849, 2048, 2187, 2197, 2209, 2401, 2809, 3125, 3481, 3721, 4096, 4489, 4913, 5041, 5329, 6241, 6561, 6859, 6889, 7921, 8192, 9409, 10201, 10609, 11449, 11881, 12167, 12769, 14641

Offset: 1

Author

Joerg Arndt, Aug 29 2014

Keywords

• nonn
• easy

Comments

These are sometimes called the proper prime powers.

A proper subset of A001597.

Equals A000961 \ A008578 = { x in A001597 | A001221(x)=1 }. - M. F. Hasler, Aug 29 2014

Links

• Jens Kruse Andersen, Table of n, a(n) for n = 1..10000
• Chai Wah Wu, Algorithms for complementary sequences, arXiv:2409.05844 [math.NT], 2024.

Crossrefs

Essentially the same as A025475.

Cf. A000961, A001597, A025528, A051953, A136141, A246655.

There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018

Programs

Maple

isA246547 := proc(n)
    local ifs;
    ifs := ifactors(n)[2] ;
    if nops(ifs) <> 1 then
        false;
    else
        is(op(2, op(1, ifs)) > 1);
    end if;
end proc:
for n from 2 do
    if isA246547(n) then
        print(n) ;
    end if;
end do: # R. J. Mathar, Feb 01 2016 # Or:
isA246547 := n -> not isprime(n) and nops(numtheory:-factorset(n)) = 1:
select(isA246547, [$1..10000]); # Peter Luschny, May 01 2018

Mathematica

With[{upto=15000},Complement[Select[Range[upto],PrimePowerQ],Prime[ Range[ PrimePi[ upto]]]]] (* Harvey P. Dale, Nov 28 2014 *)
Select[ Range@ 15000, PrimePowerQ@# && !SquareFreeQ@# &] (* Robert G. Wilson v, Dec 01 2014 *)
With[{n = 15000}, Union@ Flatten@ Table[Array[p^# &, Floor@ Log[p, n] - 1, 2], {p, Prime@ Range@ PrimePi@ Sqrt@ n}] ] (* Michael De Vlieger, Jul 06 2018, faster program *)

PARI

for(n=1,10^5,if(isprimepower(n)>=2,print1(n,", ")));

PARI

m=10^5; v=[]; forprime(p=2, sqrtint(m), e=2; while(p^e<=m, v=concat(v, p^e); e++)); v=vecsort(v) \\ Faster program. Jens Kruse Andersen, Aug 29 2014

Python

from sympy import primepi, integer_nthroot
def A246547(n):
    def f(x): return int(n-1+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(2,x.bit_length())))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Aug 14 2024

SageMath

def A246547List(n):
    return [p for p in srange(2, n) if p.is_prime_power() and not p.is_prime()]
print(A246547List(14642))  # Peter Luschny, Sep 16 2023

Formula

a(n) = A025475(n+1). - M. F. Hasler, Aug 29 2014

Sum_{n>=1} 1/a(n) = Sum_{p prime} 1/(p*(p-1)) = A136141. - Amiram Eldar, Dec 21 2020