A248509 Length of longest sequence of distinct nonzero squares summing to n, or 0 if no such sequence exists.

1, 0, 0, 1, 2, 0, 0, 0, 1, 2, 0, 0, 2, 3, 0, 1, 2, 0, 0, 2, 3, 0, 0, 0, 2, 3, 0, 0, 3, 4, 0, 0, 0, 2, 3, 1, 2, 3, 4, 2, 3, 3, 0, 0, 3, 4, 0, 0, 3, 4, 4, 2, 3, 4, 5, 3, 4, 2, 3, 0, 3, 4, 4, 1, 4, 5, 0, 2, 3, 4, 4, 0, 2, 4, 5, 0, 3, 4, 5, 2, 4, 5, 3, 4

Offset: 1

Author

Robert Israel, Oct 07 2014

Keywords

• nonn

Comments

a(n) >= k for n > A129210(k).

a(n) > 0 iff A033461(n) > 0. - Reinhard Zumkeller, Oct 07 2014

Examples

			1 = 1^2 so a(1) = 1.
2 and 3 are not sums of distinct squares, so a(2) = 0 and a(3) = 0.
4 = 2^2 so a(4) = 1.
5 = 1^2 + 2^2 so a(5) = 2.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• P. T. Bateman, A. J. Hildebrand and G. B. Purdy, Sums of distinct squares, Acta Arithmetica 67 (1994), pp. 349-380.
• Eryk Pawilan, Math Overflow question

Crossrefs

Cf. A129210.

Cf. A033461.

Programs

Maple

N:= 100: # to get a(1) to a(N)
M:= floor(sqrt(N)):
A:= Array(0..N,0..M):
sj:= unapply(sum(k^2,k=1..x),x):
for j from 1 to M do
  for n from sj(j)+1 to N do A[n,j]:= -infinity od:
  for n from 1 to j^2-1 do A[n,j]:= A[n,j-1] od:
  for n from j^2 to min(sj(j),N) do A[n,j]:= max(A[n,j-1],1+A[n-j^2,j-1]) od:
od:
subs(-infinity=0,[seq(A[n,M],n=1..N)]); # Robert Israel, Oct 07 2014

Mathematica

Nt = 100 (* = number of terms *);
M = Floor[Sqrt[Nt]];
Clear[A]; A[, ] = 0;
s[j_] := Range[j].Range[j];
For[j = 1, j <= M, j++,
  For[n = s[j] + 1, n <= Nt, n++, A[n, j] = -Infinity];
  For[n = 1, n <= j^2 - 1, n++, A[n, j] = A[n, j - 1]];
  For[n = j^2, n <= Min[s[j], Nt], n++, A[n, j] = Max[A[n, j-1], 1+A[nj^2, j-1]]]
];
Table[A[n, M] /. DirectedInfinity[-1] -> 0, {n, 1, Nt}] (* Jean-François Alcover, Mar 04 2019, after Robert Israel *)