cp's OEIS Frontend

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

%I A030052 #70 Feb 16 2025 08:32:35
%S A030052 3,5,6,15,12,25,40,84,47,63,68,81,102,95,104,162,123
%N A030052 Smallest number whose n-th power is a sum of distinct smaller positive n-th powers.
%C A030052 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
%C A030052 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
%H A030052 R. Sprague, <a href="https://doi.org/10.1007/BF01185779">Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen</a>, Math. Z. 51 (1948) 466-468.
%H A030052 Various authors, <a href="/A030052/a030052.txt">How each power is decomposed</a>
%H A030052 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DiophantineEquation.html">Diophantine Equation.</a>
%H A030052 Al Zimmermann, <a href="http://azspcs.com/Contest/SumsOfPowers/FinalReport">Sum Of Powers: Final Report</a>, Al Zimmermann's Programming Contests, April-July 2020
%F A030052 a(n) <= A001661(n)^(1/n) + 1. - _M. F. Hasler_, May 25 2020
%F A030052 a(n) >= A332101(n) = A078607(n)+2 (conjectured). - _M. F. Hasler_, May 25 2020
%e A030052 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.
%e A030052 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.
%e A030052 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
%e A030052 For more examples, see the link.
%o A030052 (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
%Y A030052 Cf. A078607, A332065, A332097, A332101.
%Y A030052 Other sequences defined by sums of distinct n-th powers: A001661, A364637.
%K A030052 nonn,nice,more,hard
%O A030052 1,1
%A A030052 Richard C. Schroeppel
%E A030052 a(8)-a(10) found by _David W. Wilson_
%E A030052 a(11) from _Al Zimmermann_, Apr 07 2004
%E A030052 a(12) from _Al Zimmermann_, Apr 13 2004
%E A030052 a(13) from Manol Iliev, Jan 04 2010
%E A030052 a(14) and a(15) from Manol Iliev, Apr 28 2011
%E A030052 a(16) and a(17) due to Jeremy Sawicki, added by _M. F. Hasler_, Jul 20 2020