cp's OEIS Frontend

A101412 Least number of odd squares that sum to n.

%I A101412 #35 Feb 22 2019 10:28:24
%S A101412 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 A101412 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 A101412 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 A101412 Least number of odd squares that sum to n.
%H A101412 Charles R Greathouse IV, <a href="/A101412/b101412.txt">Table of n, a(n) for n = 1..10000</a>
%F A101412 From _Jinyuan Wang_, Jan 29 2019: (Start)
%F A101412 For n == 1 (mod 8), if n is a perfect square, a(n) = 1, otherwise a(n) = 9.
%F A101412 For n == 2 (mod 8), if n is a term in A097269, a(n) = 2, otherwise a(n) = 10.
%F A101412 For n == k (mod 8), k = 3,4,...,8, a(n) = k.
%F A101412 For positive integer x, a(72*x+42) = a(72*x+66) = 10. (End)
%e A101412 a(13) = 5: 13 = 1+1+1+1+9.
%p A101412 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 A101412 # problem has optimal substructure:
%p A101412 a:= proc(n) option remember; local r; r:= isqrt(n);
%p A101412       `if`(r^2=n and irem(r, 2)=1, 1,
%p A101412        min(seq(a(i)+a(n-i), i=1..n/2)))
%p A101412     end:
%p A101412 seq(a(n), n=1..120);  # _Alois P. Heinz_, Jan 31 2011
%t A101412 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 A101412 (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 A101412 Cf. A002828, A151925, A097269.
%K A101412 nonn,easy
%O A101412 1,2
%A A101412 _N. J. A. Sloane_, Aug 08 2009
%E A101412 More terms from _R. J. Mathar_, Aug 08 2009
%E A101412 More terms from _Alois P. Heinz_, Jan 30 2011