The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A001597 Perfect powers: m^k where m > 0 and k >= 2. (Formerly M3326 N1336) 483

%I M3326 N1336

%S 1,4,8,9,16,25,27,32,36,49,64,81,100,121,125,128,144,169,196,216,225,

%T 243,256,289,324,343,361,400,441,484,512,529,576,625,676,729,784,841,

%U 900,961,1000,1024,1089,1156,1225,1296,1331,1369,1444,1521,1600,1681,1728,1764

%N Perfect powers: m^k where m > 0 and k >= 2.

%C Might also be called the nontrivial powers. - _N. J. A. Sloane_, Mar 24 2018

%C See A175064 for number of ways to write a(n) as m^k (m >= 1, k >= 1). - _Jaroslav Krizek_, Jan 23 2010

%C a(1) = 1, for n >= 2: a(n) = numbers m such that sum of perfect divisors of x = m has no solution. Perfect divisor of n is divisor d such that d^k = n for some k >= 1. a(n) for n >= 2 is complement of A175082. - _Jaroslav Krizek_, Jan 24 2010

%C A075802(a(n)) = 1. - _Reinhard Zumkeller_, Jun 20 2011

%C Catalan's conjecture (now a theorem) is that 1 occurs just once as a difference, between 8 and 9.

%C For a proof of Catalan's conjecture, see the paper by Metsänkylä. - _L. Edson Jeffery_, Nov 29 2013

%C m^k is the largest number n such that (n^k-m)/(n-m) is an integer (for k > 1 and m > 1). - _Derek Orr_, May 22 2014

%C From _Daniel Forgues_, Jul 22 2014: (Start)

%C a(n) is asymptotic to n^2, since the density of cubes and higher powers among the squares and higher powers is 0. E.g.,

%C a(10^1) = 49 (49% of 10^2),

%C a(10^2) = 6400 (64% of 10^4),

%C a(10^3) = 804357 (80.4% of 10^6),

%C a(10^4) = 90706576 (90.7% of 10^8),

%C a(10^n) ~ 10^(2n) - o(10^(2n)). (End)

%C A proper subset of A001694. - _Robert G. Wilson v_, Aug 11 2014

%C a(10^n): 1, 49, 6400, 804357, 90706576, 9565035601, 979846576384, 99066667994176, 9956760243243489, ... . - _Robert G. Wilson v_, Aug 15 2014

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 66.

%D R. Schoof, Catalan's Conjecture, Springer-Verlag, 2008, p. 1.

%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 David W. Wilson, <a href="/A001597/b001597.txt">Table of n, a(n) for n = 1..10000</a>.

%H Abdelkader Dendane, <a href="http://www.analyzemath.com/Calculators_2/power_calculator.html">Power (Exponential) Calculator</a>.

%H H. W. Gould, <a href="http://www.fq.math.ca/Scanned/8-3/advanced8-3.pdf">Problem H-170</a>, Fib. Quart., 8 (1970), p. 268, problem H-170.

%H W. Hürlimann, <a href="http://www.researchgate.net/profile/Werner_Huerlimann/publication/271834077">A First Digit Theorem for Powers, Communications in Mathematics and Applications Vol. 5, No. 3, pp. 91-99, 2014.

%H R. Jakimczuk, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Jakimczuk3/jakimczuk21.html">On the Distribution of Perfect Powers</a>, J. Int. Seq. 14 (2011) # 11.8.5

%H Rafael Jakimczuk, <a href="http://www.emis.de/journals/JIS/VOL15/Jakimczuk/jak29.html">Asymptotic Formulae for the n-th Perfect Power</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.5.5.

%H Holly Krieger and Brady Haran, <a href="https://www.youtube.com/watch?v=Us-__MukH9I&amp;t=0s">Catalan's Conjecture</a>, Numberphile video (2018)

%H Tauno Metsänkylä, <a href="http://dx.doi.org/10.1090/S0273-0979-03-00993-5">Catalan's conjecture: another old Diophantine problem solved</a>, Bull. Amer. Math. Soc. (NS), Vol. 41, No. 1 (2004), pp. 43-57.

%H Donald J. Newman, <a href="http://dx.doi.org/10.1007/978-1-4613-8214-0">A Problem Seminar</a>, Springer; see Problem #72.

%H M. A. Nyblom, <a href="http://www.austms.org.au/Publ/Gazette/2006/Nov06/nyblom.pdf">A Counting Function for the Sequence of Perfect Powers</a>, Austral. Math. Soc. Gaz. 33 (2006), 338-343.

%H Alf van der Poorten, <a href="/A023057/a023057.txt">Remarks on the sequence of 'perfect' powers</a>.

%H Michel Waldschmidt, <a href="http://arXiv.org/abs/math.NT/0312440">Open Diophantine problems</a>, arXiv:math/0312440 [math.NT], 2003-2004.

%H Michel Waldschmidt, <a href="https://webusers.imj-prg.fr/~michel.waldschmidt/articles/pdf/abcLahoreProceedings.pdf">Lecture on the abc conjecture and some of its consequences</a>, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/PerfectPower.html">MathWorld: Perfect Power</a>

%F Goldbach showed that Sum_{n >= 2} 1/(a(n)-1) = 1.

%F Formulas from postings to the Number Theory List by various authors, 2002:

%F Sum_{i >= 2} Sum_{j >= 2} 1/i^j = 1;

%F Sum_{k >= 2} 1/(a(k)+1) = Pi^2 / 3 - 5/2;

%F Sum_{k >= 2} 1/a(k) = Sum_{n >= 2} mu(n)(1- zeta(n)) approx = 0.87446436840494... See A072102.

%F For asymptotics see Newman.

%F For n > 1: gcd(exponents in prime factorization of a(n)) > 1, cf. A124010. - _Reinhard Zumkeller_, Apr 13 2012

%F a(n) ~ n^2. - _Thomas Ordowski_, Nov 04 2012

%p isA001597 := proc(n)

%p local e ;

%p e := seq(op(2,p),p=ifactors(n)) ;

%p return ( igcd(e) >=2 or n =1 ) ;

%p end proc:

%p A001597 := proc(n)

%p option remember;

%p local a;

%p if n = 1 then

%p 1;

%p else

%p for a from procname(n-1)+1 do

%p if isA001597(a) then

%p return a ;

%p end if;

%p end do;

%p end if;

%p end proc:

%p seq(A001597(n),n=1..70) ; # _R. J. Mathar_, Jun 07 2011

%t min = 0; max = 10^4; Union@ Flatten@ Table[ n^expo, {expo, Prime@ Range@ PrimePi@ Log2@ max}, {n, Floor[1 + min^(1/expo)], max^(1/expo)}] (* _T. D. Noe_, Apr 18 2011; slightly modified by _Robert G. Wilson v_, Aug 11 2014 *)

%t perfectPowerQ[n_] := n == 1 || GCD @@ FactorInteger[n][[All, 2]] > 1; Select[Range@ 1765, perfectPowerQ] (* _Ant King_, Jun 29 2013; slightly modified by _Robert G. Wilson v_, Aug 11 2014 *)

%t nextPerfectPower[n_] := If[n == 1, 4, Min@ Table[ (Floor[n^(1/k)] + 1)^k, {k, 2, 1 + Floor@ Log2@ n}]]; NestList[ nextPerfectPower, 1, 55] (* _Robert G. Wilson v_, Aug 11 2014 *)

%t Join[{1},Select[Range,GCD@@FactorInteger[#][[All,2]]>1&]] (* _Harvey P. Dale_, Apr 30 2018 *)

%o (MAGMA)  cat [n : n in [2..1000] | IsPower(n) ];

%o (PARI) {a(n) = local(m, c); if( n<2, n==1, c=1; m=1; while( c<n, m++; if( ispower(m), c++)); m)} /* _Michael Somos_, Aug 05 2009 */

%o (PARI) is(n)=ispower(n) || n==1 \\ _Charles R Greathouse IV_, Sep 16 2015

%o (PARI) list(lim)=my(v=List(vector(sqrtint(lim\=1),n,n^2))); for(e=3,logint(lim,2), for(n=2,sqrtnint(lim,e), listput(v,n^e))); Set(v) \\ _Charles R Greathouse IV_, Dec 10 2019

%o (Sage)

%o def A001597_list(n) :

%o return [k for k in (1..n) if k.is_perfect_power()]

%o A001597_list(1764) # _Peter Luschny_, Feb 03 2012

%o (Haskell)

%o import Data.Map (singleton, findMin, deleteMin, insert)

%o a001597 n = a001597_list !! (n-1)

%o (a001597_list, a025478_list, a025479_list) =

%o unzip3 \$ (1, 1, 2) : f 9 (3, 2) (singleton 4 (2, 2)) where

%o f zz (bz, ez) m

%o | xx < zz = (xx, bx, ex) :

%o f zz (bz, ez+1) (insert (bx*xx) (bx, ex+1) \$ deleteMin m)

%o | xx > zz = (zz, bz, 2) :

%o f (zz+2*bz+1) (bz+1, 2) (insert (bz*zz) (bz, 3) m)

%o | otherwise = f (zz+2*bz+1) (bz+1, 2) m

%o where (xx, (bx, ex)) = findMin m -- bx ^ ex == xx

%o -- _Reinhard Zumkeller_, Mar 28 2014, Oct 04 2012, Apr 13 2012

%o (Python)

%o from sympy import perfect_power

%o def ok(n): return n==1 or perfect_power(n)

%o print([m for m in range(1, 1765) if ok(m)]) # _Michael S. Branicky_, Jan 04 2021

%Y Complement of A007916.

%Y Subsequence of A072103; A072777 is a subsequence.

%Y Union of A075109 and A075090.

%Y Cf. A023055, A023057, A025478, A070428, A072102, A074981, A076404, A239728, A239870, A097054, A089579, A089580 (number of exact powers < 10^n).

%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), and which are sometimes confused with the present sequence.

%Y First differences give A053289.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_

%E Minor corrections from _N. J. A. Sloane_, Jun 27 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 13 01:36 EDT 2021. Contains 342934 sequences. (Running on oeis4.)