5
$\begingroup$

I was reflecting on the Goldbach conjecture when the following question came to my mind:

Let $n$ be a natural number. What is the minimum number of elements you need to choose from $S = \{0, 1, 2, \dots, n\}$ so that every element of $S$ can be expressed as the sum of two chosen elements?

I made some attempts to solve it, and was able to find an upper bound:

For $k\in S$, choose the elements $\begin{aligned}0, 1, \dots, k, 2k, 3k, \dots, \Big\lfloor \frac{n}{k}\Big\rfloor k\end{aligned}$. Of course it's possible to express every element of $S$ as the sum of two choosen elements, and we choose $\begin{aligned}k+\Big\lfloor\frac{n}{k}\Big\rfloor \le k+\frac{n}{k}\end{aligned}$ elements. Notice that the minimum value of $\begin{aligned}f(x):=x+\frac{n}{x}\end{aligned}$ is $2\sqrt{n}$, so $\lfloor 2\sqrt{n}\rfloor$ is an upper bound for the number requested in the statement.

I know this bound is not the answer. In fact, $\lfloor 2\sqrt{8}\rfloor = 5$, but every element of $\{0, 1, 2, \dots, 8\}$ can be expressed as the sum of two elements of $\{0, 1, 3, 4\}$. I would appreciate some help in this subject.

$\endgroup$
  • 2
    $\begingroup$ As far as I know, it's an open problem, but I could be wrong. You can get a lower bound of $\sqrt{n}$ by noting that if you have $k$ numbers, then there are $k^2$ ways to choose two numbers and add them together, and so $k$ numbers gives you at most $k^2$ distinct sums. Thus the correct number lies somewhere between $\sqrt{n}$ and $2\sqrt{n}$. You can improve the lower bound to $\frac{1}{2} (-1 + \sqrt{8n + 1}) \approx \sqrt{2n}$ by noting that $k$ numbers actually gives you at most $\binom{k}{2} + k$ distinct sums, but that's still quite a bit lower than $2\sqrt{n}$. $\endgroup$ – Dylan Aug 13 '20 at 22:34
  • 1
    $\begingroup$ Some optimal (not necessary unique) sets for lowest $n$ here (python script, exhaustive search). $\endgroup$ – Alexey Burdin Aug 13 '20 at 22:51
  • 4
    $\begingroup$ It's sequence A066063 on the OEIS: oeis.org/A066063 $\endgroup$ – Dylan Aug 13 '20 at 22:52
  • 1
    $\begingroup$ I extended the OEIS sequence to $n=50$ just now. $\endgroup$ – RobPratt Aug 13 '20 at 23:15
1
$\begingroup$

You can solve the problem via integer linear programming as follows. For $j\in S$, let binary decision variable $x_j$ indicate whether element $j$ is selected. Let $P=\{j_1\in S, j_2 \in S: j_1 \le j_2\}$ be the set of pairs of elements of $S$. For $(j_1,j_2)\in P$, let binary decision variable $y_{j_1,j_2}$ indicate whether both $j_1$ and $j_2$ are selected. The problem is to minimize $\sum_{j\in S} x_j$ subject to: \begin{align} \sum_{(j_1,j_2)\in P:\\j_1+j_2=i} y_{j_1,j_2} &\ge 1 &&\text{for $i\in S$} \tag1\\ y_{j_1,j_2} &\le x_{j_1} &&\text{for $(j_1,j_2)\in P$} \tag2\\ y_{j_1,j_2} &\le x_{j_2} &&\text{for $(j_1,j_2)\in P$} \tag3 \end{align} The objective minimizes the number of selected elements. Constraint $(1)$ forces each element of $S$ to be expressible as a sum of selected elements. Constraints $(2)$ and $(3)$ enforce $y_{j_1,j_2} = 1 \implies x_{j_1} = 1$ and $y_{j_1,j_2} = 1 \implies x_{j_2} = 1$, respectively.

$\endgroup$
0
$\begingroup$

Maybe you should use a different approach.

It can be found that sets with the least number of elements are of the following type:

$\{0,1,a_1,\dots ,a_m,\frac{n}{2}-a_m,\dots ,\frac{n}{2}-a_1,\frac{n}{2}-1,\frac{n}{2}\}$

or

$\{0,1,a_1,\dots ,a_m,\frac{n}{4},\frac{n}{2}-a_m,\dots ,\frac{n}{2}-a_1,\frac{n}{2}-1,\frac{n}{2}\}$

example $n \leq 20$

elements can be found easily with this set

$\{0,1,3,\dots ,\frac{n}{2}-1,\frac{n}{2}\}$ number of elements $2+\frac{n}{4}$

then

$\{0,1\}$ for $0 \leq n \leq 2$

$\{0,1,2\}$ for $3 \leq n \leq 4$

$\{0,1,3,4\}$ for $5 \leq n \leq 8$

$\{0,1,3,5,6\}$ for $9 \leq n \leq 12$

$\{0,1,3,5,7,8\}$ for $13 \leq n \leq 16$

$\{0,1,3,5,7,9,10\}$ for $17 \leq n \leq 20$

example $n >20$

$\{0,1,3,4,9,10,12,13\}$ for $21 \leq n \leq 26$

$\{0,1,3,4,5,8,14,20,26,32,35,36,37,39,40\}$ for $73 \leq n \leq 80$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.