A096436 a(n) = the number of squared primes and 1's needed to sum to n.

1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 4, 4, 3, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 4, 4, 3, 4, 5, 5, 4, 3, 4, 5, 5, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 4, 4, 3, 4, 5, 5, 4, 3, 4, 5, 5, 4, 5, 6, 2, 3, 4, 5, 3, 4, 5, 6, 4, 3, 4, 5, 5, 4, 5, 6, 6, 5, 4, 5, 6, 6, 5, 6, 2, 3, 4, 5, 3, 4, 5, 6

Offset: 1

Author

Tom Raes (tommy1729(AT)hotmail.com), Aug 10 2004

Keywords

• nonn
• easy

Comments

a(n) has a new maximum at n=1,2,3,7,24,73,266,795.

I suspect that a(n) <= 9 for all n. - Robert G. Wilson v, Sep 18 2004

Examples

			a(5) = 2 because 5=4+1.
a(17) = 3 because 17=9+4+4.
A number may have many such sums: 27=25+1+1=9+9+9, 50=25+25=49+1.
		

Links

• Nicholas Matteo, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001248, A002828, A045698, A051034, A063274.

Programs

Mathematica

f[n_] := Block[{d = n, k = PrimePi[ Sqrt[n]], sp = {}}, While[d > 3, While[p = Prime[k]; d >= p^2, AppendTo[sp, p]; d = d - p^2]; k-- ]; While[d != 0, AppendTo[sp, 1]; d = d - 1]; If[Position[sp, 3] != {} && sp[[ -3]] == 1, sp = Delete[Drop[sp, -3], Position[sp, 3][[1]]]; AppendTo[sp, {2, 2, 2}]]; Reverse[ Sort[ Flatten[ sp]]]]; Table[ Length[ f[n]], {n, 105}] (* Robert G. Wilson v, Sep 20 2004 *)

Extensions

Edited and extended by Robert G. Wilson v, Sep 18 2004

Edited by Don Reble, Apr 23 2006