A000015 Smallest prime power >= n.

1, 2, 3, 4, 5, 7, 7, 8, 9, 11, 11, 13, 13, 16, 16, 16, 17, 19, 19, 23, 23, 23, 23, 25, 25, 27, 27, 29, 29, 31, 31, 32, 37, 37, 37, 37, 37, 41, 41, 41, 41, 43, 43, 47, 47, 47, 47, 49, 49, 53, 53, 53, 53, 59, 59, 59, 59, 59, 59, 61, 61, 64, 64, 64, 67, 67, 67, 71, 71, 71, 71, 73

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

The length of the m-th run of {a(n)} is the length of the (m-1)-st run of A031218 for m > 1. - Colin Linzer, Mar 08 2024

Links

• David W. Wilson, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Prime Power.

Crossrefs

Cf. A000961, A031218.

Programs

Haskell

a000015 n = a000015_list !! (n-1)
a000015_list = 1 : concat
   (zipWith(\pp qq -> replicate (fromInteger (pp - qq)) pp)
           (tail a000961_list) a000961_list)
-- Reinhard Zumkeller, Nov 17 2011, Apr 25 2011

Maple

N:= 1000: # to get all terms <= N
Primes:= select(isprime,{$1..N}):
PPs:= {1} union Primes:
for k from 1 to ilog2(N) do
   PPs:= PPs union map(`^`, select(`<=`,Primes, floor(N^(1/k))),k)
od:
PPs:= sort(convert(PPs,list)):
1, seq(PPs[i]$(PPs[i]-PPs[i-1]), i=2..nops(PPs)); # Robert Israel, Jul 23 2015

Mathematica

Insert[Table[m:=n;While[Not[Length[FactorInteger[m]]==1],m++ ];m,{n,2,100}], 1, 1] (* Stefan Steinerberger, Apr 17 2006 *)
a[n_] := NestWhile[# + 1 &, n, Not@*PrimePowerQ]; (* Matthew House, Jul 14 2015, v6.0+ *)
a[ n_] := If[ n < 2, Boole[n == 1], Module[{m = n}, While[ ! PrimePowerQ[ m], m++]; m]]; (* Michael Somos, Mar 06 2018 *)
a[ n_] := If[ n < 1, 0, Module[{m = n}, While[ Length[ FactorInteger @ m ] != 1, m++]; m]]; (* Michael Somos, Mar 06 2018 *)

PARI

{a(n) = if( n<1, 0, while(matsize(factor(n))[1]>1, n++); n)}; /* Michael Somos, Jul 16 2002 */

PARI

a(n)=if(n>1,while(!isprimepower(n),n++));n \\ Charles R Greathouse IV, Feb 01 2013

Python

from itertools import count
from sympy import factorint
def A000015(n): return next(filter(lambda m:len(factorint(m))<=1, count(n))) # Chai Wah Wu, Oct 25 2024

Sage

[next_prime_power(n) for n in range(72)]  # Zerinvary Lajos, Jun 13 2009

Formula

a(A110654(n+1)) = A188666(n). - Reinhard Zumkeller, Apr 25 2011, corrected by M. F. Hasler, Jul 25 2015

a(n) = A188666(2n-1). - M. F. Hasler, Jul 25 2015

Extensions

More terms from Michael Somos, Jul 16 2002