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.

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,4

Comments

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.

Links

Table of n, a(n) for n=1..80.

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

Formula

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.

Example

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.

Prog

(PARI) 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<t+=a^n, t=a-1; break)); t>=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))}

Crossrefs

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

Cf. A000012, A000225, A083321.

Sequence in context: A123127 A167876 A241833 * A077451 A352770 A019829

Adjacent sequences: A332093 A332094 A332095 * A332097 A332098 A332099

Keyword

nonn

Author

M. F. Hasler, Jul 20 2020

Status

approved