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
R. Sprague, Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51 (1948) 466-468.
Various authors, How each power is decomposed
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
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
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)-a(15) from Manol Iliev, Apr 28 2011
a(16)-a(17) due to Jeremy Sawicki, added by M. F. Hasler, Jul 20 2020
STATUS
approved