if I want to make a subset of numbers for which sums of pairs involve all even numbers what is the subset with the smallest density?
for example {1 , 3 , 5} can pair to get 2 :1+1 , 4 :1+3 , 6 :3+3, 8: 5+3, 10 :5+5 so all even numbers until 10 can be achieved with a set of 3 numbers.
I made a java program that gets the smallest possible set by trying all possibilities. It reached 42 then (out of memory error) but the size of the set seemed to be approximately :
Size =The Largest Even Number/ log2(The Largest Even Number)
for 42 it is 7 , for 22 it is 5. Does this hold for larger numbers? And is there a theorem for that?
For fixed $n$, you can solve the problem via integer linear programming as follows. For $i\in\{1,\dots,n\}$, let binary decision variable $x_i$ indicate whether element $i$ is selected. The problem is to minimize $\sum_i x_i$ subject to $$\sum_{i\le k-i} x_i x_{k-i} \ge 1 \quad \text{for $k\in\{2,4,\dots,n\}$} \tag1\label1.$$ You can linearize these quadratic constraints \eqref{1} by introducing (nonnegative or binary) variables $y_{ij}$ to represent the products $x_i x_j$, together with linear constraints \begin{align} \sum_{i\le k-i} y_{i,k-i} &\ge 1 &&\text{for $k\in\{2,4,\dots,n\}$} \tag2\label2 \\ y_{ij} &\le x_i && \text{for $1\le i \le j \le n$} \tag3\label3 \\ y_{ij} &\le x_j && \text{for $1\le i \le j \le n$} \tag4\label4 \end{align}
The optimal objective values for even $n$ up to $100$ are: \begin{matrix} n & \sum_i x_i \\ \hline 2 & 1 \\ 4 & 2 \\ 6 & 2 \\ 8 & 3 \\ 10 & 3 \\ 12 & 4 \\ 14 & 4 \\ 16 & 4 \\ 18 & 4 \\ 20 & 5 \\ 22 & 5 \\ 24 & 5 \\ 26 & 5 \\ 28 & 6 \\ 30 & 6 \\ 32 & 6 \\ 34 & 6 \\ 36 & 7 \\ 38 & 7 \\ 40 & 7 \\ 42 & 7 \\ 44 & 8 \\ 46 & 8 \\ 48 & 8 \\ 50 & 8 \\ 52 & 8 \\ 54 & 8 \\ 56 & 9 \\ 58 & 9 \\ 60 & 9 \\ 62 & 9 \\ 64 & 9 \\ 66 & 9 \\ 68 & 10 \\ 70 & 10 \\ 72 & 10 \\ 74 & 10 \\ 76 & 10 \\ 78 & 10 \\ 80 & 10 \\ 82 & 10 \\ 84 & 11 \\ 86 & 11 \\ 88 & 11 \\ 90 & 11 \\ 92 & 11 \\ 94 & 11 \\ 96 & 12 \\ 98 & 12 \\ 100 & 12 \end{matrix}