A332097 -id:A332097 - cp's OEIS frontend

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

Richard C. Schroeppel

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

			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.

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

Cf. A078607, A332065, A332097, A332101.

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

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

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

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

A078607 Least positive integer x such that 2*x^n > (x+1)^n.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 40, 42, 43, 45, 46, 48, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 63, 65, 66, 68, 69, 71, 72, 74, 75, 76, 78, 79, 81, 82, 84, 85, 87, 88, 89, 91, 92, 94, 95, 97, 98, 100, 101, 102

Offset: 0

Jon Perry, Dec 09 2002

nonn

Also, integer for which E(s) = s^n - Sum_{0 < k < s} k^n is maximal. It appears that a(n) + 2 is the least integer for which E(s) < 0. - M. F. Hasler, May 08 2020

			a(2) = 3 as 2^2 = 4, 3^2 = 9 and 4^2 = 16.
For n = 777451915729368, a(n) = 1121626023352384 = ceiling(n log 2), where n*log(2) = 1121626023352383.5 - 2.13*10^-17 and 2*floor(n log 2)^n / floor(1 + n log 2)^n = 1 - 3.2*10^-32. - _M. F. Hasler_, Nov 02 2013
a(2) is given by floor(1/(1-1/sqrt(2))). [From former A230748.]

Vincenzo Librandi, Table of n, a(n) for n = 0..20000

Cf. A224996 (the largest integer x that satisfies 2*x^n <= (x+1)^n).
Cf. A050499, A050500.
Cf. A078608, A078609. Equals A110882(n)-1 for n > 0.
Cf. A332097 (maximum of E(s), cf comments), also related to this:  A332101 (least k such that k^n <= sum of all smaller n-th powers), A030052 (least k such that k^n = sum of distinct n-th powers), A332065 (all k such that k^n is a sum of distinct n-th powers).

Table[SelectFirst[Range@ 120, 2 #^n > (# + 1)^n &], {n, 0, 71}] (* Michael De Vlieger, May 01 2016, Version 10 *)

for (n=2,50, x=2; while (2*x^n<=((x+1)^n),x++); print1(x","))

a(n)=1\(1-1/2^(1/n)) \\ Charles R Greathouse IV, Oct 31 2013

apply( A078607(n)=ceil(1/if(n>1,sqrtn(2,n)-1,!n+n/2)), [0..80]) \\ M. F. Hasler, May 08 2020

a(n) = ceiling(1/(2^(1/n)-1)) for n > 1. (For n = 1 resp. 0 this gives the integer 1 resp. infinity as argument of ceiling.) [Edited by M. F. Hasler, May 08 2020]
For most n, a(n) is the nearest integer to n/log(2), but there are exceptions, including n=777451915729368.
Following formulae merged in from former A230748, M. F. Hasler, May 14 2020:
a(n) = floor(1/(1-1/2^(1/n))).
a(n) = n/log(2) + O(1). - Charles R Greathouse IV, Oct 31 2013
a(n) = floor(1/(1-x)) with x^n = 1/2: f(n) = 1/(2^(1/n)-1) is never an integer for n > 1, whence floor(f(n)+1) = ceiling(f(n)) = a(n). - M. F. Hasler, Nov 02 2013, and Gabriel Conant, May 01 2016

Edited by Dean Hickerson, Dec 17 2002

Initial terms a(0) = 1 and a(1) = 2 added by M. F. Hasler, Nov 02 2013

A332101 Least m such that m^n <= Sum_{k

Original entry on oeis.org

2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, 25, 27, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 42, 44, 45, 47, 48, 50, 51, 52, 54, 55, 57, 58, 60, 61, 63, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 78, 80, 81, 83, 84, 86, 87, 89, 90, 91, 93, 94, 96, 97

Offset: 0

M. F. Hasler, Apr 14 2020

nonn

In a list (1^n, 2^n, 3^n, ...) (rows of table A051128 or A051129), a(n) is the index of the first term less than or equal to the sum of all earlier terms, cf. example.

Obviously a lower bound for any s solution to s^n = Sum_{x in S} x^n, S subset of {1, ..., s-1}, cf. A030052.

			For n = 0, m^0 > Sum_{0 < k < m} k^0 = 0 for m = 0, 1 (empty sums), but 2^0 = Sum_{0 < k < 2} k^0 = 1, so a(0) = 2.
For n = 1, 1^1 > Sum_{0 < k < 1} k^1 = 0 (empty sum) and 2^1 > Sum_{0 < k < 2} k^1 = 1, but 3^1 <= Sum_{0 < k < 3} k^1 = 1 + 2, so a(1) = 3.
To find a(n) one can add up terms in row n of the table k^n until the sum equals or exceeds the next term, whose column number k is then a(n):
  n |k: 1  2   3   4    5    6          Comment
  --+---------------------------------------------------------------
  1 |  1   2   3                  1 < 2 but 1 + 2 >= 3, so a(1) = 3.
  2 |  1   4   9  16   25         1 + 4 + 9 + 16 > 25, and a(2) = 5.
  3 |  1   8  27  64  125  216    1 + 8 + 27 + 64 + 125 > 216: a(3) = 6.

Michael De Vlieger, Table of n, a(n) for n = 0..1000
Brennan Benfield and Oliver Lippard, Integers that are not the sum of positive powers, arXiv:2404.08193 [math.NT], 2024.

Cf. A051128, A051129.

Cf. A078607, A332097 (maximum of E(s), cf comments), A030052 (least k such that k^n = sum of distinct n-th powers), A332065 (all k such that k^n is a sum of distinct n-th powers).

Table[Block[{m = 1, s = 0}, While[m^n > s, s = s + m^n; m++]; m], {n, 0, 66}] (* Michael De Vlieger, Apr 30 2020 *)

PARI
```
apply( A332101(n,s)=for(m=1,oo, s
				
```

a(n) = round(n / log(2)) + 2. (Conjectured; verified up to 10^4, in particular for 3525/log(2) = 5085.500019... and 7844/log(2) ~ 11316.49990...)

a(n) = A078607(n) + 2 for almost all n > 1. (n = 777451915729368 might be an exception to this equality or the above one.) - M. F. Hasler, May 08 2020

A332066 Number of positive integers whose n-th power is not the sum of distinct smaller positive n-th powers.

Original entry on oeis.org

2, 6, 9, 32, 24, 30, 41, 83, 49, 62, 71, 83

Offset: 1

M. F. Hasler, Jul 19 2020

See A332065 for the numbers whose n-th power is the sum of distinct smaller positive n-th powers. This sequence counts the positive integers not in a given row n of that table, whence the formula.

			For n = 1, only s = 1 and s = 2 are not the sum of distinct smaller positive integers (to the power n = 1), for all s >= 3 on we have s^1 = 1^1 + (s-1)^1 with 1 and s-1 distinct positive integers. Thus a(1) = #{1, 2} = 2.
For n = 2, S2 = {1, 2, 3, 4, 6, 8} is the set of all s > 0 whose square is not the sum of distinct smaller squares, while 5^2 = 4^2 + 3^2, 7^2 = 6^2 + 3^2 + 2^2, and all s^2 >= 9^2 are also the sum of distinct smaller squares. Thus a(2) = #S2 = 6.

Cf. A332065, A030052, A332096, A332097, A332098, A332066.

a(n) = lim_{k -> oo} A332065(n,k) - k.

a(n) <= A332098(n) with equality iff A030052(n) = A332098(n) + 1 <=> A030052(n) > A332098(n), which happens for n = 1, 8, 10, ... The difference A332098(n) - a(n) is the number of "solutions" s (listed in rows of A332065) strictly less than the largest "non-solution" A332098(n).

A332096 Irregular table where T(n,m) = min_{A subset {1..m-1}} |m^n - Sum_{x in A} x^n|, for 1 <= m <= A332098(n) = largest m for which this is nonzero.

Original entry on oeis.org

1, 1, 1, 3, 4, 2, 0, 1, 0, 1, 1, 7, 18, 28, 25, 0, 1, 8, 0, 7, 1, 1, 15, 64, 158, 271, 317, 126, 45, 17, 59, 14, 2, 15, 3, 0, 2, 1, 2, 1, 2, 2, 2, 1, 2, 0, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 31, 210, 748, 1825, 3351, 4606, 3760, 398, 131, 299, 0, 318, 0, 8

Offset: 1

M. F. Hasler, Jul 20 2020

nonn

It is known (Sprague 1948, cf. A001661) that for any n, only a finite number of positive integers are not the sum of distinct positive n-th powers. Therefore each row is finite, their lengths are given by A332098.
The number of nonzero terms in row n is A332066(n).
The column of the first zero (exact solution m^n = Sum_{x in A} x^n) in each row is given by A030052, unless A030052(n) = A332066(n) + 1 = A332098(n) + 1.

			The table reads:
  n\ m=1   2    3    4     5     6     7     8    9   10   11  12   13
----+--------------------------------------------------------------------------
  1 |  1   1                                                  (A332098(1) = 2.)
  2 |  1   3    4    2     0     1     0     1                (A332098(2) = 8.)
  3 |  1   7   18   28    25     0     1     8    0    7    1
  4 |  1  15   64  158   271   317   126    45   17   59   14   2   15  3  0 ...
  5 |  1  31  210  748  1825  3351  4606  3760  398  131  299   0  318  0  8 ...
The first column is all ones (A000012), since {1..m-1} = {} for m = 1.
The second column is 2^n - 1 = A000225 \ {0}, since {1..m-1} = {1} for m = 2.
The third column is 3^n - 2^n - 1 = |A083321(n)| for n > 1.

R. Sprague, Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51 (1948) 466-468.

Cf. A001661, A332098, A332066, A030052, A332097, A078607.

Cf. A000012, A000225, A083321.

A332096(n,m,r=0)={if(r, (m<2||r<2^(n-1)) && return(r-1); my(E, t=1); while(m^n>=r, E=m--); E=abs(r-(m+!!E)^n); for(a=2,m, if(r=m && return(min(E,r-t)); while(m>=t && E, E=min(self()(n,m-1,r-m^n),E); E && E=min(self()(n,m-=1,r),E)); E, m < n/log(2)+1.5, m^n-sum(x=1,m-1,x^n), self()(n,m-1,m^n))}

For all n and m, T(n,m) <= A332097(n) = T(n,m*) with m* = A078607(n).

For m <= m* + 1, T(n,m) = m^n - Sum_{0 < x < m} x^n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A078607 Least positive integer x such that 2*x^n > (x+1)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A332101 Least m such that m^n <= Sum_{k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A332066 Number of positive integers whose n-th power is not the sum of distinct smaller positive n-th powers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A332096 Irregular table where T(n,m) = min_{A subset {1..m-1}} |m^n - Sum_{x in A} x^n|, for 1 <= m <= A332098(n) = largest m for which this is nonzero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula