|
%I #13 Aug 01 2020 11:40:32
%S 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,
%T 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,
%U 1,0,1,0,1,1,31,210,748,1825,3351,4606,3760,398,131,299,0,318,0,8
%N 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.
%C 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.
%C The number of nonzero terms in row n is A332066(n).
%C 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.
%H 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.
%F For all n and m, T(n,m) <= A332097(n) = T(n,m*) with m* = A078607(n).
%F For m <= m* + 1, T(n,m) = m^n - Sum_{0 < x < m} x^n.
%e The table reads:
%e n\ m=1 2 3 4 5 6 7 8 9 10 11 12 13
%e ----+--------------------------------------------------------------------------
%e 1 | 1 1 (A332098(1) = 2.)
%e 2 | 1 3 4 2 0 1 0 1 (A332098(2) = 8.)
%e 3 | 1 7 18 28 25 0 1 8 0 7 1
%e 4 | 1 15 64 158 271 317 126 45 17 59 14 2 15 3 0 ...
%e 5 | 1 31 210 748 1825 3351 4606 3760 398 131 299 0 318 0 8 ...
%e The first column is all ones (A000012), since {1..m-1} = {} for m = 1.
%e The second column is 2^n - 1 = A000225 \ {0}, since {1..m-1} = {1} for m = 2.
%e The third column is 3^n - 2^n - 1 = |A083321(n)| for n > 1.
%o (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))}
%Y Cf. A001661, A332098, A332066, A030052, A332097, A078607.
%Y Cf. A000012, A000225, A083321.
%K nonn
%O 1,4
%A _M. F. Hasler_, Jul 20 2020
|
