A332101 -id:A332101 - 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

A332097 Maximum of s^n - Sum_{0 < x < s} x^n.

Original entry on oeis.org

1, 1, 4, 28, 317, 4606, 84477, 1919575, 47891482, 1512466345, 48627032377, 1930020260416, 77986967769593, 3624337209819538, 178110510699972510, 9381158756438306167, 548676565488760277878, 31900481466759651567625, 2189463436999785648552851, 144075114432622269076465962

Offset: 0

M. F. Hasler, May 07 2020

nonn

For small values of s, we have Sum_{0 < x < s} x^n ~ (s-1)^n, but for s > n/log(2) + 1.5 (cf. A332101) the difference E(s) = s^n - Sum_{0 < x < s} x^n becomes negative. Just before, the difference has its maximum: We have E(s) < E(s+1) <=> 2*s^n < (s+1)^n <=> s < 1/(2^(1/n)-1), so E takes its maximum at s = A078607(n), the least integer larger than this limiting value. This appears to be almost always equal to A332101(n) - 2.

Alois P. Heinz, Table of n, a(n) for n = 0..367

Cf. A030052 (least k such that k^n = sum of distinct n-th powers).
Cf. A078607 (s for which E(s) = a(n) <=> least k such that 2*k^n > (k+1)^n).
Cf. A332065 (all k such that k^n is a sum of distinct n-th powers).
Cf. A332101 (least k such that k^n <= sum of all smaller n-th powers).

a:= proc(n) option remember; `if`(n=0, 1, (s->
      s^n-add(x^n, x=1..s-1))(ceil(1/(2^(1/n)-1))))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, May 09 2020

a[0] = 1; a[n_] := (s = Ceiling[1/(2^(1/n) - 1)])^n - Sum[k^n, {k, 1, s - 1}]; Array[a, 20, 0] (* Amiram Eldar, May 09 2020 *)

{apply( A332097(n,s=1\(sqrtn(2,n-!n)-1))=(s+1)^n-sum(k=1,s,k^n), [0..20])}

a(n) = s^n - Sum_{0 < x < s} x^n for s = ceiling(1/(2^(1/n)-1)) = A078607(n).

A332099 Square array T(n,k) = k^n - Sum_{0 < i < k} e(i)*(k-i)^n where e(i) = 1 if the partial sum up to this term would remain <= k^n, or 0 else; n, k >= 1; read by falling antidiagonals.

Original entry on oeis.org

1, 1, 1, 0, 3, 1, 0, 4, 7, 1, 0, 2, 18, 15, 1, 0, 0, 28, 64, 31, 1, 0, 1, 25, 158, 210, 63, 1, 0, 0, 0, 271, 748, 664, 127, 1, 0, 1, 1, 317, 1825, 3302, 2058, 255, 1, 0, 0, 8, 126, 3351, 10735, 14068, 6304, 511, 1, 0, 2, 0, 45, 4606, 26141, 59425, 58718, 19170, 1023, 1, 0, 0, 19, 47, 3760, 50478, 183111, 318271, 241948, 58024, 2047, 1

Offset: 1

M. F. Hasler, Apr 19 2020

To compute T(n,k), start from k^n, then subtract (progressively strictly) smaller n-th powers whenever possible.

Since we subtract the smaller n-th powers in a greedy way, T(n,k) may be nonzero even if k^n is a sum of smaller n-th powers: cf. rows of A332065 for these k.

			The square array starts
  n\k: 1   2    3     4      5      6     7     8     9    10    11    12    13
  --+----------------------------------------------------------------------------
  1 |  1   1    0     0      0      0     0     0     0     0     0     0     0
  2 |  1   3    4     2      0      1     0     1     0     2     0     2     0
  3 |  1   7   18    28     25      0     1     8     0    19    15    18     0
  4 |  1  15   64   158    271    317    126   45    47    59   191    61    285
  5 |  1  31  210   748   1825   3351   4606  3760  398   131   702     0   1229
  6 |  1  63  664  3302  10735  26141  50478 77324 84477 21595 55300 29603  2093
  (...)
Columns 1, 2, 3: A000012, A000225, |A083321|, cf. FORMULA.
We have T(2,10) = 10^2 - 9^2 - 4^2 - 1 = 2, because we first have to subtract 9^2 = 81, even though 10 is in row 2 of A332065 since 10^2 - 8^2 - 6^2 = 0.

Cf. A030052 (least k such that k^n = sum of distinct n-th powers).
Cf. A332065 (all k such that k^n is a sum of distinct n-th powers).
Cf. A332101 (least k such that k^n <= sum of all smaller n-th powers).

A332099(n,k,t=k^n)={while(k&&t,t-=(k=min(sqrtnint(t,n),k-1))^n);t}

T(n,k) > 0  for  k < A030052(n), and  T(n,k) = 0  for  k = A030052(n).
T(n,k) = k^n - Sum_{0 < m < k} m^k  for  k < A332101(n).
T(n,1) = 1 = A000012(n);  T(n,2) = 2^n - 1 = A000225(n);
T(n,3) = 3^n - 2^n - 1 = |A083321(n)|.

A332102 Least m > 0 such that 2*m^n <= Sum_{k < m} k^n.

Original entry on oeis.org

3, 5, 8, 10, 13, 15, 18, 20, 23, 25, 28, 30, 33, 35, 38, 40, 42, 45, 47, 50, 52, 55, 57, 60, 62, 65, 67, 70, 72, 75, 77, 79, 82, 84, 87, 89, 92, 94, 97, 99, 102, 104, 107, 109, 112, 114, 116, 119, 121, 124, 126, 129, 131, 134, 136, 139, 141, 144, 146, 149, 151, 153, 156, 158, 161, 163, 166

Offset: 0

M. F. Hasler, Apr 18 2020

nonn

Obviously a(n) is a lower limit for any s solution to 2*s^n = Sum_{x in S} x^n, S subset of {1, ..., s-1}.

First differences are (2, 3, 2, 3, ...) except for a duplicated 2 in positions {16, 31, 46, 61, 76, 91; 104, 119, 134, 149, 164, 179, 194, 209, 224, 239, 254, 269; 282, 297, ...}: Here the first differences are always 15 except for a 13 after the 6th, 18th, ... term.

			For n=0, 2*m^0 = 2 > Sum_{k<m} k^0 = m - 1 <=> 3 > m, so a(0) = 3.
For n=1, 2*m^1 > Sum_{k<m} k^1 = m(m-1)/2 <=> 4 > m - 1, so a(1) = 5.

Cf. A332101 (same without factor 2 in definition).

Cf. A195168, A047218, A029919 (all have common initial terms but differ later and only remain lower resp. upper bounds).

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

apply( A332102(n, s)=for(m=1, oo, s<2*m^n||return(m); s+=m^n), [0..66])

a(n) >= A195168(n+1) with equality for n not in {13, 15; 26, 28, 30; 39, 41, 43, 45; 52, 54, ..., 60; 65, 67, ..., 75, 78, 80, ..., 90; 89, 91, ..., 103; 102, 104, ..., 114, 115, ...} \ {120, 122, 124, 126, 135, 137, 139, 150, 152, 165}.
a(n) <= A047218(n+2) with equality for n <= 17 and even n <= 34.
Conjecture: a(n) = round(n/log(3/2) + 3).

A384870 The largest k such that the set {1^n, 2^n, ..., k^n} has uniquely distinct subset sums.

Original entry on oeis.org

1, 2, 4, 5, 8, 11, 15, 19, 21, 28, 30, 37, 42, 45, 45

Offset: 0

Yuto Tsujino, Jun 11 2025

a(15) >= 49. - David A. Corneth, Jun 16 2025

			For n=2, the set {1^2, 2^2, 3^2, 4^2} = {1, 4, 9, 16} has uniquely distinct subset sums.
However, adding 5^2 = 25 introduces a duplicate sum: 9 + 16 = 25.
Thus, the largest k that satisfies the subset sum uniqueness condition is 4, meaning a(2)=4.

David A. Corneth, PARI program

Cf. A000124, A208531, A332101.

A := proc(n)
    local k, S, T, subsetsum;
    k := 1;
    while true do
        S := {seq(i^n, i=1..k)};
        T := combinat[powerset](S);
        subsetsum := map(x -> add(x), T);
        if numelems(subsetsum) = numelems(T) then
            k := k + 1;
        else
            return k - 1;
        end if;
    end do;
end proc;

A[n_] := Module[{k = 1, S, subsetSums},
  While[True,
    S = Table[i^n, {i, 1, k}];
    subsetSums = Total /@ Subsets[S];
    If[Length[subsetSums] == Length[DeleteDuplicates[subsetSums]], k++, Return[k - 1]];
  ]
]

isok(k,n) = my(list=List()); forsubset(k, s, listput(list, sum(i=1, #s, s[i]^n));); if (#Set(list) != #list, return(0)); 1;
a(n) = for (k=1, oo, if (!isok(k,n), return(k-1));); \\ Michel Marcus, Jun 14 2025

PARI
```
\\ See Corneth link
```

def a(n):
    k = 1
    while True:
        powers = [(i + 1) ** n for i in range(k)]
        subset_sums = set()
        all_unique = True
        for mask in range(1 << k):
            total = sum(powers[i] for i in range(k) if mask & (1 << i))
            if total in subset_sums:
                all_unique = False
                break
            subset_sums.add(total)
        if not all_unique:
            return k - 1
        k += 1
print([a(n) for n in range(9)])

from itertools import chain, combinations, count
def powerset(s):
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def a(n):
    s, sums = {1}, {1}
    for k in count(2):
        t = k**n
        newsums = set(sum(ss)+t for ss in powerset(s))
        if newsums & sums:
            return k-1
        s, sums = s|{t}, s|newsums
print([a(n) for n in range(9)]) # Michael S. Branicky, Jun 14 2025

1/(2^(1/n)-1) + 1 <= a(n) <= e^(-LambertW(-1, -log(2)/(n+1))). - Yifan Xie, Jun 16 2025

a(9)-a(10) from Michael S. Branicky, Jun 13 2025
a(11) from Jinyuan Wang, Jun 14 2025
a(12)-a(14) from David A. Corneth, Jun 16 2025

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

A332097 Maximum of s^n - Sum_{0 < x < s} x^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A332099 Square array T(n,k) = k^n - Sum_{0 < i < k} e(i)*(k-i)^n where e(i) = 1 if the partial sum up to this term would remain <= k^n, or 0 else; n, k >= 1; read by falling antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A332102 Least m > 0 such that 2*m^n <= Sum_{k < m} k^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A384870 The largest k such that the set {1^n, 2^n, ..., k^n} has uniquely distinct subset sums.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions