|
|
A101412
|
|
Least number of odd squares that sum to n.
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
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:
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|