A000961 - OEIS

%I M0517 N0185 #218 Aug 05 2024 09:20:43

%S 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 59,61,64,67,71,73,79,81,83,89,97,101,103,107,109,113,121,125,127,128,

%U 131,137,139,149,151,157,163,167,169,173,179,181,191,193,197,199,211,223,227

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

%C The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.

%C 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 These numbers are (apart from 1) the numbers of elements in finite fields. - _Franz Vrabec_, Aug 11 2004

%C 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 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 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 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 The sequence is A000015 without repetitions, or more formally, A000961=Union[A000015]. - _Zak Seidov_, Feb 06 2008

%C 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 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 A143201(a(n)) = 1. - _Reinhard Zumkeller_, Aug 12 2008

%C Number of distinct primes dividing n=omega(n) < 2. - _Juri-Stepan Gerasimov_, Oct 30 2009

%C 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 Numbers n such that A028236(n) = 1. _Klaus Brockhaus_, Nov 06 2010

%C 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 A003415(a(n)) = A192015(n); A068346(a(n)) = A192016(n); a(n)=A192134(n) + A192015(n). - _Reinhard Zumkeller_, Jun 26 2011

%C A089233(a(n)) = 0. - _Reinhard Zumkeller_, Sep 04 2013

%C 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 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 Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - _Michel Marcus_, Jan 16 2019

%C Possible numbers of elements in a finite vector space. - _Jianing Song_, Apr 22 2021

%D 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 M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.

%D R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A000961/b000961.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 Brady Haran and Günter Ziegler, <a href="https://www.youtube.com/watch?v=5SfXqTENV_Q">Cannons and Sparrows</a>, Numberphile video (2018).

%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimePower.html">Prime Power</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ProjectivePlane.html">Projective Plane</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F a(n) = A025473(n)^A025474(n). - _David Wasserman_, Feb 16 2006

%F a(n) = A117331(A117333(n)). - _Reinhard Zumkeller_, Mar 08 2006

%F 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 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 A001221(a(n)) < 2. - _Juri-Stepan Gerasimov_, Oct 30 2009

%F A008480(a(n)) = 1 for all n >= 1. - _Alois P. Heinz_, May 26 2018

%F Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + 1 + A077761 + A136141. - _François Huppé_, Jul 31 2024

%p readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d,`,n) fi: od:

%p # second Maple program:

%p a:= proc(n) option remember; local k; for k from

%p       1+a(n-1) while nops(ifactors(k)[2])>1 do od; k

%p     end: a(1):=1: A000961:= a:

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Apr 08 2013

%t Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]

%t Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]

%t 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 Join[{1}, Select[Range[2, 250], PrimePowerQ]] (* _Jean-François Alcover_, Jul 07 2015 *)

%o (Magma) [1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by _Arkadiusz Wesolowski_, Jul 20 2012

%o (PARI) A000961(n,l=-1,k=0)=until(n--<1,until(l<lcm(l,k++),); l=lcm(l,k));k

%o 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 (PARI) isA000961(n) = (omega(n) == 1 || n == 1) \\ _Michael B. Porter_, Sep 23 2009

%o (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 (PARI) is(n)=isprimepower(n) || n==1 \\ _Charles R Greathouse IV_, Nov 20 2012

%o (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 (Haskell)

%o import Data.Set (singleton, deleteFindMin, insert)

%o a000961 n = a000961_list !! (n-1)

%o a000961_list = 1 : g (singleton 2) (tail a000040_list) where

%o g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps

%o where (m, s') = deleteFindMin s

%o -- _Reinhard Zumkeller_, May 01 2012, Apr 25 2011

%o (Sage)

%o def A000961_list(n):

%o     R = [1]

%o     for i in (2..n):

%o         if i.is_prime_power(): R.append(i)

%o     return R

%o A000961_list(227) # _Peter Luschny_, Feb 07 2012

%o (Python)

%o from sympy import primerange

%o def A000961_list(limit): # following Python style, list terms < limit

%o     L = [1]

%o     for p in primerange(1, limit):

%o         pe = p

%o         while pe < limit:

%o             L.append(pe)

%o             pe *= p

%o     return sorted(L) # _Chai Wah Wu_, Sep 08 2014, edited by _M. F. Hasler_, Jun 16 2022

%o (Python)

%o from sympy import primepi

%o from sympy.ntheory.primetest import integer_nthroot

%o def A000961(n):

%o     def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))

%o     m, k = n, f(n)

%o     while m != k:

%o         m, k = k, f(k)

%o     return m # _Chai Wah Wu_, Jul 23 2024

%Y 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 Cf. A008480, A010055, A065515, A095874, A025473.

%Y Cf. indices of record values of A003418; A000668 and A019434 give a member of twin pairs a(n+1)=a(n)+1.

%Y A138929(n) = 2*a(n).

%Y Cf. A000040, A001221, A001477. - _Juri-Stepan Gerasimov_, Dec 09 2009

%Y A028236 (if n = Product (p_j^k_j), a(n) = numerator of Sum 1/p_j^k_j). - _Klaus Brockhaus_, Nov 06 2010

%Y A000015(n) = Min{term : >= n}; A031218(n) = Max{term : <= n}.

%Y Complementary (in the positive integers) to sequence A024619. - _Jason Kimberley_, Nov 10 2015

%K nonn,easy,core,nice

%O 1,2

%A _N. J. A. Sloane_

%E Description modified by _Ralf Stephan_, Aug 29 2014