A246655 - OEIS

%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