Números primos del tipo HP (homeprimes)

Como es costumbre en este blog, se extraen temas de los cálculos que publicamos en Twitter @connumeros. El día 31/01/2023, estudiando el número 31123 vimos que OEIS lo calificaba como homeprime con cuatro orígenes. Mantengo esta denominación en inglés porque no he encontrado traducción adecuada. Lo que sigue no tiene un gran interés matemático, pero supone un cierto esfuerzo en la búsqueda de algoritmos y su codificación.

La idea para estos números es la siguiente: Dado un número compuesto cualquiera, como por ejemplo, 42, lo descomponemos en factores primos y los concatenamos de menor a mayor para formar otro número (en base 10). En este caso, 42=2*3*7, luego concatenamos y llegamos a 237. Si existen primos repetidos, no usamos exponentes, sino que los mantenemos repetidos. Por ejemplo, 24=2³*3 lo convertimos en 2223. Si el resultado es compuesto, como es el caso de 237=3*79, lo convertimos en 379. Así seguimos hasta llegar a un primo. Este sería el caso de 379, luego sería home prime, y lo podemos representar como HP(42). Un número primo p cumplirá HP(p)=p.

Esto es un entretenimiento sin más trascendencia, publicado por primera vez por Jeffrey Heleen en 1990. Al experimentar con esta idea se descubrió que era un algoritmo que podía dar más juego de lo esperado. Por ejemplo, la función HP no es biunívoca. Puedes comprobar que 379 es imagen de tres números compuestos distintos: 42, 74, 237 y el mismo 379. Esto es lo que parece ocurrir con el número 31123, que posee cuatro oígenes. Lo iremos descubriendo paso a paso.

Algoritmo básico

Podemos idear una función para la operación básica de concatenar factores, y luego pasaremos a reiterarla.

Para hoja de cálculo

La hoja más usada, Excel, presenta el problema de que al representar un número mediante texto le añade un espacio en blanco. Por eso solemos usar en este blog la función ajusta, que le elimina ese carácter si ha lugar. La hemos usado varias veces aquí.

Function ajusta$(a)

Dim d$

 

d$ = Str$(a) ‘Convierte el número en texto

While Left$(d$, 1) = " " ‘Va eliminando espacios en blanco

d$ = Right$(d$, Len(d$) - 1)

Wend

ajusta$ = d$

End Function

Con ella podemos concatenar caracteres sin problema. A continuación vemos la operación básica de concatenar factores primos:

Function concfactores(n)

Dim f, a

Dim s$

s = "" ‘Se inicia una cadena de texto

a = n 'Copia el valor de n

f = 2 'Inicia el listado de primos

While f <= a 'Recorre los primos posibles

While a / f = a \ f

a = a / f: s = s + ajusta(f) ‘Si es factor, concatena

Wend

If f = 2 Then f = 3 Else f = f + 2 ‘Avanza a otro primo

Wend

concfactores = Val(s) ‘Convierte la concatenación en número

End Function

Podemos aplicar esta función a cualquiera de nuestros ejemplos, 42, 237, 74 o 379 para comprobar su funcionamiento. Por ejemplo, CONCFACTORES(144)= 222233.

Es fácil ver que esta operación no disminuye el valor de un número, por lo que si reiteramos, siempre nos encontraremos con una sucesión no decreciente.

Charles R Greathouse IV propone en OEIS un procedimiento PARI similar, pero que se aprovecha de que este lenguaje ya suministra el vector factor con los factores primos y sus exponentes, y solo hay que extraerlos y añadirlos a un Str. El final, con eval(s) lo convierte en número.

step(n)=my(f=factor(n), s=""); for(i=1, #f~, for(j=1, f[i, 2], s=Str(s, f[i, 1]))); eval(s)

Si lo que deseamos es reproducir la función concfactores podemos usar este otro código, que no se apoya en la existencia del vector factor:

step(p)={my(s="",a=p,f=2);while(f<=a,while(a%f==0,a=a/f;s=Str(s,f));f=f+1+(f<>2));eval(s)}

print(step(144))

Está preparado para concatenar los factores de 144, con el resultado de 222233.

Búsqueda del HP(p)

Con esta función ya podemos reiterar hasta llegar al primer primo, el homeprime:

Function hp(n)

Dim p, q, r

 

p = n ‘Copia n

q = 1 ‘Inicia variable auxiliar

 

Do ‘Bucle de búsqueda

r = p

 p = concfactores(p) ‘Da un paso de concatenación

 q = p

Loop Until r = q ‘Si son iguales, es que es primo. Final.

hp = p

End Function

 

Esta función es útil si las iteraciones no llegan muy lejos, pues se entra en la zona en la que las hojas de cálculo pierden exactitud. Probamos con algunos ejemplos:

Observamos que, mientras los primeros llegan al homeprime sin problemas, el 222 sobrepasa la posibilidades de Excel. Podemos seguir  sus trayectorias paso a paso:

Los primeros se van estabilizando hasta llegar a un número primo, pero el 222 sigue buscando hasta que sobrepasa la capacidad de cálculo.

Podemos traducir el algoritmo a PARI, que admite todas las cifras:

step(p)={my(s="",a=p,f=2);while(f<=a,while(a%f==0,a=a/f;s=Str(s,f));f=f+1+(f<>2));eval(s)}

hp(n)={my(p=n,q=1);until(r==p,r=p;p=step(p);q=p);p}

print(hp(222))

 

Se conjetura que cada compuesto posee un homeprime, pero en algunos, como el 49, no se conoce el final del proceso. Tampoco se ha logrado en 77, 49, 146, 246, 312, 320…En nuestro equipo ha resultado difícil seguir el proceso para 222. Se ha llegado a estos pasos:

222, 2337, 31941, 33371313, 311123771, 7149317941, 22931219729, 112084656339, 3347911118189, 11613496501723, 97130517917327, …

El problema reside en la factorización, que puede llegar a ser inabordable.

Búsqueda de los orígenes

Nos queda un último trabajo, y es buscar los compuestos que terminan en un número primo dado, como el 31123 del primer ejemplo. Podíamos recorrer los compuestos menores que el primo, aplicarles la función hp(n) y comprobar si coincide con el primo estudiado, pero, como vimos en el párrafo anterior, el proceso se puede bloquear al llegar a ciertas factorizaciones.

Para evitar estos bloqueos, reproduciremos los pasos, pero parando el proceso si se sobrepasa el número primo dado. Con la siguiente función se resuelve el problema, aunque aumentamos algo la complejidad:

Function origenhp$(n)

Dim i, j, m

Dim s$

 

s = "" ‘Contenedor de las soluciones

If esprimo(n) Then ‘Solo actúa sobre primos

For i = 4 To n – 1 ‘Recorre los posibles compuestos

m = 0 ‘Indicador de solución

j = concfactores(i) ‘Damos pasos hacia HP(i)

While j <= n And m = 0 ‘Nos detenemos al llegar a n

If j = n Then s = s + Str$(i) + ", ": m = 1 ‘Hay un origen

If esprimo(j) Then m = 1 ‘Se llega a un primo menor que n

If m = 0 Then j = concfactores(j) ‘Si no es solución, se avanza

Wend

Next i

End If

origenhp = s

End Function

 

Con este procedimiento encontraremos los orígenes de un presunto homeprime. Lo podemos aplicar a nuestro ejemplo de 379, y resultan los orígenes conocidos, a los que hay que añadir él mismo:

Queda comprobado su funcionamiento. Ahora hay que volver al principio, y es ver qué tres orígenes tiene el número 31123. Tardará un poco en dar la solución, que es:

Hemos resuleto el problema, los cuatro orígenes son 413,  759,  3369, 31123. En la cuarta fila se compruebas los tres primeros con la función HP. En la siguiente tabla vemos los pasos necesarios para llegar a 31123.

Para emprender otras vbúsquedas posibles, insertamos el código PARI que traduce este procedimiento:

step(p)={my(s="",a=p,f=2);while(f<=a,while(a%f==0,a=a/f;s=Str(s,f));f=f+1+(f<>2));eval(s)}

origenhp(n)={my(i,j,m,s="");if(isprime(n),for(i=4,n-1,m=0;j=step(i);while(j<=n&&m==0,if(j==n,s=Str(s,", ",i);m=1);if(isprime(j),m=1);if(m==0,j=step(j)))));s}

print(origenhp(31123))

 

Esto ha sido una práctica sobre algoritmos, porque la cuestión carece de verdadero interés matemático, pero como tantas otras, es útil como pasatiempo y para pulir códigos. En nuestro caso, nos resultó interesante obviar las limitaciones de las hojas de cálculo en el tratamiento de números naturales grandes. Se logra a medias, porque con instrumentos más potentes siguen existiendo lagunas también.