A030052 Smallest number whose n-th power is a sum of distinct smaller positive n-th powers.

3, 5, 6, 15, 12, 25, 40, 84, 47, 63, 68, 81, 102, 95, 104, 162, 123

Offset: 1

Author

Richard C. Schroeppel

Keywords

• nonn
• nice
• more
• hard

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

Examples

			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.
		

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

Crossrefs

Cf. A078607, A332065, A332097, A332101.

Other sequences defined by sums of distinct n-th powers: A001661, A364637.

Programs

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

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

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