|
%I #35 Feb 22 2019 10:28:24
%S 1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9,2,
%T 3,4,5,6,7,8,9,10,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9,2,3,4,5,6,7,8,9,10,3,
%U 4,5,6,7,8,9,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9,2,3,4,5,6,7,8,9,2,3,4,5,6,7,8,9
%N Least number of odd squares that sum to n.
%H Charles R Greathouse IV, <a href="/A101412/b101412.txt">Table of n, a(n) for n = 1..10000</a>
%F From _Jinyuan Wang_, Jan 29 2019: (Start)
%F For n == 1 (mod 8), if n is a perfect square, a(n) = 1, otherwise a(n) = 9.
%F For n == 2 (mod 8), if n is a term in A097269, a(n) = 2, otherwise a(n) = 10.
%F For n == k (mod 8), k = 3,4,...,8, a(n) = k.
%F For positive integer x, a(72*x+42) = a(72*x+66) = 10. (End)
%e a(13) = 5: 13 = 1+1+1+1+9.
%p A101412 := proc(n) local lsq; lsq := [seq((2*j+1)^2,j=0..floor((sqrt(n)-1)/2))] ; lsq := convert(lsq,set) ; a := n ; for p in combinat[partition](n) do if convert(p,set) minus lsq = {} then a := min(a,nops(p)) ; fi; od: a ; end: for n from 1 do printf("%d,\n",A101412(n)) ; od: # _R. J. Mathar_, Aug 08 2009
%p # problem has optimal substructure:
%p a:= proc(n) option remember; local r; r:= isqrt(n);
%p `if`(r^2=n and irem(r, 2)=1, 1,
%p min(seq(a(i)+a(n-i), i=1..n/2)))
%p end:
%p seq(a(n), n=1..120); # _Alois P. Heinz_, Jan 31 2011
%t a[n_] := a[n] = Module[{r}, r = Sqrt[n]; If[IntegerQ[r] && OddQ[r], 1, Min[Table[a[i]+a[n-i], {i, 1, Floor[n/2]}]]]]; Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Mar 19 2014, after _Alois P. Heinz_ *)
%o (PARI) a(n)={x=n-1;if(x%8>1,k=1+x%8);if(n%8==1,k=9;if(issquare(n)&&n%2==1,k=1));if(x%8==1,k=10;y=1;while(x>0,if(issquare(x)&&x%2==1,k=2);y=y+2;x=n-y^2));k;} \\ _Jinyuan Wang_, Jan 29 2019
%Y Cf. A002828, A151925, A097269.
%K nonn,easy
%O 1,2
%A _N. J. A. Sloane_, Aug 08 2009
%E More terms from _R. J. Mathar_, Aug 08 2009
%E More terms from _Alois P. Heinz_, Jan 30 2011
|
