1,1

Express n = sum k_i^2 so as to minimize sum k_i. There may be more than one such sum; for example 12 = 3^2 + 1^2 + 1^2 + 1^2 = 2^2 + 2^2 + 2^2. If every such minimal sum uses squares only of numbers < floor(sqrt(n)), n is included in this sequence.

Sketch of proof that this sequence is finite, from Rustem Aidagulov, communicated by Max Alekseyov, Mar 26 2008

1) Reformulate the definition of A138554 as follows: (*) A138554(n) = min (k + A138554(n-k^2)), where k goes over 1..[sqrt(n)].

2) Prove by induction on n that [sqrt(n)] <= A138554(n) < [sqrt(n)] + 2*n^(1/4) + 1.6

3) These inequalities imply that if k_1^2 + ... + k_s^2 = n and A138554(n) = k_1 + ... + k_s where k_1 <= ... <= k_s, then k_s = [sqrt(n)] or [sqrt(n)] - 1.

4) By direct comparison of computations of (*) for k = [sqrt(n)] and k = [sqrt(n)] - 1, using the bounds 2), derive that the latter value can be smaller than the former one only for finitely many n. This prove the finiteness.

(PARI) dsslist(n) = {local(r, i, j, v, t, d); r=vector(n+1, k, 0); d=[]; for(k=1, n, v=k; i=1; j=0; while(i^2<=k, t=r[k-i^2+1]+i; if(t<=v, v=t; j=i); i++); r[k+1]=v; if(j<i-1, d=concat(d, [k]))); d}

Sequence in context: A008434 A130447 A116284 this_sequence A050708 A132300 A116318

Adjacent sequences: A138552 A138553 A138554 this_sequence A138556 A138557 A138558

nonn

Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Mar 24 2008