A193101 - OEIS

%I #24 Oct 12 2017 10:20:13

%S 1,2,1,2,3,2,1,2,3,2,3,4,3,1,2,3,2,3,4,3,2,3,4,3,1,2,3,2,3,4,3,2,3,4,

%T 3,4,5,4,2,3,1,2,3,2,3,3,3,2,3,2,3,4,3,4,2,3,3,3,4,4,4,3,1,2,3,2,3,4,

%U 3,2,3,4,3,4,3,4,2,3,4,3,4,2,3,3,3,4,4,2,3,4,3,1,2,3,2,3,4,3,2,3,4,3,4,2,3,2,3,4,3,4,3,4,3,4,5,4,2,3,4,3

%N Minimal number of numbers of the form (m^3+5m)/6 (see A004006) needed to sum to n.

%C Watson showed that a(n) <= 8 for all n.

%C It is conjectured that a(n) <= 5 for all n.

%H Lars Blomberg, <a href="/A193101/b193101.txt">Table of n, a(n) for n = 1..10000</a>

%H H. E. Salzer and N. Levine, <a href="https://doi.org/10.1090/S0025-5718-1968-0224578-6">Proof that every integer <= 452,479,659 is a sum of five numbers of the form Q_x = (x^3+5x)/6, x>= 0</a>, Math. Comp., (1968), 191-192.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H G. L. Watson, <a href="https://doi.org/10.1112/jlms/s1-27.2.217">Sums of eight values of a cubic polynomial</a>, J. London Math. Soc., 27 (1952), 217-224.

%p # LAGRANGE transform of a sequence {a(n)}

%p # Suggested by Lagrange's theorem that at most 4 squares are needed to sum to n.

%p # Returns b(n) = minimal number of terms of {a} needed to sum to n for 1 <= n <= M.

%p # C = maximal number of terms of {a} to try to build n

%p # M = upper limit on n

%p # Internally, the initial terms of both a and b are taken to be 0, but since this is a number-theoretic function, the output starts at n=1

%p LAGRANGE:=proc(a,C,M)

%p local t1,ip,i,j,a1,a2,b,c,N1,N2,Nc;

%p if whattype(a) <> list then RETURN([]); fi:

%p # sort a, remove duplicates, include 0

%p t1:=sort(a);

%p a1:=sort(convert(convert(a,set),list));

%p if not member(0,a1) then a1:=[0,op(a1)]; fi;

%p N1:=nops(a1);

%p b:=Array(1..M+1,-1);

%p for i from 1 to N1 while a1[i]<=M do b[a1[i]+1]:=1; od;

%p a2:=a1; N2:=N1;

%p for ip from 2 to C do

%p c:={}:

%p    for i from 1 to N1 while a1[i] <= M do

%p       for j from 1 to N2 while a1[i]+a2[j] <= M do

%p c:={op(c),a1[i]+a2[j]};

%p                                                 od;

%p                                        od;

%p c:=sort(convert(c,list));

%p Nc:=nops(c);

%p    for i from 1 to Nc do

%p       if b[c[i]+1] = -1 then b[c[i]+1]:= ip; fi;

%p                       od;

%p a2:=c; N2:=Nc;

%p                    od;

%p [seq(b[i],i=2..M+1)];

%p end;

%p Q:=[seq((m^3+5*m)/6,m=0..20)];

%p LAGRANGE(Q,8,120);

%Y Cf. A004006. A002828, A104246, A193105.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Jul 15 2011