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

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

Offset: 1

Author

N. J. A. Sloane, Jul 15 2011

Keywords

• nonn

Comments

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

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

Links

• Lars Blomberg, Table of n, a(n) for n = 1..10000
• H. E. Salzer and N. Levine, Proof that every integer <= 452,479,659 is a sum of five numbers of the form Q_x = (x^3+5x)/6, x>= 0, Math. Comp., (1968), 191-192.
• N. J. A. Sloane, Transforms
• G. L. Watson, Sums of eight values of a cubic polynomial, J. London Math. Soc., 27 (1952), 217-224.

Crossrefs

Cf. A004006. A002828, A104246, A193105.

Programs

Maple

# LAGRANGE transform of a sequence {a(n)}
# Suggested by Lagrange's theorem that at most 4 squares are needed to sum to n.
# Returns b(n) = minimal number of terms of {a} needed to sum to n for 1 <= n <= M.
# C = maximal number of terms of {a} to try to build n
# M = upper limit on n
# 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
LAGRANGE:=proc(a,C,M)
local t1,ip,i,j,a1,a2,b,c,N1,N2,Nc;
if whattype(a) <> list then RETURN([]); fi:
# sort a, remove duplicates, include 0
t1:=sort(a);
a1:=sort(convert(convert(a,set),list));
if not member(0,a1) then a1:=[0,op(a1)]; fi;
N1:=nops(a1);
b:=Array(1..M+1,-1);
for i from 1 to N1 while a1[i]<=M do b[a1[i]+1]:=1; od;
a2:=a1; N2:=N1;
for ip from 2 to C do
c:={}:
   for i from 1 to N1 while a1[i] <= M do
      for j from 1 to N2 while a1[i]+a2[j] <= M do
c:={op(c),a1[i]+a2[j]};
                                                od;
                                       od;
c:=sort(convert(c,list));
Nc:=nops(c);
   for i from 1 to Nc do
      if b[c[i]+1] = -1 then b[c[i]+1]:= ip; fi;
                      od;
a2:=c; N2:=Nc;
                   od;
[seq(b[i],i=2..M+1)];
end;
Q:=[seq((m^3+5*m)/6,m=0..20)];
LAGRANGE(Q,8,120);