Iteración basada en la suma de cuadrados de cifras (5) - Alcances

Alcances entre números

Una cuestión amena es la de averiguar si un número de cierto tipo (primo, cuadrado, triangular,…) es alcanzable desde otro del mismo tipo mediante una recurrencia consistente en ir sumando a cada término el cuadrado de las cifras.

Por ejemplo, 23 es alcanzable desde 11, ambos primos, porque 13=11+1^2+1^2, 23=13+1^2+3^2

Todos los números sin ningún tipo especial son alcanzables, salvo los colombianos cuadráticos, ya estudiados aquí: 1, 3, 4, 5, 7, 8, 9, 10, 14, 15, 16, 18, 19, 21, 22, 25, 27, 28,…

El resto, por ejemplo el 6 y el 12 o el 13, son alcanzables desde otro número:

2+2^2=6, 3+3^2=12, 11+1^2+1^2=13.

Además, todos los son con un solo paso, pues basta elegir el último término de cualquier recurrencia.

Pasamos entonces a estudiar diversos tipos:

Números primos

Hemos preparado una función en Excel que nos puede ayudar a decidir si un número es alcanzable en el sentido que le hemos dado a la palabra. El listado que sigue es la versión entre primos, pero se cambia fácilmente por otro tipo:

Public Function alcance$(n)

'desde el final del alcance hacia atrás para ver si alguno lo alcanza

Dim i, j

Dim s$

If Not esprimo(n) Then alcance = "NO": Exit Function 'Si no es primo, renunciamos.

s$ = "" ‘Contendrá las soluciones

i = 1

While i <= n And s = ""

If esprimo(i) Then 'Puede ser otra condición

j = i

While j < n

j = j + sumacifras(j, 2)

If j = n Then s = s + Str$(i)

Wend

End If

i = i + 1

Wend

If s$ = "" Then s$ = "NO"

alcance = s

End Function

Si no existen soluciones, devuelve un “NO” y si las hay, el conjunto de ellas. Aquí tienes la función aplicada a los números primos entre 20 y 80:

Solo son alcanzables 23, 41 y 67. Ampliamos el rango de búsqueda para confeccionar una tabla. Aquí tienes los primeros primos alcanzables:

Los puedes obtener en PARI con un algoritmo similar al de Excel:

forprime(n=1,1000,s=0;i=1;while(i<=n&&s==0,if(isprime(i),j=i;s=0;while(j<n&&s==0,j=j+norml2(digits(j));if(j==n,s=1;write1("final.txt",n,", "))));i+=1))

13, 17, 23, 41, 67, 101, 103, 107, 113, 127, 131, 157, 163, 181, 191, 199, 227, 251, 263, 269, 271, 281, 311, 379, 421, 457, 461, 467, 499, 509, 521, 541, 547, 563, …

Final de la recurrencia

Podemos plantearnos la cuestión opuesta, la de si dado un número primo, llega a alcanzar a otro primo en la recurrencia. En este tipo de cuestiones el problema que solemos tener es el de fijar una cota de búsqueda. En la sucesión A094830 se nos da una pista, pues contiene los pasos que se han de dar para cada primo.

A094830              Start with x = n, repeatedly replace x with x + sum of squares of digits of x until you reach a prime; sequence gives number of steps.                  

1, 0, 0, 6, 0, 4, 0, 11, 5, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 5, 13, 9, 0, 4, 11, 12, 17, 3, 0, 8, 0, 8, 7, 1, 7, 3, 0, 5, 7, 4, 0, 3, 0, 3, 7, 8, 0, 2, 2, 2, 6, 3, 0, 10, 2, 3, 1, 3, 0, 3, 0, 2, 2, 18, 2, 11, 0, 2, 6, 9, 0, 10, 0, 1, 1, 2, 5, 1, 0, 16, 2, 8, 0, 3, 11, 6, 10, 2, 0, 4, 1, 15, 2, 1, 9, 2, 0, 7, 7, 1

Según esta tabla, el máximo número de pasos de recurrencia para números pequeños es de 18, contando primos y compuestos. Podemos buscar, por ejemplo, hasta 25 iteraciones y marcar aquellos primos en los que ese número sea insuficiente.

Entre los primos menores que 5000 aparecen ya ejemplos en los que no basta con 25 iteraciones:

167, 191, 1709, 1783, 1831, 4229, 4421, 4621, 4787, 4793, 4817, 4969, 4993

Si aumento a 50, prácticamente todos los primos de ese rango alcanzan a otro primo:

Podemos conjeturar que siempre se alcanza un primo, pero actualmente no se sabe si es cierto o no.

Son muchos los que se repiten en la segunda columna. Llama la atención la frecuencia con la que aparecen. Con una nueva función que no vamos a insertar aquí, descubrimos que esos números provienen de muchos inicios primos en la recurrencia. Por ejemplo, 10391 proviene de 243 recurrencias distintas.

Números cuadrados

Los primeros cuadrados alcanzables por otro cuadrado son estos:

 

En la primera columna el alcanzable y en la tercera el origen de la recurrencia

Hemos adaptado la función de alcance a cuadrados

Public Function alcance$(n)

Dim i, j, m

Dim s$

If Not escuad(n) Then alcance = "NO": Exit Function 'U otra condición

s$ = ""

i = 1

m = 0

While i * i <= n And s = ""

'If escuad(i) Then 'puede ser otra condición, e incluso i=i

j = i * i

While j < n

j = j + sumacifras(j, 2)

If j = n Then s = s + Str$(i): m = m + 1

Wend

'End If

i = i + 1

Wend

If s$ = "" Then s$ = "NO"

alcance = s$

End Function

Con PARI

for(n=1,500,m=n*n;s=0;i=1;while(i<=n&&s==0,j=i*i;while(j<m&&s==0,j=j+norml2(digits(j));if(j==m,s=1;print1(m,", ")));i+=1))

Obtenemos el listado:

81, 196, 1024, 1156, 1225, 1600, 3600, 4489, 4624, 5625, 7056, 7225, 10201, 12100, 13225, 13456, 15625, 28900, 37636, 40401, 43681, 46225, 50625, 55696, …

Problema inverso

Podemos estudiar hasta donde llega cada origen. Al igual que con números primos, conjeturaremos que todos los cuadrados finalizan en otro cuadrado con un número de pasos adecuado en la recurrencia.

Hemos ido aumentando el máximo de pasos en la misma y, si llegamos a 2000 iteraciones, aún quedan estos tres al menos:

197136, 200704, 201601

Con 5000 iteraciones, los que quedan fuera se acercan a 300000:

2961841, 2965284, 2968729,…

Por último, con 10000 iteraciones, todos los cuadrados inferiores a 9000000 alcanzan a otro cuadrado. Podemos conjeturar que los cuadrados terminan alcanzando a otro cuadrado.

Triangulares

Sólo insertaremos la tabla de los primeros triangulares alcanzables por otro triangular:

Como en otros temas parecidos, una vez que hemos construido funciones para las búsquedas importantes, detenemos aquí los posibles otros casos (cubos, oblongos,…) y los dejamos como ejercicio.