Questions on sums of squares/PARI

[Max Alekseyev]

Rustem Aidagulov has outlined the following proof of finiteness of A138555:

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) The above inequality implies 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 of A138555.

I did not really check all these arguments,
so it would be nice if somebody check them up along with all missing details.

Regards,
Max

On Mon, Mar 24, 2008 at 4:37 PM, Max Alekseyev <maxale at gmail.com> wrote:
> Just a brief comment.
>  There is an obvious property of A138554 (convexity) that follows
>  straight from the definition:
>
>  A138554(n) <= A138554(m) + A138554(n-m)
>
>  for any 0 <= m <= n.
>  Moreover, for some m this inequality turns into the equality. That
>  clearly happens for trivial cases of m=0 and m=n, but also for some
>  nontrivial m. In particular, if k_1, ..., k_s deliver the minimum
>  value for the sum k_1 + ... + k_s under the constraint k_1^2 + ... +
>  k_s^2 = n, then m = k_i^2 for each i=1..s turns the above inequality
>  into the equality.
>
>  Another, obvious property is that A138554(n^2) = n for all n.
>
>  Your observation on possible finiteness of A138555 can be reformulated
>  as the finiteness of the number of solutions (w.r.t. to n) to the
>  following strict inequality:
>
>  A138554(n) < floor(sqrt(n)) + A138554( n - floor(sqrt(n))^2 )
>
>  Moreover, A138555 is nothing more than a list of solutions to this inequality.
>  If the number of solutions is indeed finite then the following
>  equality holds for all large enough n:
>
>  A138554(n) = floor(sqrt(n)) + A138554( n - floor(sqrt(n))^2 )
>
>  Regards,
>  Max
>
>
>
>  On Mon, Mar 24, 2008 at 2:41 PM,  <franktaw at netscape.net> wrote:
>  > I have just submitted the following two sequences:
>  >
>  >  %I A138554
>  >  %S A138554
>  >  0,1,2,3,2,3,4,5,4,3,4,5,6,5,6,7,4,5,6,7,6,7,8,9,8,5,6,7,8,7,8,9,8,9,8,9,6
>  >  ,7,8,9,8,
>  >  9,10,11,10,9,10,11,12,7,8,9,10,9,10,11,12,11,10,11,12,11,12,13,8,9,10,11,
>  >  10,11,12,
>  >  13,12,11,12,13,14,13,14,15,12,9,10,11,12,11,12,13,14,13,12,13,14,15,14,15
>  >  ,16,13,
>  >  14,15,10,11,12,13,12,13,14,15,14,13,14,15,16,15,16,17,14,15,16,17,16
>  >  %N A138554 Minimum value of sum k_i when sum k_i^2 = n.
>  >  %e A138554 32 = 4^2 + 4^2, and 4+4 = 8.  Using 5, the best we can do is
>  >  32 = 5^2
>  >  + 2^2 + 1^2 + 1^2 + 1^2, and 5+2+1+1+1 = 10, so a(32) = 8.
>  >  %o A138554 (PARI) sslist(n) = {local(r,i,v,t);
>  >  r=vector(n+1,k,0);
>  >  for(k=1,n,v=k;i=1;while(i^2<=k,t=r[k-i^2+1]+i;if(t<v,v=t);i++);r[k+1]=v);
>  >
>  >  r}
>  >  %Y A138554 Cf A063772, A138555, A001156.
>  >  %O A138554 0
>  >  %K A138554 ,nonn,
>  >
>  >  %I A138555
>  >  %S A138555
>  >  32,61,136,193,218,219,320,464,673,776,777,884,1021,1145,1417,1440,1744,21
>  >  94,2195,
>  >  2285,2696,2697,2797,3361,3560,4321,4880,5156,5618,5619,5765,7048,8424,957
>  >  7,9770,
>  >  9771,11216,11217,12541,13856,15817,20129,21312,22480,24961
>  >  %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.
>  >  %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}
>  >  %O A138555 1
>  >  %K A138555 ,nonn,
>  >
>  >  Based on the PARI program shown, these are the only values of A138555
>  >  up to 200000.  I'm wondering if
>  >  this is correct, or some kind of bug in PARI.  Could someone program it
>  >  with some other tool to verify (and
>  >  perhaps extend) these results?
>  >
>  >  If this is correct, could it be that the sequence is finite?
>  >
>  >  Franklin T. Adams-Watters
>  >
>