cp's OEIS Frontend

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

%I A000961 M0517 N0185 #229 Aug 04 2025 10:13:45
%S A000961 1,2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41,43,47,49,53,
%T A000961 59,61,64,67,71,73,79,81,83,89,97,101,103,107,109,113,121,125,127,128,
%U A000961 131,137,139,149,151,157,163,167,169,173,179,181,191,193,197,199,211,223,227
%N A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).
%C A000961 The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.
%C A000961 Any nonzero integer is a product of primes and units, where the units are +1 and -1. This is tied to the Fundamental Theorem of Arithmetic which proves that the factorizations are unique up to order and units. (So, since 1 = p^0 does not have a well defined prime base p, it is sometimes not regarded as a prime power. See A246655 for the sequence without 1.)
%C A000961 These numbers are (apart from 1) the numbers of elements in finite fields. - _Franz Vrabec_, Aug 11 2004
%C A000961 Numbers whose divisors form a geometrical progression. The divisors of p^k are 1, p, p^2, p^3, ..., p^k. - _Amarnath Murthy_, Jan 09 2002
%C A000961 These are also precisely the orders of those finite affine planes that are known to exist as of today. (The order of a finite affine plane is the number of points in an arbitrarily chosen line of that plane. This number is unique for all lines comprise the same number of points.) - Peter C. Heinig (algorithms(AT)gmx.de), Aug 09 2006
%C A000961 Except for first term, the index of the second number divisible by n in A002378, if the index equals n. - _Mats Granvik_, Nov 18 2007
%C A000961 These are precisely the numbers such that lcm(1,...,m-1) < lcm(1,...,m) (=A003418(m) for m>0; here for m=1, the l.h.s. is taken to be 0). We have a(n+1)=a(n)+1 if a(n) is a Mersenne prime or a(n)+1 is a Fermat prime; the converse is true except for n=7 (from Catalan's conjecture) and n=1, since 2^1-1 and 2^0+1 are not considered as Mersenne resp. Fermat prime. - _M. F. Hasler_, Jan 18 2007, Apr 18 2010
%C A000961 The sequence is A000015 without repetitions, or more formally, A000961=Union[A000015]. - _Zak Seidov_, Feb 06 2008
%C A000961 Except for a(1)=1, indices for which the cyclotomic polynomial Phi[k] yields a prime at x=1, cf. A020500. - _M. F. Hasler_, Apr 04 2008
%C A000961 Also, {A138929(k) ; k>1} = {2*A000961(k) ; k>1} = {4,6,8,10,14,16,18,22,26,32,34,38,46,50,54,58,62,64,74,82,86,94,98,...} are exactly the indices for which Phi[k](-1) is prime. - _M. F. Hasler_, Apr 04 2008
%C A000961 A143201(a(n)) = 1. - _Reinhard Zumkeller_, Aug 12 2008
%C A000961 Number of distinct primes dividing n=omega(n) < 2. - _Juri-Stepan Gerasimov_, Oct 30 2009
%C A000961 Numbers n such that Sum_{p-1|p is prime and divisor of n} = Product_{p-1|p is prime and divisor of n}. A055631(n) = A173557(n-1). - _Juri-Stepan Gerasimov_, Dec 09 2009, Mar 10 2010
%C A000961 Numbers n such that A028236(n) = 1. _Klaus Brockhaus_, Nov 06 2010
%C A000961 A188666(k) = a(k+1) for k: 2*a(k) <= k < 2*a(k+1), k > 0; notably a(n+1) = A188666(2*a(n)). - _Reinhard Zumkeller_, Apr 25 2011
%C A000961 A003415(a(n)) = A192015(n); A068346(a(n)) = A192016(n); a(n)=A192134(n) + A192015(n). - _Reinhard Zumkeller_, Jun 26 2011
%C A000961 A089233(a(n)) = 0. - _Reinhard Zumkeller_, Sep 04 2013
%C A000961 The positive integers n such that every element of the symmetric group S_n which has order n is an n-cycle. - _W. Edwin Clark_, Aug 05 2014
%C A000961 Conjecture: these are numbers m such that Sum_{k=0..m-1} k^phi(m) == phi(m) (mod m), where phi(m) = A000010(m). - _Thomas Ordowski_ and _Giovanni Resta_, Jul 25 2018
%C A000961 Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - _Michel Marcus_, Jan 16 2019
%C A000961 Possible numbers of elements in a finite vector space. - _Jianing Song_, Apr 22 2021
%D A000961 M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
%D A000961 M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.
%D A000961 R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.
%D A000961 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000961 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000961 T. D. Noe, <a href="/A000961/b000961.txt">Table of n, a(n) for n = 1..10000</a>
%H A000961 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H A000961 Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, and Tony W. H. Wong, <a href="https://arxiv.org/abs/2507.16135">A further investigation on covering systems with odd moduli</a>, arXiv:2507.16135 [math.NT], 2025. See p. 3.
%H A000961 Brady Haran and Günter Ziegler, <a href="https://www.youtube.com/watch?v=5SfXqTENV_Q">Cannons and Sparrows</a>, Numberphile video (2018).
%H A000961 Laurentiu Panaitopol, <a href="http://dx.doi.org/10.1216/rmjm/1021249445">Some of the properties of the sequence of powers of prime numbers</a>, Rocky Mountain Journal of Mathematics, Volume 31, Number 4, Winter 2001.
%H A000961 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimePower.html">Prime Power</a>
%H A000961 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ProjectivePlane.html">Projective Plane</a>
%H A000961 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000961 a(n) = A025473(n)^A025474(n). - _David Wasserman_, Feb 16 2006
%F A000961 a(n) = A117331(A117333(n)). - _Reinhard Zumkeller_, Mar 08 2006
%F A000961 Panaitopol (2001) gives many properties, inequalities and asymptotics, including a(n) ~ prime(n). - _N. J. A. Sloane_, Oct 31 2014, corrected by _M. F. Hasler_, Jun 12 2023 [The reference gives pi*(x) = pi(x) + pi(sqrt(x)) + ... where pi*(x) counts the terms up to x, so it is the inverse function to a(n).]
%F A000961 m=a(n) for some n <=> lcm(1,...,m-1) < lcm(1,...,m), where lcm(1...0):=0 as to include a(1)=1. a(n+1)=a(n)+1 <=> a(n+1)=A019434(k) or a(n)=A000668(k) for some k (by Catalan's conjecture), except for n=1 and n=7. - _M. F. Hasler_, Jan 18 2007, Apr 18 2010
%F A000961 A001221(a(n)) < 2. - _Juri-Stepan Gerasimov_, Oct 30 2009
%F A000961 A008480(a(n)) = 1 for all n >= 1. - _Alois P. Heinz_, May 26 2018
%F A000961 Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + 1 + A077761 + A136141. - _François Huppé_, Jul 31 2024
%p A000961 readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d,`,n) fi: od:
%p A000961 # second Maple program:
%p A000961 a:= proc(n) option remember; local k; for k from
%p A000961       1+a(n-1) while nops(ifactors(k)[2])>1 do od; k
%p A000961     end: a(1):=1: A000961:= a:
%p A000961 seq(a(n), n=1..100);  # _Alois P. Heinz_, Apr 08 2013
%t A000961 Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]
%t A000961 Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]
%t A000961 max = 0; a = {}; Do[m = FactorInteger[n]; w = Sum[m[[k]][[1]]^m[[k]][[2]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* _Artur Jasinski_ *)
%t A000961 Join[{1}, Select[Range[2, 250], PrimePowerQ]] (* _Jean-François Alcover_, Jul 07 2015 *)
%o A000961 (Magma) [1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by _Arkadiusz Wesolowski_, Jul 20 2012
%o A000961 (PARI) A000961(n,l=-1,k=0)=until(n--<1,until(l<lcm(l,k++),); l=lcm(l,k));k
%o A000961 print_A000961(lim=999,l=-1)=for(k=1,lim, l==lcm(l,k) && next; l=lcm(l,k); print1(k,",")) \\ _M. F. Hasler_, Jan 18 2007
%o A000961 (PARI) isA000961(n) = (omega(n) == 1 || n == 1) \\ _Michael B. Porter_, Sep 23 2009
%o A000961 (PARI) nextA000961(n)=my(m,r,p);m=2*n;for(e=1,ceil(log(n+0.01)/log(2)),r=(n+0.01)^(1/e);p=prime(primepi(r)+1);m=min(m,p^e));m \\ _Michael B. Porter_, Nov 02 2009
%o A000961 (PARI) is(n)=isprimepower(n) || n==1 \\ _Charles R Greathouse IV_, Nov 20 2012
%o A000961 (PARI) list(lim)=my(v=primes(primepi(lim)),u=List([1])); forprime(p=2,sqrtint(lim\1),for(e=2,log(lim+.5)\log(p),listput(u,p^e))); vecsort(concat(v,Vec(u))) \\ _Charles R Greathouse IV_, Nov 20 2012
%o A000961 (Haskell)
%o A000961 import Data.Set (singleton, deleteFindMin, insert)
%o A000961 a000961 n = a000961_list !! (n-1)
%o A000961 a000961_list = 1 : g (singleton 2) (tail a000040_list) where
%o A000961 g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps
%o A000961 where (m, s') = deleteFindMin s
%o A000961 -- _Reinhard Zumkeller_, May 01 2012, Apr 25 2011
%o A000961 (Sage)
%o A000961 def A000961_list(n):
%o A000961     R = [1]
%o A000961     for i in (2..n):
%o A000961         if i.is_prime_power(): R.append(i)
%o A000961     return R
%o A000961 A000961_list(227) # _Peter Luschny_, Feb 07 2012
%o A000961 (Python)
%o A000961 from sympy import primerange
%o A000961 def A000961_list(limit): # following Python style, list terms < limit
%o A000961     L = [1]
%o A000961     for p in primerange(1, limit):
%o A000961         pe = p
%o A000961         while pe < limit:
%o A000961             L.append(pe)
%o A000961             pe *= p
%o A000961     return sorted(L) # _Chai Wah Wu_, Sep 08 2014, edited by _M. F. Hasler_, Jun 16 2022
%o A000961 (Python)
%o A000961 from sympy import primepi
%o A000961 from sympy.ntheory.primetest import integer_nthroot
%o A000961 def A000961(n):
%o A000961     def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
%o A000961     m, k = n, f(n)
%o A000961     while m != k:
%o A000961         m, k = k, f(k)
%o A000961     return m # _Chai Wah Wu_, Jul 23 2024
%Y A000961 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
%Y A000961 Cf. A008480, A010055, A065515, A095874, A025473.
%Y A000961 Cf. indices of record values of A003418; A000668 and A019434 give a member of twin pairs a(n+1)=a(n)+1.
%Y A000961 A138929(n) = 2*a(n).
%Y A000961 Cf. A000040, A001221, A001477. - _Juri-Stepan Gerasimov_, Dec 09 2009
%Y A000961 A028236 (if n = Product (p_j^k_j), a(n) = numerator of Sum 1/p_j^k_j). - _Klaus Brockhaus_, Nov 06 2010
%Y A000961 A000015(n) = Min{term : >= n}; A031218(n) = Max{term : <= n}.
%Y A000961 Complementary (in the positive integers) to sequence A024619. - _Jason Kimberley_, Nov 10 2015
%K A000961 nonn,easy,core,nice
%O A000961 1,2
%A A000961 _N. J. A. Sloane_
%E A000961 Description modified by _Ralf Stephan_, Aug 29 2014