Toda conjetura relacionada con números primos tiene, de una forma u otra, gran interés y, por qué no decirlo, cierta belleza. Y la que os presento hoy, la conjetura de «escalada hasta un primo» (en inglés, «climb to a prime»), es otro ejemplo más de ello.
La conjetura de escalada hasta un primo trata, como su propio nombre indica, de, partiendo de un número, ir «escalando» a través de otros números hasta llegar a un número primo. Aunque no he conseguido encontrar el año en el que la planteó, fue propuesta por John Horton Conway, matemático británico del cual ya hemos hablando por aquí en algunas ocasiones, por ejemplo en Look-and-say y la constante de Conway, La circunferencia de Conway, El porqué de la «universalidad cuadrática» del 15 y del 290 y en La Regla del Fin de los Días.
La conjetura es sencilla de plantear, pero primero vamos a ver qué es eso de escalar hasta un primo. Tomamos un número cualquiera y lo descomponemos en factores primos (colocados en orden ascendente). Si el número era primo, ya hemos acabado; si no era primo, construimos el número formado por los factores primos y los exponentes de los mismos colocados tal cual salen en la factorización. Con el número obtenido hacemos lo mismo que antes. La escalada finaliza cuando obtengamos un número primo.
Como esto puede parecer un poco lioso, veamos un ejemplo. tomemos el número . Como
, si llamamos
a la función que convierte a un número en el número que resulta al colocar factores primos y exponentes, tenemos que
. Este número no es primo, por lo que tenemos que hacer con él lo mismo que hicimos con el 30:
y, por tanto,
. Como
es primo, aquí termina la escalada hasta un primo del número 30.
Veamos un nuevo ejemplo, esta vez con el 333:
Como es primo, ya hemos terminado la escalada del 333.
Está claro, ¿verdad? Bien, pues la conjetura de Conway sobre «escalada hasta un primo» dice que todo número natural mayor o igual que 2 termina su escalada en un número primo. Como los números primos no tienen que «escalar» (ya han llegado a un número primo, ellos mismos), para dar respuesta a esta conjetura debemos conseguir una de estas dos cosas:
- Demostrar que todo número compuesto «escala» hasta un número primo con el proceso mencionado antes.
- Encontrar un contraejemplo, que sería un número compuesto que no consiga «escalar» hasta un número primo con el método propuesto.
¿Qué pensáis? El propio Conway decía que parecía que él era el único que creía que era cierta, aunque daba un número pequeño para el cual todavía no se había verificado: el 20. Podéis probar vosotros mismos con otros números, pero no os aconsejo el 20, ya que para él el proceso se alarga más de 100 pasos…¡¡y parece ser que todavía no se sabe si culmina en un primo o no!!
Pero esto no nos vale como contraejemplo, ya que el hecho de no saber si el 20 «escala» hasta un primo no nos asegura nada. ¿Será cierta la conjetura o, por el contrario, existirá algún contraejemplo?
Bien, despejemos ya la incógnita: la conjetura es falsa. Hace pocos meses, James Davis encontró un contraejemplo de la misma: el número 13532385396179. ¿Por qué es un contraejemplo? Pues es muy sencillo de ver si atendemos a su factorización en primos:
Es decir, . Como es un número compuesto y
lo convierte en sí mismo (es un punto fijo de
), tenemos ante nosotros un número que no consigue «escalar» hasta un número primo. Señor Conway, estaba usted equivocado, su conjetura sobre «escalada hasta un primo» no es cierta.
Como alguno habrá pensado ya, éste no es el único contraejemplo, ya que con él podemos construir otros. Tomemos el número 45214884853168941713016664887087462487 y descompongámoslo en factores primos. ¿Os atrevéis? Venga, os doy yo la factorización:
Por tanto:
que es el número anterior que hemos visto que transforma en sí mismo. Tenemos entonces un nuevo contraejemplo, el número 45214884853168941713016664887087462487 tampoco es capaz de «escalar» hasta un primo.
Este número está construido a partir del anterior para «forzarlo» a que sea un contraejemplo. Existen otras maneras de construir contraejemplos a partir de alguno ya conocido, y sería magnífico que jugarais con ellos y nos mostrarais vuestros descubrimientos en los comentarios.
Por cierto, esta conjetura de la «escalada hasta un primo» de Conway forma parte de una lista de cinco problemas que el propio Conway propuso, ofreciendo una recompensa de 1000$ para quien consiguiera dar respuesta a alguna de ellas. James Davis ya se ha llevado los 1000$ correspondientes a ésta, pero (hasta donde yo sé) los otros cuatro problemas siguen sin respuesta. Si alguien está interesado en intentar alguno de ellos, aquí los tenéis:
Fuentes y más información:
- What’s so special about 13532385396179?, en Glad Hobo Express.
- 13532385396179 precursors, también en Glad Hobo Express.
- 13532385396179 doesn’t climb to a prime, en The Aperiodical.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
La gente muy creativa, como Conway se deja sobrellevar, a veces, por extrañas lagunas, no ven lo obvio en medio de la maraña. Bastaba con escribir un programa muy sencillo, en Pari GP, por ejemplo y en solo unas 24 horas, con un PC rápido de ahora, hubiera encontrado este número. No soy un experto en heurística, ni matematico. Ni siquiera soy físico (esos experimentalistas que dicen que inventan algo), pero creo que existirían infinitos números, aunque dispersos, que concatenados sus factores primos, incluida su multiplicidad, si es mayor que 1, nos reproducen el número en cuestión. Y si optamos… Lee más »
Entrando en el campo de las conjeturas podría ser que el conjunto de los números que no escalan a primo (sin buscar carácter cíclico en otro anterior) es infinito y, también, el de los números que sí escalan a primo es infinito. Ahora ya a un asunto más concreto: ¿podría el moderador de este magnífico blog, o algún amable lector, indicarme como se logra factorizar números con tantísimos dígitos? Me parece haber contado 38 dígitos en uno de ellos ¿Existe alguna aplicación que aborde el problema de manejar tantos dígitos y su factorización? La factorización en factores primos a la… Lee más »
Prueba Pari GP gratuito y que se descarga en pocos segundos.
? factor(45214884853168941713016664887087462487)
%1 = [13,1;5323,8;5396179,1] En mi móvil chino y barato esta factorización ha tardado mucho menos de un segundo.
Y en solo dos segundos:
? factor(1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111)
%6 = [11,1;41,1;101,1;251,1;271,1;3541,1;5051,1;9091,1;21401,1;25601,1;27961,1;60101,1;7019801,1;182521213001,1;14103673319201,1;78875943472201,1;1680588011350901,1]
En solo dos segundos en mi móvil barato :
? factor(10^101+1)
%2 = [11,1;607,1;809,1;1213,1;1327067281,1;11500490394117824585468796003575163076836624586334794818271756072956027758946488969,1]
En solo un segundo :
? factor(10^101+3)
%3 = Mat([100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003,1])
He aquí lo que los estadounidenses llaman un near-miss de solo 6 dígitos, que mi viejo PC tardo 4 segundos en hallar ( y yo bastante más en escribir el programa) :
264128 = 2^6*4127
Claro que tiene que ser así, puesto que en un número par, los requisitos de autosemejanza plena no se pueden cumplir. Pero solo hay una unidad de diferencia.
Escrito desde un móvil con acentuación automatica claramente deficiente de Google.
Menos mal que hay alguien ahí. Gracias Robín García por tus indicaciones, voy a descargar la aplicación que me recomiendas de Pari GP. Esperemos sea amigable, digo esto porque yo huyo de todo lo que suene a C, como Java, Python y otras especies. Me arreglo en lo que a la programación se refiere, pásmate, con QB64 que es un BASIC moderno y estructurado, lógicamente gratuito, y que es capaz de hacer cosas verdaderamente increíbles. Hablando de aplicaciones gratuitas te comento una que estoy estudiando que se llama XPCalc & XICalc y que, a juzgar por lo poco que he… Lee más »
Pari GP es muy fácil de utilizar y hay manuales rápidos en la red, así como ayudas en el propio bloque del programa.
He aquí otro «near miss» relacionado con los números de Conway: 351446283 = 3^5*1446281
Hola. ¿Alguien sabe donde estan escritos los problemas de Conway en castellano? Gracias.
El tema de los números primos es el que mas me apasiona, un hermoso misterio sin duda, en lo personal me fascina buscar patrones y propiedades en ellos, una que me parece curiosa, es el hecho de que sumando ciertas tercias de números primos consecutivos, como resultado se obtiene un numero primo, 7+11+13=31, 17+19+23=59, 29+31+37=97, 41+43+47=131, 53+59+61=173, 67+71+73=211, 79+83+89=251, 101+103+107=311, 109+113+127=349, 139+149+151=439, 163+167+173=503