¿Cómo puedo encontrar el conjunto más pequeño que todos enteros incluso $4≤x≤N$ puede escribirse como la suma de dos elementos en el conjunto?

Question

Dado un entero positivo N, quiero crear un conjunto de enteros positivos tales que cualquier número $4,6,8,...N$ puede ser escrito como la suma de dos elementos en el conjunto. También quiero que el conjunto sea tan pequeño como sea posible.

Por ejemplo, con $N=24$, el conjunto {${2,4,8,10,14}$} es un resultado posible. El conjunto ha $5$ elementos, y no establecer con menos elementos tiene la propiedad deseada.

4=2+2
6=2+4
8=4+4
10=2+8
12=2+10=4+8
14=4+10
16=2+14=8+8
18=4+14=8+10
20=10+10
22=8+14
24=10+14

Este ejemplo fue encontrado por la mano. Hay un más rápido, más "matemática"?

Esta pregunta está relacionada con un reto que he creado en codegolf.SE. Decidí que la matemática subyacente era bastante interesante y que quería aprender más sobre él.

Answer 1

Voy a reducir esto a una más natural de la problema, y luego dar una solución de ese uno. Mi solución no es seguramente la mejor, pero es dentro de un factor constante.

A mí me parece que la restricción a los conjuntos de números no aporta nada al problema. Así que vamos a considerar el siguiente más natural problema: encontrar un conjunto $S$ de los números, de tamaño mínimo, de tal forma que cada número en el conjunto $\{1,...,n\}$ es la suma de dos elementos de la $S$. Este problema es equivalente al problema original con $n=N/2$. Simplemente haga doble cada elemento de a $S$ para obtener una solución del problema original.

Deje $s$ el número de elementos en $S$. El número de pares de elementos en $S$$s \choose{2}$, y este debe ser mayor que o igual a $n$. Por lo $s>O(\sqrt{n})$. Y en el párrafo siguiente se proporciona un ejemplo que muestra que esta enlazado puede ser alcanzado, por lo que sabemos $s=O(\sqrt{n})$.

Para su comodidad, suponga $n$ es un cuadrado perfecto. Si no lo es, redondeando a la siguiente cuadrado perfecto dará una solución que sólo demasiado grande por $O(1)$. La solución es el conjunto de números enteros $\{0,...,\sqrt{n}-1\} \cup \{0, \sqrt{n}, 2 \sqrt{n}, ... , n-\sqrt{n}\}$. Cualquier número puede ser dada por la suma de un número en el primer set y un número en el segundo set. Como había prometido, $s=2\sqrt{n}=O(\sqrt{n})$. No me sorprendería si esto podría ser mejorado por un pequeño factor constante.