# A problem related with 'Postage stamp problem'

A friend of mine taught me this question. I found that it is related with 'Postage stamp problem' (though it does not seem to be same).

Let $m,a_1\lt a_2\lt \cdots\lt a_n$ be natural numbers. Now let us consider the following condition :

Condition : For each $k\in\mathbb N$ which satisfies $1\le k\le m$, $k$ can be represented as $a_i, 2a_i$ or $a_i+a_j\ (i\not=j)$.

Letting $\min_m(n)$ be the min of $n$, then here are my questions.

Question 1 : What is $\min_{m=100}(n)$ under the condition?

Question 2 : What is $\min_{m}(n)$ under the condition?

Example : For $m=100$, $(1,2,\cdots, 8,9,10, 20, \cdots,80,90)$ is an obvious example with $n=18$.

Motivation : For $m=100$, it was almost by chance that I discovered the following example with $n=16$ :

$$(1,3,4,7,8,9,16,17,21,24,35,46,57,68,79,90)$$ I expect that $\min_{m=100}(n)$ would be $16$, but I can't prove it.

For smaller $m$, we can get $\min_{m}(n)$ such as $$\min_{m=1}(n)=\min_{m=2}(n)=1,\min_{m=3}(n)=\min_{m=4}(n)=2,$$$$\min_{m=5}(n)=\min_{m=6}(n)=\min_{m=7}(n)=\min_{m=8}(n)=3,\min_{m=9}(n)=4.$$

Since we know that $(1,2,\cdots,k)$ is an example for $m=2k$, we get $\min_{m=2k}(n)\le k$ for any $k\in\mathbb N$. However, I don't have any good idea. Can anyone help?

Update : For $m=100$, I found an interesting example with $n=16$ : $$(1,2,3,7,11,15,19,23,27,28,29,30,61,64,67,70)$$ Using arithmetic progressions might be a key.

-
One can get 14 as a lower bound for $\min_{100}(n)$ by checking that 13 maximally yields 92 numbers. – Uwe Stroinski Nov 10 '13 at 17:38

To my understanding, you are asking about the smallest size of a subset $A\subset[0,m]$ such that $[0,m]\subset 2A$ (where $2A:=\{a'+a''\colon a',a''\in A\}$ is the doubling of $A$). This is OEIS sequence A066063. There is no hope to give an explicit formula, but clearly, you need $\binom{|A|}2+|A|\ge m+1$, implying $|A|\ge(1+o(1)\sqrt{2m}$. On the other hand, one can get away with $|A|=(2+o(1))\sqrt m$: to see this, assume for simplicity that $m$ is a square, say $m=l^2$, and take $A=\{0,1,\ldots,l-1\}\cup\{l, 2l,\ldots,l^2\}$.
To add to Seva's answer: see this paper by Gunturk and Nathanson which discusses some history on the problem and gives new bounds arxiv.org/pdf/math/0503241.pdf . Interestingly the constant is neither $\sqrt{2}$ nor $2$. – Lucia Nov 10 '13 at 18:10
I believe the question is asking for the smallest size of a set $A\subset [0,m]$ such that $[0,m]\subset 2A\cup A$, not $[0,m]\subset 2A$. – Steven Landsburg Nov 15 '13 at 17:48
@Steven Landsburg: this is completely equivalent, as $[0,m]\subset 2A$ enforces $0\in A$, whence $2A\cup A=2A$. – Seva Nov 15 '13 at 18:08
@Seva: Right. But I mistyped. I meant to say that the OP seems to have been asking for the smallest size of a set $A\subset[1,m]$ such that $[1,m]\subset 2A\cup A$. – Steven Landsburg Nov 15 '13 at 19:45