OFFSET
1,2
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
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)
EXAMPLE
a(13) = 5: 13 = 1+1+1+1+9.
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Aug 08 2009
EXTENSIONS
More terms from R. J. Mathar, Aug 08 2009
More terms from Alois P. Heinz, Jan 30 2011
STATUS
approved