El otro día estaba pensando en la demostración de Euclides de la infinitud de los números primos y me puse a pensar en lo que ocurriría para conjuntos iniciales de números primos distintos del habitual primero $N$ primos. ¿Existe un subconjunto finito de los números primos que nunca dé con un número compuesto al generar números como en la demostración de Euclides?
Considere el siguiente algoritmo:
Tome un juego $A_{k}=\left\{q_{1},\ldots,q_{k}\right\}$ de primos y sea $n = q_{1}\cdots q_{k}+1$ . Si $n$ es primo, comience de nuevo con $A_{k+1} = A_{k}\cup\left\{n\right\}$ . Si $n$ es compuesto, termina.
Escrito en un pseudocódigo similar a C:
function euclid(array primes[])
{
n = 1;
steps = 1;
for(i = 0; i < primes.size(); i++)
{
n *= primes[i];
}
n++;
while(isPrime(n))
{
steps++;
primes.append(n);
n = n*(n-1) + 1;
}
return steps;
}
Mi pregunta es: ¿Esto siempre termina para cualquier conjunto inicial de primos? Si es así, ¿cómo podemos expresar el número de pasos en función del conjunto inicial de primos? ¿Es ilimitado el número de pasos si variamos el conjunto inicial de números primos?
Lo único que he podido determinar por mi cuenta, hasta ahora, es que esto obviamente termina después del primer paso siempre que no se incluya el 2.
He aquí algunos ejemplos (todos incluyen 2):
$\{2\}\to\{2,3\}\to\{2,3,7\}\to\{2,3,7,43\}\to\{2,3,7,43,1807\}\to$ Terminar: $13\mid1807$ . 4 pasos.
$\{2,5\}\to\{2,5,11\}\to\{2,5,11,111\}\to$ Terminar: $3\mid111$ . 2 pasos.
$\{2,7\}\to\{2,7,15\}\to$ Terminar: $3\mid15$ . 1 paso.
$\{2,3,5\}\to\{2,3,5,31\}\to\{2,3,5,31,931\}\to$ Terminar: $7\mid931$ . 2 pasos.
Desde $q_{\ell+1} = q_{\ell}\left(q_{\ell}-1\right)+1$ para todos $\ell>k$ parece que mirando el polinomio $x^{2}-x+1$ puede aportar alguna información.
Si alguien puede enlazar referencias de este problema o similares, se lo agradecería mucho.
2 votos
Comprobación de los valores de $x^2-x+1\pmod{7}$ muestra que si el primer producto no es congruente con $0$ ou $1$ mod $7$ entonces el proceso termina como máximo en $4$ pasos.
7 votos
Pregunta relacionada sobre mathoverflow Recomendado por Respuesta de Pete L. Clark y el problema al que enlaza. El problema 6)f) es este problema, listado como abierto.
0 votos
La intuición dice que sí, que siempre dará con un número compuesto. Una pregunta muy interesante.