OFFSET
1,2
COMMENTS
Might also be called the nontrivial powers. - N. J. A. Sloane, Mar 24 2018
See A175064 for number of ways to write a(n) as m^k (m >= 1, k >= 1). - Jaroslav Krizek, Jan 23 2010
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
A075802(a(n)) = 1. - Reinhard Zumkeller, Jun 20 2011
Catalan's conjecture (now a theorem) is that 1 occurs just once as a difference, between 8 and 9.
For a proof of Catalan's conjecture, see the paper by Metsänkylä. - L. Edson Jeffery, Nov 29 2013
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
From Daniel Forgues, Jul 22 2014: (Start)
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.,
a(10^1) = 49 (49% of 10^2),
a(10^2) = 6400 (64% of 10^4),
a(10^3) = 804357 (80.4% of 10^6),
a(10^4) = 90706576 (90.7% of 10^8),
a(10^n) ~ 10^(2n) - o(10^(2n)). (End)
A proper subset of A001694. - Robert G. Wilson v, Aug 11 2014
a(10^n): 1, 49, 6400, 804357, 90706576, 9565035601, 979846576384, 99066667994176, 9956760243243489, ... . - Robert G. Wilson v, Aug 15 2014
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 66.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section D9.
René Schoof, Catalan's Conjecture, Springer-Verlag, 2008, p. 1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
David W. Wilson, Table of n, a(n) for n = 1..10000.
Abdelkader Dendane, Power (Exponential) Calculator.
H. W. Gould, Problem H-170, Fib. Quart., 8 (1970), p. 268, problem H-170.
Werner Hürlimann, A First Digit Theorem for Powers, Communications in Mathematics and Applications Vol. 5, No. 3 (2014), pp. 91-99.
Rafael Jakimczuk, On the Distribution of Perfect Powers, Journal of Integer Sequences, Vol. 14 (2011), Article 11.8.5.
Rafael Jakimczuk, Asymptotic Formulae for the n-th Perfect Power, Journal of Integer Sequences, Vol. 15 (2012), Article 12.5.5.
Holly Krieger and Brady Haran, Catalan's Conjecture, Numberphile video (2018).
Tauno Metsänkylä, Catalan's conjecture: another old Diophantine problem solved, Bull. Amer. Math. Soc. (NS), Vol. 41, No. 1 (2004), pp. 43-57.
Preda Mihailescu, Primary Cyclotomic Units and a Proof of Catalan’s Conjecture, Journal für die Reine und Angewandte Mathematik, vol. 27 (2004), pp. 167-195.
Donald J. Newman, A Problem Seminar, Springer; see Problem #72.
M. A. Nyblom, A Counting Function for the Sequence of Perfect Powers, Austral. Math. Soc. Gaz. 33 (2006), 338-343.
Hugo Pfoertner, 1010196 perfect powers up to 10^12, compressed 7z archive, 3.3 MB (2023).
Alf van der Poorten, Remarks on the sequence of 'perfect' powers.
Michel Waldschmidt, Open Diophantine problems, arXiv:math/0312440 [math.NT], 2003-2004.
Michel Waldschmidt, Lecture on the abc conjecture and some of its consequences, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.
Eric Weisstein's World of Mathematics, Perfect Power.
FORMULA
Goldbach showed that Sum_{n >= 2} 1/(a(n)-1) = 1.
Formulas from postings to the Number Theory List by various authors, 2002:
Sum_{i >= 2} Sum_{j >= 2} 1/i^j = 1;
Sum_{k >= 2} 1/(a(k)+1) = Pi^2 / 3 - 5/2;
Sum_{k >= 2} 1/a(k) = Sum_{n >= 2} mu(n)(1- zeta(n)) approx = 0.87446436840494... See A072102.
For asymptotics see Newman.
For n > 1: gcd(exponents in prime factorization of a(n)) > 1, cf. A124010. - Reinhard Zumkeller, Apr 13 2012
a(n) ~ n^2. - Thomas Ordowski, Nov 04 2012
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
MAPLE
isA001597 := proc(n)
local e ;
e := seq(op(2, p), p=ifactors(n)[2]) ;
return ( igcd(e) >=2 or n =1 ) ;
end proc:
A001597 := proc(n)
option remember;
local a;
if n = 1 then
1;
else
for a from procname(n-1)+1 do
if isA001597(a) then
return a ;
end if;
end do;
end if;
end proc:
seq(A001597(n), n=1..70) ; # R. J. Mathar, Jun 07 2011
N:= 10000: # to get all entries <= N
sort({1, seq(seq(a^b, b = 2 .. floor(log[a](N))), a = 2 .. floor(sqrt(N)))}); # Robert FERREOL, Jul 18 2023
MATHEMATICA
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 *)
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 *)
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 *)
Join[{1}, Select[Range[2000], GCD@@FactorInteger[#][[All, 2]]>1&]] (* Harvey P. Dale, Apr 30 2018 *)
PROG
(Magma) [1] cat [n : n in [2..1000] | IsPower(n) ];
(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 */
(PARI) is(n)=ispower(n) || n==1 \\ Charles R Greathouse IV, Sep 16 2015
(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
(Sage)
def A001597_list(n) :
return [k for k in (1..n) if k.is_perfect_power()]
A001597_list(1764) # Peter Luschny, Feb 03 2012
(Haskell)
import Data.Map (singleton, findMin, deleteMin, insert)
a001597 n = a001597_list !! (n-1)
(a001597_list, a025478_list, a025479_list) =
unzip3 $ (1, 1, 2) : f 9 (3, 2) (singleton 4 (2, 2)) where
f zz (bz, ez) m
| xx < zz = (xx, bx, ex) :
f zz (bz, ez+1) (insert (bx*xx) (bx, ex+1) $ deleteMin m)
| xx > zz = (zz, bz, 2) :
f (zz+2*bz+1) (bz+1, 2) (insert (bz*zz) (bz, 3) m)
| otherwise = f (zz+2*bz+1) (bz+1, 2) m
where (xx, (bx, ex)) = findMin m -- bx ^ ex == xx
-- Reinhard Zumkeller, Mar 28 2014, Oct 04 2012, Apr 13 2012
(Python)
from sympy import perfect_power
def ok(n): return n==1 or perfect_power(n)
print([m for m in range(1, 1765) if ok(m)]) # Michael S. Branicky, Jan 04 2021
(Python)
import sympy
class A001597() :
def __init__(self) :
self.a = [1]
def at(self, n):
if n <= len(self.a):
return self.a[n-1]
else:
cand = self.at(n-1)+1
while sympy.perfect_power(cand) == False:
cand += 1
self.a.append(cand)
return cand
a001597 = A001597()
for n in range(1, 20):
print(a001597.at(n)) # R. J. Mathar, Mar 28 2023
(Python)
from sympy import mobius, integer_nthroot
def A001597(n):
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())))
kmin, kmax = 1, 2
while f(kmax) >= kmax:
kmax <<= 1
while True:
kmid = kmax+kmin>>1
if f(kmid) < kmid:
kmax = kmid
else:
kmin = kmid
if kmax-kmin <= 1:
break
return kmax # Chai Wah Wu, Aug 13 2024
CROSSREFS
Complement of A007916.
Cf. A023055, A023057, A025478, A070428, A072102, A074981, A076404, A239728, A239870, A097054, A089579, A089580.
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.
First differences give A053289.
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Minor corrections from N. J. A. Sloane, Jun 27 2010
STATUS
approved