Escribe los números enteros de cualquier $n$ a través de $0$ descendente en una columna, donde $n \geq 2$ y comenzar una segunda columna con el valor $2n$ . Para cada entrada posterior, si los dos números de esa línea comparten un factor, copie la entrada sin cambios, pero si son coprimos, reste $1$ .
Nos referiremos a la primera columna como $a$ donde cada valor es igual a su índice, y la segunda columna como $b$ donde el $a$ a entrada de la fila es $b_a$ . En $0$ -index se refiere a la fila inferior. Equivalentemente,
$$ b_a = \begin{cases} 2n & \textrm{if } a = n \\ b_{a+1} - 1 & \textrm{if }\gcd(a+1,b_{a+1})=1 \\ b_{a+1} & \textrm{otherwise}\end{cases}$$
Considere el siguiente ejemplo $n=8$ . También he incluido una columna que muestra $\gcd(a,b_a)$ y los coloreó $b_a$ que comparten un factor con $a$ y, por tanto, no cambian.
$$ \begin{array}{|c|c|c|} \hline a & b_a & (a,b_a) \\ \hline 8 & \color{red}{16} & 8 \\ \hline 7 & 16 & 1 \\ \hline 6 & \color{red}{15} & 3 \\ \hline 5 & \color{red}{15} & 5 \\ \hline 4 & 15 & 1 \\ \hline 3 & 14 & 1 \\ \hline 2 & 13 & 1 \\ \hline 1 & 12 & 1 \\ \hline 0 & 11 & 11 \\ \hline \end{array} $$
Afirmación: $b_0$ siempre será primo.
¿Por qué? Bueno, supongamos que no, que algún primo más pequeño $p<b_0$ la divide. En particular, dejemos que $p$ sea el factor primo más pequeño que divide a $b_0$ . Desde $b_0 \neq b_n$ y $p\geq 2$ tenemos $p<n$ por lo que si un primo divide $b_0$ debe estar en nuestra columna de $a$ valores.
$p \mid b_0 \implies p \mid b_p$ . Esto se debe a que $p$ sólo puede dividir $b_0$ si ya se ha establecido dividiendo $b_{kp}$ para algunos $k\geq 1$ . Un factor no puede aparecer por primera vez en $b_0$ a menos que sea primo.
Dicho esto, $p \mid b_p \implies b_p = b_{p-1}$ . Sin embargo, eso significa $b_{p-1} \not\equiv b_0 \pmod {p}$ independientemente de $b_a$ decremento o no; hay uno demasiado pocos para volver a nuestra divisibilidad afirmada, y nos quedamos con $b_0 \not\equiv 0 \pmod {p}$ es decir $p \nmid b_0$ una contradicción. (Recordemos que $b_1 - b_0 = 1$ siempre, evitando una constante $0 \pmod p$ hasta el fondo).
$$ \begin{array}{|l|l|} \hline n & 2n \\ \hline \dots & \dots \\ \hline p & b_p \equiv 0 \pmod{p} \\ \hline p-1 & b_{p-1} \equiv 0 \pmod {p} \\ \hline p-2 & b_{p-2} \equiv \{0\text{ or } p-1\} \pmod{p} \\ \hline p-3 & b_{p-3} \equiv \{0\text{ or } p-1 \text{ or }p-2\} \pmod{p} \\ \hline \dots & \dots \\ \hline 0 & b_0 \not\equiv 0 \pmod{p} \\ \hline \end{array} $$
Conclusión: Como hemos establecido no puede haber un factor primo más pequeño que divida a $b_0$ debe ser primo. Ahora que tenemos primo $b_0$ podemos aplicar el mismo proceso arbitrariamente con cualquier $n$ e inmediatamente hemos demostrado que existe un primo en cualquier $(n,2n)$ intervalo.
Está bastante claro que me equivoqué en la lógica de una parte importante de la prueba, y estoy trabajando en una forma inteligente de resolverlo, pero mientras tanto, tengo una idea para una solución menos elegante.
Si nos fijamos en el mecanismo real de lo que está pasando, es básicamente esto. La resta de uno sólo cuando coprime esencialmente mantiene un número (la diferencia $b_a - a$ para cualquier $a$ ) que intenta descartar como primo. Esto empieza como $n$ que pasa automáticamente a $n+1$ en la línea siguiente, ya que $n \mid 2n$ . A partir de entonces, siempre que cualquier factor en $a$ es compartida por un factor en $b_a -a$ está marcando $b_a-a$ como compuesto y seguir adelante. Puede verlo en este gráfico parcial de $n=113$ donde la columna de la derecha es sólo la diferencia de las dos primeras:
$$ \begin{array}{|l|l|l|} \hline 113 & 226 = 2 \cdot 113 & 113 \\ \hline 112 = 2^4\cdot 17 & 226 = 2 \cdot 113 & 114=2\cdot 3 \cdot 19 \\ \hline 111 = 3\cdot 37 & 226 = 2 \cdot 113 & 115 = 5 \cdot 23 \\ \hline 110 = 2\cdot 5\cdot 11 & 225 = 3^2 \cdot 5^2 & 115 = 5 \cdot 23 \\ \hline 109 & 225 = 3^2 \cdot 5^2 & 116 = 2^2 \cdot 29 \\ \hline 108 = 2^2 \cdot 3^3 & 224=2^5 \cdot 7 & 116 = 2^2 \cdot 29 \\ \hline 107 & 224=2^5 \cdot 7 & 117 = 3^2 \cdot 13 \\ \hline 106 = 2 \cdot 53 & 223 & 117 = 3^2 \cdot 13 \\ \hline 105 = 3 \cdot 5 \cdot 7 & 222 = 2\cdot 3 \cdot 37 & 117 = 3^2 \cdot 13 \\ \hline 104 = 2^3 \cdot 13 & 222 = 2\cdot 3 \cdot 37 & 118 = 2\cdot 59 \\ \hline 103 & 222 = 2\cdot 3 \cdot 37 & 119 = 7 \cdot 17 \\ \hline 102 = 2 \cdot 3 \cdot 17 & 221=13 \cdot 17 & 119 = 7 \cdot 17 \\ \hline 101 & 221=13 \cdot 17 & 120 = 2^3 \cdot 3 \cdot 5 \\ \hline 100 = 2^2 \cdot 5^2 & 220 = 2^2 \cdot 5 \cdot 11 & 120 = 2^3 \cdot 3 \cdot 5 \\ \hline \dots & \dots & \dots \\ \hline 88 = 2^3 \cdot 11 & 214 = 2 \cdot 107 & 126 = 2 \cdot 3^2 \cdot 7 \\ \hline 87 = 3 \cdot 29 & 214 = 2 \cdot 107 & 127 \\ \hline 86 = 2 \cdot 43 & 213 = 3 \cdot 71 & 127 \\ \hline \dots & \dots & \dots \\ \hline \end{array} $$
Se necesita $14$ no decrece, que es exactamente la cantidad necesaria para pasar de $113$ a través de la gran brecha allí hasta la siguiente prima $127$ y después ya no hay factores compartidos y se queda $127$ todo el camino hacia abajo, y de hecho siempre funciona así.
Así que el tamaño de la brecha de primos es uno de los factores determinantes de la duración de esa sección de "división de prueba", y el otro es el tamaño de los propios factores. Como ya he dicho, cualquier factor presente servirá, y no puedo discernir mucha rima o razón para ello, así que eso nos deja con hacer una estimación del límite superior en el peor de los casos de la suma de los factores menos primos que comprenden cada número en el hueco primo. En este ejemplo, creo que suma $60$ más o menos, pero es uno de los peores casos, si no el peor.
Para que esto sea riguroso, podemos utilizar el mejor límite superior actual establecido sobre el tamaño de la brecha de primos para un tamaño suficientemente grande de $x$ de $x^{0.525}$ . Si consideramos algunos grandes $x$ que tiene un hueco de ese tamaño, podemos marcar inmediatamente la mitad de esas entradas como pares, lo que significa que, en el peor de los casos, se necesitarían dos $a$ -para pasar cada una de esas entradas dentro de la brecha. Así que la mitad de la brecha es sólo
$$x^{0.525} / 2 \times 2 = x^{0.525},$$
y nos deja a medias. Aquí, sin duda, podríamos seguir reduciendo nuestra estimación eliminando otros pequeños factores, pero no estoy seguro de que eso ayude realmente. Ignorando la eliminación de pequeños factores, nuestra conclusión es que necesitamos
$$x^{0.525} x^k < x,$$
donde $x^k$ representa un límite superior para la suma de los factores primos menores de ese hueco, y parece que necesitamos $k<0.475$ . Yo esperaría que $x^k$ a algo más parecido a $\log{x}$ pero no conozco ningún límite que lo diga inmediatamente.
Así que no, esto tampoco es una prueba completa, pero pensé que podría compartir algunas de mis ideas. Sigo esperando que aparezca una solución elegante. Dicho esto, si este enfoque se puede hacer para trabajar, que al instante debe demostrar mi enfoque válido para grandes $n$ ... pero, por supuesto, usar algo más poderoso que el postulado de Bertrand para ayudar a hacerlo como que frustra el propósito. Más actualizaciones más tarde.
Otra cosa que vale la pena mencionar. Hay una solución fácil para los casos en que esto falla. Si $b_0=cd$ , algún compuesto, reinicie el proceso utilizando $c, (c+1)d$ y repita la operación si es necesario. Esto le permite hacer cosas divertidas como golpear los valores primos en $p(p+1)$ .
Por ejemplo, a partir de $\{29, 29\cdot 30\}$ producirá $b_0=851=23\cdot 37$ . Reiniciar con $\{23, 23\cdot 37 + 23\}$ y obtendrá un $b_0=853$ . Esto parece funcionar bien empíricamente, pero tengo que dudar de que haya alguna forma de justificarlo rigurosamente.
Actualización : Sólo una cosa rápida. Me puse a pensar en la nota de Arnaud acerca de la ingeniería inversa, y tengo una idea para flotar. Traté de hacer un poco de mapeo de las posibilidades de origen para varios $b_0$ y mientras que los primos son bonitos y robustos, los compuestos no lo son. Lo mejor que tienen que ofrecer en los primeros 500 o así es probablemente:
lo que tiene sentido, con $209$ siendo un semiprimo mayor y $233$ arriba siendo la mitad de un problema semiprimo que aparece un poco.
Esperaba que los gráficos de posibilidades de los primos fueran infinitos, pero si mi código es correcto, resulta que son simplemente mucho mayores que los no primos. Aquí está una muestra:
\begin{array}{|l|l|l|l|} \hline \mathbf{b_0} & & \textbf{nodes} & \textbf{max length} \\ \hline 101 & 101 & 6206 & 818 \\ \hline 102 & 2\cdot 3\cdot 17 & 1 & 0 \\ \hline 103 & 103 & 9779 & 918 \\ \hline 104 & 2^3\cdot 13 & 1 & 0 \\ \hline 105 & 3\cdot 5\cdot 7 & 4 & 2 \\ \hline 106 & 2\cdot 53 & 1 & 0 \\ \hline 107 & 107 & 11059 & 1074 \\ \hline 108 & 2^2\cdot 3^3 & 1 & 0 \\ \hline 109 & 109 & 6293 & 1094 \\ \hline 110 & 2\cdot 5\cdot 11 & 1 & 0 \\ \hline 111 & 3\cdot 37 & 4 & 2 \\ \hline 112 & 2^4\cdot 7 & 1 & 0 \\ \hline 113 & 113 & 8886 & 1184 \\ \hline 114 & 2\cdot 3\cdot 19 & 1 & 0 \\ \hline 115 & 5\cdot 23 & 8 & 4 \\ \hline 116 & 2^2\cdot 29 & 1 & 0 \\ \hline 117 & 3^2\cdot 13 & 4 & 2 \\ \hline 118 & 2\cdot 59 & 1 & 0 \\ \hline 119 & 7\cdot 17 & 44 & 14 \\ \hline 120 & 2^3\cdot 3\cdot 5 & 1 & 0 \\ \hline 121 & 11^2 & 70 & 22 \\ \hline 122 & 2\cdot 61 & 1 & 0 \\ \hline 123 & 3\cdot 41 & 4 & 2 \\ \hline 124 & 2^2\cdot 31 & 1 & 0 \\ \hline 125 & 5^3 & 20 & 8 \\ \hline 126 & 2\cdot 3^2\cdot 7 & 1 & 0 \\ \hline 127 & 127 & 12230 & 1268 \\ \hline \end{array}
También analicé algunos parámetros del primer $15000$ grafos no primos. Hay algunas correlaciones fuertes, en particular entre semiprimos grandes y grafos más grandes, pero el hallazgo más prometedor es lo que parece un límite fuerte en la proporción de nodos totales en el grafo a $b_0$ . Fue $<1$ siempre, y parecía estar disminuyendo, lo que sugiere que un límite fuerte podría ser posible. (Esta misma proporción se $>1$ para todos los primos, y a escala muy próxima a la lineal).
Puesto que la longitud máxima (o altura, si se prefiere) del grafo es la pieza crítica que determina si toda esta conjetura funciona o no, y puesto que esa longitud es un subconjunto del grafo total, un límite duro al número de nodos sería efectivamente una prueba de que la conjetura se sostiene.
Para que quede claro, los "nodos" corresponden a pares de números iniciales que conducirían a un determinado $b_0$ . El par de números en cuestión son los que antes llamábamos $n$ y $2n$ pero ahora somos más flexibles. Así que, si resulta que hay alguna razón de peso por la que un compuesto dado $m$ debe tener menos de $m$ diferentes pares de partida que llevaron a su $b_0$ sería suficiente para una prueba.
Último intento
De acuerdo. Voy a tratar de justificar el original $(n,2n)$ enfoque de nuevo.
En primer lugar, sin embargo, creo que sirve para mirar a $(n,n+2)$ como par de semillas. $n=16$ queda bien a efectos ilustrativos. Aquí hay un gráfico para ello; como alguien más señaló, el $b$ es innecesaria en este caso. Podríamos sustituirla por $c=b-a$ que es más claro y compartirá todos los $b$ ya que sólo nos interesa saber dónde $a$ y $b$ solapamiento. Dicho esto, lo dejaremos por esta vez.
$$ \begin{array}{|ll|ll|ll|} \hline \textbf{a} & & \textbf{b} & & \textbf{c} & \\ \hline 16 &= 2^4 & 18 &= 2 \cdot 3^2 & 2 & \\ \hline 15 &= 3\cdot 5 & 18 &= 2 \cdot 3^2 & 3 \\ \hline 14 &= 2 \cdot 7 & 18 &= 2 \cdot 3^2 & 4 &= 2^2 \\ \hline 13 & & 18 &= 2 \cdot 3^2 & 5 & \\ \hline 12 &= 2^2 \cdot 3 & 17 & & 5 & \\ \hline 11 & & 16 &= 2^4 & 5 & \\ \hline 10 &= 2 \cdot 5 & 15 &= 3\cdot 5 & 5 & \\ \hline 9 &= 3^2 & 15 &= 3\cdot 5 & 6 &= 2 \cdot 3 \\ \hline 8 &= 2^3 & 15 &= 3\cdot 5 & 7 \\ \hline 7 & & 14 &= 2 \cdot 7 & 7 & \\ \hline 6 &= 2 \cdot 3 & 14 &= 2 \cdot 7 & 8 &= 2^3 \\ \hline 5 & & 14 &= 2 \cdot 7 & 9 &=3^2 \\ \hline 4 &= 2^2 & 13 & & 9 &=3^2 \\ \hline 3 & & 12 &= 2^2 \cdot 3 & 9 &=3^2 \\ \hline 2 & & 12 &= 2^2 \cdot 3 & 10 &=2\cdot 5 \\ \hline 1 & & 12 &= 2^2 \cdot 3 & 11 &\\ \hline 0 & & 11 & & 11 &\\ \hline \end{array} $$
Estamos utilizando el mismo sistema aquí para determinar los valores sucesivos en $b$ como hicimos antes: restar $1$ cuando es coprimo de $a$ de lo contrario, muévelo hacia abajo sin cambios.
Me gustaría utilizar esta tabla sobre todo para señalar que aquí no ocurre nada mágico ni inexplicable. Probablemente esté más claro en $c$ simplemente contamos desde $2$ y manteniendo cada valor hasta que coincida con un factor en $a$ y luego incrementamos en uno. Cualquier factor servirá, siempre que se comparta con $a$ .
Algunas cosas a tener en cuenta. En primer lugar, puesto que $a$ es ascendente sin pausas y $c$ es descendente pero espera una coincidencia antes de incrementarse, es natural que $c$ crecerá más lentamente, pero dado el gran número de pequeños factores disponibles como $a$ pasa volando, seguirá creciendo una cantidad respetable.
Lo segundo, y esto es realmente lo importante, es observar la $11$ en la parte inferior de la columna. Todo nuestro sistema se basa en la idea de que este número siempre será primo, siempre que se introduzcan valores semilla razonables. Y esta tabla muestra por qué.
Para empezar diciendo lo obvio, teníamos que terminar con algo. Tal vez no sabíamos que tenía que ser el primero, pero es obvio $c$ estaba contando y acabaría en algún sitio. Más concretamente, hay que tener en cuenta que no estamos afirmando que vaya a alcanzar ningún valor primo específico todavía, sólo que está creciendo lentamente. Así que la pregunta es, ¿por qué deberíamos esperar que ese valor inferior sea necesariamente primo?
Mira el penúltimo primo, el $7$ . No siempre será $7$ pero siempre habrá un penúltimo primo, y después de alcanzarlo, suele haber una salpicadura de aniquilación de factores pequeños como la que vemos a continuación. Si esto ocurrió en $7$ o en $737$ El espacio y los factores necesarios para salvar la distancia hasta el siguiente prime siempre estarán disponibles.
El resultado es que un primo siempre estará esperando allí, ya que obviamente no aparecen grandes factores entre $1$ y $0$ . En particular, sólo los factores menores vienen después del penúltimo primo. Normalmente hay espacio de sobra; este ejemplo muestra lo más cerca que se llega a estar de que el primo sea sustituido por factores pequeños.
Me doy cuenta de que esto no es una justificación a nivel de prueba de que eso nunca puede suceder. Dicho esto, creo que podría señalar explícitamente un mapeo biyectivo suficientemente cubriente de factores de una columna a la otra que siempre tiene lugar, pero de momento me doy por satisfecho si eso fuera persuasivo.
Y eso es lo esencial. Creo que tomar $(n,n+2)$ ilustra mejor el mecanismo subyacente, pero si te fijas bien, verás que la línea $7$ con $14$ a su lado. Eso significa que de ahí para abajo, este gráfico es idéntico a si hubiéramos utilizado $(7,14)$ como nuestra pareja semilla desde el principio.
Lo mismo se aplica a cualquier $(p,2p)$ ; hay un número arbitrario de $(n,n+2)$ gráficos que se pueden cortar para obtener el par que se desee. Es de suponer que esto es válido para $(n,2n)$ aunque lo evitaremos para ir sobre seguro. Y, por supuesto, no hay necesidad de encontrar realmente tales gráficos; si usted suscribe la validez del proceso de ejemplo, que debería ser suficiente para demostrar la validez de la utilización de cualquier $(p,2p)$ como par de semillas.
Un par de notas finales. Cuando usamos $(p,2p)$ tiene la ventaja adicional de proporcionar no sólo un primo en ese rango, sino también el siguiente primo mayor que $p$ . Esto debería tener sentido después de haber visto nuestro ejemplo.
Por último, obsérvese que esto nos da lo que buscábamos desde el principio: una prueba de primos en cada $2n$ intervalo. Por supuesto, podemos aplicar esto tanto como queramos utilizando los argumentos que queramos para $p$ . Algunos de mis datos adicionales también sugieren que después de que hayan pasado cinco o diez excepciones tempranas, deberíamos ser capaces de utilizar $(4p,5p)$ , y algún tiempo después de levantarse a $1000$ más o menos, $(9p,10p)$ e incluso $(19p,20p)$ lo que nos da límites mucho más estrictos en esos intervalos.
Creo que eso lo cubre todo. ¿Qué elemento crucial me he perdido esta vez? Específicamente, ¿es el factor de emparejamiento una parte crítica complicada que anula todo el propósito si lo omito, o es tan sencillo de probar como espero?
(...de hecho, desde que escribí esto, he hecho una serie de pruebas con ese principio general de correspondencia de factores. Es ROBUSTO . Esto es lo mínimo que puede hacer de forma fiable. Sigue sin ser una prueba, pero ahora estoy mucho más convencido de que sería fácil encontrar una).
