Questions on sums of squares/PARI

[Max Alekseyev]

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
>