|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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.
|
|
|
KEYWORD
|
nonn,nice,more,hard
|
|
|
AUTHOR
|
Richard C. Schroeppel
|
|
|
EXTENSIONS
|
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
|
| |
|
|
