A061345 Powers of odd primes. Alternatively, 1 and the odd prime powers (p^k, p an odd prime, k >= 1).

1, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239

Offset: 0

Author

N. J. A. Sloane, Jun 08 2001

Keywords

• nonn
• easy

Comments

Let a(n)=p^e, then tau(a(n)^2) = tau(p^(2*e)) = 2*e+1 = 2*(e+1)-1 = tau(2*a(n))-1 where tau=A000005. - Juri-Stepan Gerasimov, Jul 14 2011

For n > 0, also the allowed indices of a Cossidente-Penttila graph. - Eric W. Weisstein, Feb 24 2025

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• L. J. Corwin, Irreducible polynomials over the integers which factor mod p for every p, Unpublished Bell Labs Memo, Sep 07 1967 [Annotated scanned copy]
• Eric Weisstein's World of Mathematics, Odd Prime Power.

Crossrefs

Cf. A061346, A000961, A005408, A061344, A075109, A075110.

Programs

Magma

[1] cat [n: n in [3..300 by 2] | IsPrimePower(n)]; // Bruno Berselli, Feb 25 2016

Maple

select(t -> nops(ifactors(t)[2])<=1, [seq(2*i+1,i=0..1000)]); # Robert Israel, Jun 11 2014
# alternative:
A061345 := proc(n)
    option remember;
    local k ;
    if n = 0 then
        1;
    else
        for k from procname(n-1)+2 by 2 do
            if nops(numtheory[factorset](k)) = 1 then
                return k ;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Jun 25 2016
isOddPrimepower := n -> type(n, 'primepower') and not type(n, 'even'):
A061345List := up_to -> select(isOddPrimepower, [`$`(1..up_to)]):
A061345List(240); # Peter Luschny, Feb 02 2023

Mathematica

t={1};k=0;Do[If[k==1,AppendTo[t,a1]];k=0;Do[c=Sqrt[a^2+b^2];If[IntegerQ[c]&&GCD[a,b,c]==1,k++;a1=a;b1=b;c1=c;],{b,4,a^2/2,2}],{a,3,260,2}];t (* Vladimir Joseph Stephan Orlovsky, Jan 29 2012 *)
Select[2 Range@ 130 - 1, PrimeNu@# < 2 &] (* Robert G. Wilson v, Jun 12 2014 *)
Join[{1}, Select[Range[1, 200, 2], PrimePowerQ]] (* Eric W. Weisstein, Feb 23 2025 *)

PARI

is(n)=my(p); if(isprimepower(n,&p), p>2, n==1) \\ Charles R Greathouse IV, Jun 08 2016

Python

from sympy import primepi, integer_nthroot
def A061345(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = 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-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length())))
    return bisection(f,n+1,n+1) # Chai Wah Wu, Feb 03 2025

Formula

a(n) = A061344(n)-1.

Intersection of A000961 (prime powers) and A005408 (odd numbers). - Robert Israel, Jun 11 2014

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Jun 12 2001