%I #114 Sep 17 2024 12:33:58
%S 2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41,43,47,49,53,59,
%T 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
%N Prime powers: numbers of the form p^k where p is a prime and k >= 1.
%C The elements are called prime powers in contrast to the powers of primes which are the numbers of the same form but with k >= 0, cf. A000961.
%C Every nonzero integer is the product of elements of this sequence which are relatively prime and an element of {-1, 1}. This product is up to a rearrangement of the factors unique. (This statement is the fundamental theorem of arithmetic.)
%C These numbers are the numbers such that the von Mangoldt function is nonzero.
%C These numbers are the numbers of elements in finite fields. - _Franz Vrabec_, Aug 11 2004
%C A positive integer n is a prime power if and only if nZ is a primary ideal of Z. - _John Cremona_, Sep 02 2014
%C Also, numbers n divisible by their cototients A051953(n). - _Ivan Neretin_, May 29 2016
%C Numbers n such that (theta_3(q) - theta_3(q^n)) / 2 is the g.f. of a multiplicative sequence. - _Michael Somos_, Oct 17 2016
%C Numbers that are evenly divisible by exactly one prime number. - _Lee A. Newberg_, May 07 2018
%C Ram proved that these are precisely the numbers n such that the binomial coefficients n!/(m!(n-m)!) for m = 1..n-1 have a common factor greater than 1 (which is the unique prime dividing n). See Joris, Oestreicher & Steinig for a generalization. - _Charles R Greathouse IV_, Apr 24 2019
%C Blagojević & Ziegler prove that for these n and for any convex polygon in the plane, the polygon can be partitioned into n polygons with equal area and equal perimeter. The result is conjectured (by Nandakumar & Rao, who proved the case n = 2) to hold for all n. - _Charles R Greathouse IV_, Apr 24 2019
%C Numbers n such that A367064(n) < 0. - _Chai Wah Wu_, Nov 06 2023
%H Robert Israel, <a href="/A246655/b246655.txt">Table of n, a(n) for n = 1..10000</a>
%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 H. Joris, C. Oestreicher and J. Steinig, <a href="https://doi.org/10.1016/0022-314X(85)90013-7">The greatest common divisor of certain sets of binomial coefficients</a>, Journal of Number Theory 21 (1985), pp. 101-119.
%H Pavle V. M. Blagojević and Günter M. Ziegler, <a href="https://arxiv.org/abs/1202.5504">Convex equipartitions via equivariant obstruction theory</a>, arXiv:1202.5504 [math.AT], 2012-2013; Israel Journal of Mathematics 200:1 (June 2014), pp 49-77.
%H Hans Montanus and Ron Westdijk, <a href="https://greenbluemath.nl/wp-content/uploads/2024/03/Cellular-Automation-and-Binomials.pdf">Cellular Automation and Binomials</a>, Green Blue Mathematics (2022), p. 90.
%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 Balak Ram, <a href="https://babel.hathitrust.org/cgi/pt?id=njp.32101080760422;view=1up;seq=51">Common factors of n!/(m!(n-m)!), (m = 1, 2, ... n-1)</a>, Journal of the Indian Mathematical Club (Madras) 1 (1909), pp. 39-43.
%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 Chai Wah Wu, <a href="https://arxiv.org/abs/2409.05844">Algorithms for complementary sequences</a>, arXiv:2409.05844 [math.NT], 2024.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Prime_power">Prime power</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F a(n) is characterized by A001221(a(n)) = 1.
%F a(n) is characterized by A014963(a(n)) != 1.
%F Euler's A000010(a(n)) = a(n)*(1 - 1/A014963(a(n))).
%F All three relations above are not true for A000961(n) instead of a(n).
%F Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + A077761 + A136141. - _François Huppé_, Jul 31 2024
%p select(t -> nops(numtheory:-factorset(t))=1, [$1..1000]); # _Robert Israel_, Sep 01 2014
%p A246655 := proc(n) A000961(n+1) end proc: # _R. J. Mathar_, Jan 09 2017
%p isprimepower := n -> nops(NumberTheory:-PrimeFactors(n)) = 1: # _Peter Luschny_, Oct 09 2022
%t Select[Range[222], PrimePowerQ]
%o (Sage)
%o [n for n in (1..222) if sloane.A001221(n) == 1]
%o (PARI)
%o [p| p <- [1..222], isprimepower(p)]
%o (PARI) list(lim)=my(v=List(primes([2,lim\=1]))); for(e=2,logint(lim,2), forprime(p=2,sqrtnint(lim,e), listput(v,p^e))); Set(v) \\ _Charles R Greathouse IV_, Feb 03 2023
%o (Python)
%o from sympy import primerange
%o m = 10**5
%o A246655 = []
%o for p in primerange(1,m):
%o pe = p
%o while pe < m:
%o A246655.append(pe)
%o pe *= p
%o A246655 = sorted(A246655) # _Chai Wah Wu_, Sep 04 2014
%o (Python)
%o from sympy import primepi, integer_nthroot
%o def A246655(n):
%o def f(x): return int(n-1+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
%o kmin, kmax = 1,2
%o while f(kmax) >= kmax:
%o kmax <<= 1
%o while True:
%o kmid = kmax+kmin>>1
%o if f(kmid) < kmid:
%o kmax = kmid
%o else:
%o kmin = kmid
%o if kmax-kmin <= 1:
%o break
%o return kmax # _Chai Wah Wu_, Aug 20 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. A001221, A014963, A069513, A367064.
%Y Partial sums of A275120.
%K nonn,nice,core,easy
%O 1,1
%A _Peter Luschny_ and _Franklin T. Adams-Watters_, Sep 01 2014