A074981 -id:A074981 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane

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

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

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 of Perfect 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 Mihǎilescu, 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.

Complement of A007916.
Subsequence of A072103; A072777 is a subsequence.
Union of A075109 and A075090.
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.

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

[1] cat [n : n in [2..1000] | IsPower(n) ];

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

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 *)

{a(n) = local(m, c); if( n<2, n==1, c=1; m=1; while( cMichael Somos, Aug 05 2009 */

is(n)=ispower(n) || n==1 \\ Charles R Greathouse IV, Sep 16 2015

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

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

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

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

def A001597_list(n) :
    return [k for k in (1..n) if k.is_perfect_power()]
A001597_list(1764) # Peter Luschny, Feb 03 2012

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

Minor corrections from N. J. A. Sloane, Jun 27 2010

A023057 (Apparently) not the difference between adjacent perfect powers (A001597, integers of form a^b, a >= 1, b >= 2).

Original entry on oeis.org

6, 14, 22, 29, 31, 34, 42, 44, 46, 50, 52, 54, 58, 62, 64, 66, 70, 72, 78, 82, 84, 86, 88, 90, 91, 96, 98, 102, 105, 110, 111, 114, 117, 118, 120, 122, 124, 126, 130, 132, 134, 136, 140, 142, 153, 156, 158, 160, 162, 164, 165, 172, 176, 177, 178, 179, 181, 182, 188, 190

Offset: 1

David W. Wilson

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

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

Robert G. Wilson v, Table of n, a(n) for n = 1..4479
Alf van der Poorten, Remarks on the sequence of 'perfect' powers.

Cf. A001597 (perfect powers), A023055 (complement). See also A074980, A074981, A077286.

pp = Union[ Join[{1}, Flatten[ Table[n^i, {n, 2, Sqrt[10^12]}, {i, 2, Log[n, 10^12]}]]]]; l = Length[pp]; d = Sort[Take[pp, -l + 1] - Take[pp, l - 1]]; Complement[ Table[i, {i, 1, 200}], Take[ Union[d], 200]] (* Robert G. Wilson v *)

A057897 Numbers which can be written as m^k-k, with m, k > 1.

Original entry on oeis.org

2, 5, 7, 12, 14, 23, 24, 27, 34, 47, 58, 61, 62, 77, 79, 98, 119, 121, 122, 142, 167, 194, 213, 223, 238, 248, 252, 254, 287, 322, 340, 359, 398, 439, 482, 503, 509, 527, 574, 621, 623, 674, 723, 726, 727, 782, 839, 898, 959, 997, 1014, 1019, 1022, 1087, 1154

Offset: 1

Henry Bottomley, Sep 26 2000

nonn

It may be that positive integers can be written as m^k-k (with m and k > 1) in at most one way [checked up to 10000].

All numbers < 10^16 of this form have a unique representation. The uniqueness question leads to a Pillai-like exponential Diophantine equation a^x-b^y = x-y for x > y > 1 and b > a > 1, which appears to have no solutions. - T. D. Noe, Oct 06 2004

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Cf. A000325, A008865, A024024, A024037, A024050, A057895, A057898, A057899.

Cf. A099225 (numbers of the form m^k+k, with m and k > 1), A074981 (n such that there is no solution to Pillai's equation), A099226 (numbers that can be represented as both a^x+x and b^y-y, for some a, b, x, y > 1).

nLim=1000; lst={}; Do[k=2; While[n=m^k-k; n<=nLim, AppendTo[lst, n]; k++ ], {m, 2, Sqrt[nLim]}]; Union[lst] (* T. D. Noe, Oct 06 2004 *)

ok(n)={my(e=2); while(2^e <= n+e, if(ispower(n+e, e), return(1)); e++); 0} \\ Andrew Howroyd, Oct 20 2020

upto(lim)={my(p=logint(lim,2)); while(logint(lim+p+1,2)>p, p++); Vec(Set(concat(vector(p-1, e, e++; vector(sqrtnint(lim+e,e)-1, m, (m+1)^e-e)))))} \\ Andrew Howroyd, Oct 20 2020

A076438 Numbers k which appear to have a unique representation as the difference of two perfect powers; that is, there is only one solution to Pillai's equation a^x - b^y = k, with a > 0, b > 0, x > 1, y > 1.

Original entry on oeis.org

1, 2, 10, 29, 30, 38, 43, 46, 52, 59, 122, 126, 138, 142, 146, 150, 154, 166, 170, 173, 181, 190, 194, 214, 222, 234, 263, 270, 282, 283, 298, 317, 318, 332, 338, 342, 347, 349, 354, 361, 370, 379, 382, 383, 386, 406, 419, 428, 436, 461, 467, 479, 484, 486

Offset: 1

T. D. Noe, Oct 12 2002

This is the classic Diophantine equation of S. S. Pillai, who conjectured that there are only a finite number of solutions for each k. A generalization of Catalan's conjecture that a^x - b^y = 1 has only one solution. See A076427 for the number of solutions for each k. Interestingly, the unique solutions (k,a,x,b,y) fall into two groups: (A076439) those in which x and y are even numbers, so that k is the difference of squares, and (A076440) those requiring an odd power. This sequence was found by examining all perfect powers (A001597) less than 2^63-1. By examining a larger set of perfect powers, we may discover that some of these numbers do not have a unique representation.

R. K. Guy, Unsolved Problems in Number Theory, D9.
T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge University Press, 1986.

M. E. Bennett, On Some Exponential Equations Of S. S. Pillai, Canad. J. Math. 53 (2001), 897-922.
T. D. Noe, Unique solutions to Pillai's Equation for n <= 1000.
Eric Weisstein's World of Mathematics, Pillai's Conjecture.

Cf. A001597, A053289, A074981, A076427, A076438, A076439, A076440, A207079.

A099225 Numbers of the form m^k+k, with m and k > 1.

Original entry on oeis.org

6, 11, 18, 20, 27, 30, 37, 38, 51, 66, 67, 70, 83, 85, 102, 123, 128, 135, 146, 171, 198, 219, 227, 248, 258, 260, 264, 291, 326, 346, 363, 402, 443, 486, 515, 521, 531, 578, 627, 629, 678, 731, 732, 735, 786, 843, 902, 963, 1003, 1026, 1029, 1034, 1091, 1158

Offset: 1

T. D. Noe, Oct 06 2004

nonn

For n=11, there are two representations: 2^3+3 and 3^2+2. All other numbers < 10^16 of this form have a unique representation. The uniqueness question leads to a Pillai-like exponential Diophantine equation a^x-b^y = y-x for y > x > 1 and b > a > 1, which appears to have only one solution.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A057897 (numbers of the form m^k-k, with m and k > 1), A074981 (n such that there is no solution to Pillai's equation), A099226 (numbers that can be represented as both a^x+x and b^y-y, for some a, b, x, y > 1).

N:= 2000: # for terms <= N
S:= {}:
for k from 2 to floor(log[2](N)) do
  S:= S union {seq(m^k+k, m=2..floor((N-k)^(1/k)))}
od:
sort(convert(S,list)); # Robert Israel, Apr 28 2019

nLim=2000; lst={}; Do[k=2; While[n=m^k+k; n<=nLim, AppendTo[lst, n]; k++ ], {m, 2, Sqrt[nLim]}]; Union[lst]

A076427 Number of solutions to Pillai's equation a^x - b^y = n, with a>0, b>0, x>1, y>1.

Original entry on oeis.org

1, 1, 2, 3, 2, 0, 5, 3, 4, 1, 4, 2, 3, 0, 3, 3, 7, 3, 5, 2, 2, 2, 4, 5, 2, 3, 3, 7, 1, 1, 2, 4, 2, 0, 3, 2, 3, 1, 4, 4, 3, 0, 1, 3, 4, 1, 6, 4, 3, 0, 2, 1, 2, 2, 3, 4, 3, 0, 1, 4, 2, 0, 4, 4, 4, 0, 2, 5, 2, 0, 4, 4, 6, 2, 3, 3, 2, 0, 4, 4, 4, 0, 2, 2, 2, 0, 3, 3, 6, 0, 3, 4, 4, 2, 4, 5, 3, 2, 4, 10

Offset: 1

T. D. Noe, Oct 11 2002

This is the classic Diophantine equation of S. S. Pillai, who conjectured that there are only a finite number of solutions for each n. A generalization of Catalan's conjecture that a^x-b^y=1 has only one solution. For n <=100, a total of 274 solutions were found for perfect powers less than 10^12. No additional solutions were found for perfect powers < 10^18.

			a(4)=3 because there are 3 solutions: 4 = 2^3 - 2^2 = 6^2 - 2^5 = 5^3 - 11^2.

R. K. Guy, Unsolved Problems in Number Theory, D9.
T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge University Press, 1986.

T. D. Noe, Solutions to Pillai's Equation for n<=100
Dorin Andrica and Ovidiu Bagdasar, On k-partitions of multisets with equal sums, The Ramanujan J. (2021) Vol. 55, 421-435.
Dorin Andrica and George C. Ţurkaş, An elliptic Diophantine equation from the study of partitions, Stud. Univ. Babeş-Bolyai Math. (2019) Vol. 64, No. 3, 349-356.
M. A. Bennett, On some exponential equations of S. S. Pillai, Canad. J. Math. 53 (2001), 897-922.
Dana Mackenzie, 2184: An absurd (and adsurd) tale, Integers (2018) 18, Article #A33.
Roswitha Rissner and Daniel Windisch, Absolute irreducibility of the binomial polynomials, arXiv:2009.02322 [math.AC], 2020.
Eric Weisstein's World of Mathematics, Pillai's Conjecture

Cf. A189117, A001597, A074981.

cp's OEIS Frontend

A075788 If n can be written in the form r^i-s^j (see A074981), where r,s,i,j are integers with r>0, s>0, i>1, j>1 choose the representation with smallest r^i (in case of ties, minimize i and j); or if n is not of this form set r=s=i=j=0; sequence gives values of r.

Views

Author

Keywords

Comments

Examples

Extensions

A075791 If n can be written in the form r^i-s^j (see A074981), where r,s,i,j are integers with r>0, s>0, i>1, j>1 choose the representation with smallest r^i (in case of ties, minimize i and j); or if n is not of this form set r=s=i=j=0; sequence gives values of j.

Views

Author

Keywords

Comments

Examples

Extensions

A075790 If n can be written in the form r^i-s^j (see A074981), where r,s,i,j are integers with r>0, s>0, i>1, j>1 choose the representation with smallest r^i (in case of ties, minimize i and j); or if n is not of this form set r=s=i=j=0; sequence gives values of s.

Views

Author

Keywords

Comments

Examples

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Sage

Formula

Extensions

A023057 (Apparently) not the difference between adjacent perfect powers (A001597, integers of form a^b, a >= 1, b >= 2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A057897 Numbers which can be written as m^k-k, with m, k > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A076438 Numbers k which appear to have a unique representation as the difference of two perfect powers; that is, there is only one solution to Pillai's equation a^x - b^y = k, with a > 0, b > 0, x > 1, y > 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A099225 Numbers of the form m^k+k, with m and k > 1.

Views

Author

Keywords

Comments

Links

Crossrefs