login
A030052
Smallest number whose n-th power is a sum of distinct smaller positive n-th powers.
12
3, 5, 6, 15, 12, 25, 40, 84, 47, 63, 68, 81, 102, 95, 104, 162, 123
OFFSET
1,1
COMMENTS
Sprague has shown that for any n, all sufficiently large integers are the sum of distinct n-th powers. Sequence A001661 lists the largest number not of this form, so we know that a(n) is less than or equal to the next larger n-th power. - M. F. Hasler, May 25 2020
a(18) <= 200, a(19) <= 234, a(20) <= 242; for more upper bounds see the Al Zimmermann's Programming Contests link: The "Final Report" gives exact solutions for n = 16 through 30; those for n = 16 and 17 have been confirmed to be minimal by Jeremy Sawicki. - M. F. Hasler, Jul 20 2020
LINKS
Eric Weisstein's World of Mathematics, Diophantine Equation.
Al Zimmermann, Sum Of Powers: Final Report, Al Zimmermann's Programming Contests, April-July 2020
FORMULA
a(n) <= A001661(n)^(1/n) + 1. - M. F. Hasler, May 25 2020
a(n) >= A332101(n) = A078607(n)+2 (conjectured). - M. F. Hasler, May 25 2020
EXAMPLE
3^1 = 2^1 + 1^1, and there is no smaller solution given that the r.h.s. is the smallest possible sum of distinct positive powers.
For n = 2, one sees immediately that 3 is not a solution (3^2 > 2^2 + 1^2) and one can check that 4^2 isn't equal to Sum_{x in A} x^2 for any subset A of {1, 2, 3}. Therefore, the well known hypotenuse number 5 (cf. A009003) with 5^2 = 4^2 + 3^2 provides the smallest possible solution.
a(17) = 123 since 123^17 = Sum {3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 30, 33, 34, 35, 38, 40, 41, 43, 51, 52, 54, 55, 58, 59, 60, 63, 66, 69, 70, 71, 72, 73, 75, 76, 81, 86, 87, 88, 89, 90, 92, 95, 98, 106, 107, 108, 120}^17, with obvious notation. [Solution found by Jeremy Sawicki on July 3, 2020, see Al Zimmermann's Programming Contests link.] - M. F. Hasler, Jul 18 2020
For more examples, see the link.
PROG
(PARI) A030052(n, m=n\/log(2)+1, s=0)={if(!s, until(A030052(n, m, (m+=1)^n), ), s < 2^n || s > (m+n+1)*m^n\(n+1), m=s<2, m=min(sqrtnint(s, n), m); s==m^n || until( A030052(n, m-1, s-m^n) || (s>=(m+n)*(m-=1)^n\(n+1) && !m=0), )); m} \\ Does exhaustive search to find the least solution m. Use optional 2nd arg to specify a starting value for m. Calls itself with nonzero 3rd (optional) argument: in this case, returns nonzero iff s is the sum of powers <= m^n. - For illustration only: takes very long already for n = 8 and n >= 10. - M. F. Hasler, May 25 2020
CROSSREFS
Other sequences defined by sums of distinct n-th powers: A001661, A364637.
Sequence in context: A290964 A298563 A180694 * A227963 A099678 A287687
KEYWORD
nonn,nice,more,hard
AUTHOR
Richard C. Schroeppel
EXTENSIONS
a(8)-a(10) found by David W. Wilson
a(11) from Al Zimmermann, Apr 07 2004
a(12) from Al Zimmermann, Apr 13 2004
a(13) from Manol Iliev, Jan 04 2010
a(14) and a(15) from Manol Iliev, Apr 28 2011
a(16) and a(17) due to Jeremy Sawicki, added by M. F. Hasler, Jul 20 2020
STATUS
approved