lunes, 8 de junio de 2015

La función de Smarandache y los números de Kempner (3)


Asociado Kempner de un número entero

En las dos entradas anteriores llamamos S(n) al menor número tal que su factorial sea múltiplo de n. Estudiamos los algoritmos para encontrar valores de esa función y algunas de sus propiedades. Nos basaremos en éstas para desarrollar el concepto de “asociado Kempner” de un número. Lo definiremos así:

A(n)=S(n)!/n

Es fácil ver que A(n) es el número que multiplicado por n lo convierte en el factorial mínimo que es divisible por él. Si disponemos de S(n), bastará encontrarle el factorial, que será múltiplo de n y por tanto podremos dividir.

Los resultados de esta operación los tienes en http://oeis.org/A007672

1, 1, 2, 6, 24, 1, 720, 3, 80, 12, 3628800, 2, 479001600, 360, 8, 45, 20922789888000, 40, 6402373705728000, 6, 240, 1814400, 1124000727777607680000, 1, 145152, 239500800, 13440, 180, 304888344611713860501504000000…

Sólo con recorrerlos brevemente descubrimos las oscilaciones enormes que existen entre cada término y el siguiente. La razón es obvia, y está basada en las propiedades de S(n), de las que se derivan las de A(n):

El asociado de un número primo p es A(p)=(p-1)!

Porque S(p)=p, luego A(p)=p!/p=(p-1)!

En la sucesión puedes comprobarlo: A(7)=720=6!, A(11)=3628800=10!

Esto nos indica que la sucesión no está acotada. Dada una constante cualquiera, existe un factorial que la sobrepasa.

El asociado de un factorial es igual a 1

Es evidente, porque S(n!)/n=n/n=1

Ya tenemos aquí uno de los orígenes de las oscilaciones que se descubren en la sucesión.

Algoritmo de cálculo

La existencia de términos muy grandes en la sucesión nos aconseja un algoritmo que no tenga, en lo posible, que usar factoriales. Aquí está muy indicado el que propusimos del MCD en la entrada anterior. Para un valor n, recorremos el conjunto 1, 2, 3, 4,…n y dividimos n entre el MCD de n y un elemento del conjunto, hasta convertirlo en 1. Aquí recorreremos los mismos pasos, pero acumulando los cocientes obtenidos multiplicados entre sí en una variable. Al final del proceso tendremos el producto de todos los factores que multiplicados por n lo convierten en S(n)! Sólo hay que cambiar unas líneas en el algoritmo que propusimos. Destacamos en rojo los cambios:

Public Function asoc(x)
Dim n, x1, m, a

If x < 3 Then asoc = 1: Exit Function
n = 1: x1 = x: a = 1 ‘Introducimos una variable que recoja los cocientes n/m
While x1 > 1 ‘Estructura de algoritmo idéntica a la del cálculo de S(x)
n = n + 1
m = mcd(n, x1)
x1 = x1 / m
a = a * n / m ‘Se van multiplicando los cocientes para formar A(x)
Wend
asoc = a
End Function

Con Excel el cálculo es prácticamente instantáneo para los primeros números naturales:



Al igual que procedimos con el algoritmo primitivo, podemos traducir también a PARI para poder llegar a números mayores sin el estorbo de la notación exponencial:

a(n)={local(m=1,x=n,as=1,p);while(x>1,m++;p=gcd(x,m);x=x/p;as*=m/p);as}

Destacamos en rojo las novedades. Los resultados para los primeros números los tienes en esta imagen



Como era de esperar, coinciden con los publicados en A007672, y llegan más lejos. Hemos incorporado este algoritmo a esta sucesión http://oeis.org/A007672

Iteración de la función A(n)

Con lo expuesto hasta ahora podemos esperar que si iteramos la función desde un valor inicial dado, la órbita que se produzca será totalmente oscilante. Sin embargo, ocurre lo contrario, que para cualquier número entero, la iteración sólo puede presentar uno de dos finales posibles: o termina teniendo todos sus términos iguales a la unidad, o se convierte en periódica de periodo 2. Lo estudiamos:

Dado un número natural cualquiera N, el valor de la función A(N) es divisor de S(N)!, ya que por definición, A(N)=S(N)!/N. Quiere decir que S(N)! es un factorial múltiplo de A(N). Por tanto, si calculamos S(A(N)) nos dará S(N) o un número menor, si existe un factorial múltiplo de A(N) que sea menor que S(N). Por tanto:

S(N)>=S(A(N))

Pueden ocurrir dos casos

(1) Si para un N se da que S(N)=S(A(N)), al iterar y calcular A(A(N)) resultará A(A(N))=S(A(N))!/A(N)=S(N)!/(S(N)!/N)=N

Si S(N)=S(A(N)), resultará A(A(N))=N y la sucesión de iteraciones será periódica.

Esto ocurre, por ejemplo, para N=25, pues A(25)=145152 y A(145152)=25. Los dos asociados tienen el mismo factorial mínimo común a ambos. La sucesión será periódica. Lo podemos ver con la hoja de cálculo y la función ASOC:



(2) Si en un conjunto de iteraciones se da que S(N)>S(A(N)), los factoriales mínimos irán decreciendo, con lo que, o bien llegaremos a un número que produzca periodicidad como en el primer caso, o bien desembocaremos en 1!=1, y a partir de él todos serán iguales a la unidad, porque S(1)=1.

Esto se da en todos los números primos, porque entonces A(P)=(P-1)! Y A(A(P))=A((P-1)!)=1.

También en otros que no son primos, como el 21: A(21)=240, que es el cociente entre 7! Y 21. A(240)=3, es decir 6!/240. Seguimos iterando: A(3)=2 y por último, A(2)=1

Con la hoja:



La mayoría de números desemboca en la unidad al iterar la función A(N). Los únicos números que producen periodos de 2 términos son:

9, 16, 25, 45, 49, 63, 75, 80, 81, 99, 112, 117, 121, 125, 128, 147, 153, 169, 171, 175, 176, 207, 208, 225, 243, 245, 250, 256, 261, 275, 279, 289, 304, 315, 325, 333, 343, 361, 363, 368, 369, 375, 387, 405, 423, 425, 441, 464, 475, 477, 486, 495, 496, 500, 507, 512, 525, 529, 531, 539, 549, 560, 567, 575, 585, 592, 603, 605, 625, 637, 639, 640, …

Los hemos generado con el programa PARI siguiente:

a(n)={local(m=1,x=n,as=1,p);while(x>1,m++;p=gcd(x,m);x=x/p;as*=m/p);as}
{for(i=1,10^3,m=i;v=1;while(m>1&&v,n=a(m);if(m==a(n),v=0;print1(i,", "));m=n))}

Publicados en http://oeis.org/A256705

No hemos encontrado regularidades en estos números y sus asociados. Unos son cuadrados y otros no, en la mayoría de las veces un número y su asociado son coprimos, pero en otras tienen MCD mayor que 1, como MCD(495,80640)=3. Según hemos explicado anteriormente, ninguno es primo.

Lo que sí poseen todos es una parte cuadrada mayor que 1. Si fueran libres de cuadrados, se descompondrían en un producto de primos elevados todos a la unidad. Si los ordenamos de menor a mayor tendríamos  N=p1p2p3…pk  y según lo explicado en entradas anteriores, S(N)=pk!, con lo que A(N) carecería de ese factor pk, pero el factorial en que se basa ha de ser el mismo pk! o inferior. El mismo no es, porque al carecer de ese factor primo, no es necesario llegar hasta pk!. Por tanto, S(N)>S(A(N)) y no puede pertenecer al conjunto. Como la relación es recíproca, A(N) tampoco puede ser libre de cuadrados:

Si N pertenece a la sucesión que estamos estudiando, ni él ni su asociado serán números libres de cuadrados.

No existe la propiedad contraria. Existen números no libres de cuadrados, como el 12, que no pertenecen a la sucesión.