login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A138555 Indices where A138554 requires only squares < floor(sqrt(n))^2. 1
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 18:37 EDT 2020. Contains 336428 sequences. (Running on oeis4.)