miércoles, 10 de diciembre de 2014

Factores primos de la parte libre de cuadrados (2)

La función G(n), cuadrados y factoriales

Hace unas semanas, navegando por Twitter encontré unos comentarios de Republic of Math (@republicofmath)  sobre resultados relativos a esta función. Me interesaron bastante y decidí estudiarla mediante hojas de cálculo, que es donde nos movemos en este blog. En la anterior entrada se incluyó un estudio sobre los factores primos de las partes cuadrada y libre como introducción al que se inicia hoy.

En dichos textos de Twiter se define g(n) como el mínimo número que multiplicado por el factorial de n lo convierte en un cuadrado. Ahora bien, según razonamos en la entrada

http://hojaynumeros.blogspot.com.es/2011/12/emparedado-de-cuadrados-2.html

esa función g(n) es, simplemente la parte libre de cuadrados del factorial de n. Si la parte libre la representamos como PL, la fórmula adecuada sería g(n)=PL(n!).

En lenguaje PARI esta función se representaría por core(n!), y así es como se ha engendrado la sucesión de valores de g(n) en http://oeis.org/A055204:

1, 2, 6, 6, 30, 5, 35, 70, 70, 7, 77, 231, 3003, 858, 1430, 1430, 24310, 12155, 230945, 46189, 969969, 176358, 4056234, 676039, 676039, 104006…

Desafortunadamente, en hoja de cálculo, si usamos la expresión equivalente con funciones nuestras: PARTELIBRE(FACT(N)), el cálculo se ralentiza hasta llegar a hacerse inútil. Para conseguir la tabla que sigue, hemos tenido que esperar varios minutos.



Para resolver esto, y entrando ya en un tema de algoritmos, podemos contar con una ayuda:

Fórmula de Polignac

Esta útil fórmula la estudiamos en la entrada http://hojaynumeros.blogspot.com.es/2009/02/formula-de-polignac.html, a la que remitimos para su definición y estudio.

La fórmula recorre todas las potencias de los factores primos menores que n y para cada una de ellas evalúa la parte entera del cociente de n entre cada una de las potencias.



El resultado equivale al exponente del factor primo dentro del factorial. Esto nos da una oportunidad para encontrar la parte libre de dicho factorial:

* Recorremos todos los números primos menores que n
* A cada uno le aplicamos la fórmula de Polignac
* Si su exponente es par, pertenece a la parte cuadrada del factorial, y no nos interesa.
* Si es impar, pertenecerá la parte libre, es decir, a g(n), tomándolo con exponente la unidad.

No es difícil programar como función estos cálculos. Este listado lo entenderás bien. Devuelve un cero si el número no es primo y su exponente dentro del factorial si lo es:

Public Function polignac(n, p)  n es el número y p el primo
Dim pol, pote

pol = 0 El valor se inicia en cero. Si no es primo p, se queda así
If esprimo(p) Then
pote = p Recorrerá las potencias de p menores que n
While pote <= n
pol = pol + Int(n / pote)  Sumando de la fórmula de Polignac
pote = pote * p  Se pasa a otra potencia del primo.
Wend
End If
polignac = pol
End Function

Puedes comprobar con esta fórmula la descomposición de 22! que publicamos en la entrada sobre Polignac:


Con esta función podemos encontrar los valores de la parte libre de cuadrados del factorial. En el ejemplo obtendríamos g(22)=2*3*7*13*17*19=176358.

Seguimos las operaciones sugeridas más arriba: recorrer los primos y tomar tan sólo aquellos que presenten un valor impar en la fórmula de Polignac:

Este segundo listado es más simple, y nos da el valor de g(n):

Public Function g(n)
Dim i, s
s = 1
For i = 1 To n Recorre los menores que n, sean o no primos
If Not esnumpar(polignac(n, i)) Then s = s * i Multiplica sólo los de exponente impar (si no es primo suma cero)
Next i
g = s
End Function

Ahora el proceso es mucho más rápido. Este listado se ha conseguido en segundos:



A primera vista hay algo que llama la atención, y es que la función no es creciente, aunque sí tenga esa tendencia a la larga, y que el valor para un cuadrado es idéntico al de su número anterior. Esto último se comprende porque un cuadrado no aporta nada a la parte libre de cuadrados del factorial. El que no sea creciente se explica porque la aportación del nuevo número puede ser de exponente impar que se acumule a otro impar ya existente y que entre ambos formen uno par, que por ser cuadrado se elimina. Pensemos en esto con más detenimiento.

Proceso recursivo

Si disponemos de la descomposición en factores primos de g(n) y la de n+1 entenderemos mejor por qué la función g(n) a veces crece otras decrece y en algunos casos queda igual. Usaremos el siguiente esquema:



En él hemos representado los exponentes (todos iguales a 1) de g(15) que es el producto 2*5*11*13. En la siguiente columna se han situado los exponentes de 16, que en este caso sólo figura el 4 correspondiente a 24. Al pasar de 15! a 16!, el factor nuevo tiene exponente  par, luego el exponente del 2 no cambia, con lo que g(15)=g(16)=1430. Esto ocurriría en todos los cuadrados.

El valor de g(n) es igual al de g(n+1) cuando n+1 sea un cuadrado.

Si n+1 es un número primo, la situación es la opuesta, Observa el paso de 18 a 19:



g(18)=5*11*13*17. Como 19 es primo, no se combinará con los anteriores, y aparecerá como factor nuevo en g(19)= 5*11*13*17*19. Así ocurrirá con todos los números primos:

Si n+1 es primo, se cumplirá g(n+1)=(n+1)*g(n)

Recorre la tabla, detente en un número primo N  y observarás que g(N)=g(N-1)*N

En los demás casos, crece cuando el producto de los nuevos factores es superior al de los que se eliminan. Vemos dos ejemplos:

Paso del 19 al 20



Aquí los factores nuevos que aporta el 20 son 2 y 5. El 2 no cuenta porque está elevado al cuadrado, y se elimina. El 5 tampoco cuenta, porque con el 5 que ya está presente en g(19) forma un cuadrado y también se elimina. El resultado es que se pierde un 5 y la función disminuye.

Paso del 14 al 15

Aumenta, según el esquema. Estúdialo bien:


En la siguiente entrada estudiaremos los ajustes de esta función y veremos que existe una tendencia lineal para ella bastante clara.