cp's OEIS Frontend

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

%I A138555 #4 Jul 25 2016 21:35:50
%S A138555 32,61,136,193,218,219,320,464,673,776,777,884,1021,1145,1417,1440,
%T A138555 1744,2194,2195,2285,2696,2697,2797,3361,3560,4321,4880,5156,5618,
%U A138555 5619,5765,7048,8424,9577,9770,9771,11216,11217,12541,13856,15817,20129,21312
%N A138555 Indices where A138554 requires only squares < floor(sqrt(n))^2.
%C A138555 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.
%C A138555 Sketch of proof that this sequence is finite, from Rustem Aidagulov, communicated by _Max Alekseyev_, Mar 26 2008
%C A138555 (1) Reformulate the definition of A138554 as follows: (*) A138554(n) = min (k + A138554(n-k^2)), where k goes over 1,2,...,[sqrt(n)].
%C A138555 (2) Prove by induction on n that [sqrt(n)] <= A138554(n) < [sqrt(n)] + 2*n^(1/4) + 1.6
%C A138555 (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.
%C A138555 (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.
%o A138555 (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}
%K A138555 nonn
%O A138555 1,1
%A A138555 _Franklin T. Adams-Watters_, Mar 24 2008