A138554 - OEIS

%I #20 Nov 05 2020 06:40:50

%S 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,

%T 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,

%U 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

%N Minimal value of sum k_i when sum (k_i)^2 = n.

%H Alois P. Heinz, <a href="/A138554/b138554.txt">Table of n, a(n) for n = 0..20163</a>

%H Phillip Tomas Heikoop, <a href="https://digitalcommons.wpi.edu/mqp-all/6822">Dimensions of Matrix Subalgebras</a>, Bachelor's Thesis, Worcester Polytechnic Institute (Massachusetts, 2019).

%e 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.

%p b:= proc(n, i) option remember; `if`(n=0 or i=1, n,

%p        min(seq(b(n-j*i^2, i-1)+j*i, j=0..n/i^2)))

%p     end:

%p a:= n-> b(n, isqrt(n)):

%p seq(a(n), n=0..100);  # _Alois P. Heinz_, Jun 30 2015

%t b[n_, i_] := b[n, i] = If[n == 0 || i == 1, n, Min[Table[b[n - j i^2, i - 1] + j i, {j, 0, n/i^2}]]];

%t a[n_] := b[n, Sqrt[n] // Floor];

%t a /@ Range[0, 100] (* _Jean-François Alcover_, Nov 05 2020, after _Alois P. Heinz_ *)

%o (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 Cf A063772, A138555, A001156.

%K nonn,look

%O 0,3

%A _Franklin T. Adams-Watters_, Mar 24 2008