A101412 Least number of odd squares that sum to n.

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

Offset: 1

Author

N. J. A. Sloane, Aug 08 2009

Keywords

• nonn
• easy

Examples

			a(13) = 5: 13 = 1+1+1+1+9.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A002828, A151925, A097269.

Programs

Maple

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
# problem has optimal substructure:
a:= proc(n) option remember; local r; r:= isqrt(n);
      `if`(r^2=n and irem(r, 2)=1, 1,
       min(seq(a(i)+a(n-i), i=1..n/2)))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jan 31 2011

Mathematica

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 *)

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

Formula

From Jinyuan Wang, Jan 29 2019: (Start)

For n == 1 (mod 8), if n is a perfect square, a(n) = 1, otherwise a(n) = 9.

For n == 2 (mod 8), if n is a term in A097269, a(n) = 2, otherwise a(n) = 10.

For n == k (mod 8), k = 3,4,...,8, a(n) = k.

For positive integer x, a(72*x+42) = a(72*x+66) = 10. (End)

Extensions

More terms from R. J. Mathar, Aug 08 2009

More terms from Alois P. Heinz, Jan 30 2011