Return to Answer

Short answer: Such a set $S$ is known as a restricted additive basis.

As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

1. given $k$, what is the largest $n$ ...
2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by your truly. Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$, and $k(367)=48$.

To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our notation (with target interval $[2n]$) this means the factor in front of $\sqrt n$ is asymptotically at least $2.18264$.

And about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this paper by me and coauthors, where the corresponding problem is studied in two dimensions.

Short answer: Such a set $S$ is known as a restricted additive basis.

As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

1. given $k$, what is the largest $n$ ...
2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by yours truly (2015). Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$, and $k(367)=48$.

To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our notation (with target interval $[2n]$) this means the factor in front of $\sqrt n$ is asymptotically at least $2.18264$.

And about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this 2018 paper by me and coauthors, where the corresponding problem is studied in two dimensions.

Short answer: Such a set $S$ is known as a restricted additive basis.

As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

1. given $k$, what is the largest $n$ ...
2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by your truly. Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$.

To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our notation (with target interval $[2n]$) this means the factor in front of $\sqrt n$ is asymptotically at least $2.18264$.

And about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this paper by me and coauthors, where the corresponding problem is studied in two dimensions.

Short answer: Such a set $S$ is known as a restricted additive basis.

As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

1. given $k$, what is the largest $n$ ...
2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by your truly. Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$, and $k(367)=48$.

To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our notation (with target interval $[2n]$) this means the factor in front of $\sqrt n$ is asymptotically at least $2.18264$.

And about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this paper by me and coauthors, where the corresponding problem is studied in two dimensions.

Short answer: Such a set $S$ is known as a restricted additive basis.

As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

1. given $k$, what is the largest $n$ ...
2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by your truly. Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$.

To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our the notation (with target interval $[2n]$) this means the factor is asymptotically at least $2.18264$.

Oh, about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this paper by me and coauthors, where the corresponding problem is studied in two dimensions.

Short answer: Such a set $S$ is known as a restricted additive basis.

As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

1. given $k$, what is the largest $n$ ...
2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by your truly. Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$.

To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our notation (with target interval $[2n]$) this means the factor in front of $\sqrt n$ is asymptotically at least $2.18264$.

And about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this paper by me and coauthors, where the corresponding problem is studied in two dimensions.