A167184 Smallest prime power >= n that is not prime.

1, 4, 4, 4, 8, 8, 8, 8, 9, 16, 16, 16, 16, 16, 16, 16, 25, 25, 25, 25, 25, 25, 25, 25, 25, 27, 27, 32, 32, 32, 32, 32, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 81, 81, 81, 81, 81, 81, 81, 81

Offset: 1

Author

Michael B. Porter, Oct 29 2009

Keywords

• easy
• nonn

Examples

			For a(12), 12, 14, and 15 are not prime powers, and 13 is a prime power but it is prime. Since 16 = 2^4 is a prime power, a(12) = 16.
		

Links

• Robert Price, Table of n, a(n) for n = 1..2000

Crossrefs

List of nonprime prime powers: A025475.

Previous nonprime prime power: A167185.

Next prime power including primes: A000015.

Programs

Mathematica

Module[{ppwrs=Join[{1},Sort[Flatten[Table[Prime[Range[5]]^p,{p,2,10}]]]]}, Flatten[ Table[Select[ppwrs,#>=n&,1],{n,90}]]] (* Harvey P. Dale, Oct 06 2014 *)

PARI

isA025475(n) = (omega(n) == 1 & !isprime(n)) || (n == 1)
A167184(n) = {local(m);m=n;while(!isA025475(m),m++);m}

Python

from itertools import count
from sympy import factorint
def A167184(n): return next(filter(lambda m:len(f:=factorint(m))<=1 and max(f.values(),default=2)>1, count(n))) # Chai Wah Wu, Oct 25 2024