|
|
A001597
|
|
Perfect powers: m^k where m > 0 and k >= 2.
(Formerly M3326 N1336)
|
|
568
|
|
|
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000, 1024, 1089, 1156, 1225, 1296, 1331, 1369, 1444, 1521, 1600, 1681, 1728, 1764
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
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
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(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.
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
|
H. W. Gould, Problem H-170, Fib. Quart., 8 (1970), p. 268, problem H-170.
|
|
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.
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:
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:
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) 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)
return [k for k in (1..n) if k.is_perfect_power()]
(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
(Python)
from sympy import perfect_power
def ok(n): return n==1 or perfect_power(n)
(Python)
import sympy
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
for n in range(1, 20):
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|