How to get even numbers from adding pairs? (best title I thought of)

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?

• oeis.org/A066063 Aug 7 at 18:42
• When you format your equations in a good mathematical style, it's easier to see whether you mean $(\log 2)\times(\text{largest even number})$ or $\log_2(\text{largest even number}).$ Although we can see from the answer below that even the second formula is not accurate for larger sums. Aug 7 at 19:16

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}$$
• good. Note that the smallest set $S$ of non-negative integers for which $S+S$ contains all even naturals has density zero. Indeed, if we let $S$ be the set of all integers $n = x^2 + y^2$ where $x,y$ are integers, in fact $S+S$ contains all natural numbers. Aug 7 at 18:06
• Indeed, the same is true when $S$ equals the set of primes ... conjecturally! Aug 7 at 18:51
• @GregMartin is there any set $S$ that gives all evens as pair sums and has density similar to the primes? i. e. up to large positive $n,$ the count of $S$ elements is about $\frac{x}{\log x}$ Aug 7 at 19:30
• Yes: it's known that most even numbers can be written as the sum of two primes, so we could just insert $n-3$ for every exceptional even number $n$ without changing the density. That being said, the smallest such $S$ has counting function asymptotic to a constant times $\sqrt x$. I believe a reference to such a construction is: J. W. S. Cassels, Uber Basen der natürlichen Zahlenreihe, Abhandlungen Math. Seminar Univ. Hamburg 21 (1975), 247–257. Aug 7 at 20:03
• An easy $x^{2/3}$ construction is to take all integers whose base-$8$ representation only has the digits $0, 1, 2, 5$. For this approach, it's enough to check that every base-$8$ digit can be decomposed: $0=0+0, 1=1+0, 2=2+0, 3=2+1, 4=2+2,5=5+0,6=5+1,7=5+2$. Then apply this to each digit: for example, $2022$ is $3722_8$, so it is the sum of $2522_8$ and $1200_8$. Aug 8 at 1:37