A001597 - OEIS

%I M3326 N1336 #227 Oct 05 2024 16:29:12

%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. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section D9.

%D René 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 Werner 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 (2014), pp. 91-99.

%H Rafael Jakimczuk, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Jakimczuk3/jakimczuk21.html">On the Distribution of Perfect Powers</a>, Journal of Integer Sequences, Vol. 14 (2011), Article 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), Article 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 Preda Mihailescu, <a href="https://doi.org/10.1515/crll.2004.048">Primary Cyclotomic Units and a Proof of Catalan’s Conjecture</a>, Journal für die Reine und Angewandte Mathematik, vol. 27 (2004), pp. 167-195.

%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 Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/a001597.7z">1010196 perfect powers up to 10^12</a>, compressed 7z archive, 3.3 MB (2023).

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

%H Michel Waldschmidt, <a href="https://arxiv.org/abs/math/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 Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectPower.html">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

%F a(n) = n^2 - 2*n^(5/3) - 2*n^(7/5) + (13/3)*n^(4/3) - 2*n^(9/7) + 2*n^(6/5) - 2*n^(13/11) + o(n^(13/11)) (Jakimczuk, 2012). - _Amiram Eldar_, Jun 30 2023

%p isA001597 := proc(n)

%p     local e ;

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

%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

%p N:= 10000: # to get all entries <= N

%p sort({1,seq(seq(a^b, b = 2 .. floor(log[a](N))), a = 2 .. floor(sqrt(N)))}); # _Robert FERREOL_, Jul 18 2023

%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[2000],GCD@@FactorInteger[#][[All,2]]>1&]] (* _Harvey P. Dale_, Apr 30 2018 *)

%o (Magma) [1] 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

%o (Python)

%o import sympy

%o class A001597() :

%o     def __init__(self) :

%o         self.a = [1]

%o     def at(self, n):

%o         if n <= len(self.a):

%o             return self.a[n-1]

%o         else:

%o             cand = self.at(n-1)+1

%o             while sympy.perfect_power(cand) == False:

%o                 cand += 1

%o             self.a.append(cand)

%o             return cand

%o a001597 = A001597()

%o for n in range(1,20):

%o     print(a001597.at(n)) # _R. J. Mathar_, Mar 28 2023

%o (Python)

%o from sympy import mobius, integer_nthroot

%o def A001597(n):

%o     def f(x): return int(n-2+x+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,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 13 2024

%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.

%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