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.

Relaciones entre PHI(n) y TAU(n)

Función TAU

Las funciones PHI y TAU, aplicadas a un número entero positivo, tienen algo de complementarias. La segunda, TAU, cuenta los divisores de un número N. También es llamada función divisor, o D(x). En el caso de un número primo p, es claro que los divisores son 1 y p, luego la función TAU valdrá 2 en este caso. 

Igualmente, es fácil deducir que para potencias de un número primo, p^k, TAU(p^k)=1+k

Puedes acudir  a nuestra publicación Funciones multiplicativas (http://www.hojamat.es/publicaciones/multifun.pdf)

para consultar la fórmula general.

TAU(N)=(1+a₁)(1+a₂)…(1+a_k)

a₁, a₂, …a_k son los exponentes de los factores primos de N.

Por ejemplo, TAU(24)=TAU(2³*3)=(1+3)(1+1)=8

Efectivamente, los divisores de 24 son ocho: 1, 2, 3, 4, 6, 8, 12 y 24.

Función PHI

La función j(n) (indicatriz o indicador de Euler) es el cardinal del conjunto de elementos inversibles en Z_n o bien el conjunto de números coprimos con n y menores que él contando el 1. Esta segunda versión es más clara y adecuada al estudio que vamos a iniciar: cuenta los números primos con N y menores que N, con el añadido del 1.

La función indicatriz de Euler es multiplicativa, porque si m y n son coprimos, se cumple que

j(m). j(n) = j(m.n)

Su fórmula explícita es

(p_i son sus factores primos)

Por ejemplo, el número 18=3²*2 posee un valor de PHI igual a 18(1-1/2)(1-1/3)=6, Podemos comprobar que los números coprimos con 18 y menores que él son: 1, 5, 7, 11, 13 y 17. En total 6.

En los números primos p el valor de PHI(p)=p-1, como es fácil deducir.

En algunos lenguajes de programación recibe el nombre de función totient.

Relaciones entre TAU y PHI

Para cualquier número natural N, los números comprendidos entre 1 y N pertenecen a uno de estos tres conjuntos:

{A} Divisores de N: los cuenta la función TAU

{B} Coprimos con N incluido el 1: los cuenta la función PHI. En ambos conjuntos se encuentra el 1, lo que hace que no sean disjuntos.

{C} Resto de números: son aquellos números r que no son divisores de N ni coprimos con él: tienen un m.c.d con N que es mayor que 1 y menor que r.

Por ejemplo, en el número 30, los conjuntos serían:

{A} = {1, 2, 3, 5, 6, 10, 15, 30}, pues 30=2*3*5 y TAU(30)=(1+1)(1+1)(1+1)=8

{B} = {1, 7, 11, 13, 17, 19, 23, 29}, y PHI(30)=30(1-1/2)(1-1/3)(1-1/5)=1*2*4=8

{C} = {4, 8, 9, 12, 14, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28}, que son 15 elementos.

La suma de los cardinales de los tres conjuntos es 31, porque el 1 está repetido, y 8+8+15=31.

Con este planteamiento se adivina que pueden existir varias relaciones distintas entre los tres cardinales. El primero lo recoge TAU y el segundo PHI. El tercero lo dejamos como complemento de los otros dos.

PHI=TAU

Según lo publicado en http://oeis.org/A020488, solo existen estos casos: 1, 3, 8, 10, 18, 24, 30.

Por ejemplo, en N=10, TAU(10)=TAU(2*5)=(1+1)(1+1)=4 y PHI(10)=10(1-1/2)(1-1/5)=1*4=4.

No debemos conformarnos con lo publicado. Puedes comprobarlo con las dos versiones sencillas para el cálculo de ambas funciones que hemos preparado con el Basic de las hojas de cálculo. Para no interrumpir el estudio, las incluimos en un Anexo.

Jud McCranie da razones en esa página de por qué no hay más soluciones, y lo probó A. P. Minin  1894 . Lo comprobamos con nuestras funciones de hoja de cálculo:

El único número primo de la lista es 3, pues TAU(p)=2  para cualquier primo, y PHI(p)=p-1. Luego ha de ser 2=p-1 y p=3.

PHI doble de  TAU

También existen pocos casos (http://oeis.org/A062516):

5, 9, 15, 28, 40, 72, 84, 90 y 120.

Con nuestras funciones tenemos:

TAU doble de PHI

Sólo hay dos casos:

Otros casos

Con PHI=TAU+1 parece que no hay ninguno, y con PHI+1=TAU, solo dos casos:

PHI múltiplo de TAU

Si solo tenemos en cuenta múltiplos propios, cuyo cociente es mayor que 1, nos aparecen muchas soluciones. Las primeras son:

Si la relación de múltiplo es a la inversa, solo aparecen las soluciones ya vistas en las que TAU es el doble de PHI.

Por último, una curiosidad:

Pitagóricos

PHI y TAU son ambos catetos de una terna pitagórica. Solo se encuentran cinco soluciones:

20, 36, 60, 100, 300

Según el siguiente cuadro, en las ternas formadas sus elementos son múltiplos de las primitivas {3, 4, 5} o {9. 40, 41}.

Esta sucesión estaba inédita, y la hemos publicado en http://oeis.org/A308664. En esa página podrás leer un razonamiento de de Giovanni Resta con el que justifica que la sucesión sea finita.

  

ANEXO

Listado de la función PHI (Basic de Excel)

Public Function euler(n)

Dim f, a, e

Dim es As Boolean

'Calcula la indicatriz de Euler de un número

a = n ‘Copia el valor de n

f = 2 ‘Inicia el listado de primos

e = n ‘Inicia el valor de PHI

While f <= a ‘Recorre los primos posibles

es = False ‘Variable que indica si hemos llegado a un divisor primo o no

While a / f = a \ f ‘Si es un factor, se va eliminando del valor de n

a = a / f: es = True

Wend

If es Then e = e * (f - 1) / f ‘Si se ha encontrado un factor primo, se incorpora a PHI

If f = 2 Then f = 3 Else f = f + 2 ‘Busca el siguiente primo

Wend

euler = e

End Function

Listado de TAU

Es muy parecido al anterior

Public Function tau(n)

Dim f, a, e, exx

a = n ‘Copia el valor de n

f = 2 ‘Inicia el listado de primos

e = 1  ‘Inicia el valor de TAU

While f <= a ‘Recorre los primos posibles

exx = 0

While a / f = a \ f

a = a / f: exx = exx + 1 ‘Incrementa el exponente del factor primo encontrado

Wend

e = e * (1 + exx) ‘Construye TAU

If f = 2 Then f = 3 Else f = f + 2

Wend

tau = e

End Function

Unidos por el SOPF

Es tradición en este blog aprovechar cuestiones surgidas en Twitter. La de hoy se basa en una planteada por Juan Carlos Amez, @juankaamez, el día 28 de septiembre de 2019.

¿Podríamos probar que para cualquier valor k existe siempre al menos un valor n que verifica que: sopf(n)=sopf(n+k)?

Como la cuestión directa puede tener una respuesta complicada, abordamos antes la inversa, que dado un N debamos encontrar el K correspondiente.

Recordemos: la función SOPF(N) es la suma de los factores primos de N tomados sin repetición. Así SOPF(6)=2+3=5 y SOPF(12)=5 también, porque ambos tienen los mismos factores primos 2 y 3.

Primera cuestión: Encontrar K para un N dado

Existe una forma sencilla de evaluar la función SOPF sin necesidad de descomponer N en factores primos. Su código para Excel puede ser este:

Public Function sopf(n)

Dim f, a, e, g

a = n

f = 2 ‘Esta variable recorrerá los primos

e = 0 ‘Aquí se sumarán los factores primos

g = 0 ‘Recogerá los divisores primos

While f <= a

While a / f = a \ f ‘Se encuentra un factor

g = f: a = a / f ‘Tomamos nota en g y eliminamos ese factor

Wend

If g <> 0 Then e = e + g: g = 0 ‘Se suman factores en SOPF

If f = 2 Then f = 3 Else f = f + 2 ‘Se buscan nuevos factores

Wend

sopf = e

End Function

Con ella podemos ir descubriendo ya las coincidencias en los valores de SOPF. En la tabla podemos comprobar algunas.

Queda claro en ella que comparten valores de SOPF aquellos números que coinciden en sus factores primos sin contar repeticiones. Los tres primeros se basan en 2+3=5, los segundos en 3+7=10 y los últimos en 2+5=7.

Basta restar dos de ellos para tener una solución a la primera cuestión:

SOPF(6)=SOPF(6+6)=SOPF(6+138)

SOPF(21)=SOPF(21+42)=SOPF(21+126)

Esto resuelve la cuestión para un N dado y K desconocido: los valores posibles de K para un N dado son infinitos. Basta aumentar los exponentes de los factores primos de N y después restar.

Esto tiene una traducción a fórmula: 

Es decir, serán valores válidos de K aquellos formados por la descomposición factorial de N multiplicada a su vez por un producto similar al que restamos una unidad. Los exponentes r, s y t pueden ser nulos (salvo uno, para evitar la solución K=0)

Por ejemplo, para 12=2²*3, K podría tener cualquiera de estas estructuras:

2²*3*(2³-1)=84, que equivaldría a

SOPF(12)=SOPF(12+84)=SOPF(96)=5

2²*3*(2*3-1)=60, luego SOPF(12)=SOPF(12+60)=SOPF(72)=5

Así que la primera cuestión ya está resuelta, con la multiplicidad de soluciones de K `para cualquier N.

Segunda cuestión: Dado un valor de K, encontrar posibles valores de N

Esta cuestión es mucho más complicada, pues los valores de N no están acotados. Por ejemplo, para K=87654321, hemos encontrado un valor de N de 13761, lo que ha supuesto recorrer más de trece mil números. Efectivamente es una solución, porque

SOPF(13761)=153, ya que 13761=3²*11*139, y 3+11+139=153.

y

SOPF(13761+87654321)=SOPF(87668082)=153, porque 87668082=2*3⁹*17*131, con lo que SOPF(87668082)=2+3+17+131=153.

No parece sencillo demostrar que la conjetura planteada sea verdadera. Son muchas las coincidencias entre sumas de primos, como 29+5=31+3=34 y la herencia de los valores de SOPF que vimos en la primera cuestión, por lo que se puede confiar en que para todo K exista un N que cumpla SOPF(N)=SOPF(N+K). Pero demostrarlo es otra cuestión bien distinta.

Sí podemos presentarlo como conjetura, y esto es lo que figura en la página web

https://www.primepuzzles.net/conjectures/conj_025.htm

rotulada como conjetura 25. En ella puedes consultar algunos intentos de demostración de la misma.

Si no se sabe demostrar la conjetura, sí se puede establecer una búsqueda del mínimo valor de N para cada K. 

Esto lo tienes publicado en http://oeis.org/A065925, y ahí remiten a la conjetura 25. 

Los primeros valores de N son 5, 2, 7, 4, 114, 2, 5, 8, 13, 10, 25, 4, 5, 2, 19, 16, 85, 6, 5, 5, 209, 22, 25, 3, 493, 26, 31, 4, 20, 2, 5, 32, 7, 34, 516, 12, 33, 38, 10, 10, 99, 6, 5, 44, 57, 46, 25, 6,…

Aquí podemos comprobar la conjetura con dos herramientas. Para Excel usaremos una “atrevida” función, que encontrará N para un K dado. La llamamos así porque se basa en un bucle que puede no tener final si la conjetura es falsa, con lo que habría que detener Excel antes de que terminara el proceso. Su código es

Function dsopf(k)

Dim d, n

d = 0

n = 2

While d = 0 ‘En este while radica el peligro, ya que puede no detenerse

If sopf(n) = sopf(n + k) Then d = n

n = n + 1

Wend

dsopf = d

End Function

Se supone definida ya la función SOPF.

Esta función devuelve un 0 si no encuentra ningún valor de N. En realidad no lo devolvería, porque la ejecución no podría detenerse. Se ve que hemos confiado en la conjetura.

Con esta función es fácil reproducir la lista de valores de N publicada en OEIS:

También podemos probar con valores grandes de K, como el número de fecha de la Navidad de este año:

DSOPF(251219)=3256.

Comprobamos: SOPF(3256)=50, SOPF(251219+3256)=SOPF(254475)=50

Parece que podemos confiar en que la conjetura sea cierta. Como Excel tiene una capacidad limitada cuando trata con números grandes, traducimos la cuestión al lenguaje PARI:

sopf(n)= my(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); s

dsopf(k)= my(d=0,n=2);while(d==0,if(sopf(n)==sopf(n+k),d=n);n+=1);d

print(dsopf(12345678910))

Puedes copiar este código y ejecutarlo en la página

https://pari.math.u-bordeaux.fr/gp.html

Aquí tienes el resultado: 81147.

Cambiando el ejemplo 12345678910 por otro iríamos comprobando la conjetura para diversos valores.

Este número 12345678910 nos daría problemas de lentitud en Excel, pero hasta aquí sí puede con el problema:

Por si acaso, es preferible usar PARI para evitar los problemas de la coma flotante de Excel.

Esto es lo que podemos afirmar sobre la conjetura. Hay que agradecer a Juan Carlos Amez su propuesta, pues nos ha permitido estudiar un tema interesante.