A138555 Indices where A138554 requires only squares < floor(sqrt(n))^2.

32, 61, 136, 193, 218, 219, 320, 464, 673, 776, 777, 884, 1021, 1145, 1417, 1440, 1744, 2194, 2195, 2285, 2696, 2697, 2797, 3361, 3560, 4321, 4880, 5156, 5618, 5619, 5765, 7048, 8424, 9577, 9770, 9771, 11216, 11217, 12541, 13856, 15817, 20129, 21312

Offset

1,1

Comments

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 Alekseyev, Mar 26 2008

(1) Reformulate the definition of A138554 as follows: (*) A138554(n) = min (k + A138554(n-k^2)), where k goes over 1,2,...,[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 proves the finiteness.

Links

Table of n, a(n) for n=1..43.

Prog

(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}

Crossrefs

Sequence in context: A008434 A130447 A116284 * A050708 A132300 A206371

Adjacent sequences: A138552 A138553 A138554 * A138556 A138557 A138558

Keyword

nonn

Author

Franklin T. Adams-Watters, Mar 24 2008

Status

approved