A066063 Size of the smallest subset S of T={0,1,2,...,n} such that each element of T is the sum of two elements of S.

1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12

Offset: 0

Author

John W. Layman, Dec 01 2001

Keywords

• nonn
• more

Comments

If one counts all subsets S of T={0,1,2,...n} such that each number in T is the sum of two elements of S, sequence A066062 is obtained.

Since each k-subset of S covers at most binomial(k + 1, 2) members of T, we have binomial(a(n) + 1, 2) >= n + 1. It follows that A002024(n-1) is a lower bound. - Rob Pratt, May 14 2004

This is an instance of the <= 2-stamp postage problem with n denominations. For n > 0, a(n) = 1 + the smallest i such that A001212(i) >= n (adding one adjusts for the fact that A001212 has offset 1). - Tim Peters (tim.one(AT)comcast.net), Aug 25 2006

Examples

			For n=2, it is clear that S={0,1} is the unique subset of {0,1,2} that satisfies the definition, so a(2)=2.
		

Crossrefs

Cf. A066062, A002024, A001212.

Extensions

a(27)-a(50) from Rob Pratt, Aug 13 2020