Ejemplo
Supongamos que queremos demostrar que todos los números naturales pueden generarse sumando números primos, entonces la prueba puede ser la siguiente:
- Si el número natural en cuestión es par, debe ser una suma de dos.
- En el caso de que sea impar, podemos sustituir uno de los dos del número par más pequeño que este número por un tres.
Esto significa que el uno no se genera de esta manera, pero el resto de los números naturales sí.
Supongamos que sacamos el dos del conjunto de todos los números primos. Con una prueba un poco más complicada podemos demostrar que todos los números mayores que cuatro se pueden generar sumando los primos restantes.
Supongamos que quitamos el dos y el tres, entonces, de nuevo, podemos demostrar que todo número mayor que quince se puede generar usando los primos restantes.
La pregunta
Utilizando el ejemplo anterior, dejemos que $+^*$ sea la operación de "tantas sumas como sean necesarias", sea $P$ sea el conjunto de todos los primos. Definir $N_p$ sea el número tal que $\{q \;|\; s, r \in P \land s, r \geq p \land q = s +^* r\} \cap \{ n \;|\; n \in \mathbb{N} \land n < N_p\} = \emptyset$ . ¿Es el conjunto $\{N_q \;|\; q \in \mathbb{N}\}$ ¿Finito?
En otras palabras: supongamos que seguimos eliminando el primo más pequeño del conjunto de todos los primos, ¿encontraremos alguna vez una situación en la que haya intervalos repetidos de números naturales que no podamos generar sumando los primos restantes?
PS. Esto no es una tarea. El problema original al que me enfrentaba estaba relacionado con la teoría de autómatas y el monoide libre de un lenguaje definido como $L'=L^*, L=\{a^p \;|\; Prime(p)\}$ pero no estaba pidiendo resolver la pregunta anterior.
