La conjetura de la “escalada hasta un primo”

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.

John Horton Conway

John Horton Conway. Fuente.

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 30. Como 30=2 \cdot 3 \cdot 5, si llamamos f a la función que convierte a un número en el número que resulta al colocar factores primos y exponentes, tenemos que f(30)=235. Este número no es primo, por lo que tenemos que hacer con él lo mismo que hicimos con el 30: 235=5 \cdot 47 y, por tanto, f(235)=547. Como 547 es primo, aquí termina la escalada hasta un primo del número 30.

Veamos un nuevo ejemplo, esta vez con el 333:

  • 333=3^2 \cdot 37 \longrightarrow f(333)=3237
  • 3237=3 \cdot 13 \cdot 83 \longrightarrow f(3237)=31383
  • 31383=3^2 \cdot 11 \cdot 317 \longrightarrow f(31383)=3211317
  • 3211317=3^2 \cdot 17 \cdot 139 \cdot 151 \longrightarrow f(3211317)=3217139151
  • 3217139151=3 \cdot 97 \cdot 2297 \cdot 4813 \longrightarrow f(3217139151)=39722974813

Como 39722974813 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:

  1. Demostrar que todo número compuesto “escala” hasta un número primo con el proceso mencionado antes.
  2. 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:

13532385396179=13 \cdot 53^2 \cdot 3853 \cdot 96179

Es decir, f(13532385396179)=13532385396179. Como es un número compuesto y f lo convierte en sí mismo (es un punto fijo de f), 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:

45214884853168941713016664887087462487=13 \cdot 5323^8 \cdot 5396179

Por tanto:

f(45214884853168941713016664887087462487)=13532385396179

que es el número anterior que hemos visto que f 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:

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. 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 por añadir el 1 para tal multiplicidad ? Y si situamos el dígito de la multiplicidad antes del factor ?

    Publica una respuesta
  2. 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 que me refiero es la del siguiente número:

    45214884853168941713016664887087462487

    que el autor del artículo da el resultado, previendo que nadie será capaz de calcular, como es mi caso.

    Saludos y enhorabuena por el artículo.

    Publica una respuesta
    • 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]

      Publica una respuesta
      • 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]

        Publica una respuesta
  3. En solo un segundo :

    ? factor(10^101+3)
    %3 = Mat([100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003,1])

    Publica una respuesta
  4. 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.

    Publica una respuesta
    • 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 visto, es un “bastinazo”.

      Bueno reitero mi agradecimiento y saludos.
      Manuel

      Publica una respuesta
      • 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

        Publica una respuesta
  5. Hola. ¿Alguien sabe donde estan escritos los problemas de Conway en castellano? Gracias.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.