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

Author

Franklin T. Adams-Watters, Mar 24 2008

Keywords

• nonn

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.

Programs

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