lunes, 22 de diciembre de 2014

Factores primos de la parte libre de cuadrados (y 4)


Función P(n), la omega de G(n) 

En los tuits citados en las anteriores tres entradas, de @republicofmath y @jamestanton en los que hemos basado los desarrollos de las mismas se introduce también la función P(n), que es el número de factores primos de G(n). Para entender mejor lo que sigue es conveniente releer esas  entradas. Son las tres anteriores a esta.

Las funciones P y Q aplicadas a G(n)

Si en lugar de multiplicar los factores primos de la parte libre de cuadrados del factorial, los contamos (función OMEGA), obtendremos la función P(n), que ya estudiamos en anterior entrada en su versión general.

Definiremos, pues, P(n)=omega(partelibre(n!). En código PARI se escribiría

P(n) = omega(core(n!))

Así se han encontrado los primeros valores de P(n): 0, 1, 2, 2, 3, 1, 2, 3, 3, 1, 2, 3, 4, 4, 4, 4, 5, 4, 5, 4, 6, 6, 7, 5, 5, 5, 6, 5, 6, 5, 6, 7, 9,… recogidos en http://oeis.org/A055460

Por ejemplo P(5)=3, porque 5!=120= 23*3*5 contiene tres factores primos con exponente impar. Sin embargo P(7)=2 porque su factorial contiene primos elevados a un exponente par salvo el  5 y el 7.

En el Basic de las hojas de cálculo se evalúa esta función de forma idéntica a la de g(n), usando la fórmula de Polignac, solo que se cuentan factores en lugar de multiplicarlos:

Public Function p(n)
Dim i, s
s = 0
For i = 1 To n
If Not esnumpar(polignac(n, i)) Then s = s + 1
Next i
p = s
End Function

Así hemos reproducido sin dificultad los primeros valores:



Al igual que g(n), la función p(n) crecerá en los números primos y se mantendrá constante en los cuadrados. En los demás podrá aumentar o disminuir. Recorre la tabla para verificarlo.

Su crecimiento queda claro en el gráfico





Ajustes de P(n)

Esta función presenta una clara tendencia lineal. Si aumentamos el número de términos y añadimos una línea de tendencia obtenemos un ajuste bastante bueno a una recta de pendiente 0,1236 con R2=0,9853















¿Podríamos afinar más?

En los tuits citados se sugiere un crecimiento potencial suave. Proponen la fórmula potencial P(n) »  0.307*n^0.854. Hemos creado dos columnas paralelas, una con P(n) y otra con la formula 0.307*n^0.854.


La hemos prolongado a más de 1000 filas y hemos pedido una función que no se suele usar mucho en las hojas de cálculo: COEFICIENTE.R2. Esta función te devuelve el coeficiente de determinación, que evalúa la parte explicada de la función P(n) mediante esa aproximación. Resulta, tal como afirman los autores, R2=0,996998973, impresionante en su ajuste.

Volvemos al Solver

Como uno de los objetivos de este blog es el aprendizaje del uso de las hojas de cálculo, acudimos a la herramienta Solver para ver si Excel (en este caso) puede aproximar los valores 0.307 y 0.854 de la formula.  Al igual que operamos en la entrada anterior, asignamos dos celdas a estos parámetros, y los iniciamos, por ejemplo, en 0,3 y 0,8, a ver qué ocurre. A su derecha construimos la columna de las diferencias al cuadrado



Sumamos la columna de diferencias en la celda J1146. Con todo ello acudimos a Solver para ponerlo a prueba:


La solución que nos da no es la óptima



Para una herramienta no dedicada a usos científicos no está mal, pero vemos que no es fiable si se le exige mucho. Para comprobaciones serviría, pero sólo para eso.

martes, 16 de diciembre de 2014

Factores primos de la parte libre de cuadrados (3)

Ajustes de la función g(n) 

La entrada anterior la dedicamos a la parte libre de cuadrados de los factoriales. La llamamos g(n)=core(n!) e indicábamos que sus valores estaban contenidos en http://oeis.org/A055204. En dicha página señala Charles R Greathouse IV que log g(n) ~ n log 2. Comencemos por ahí:

Como en la entrada anterior se ofrecía una forma de evaluar g(n), podemos crear dos columnas paralelas, una con log(g(n)) y otra con n*log(2). El gráfico correspondiente a los primeros números nos indica que esta aproximación es siempre por exceso, y con un ajuste bastante alto: R2=0,99


La función log(g(n)) tiende a infinito con n de forma sensiblemente lineal

No he encontrado desarrollo teórico sobre esta aproximación, pero es algo que llama la atención. También se puede expresar como g(n) » 2nTambién es sorprendente que g(n) se ajuste bastante bien al número de subconjuntos de un conjunto de n elementos.

James Tanton propone como aproximación inferior en media g(n) » 1,85n.  ¿Qué podríamos afirmar nosotros con una hoja de cálculo? No mucho, pero lo intentaremos:

Ajuste por mínimos cuadrados y Solver

Preparamos cuatro columnas de datos, en la imagen desde la I hasta la L



En la columna I escribimos los primeros números naturales, en la siguiente el logaritmo de G(N), y su aproximación mediante N*LOG(2) en la columna K. Observa que el 2 está escrito en la celda K1. A continuación calculamos en la última columna la diferencia de ambas expresiones elevada al cuadrado. Esta columna la sumamos al final, en la imagen en la celda L1057.



Ahora interviene Solver: le pedimos que elija el valor mínimo en la celda K1 (para sustituir el 2) que consiga minimizar la suma de diferencias al cuadrado contenida en L1057 con lo que habremos realizado un ajuste por mínimos cuadrados:



Nos da como mejor valor 1,94 aproximadamente, muy cercano al 2 de partida.



Este pequeño cambio hace que el ajuste en el gráfico se aprecie mejor:



El ajuste no está sesgado como en el caso del 2.

Esta técnica que acabamos de usar es sencilla, pero no muy usada. La ventaja que tiene es que tú puedes elegir la función de ajuste, que en las líneas de tendencia está obligada a ser lineal, exponencial o potencial. Recuerda los pasos:

* Situamos en dos columnas paralelas la función a estudiar y la que deseamos sirva de ajuste
* Si la función de ajuste depende de unos parámetros, tomamos nota de en qué celdas están situados.
* Creamos una tercera columna con las diferencias al cuadrado entre las dos primeras. La sumamos en una celda cuya referencia recordaremos.
* Acudimos a Solver y solicitamos minimizar la celda de la suma de diferencias al cuadrado a partir de las celdas que contienen los parámetros. Se usará un Solver no lineal.
* Si el ajuste es posible, aparecerán los nuevos valores de los parámetros.

Podemos, por pura curiosidad, intentar un ajuste lineal al LOG(G(N)) (neperiano). Resulta una coincidencia bastante fuerte, porque, además del sumando -7,2383, descubrimos que el coeficiente que da para la X es 0,6738, que es el logaritmo de 1,96, luego la expresión  log g(n) ~ n log 2 da un ajuste ligeramente superior.


G(n) y el primorial

Podemos conseguir otra aproximación comparando G(n) con los primoriales:

Recordamos que G(n) es la parte libre de cuadrados del factorial de n. Es un divisor del primorial n#, que es el producto de todos los números primos menores o iguales que n

 (ver http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html)

G(n) elige del primorial sólo los factores primos que presentan exponente impar en n. Basta recordar los esquemas que usamos cuando presentamos la función:



En el esquema, si multiplicamos los elementos de la primera columna nos resultará un primorial, y como en la segunda se marcan los que entran en G(n), si sólo multiplicamos los que figuran con 1, resultará, como hemos afirmado, que G(n) es un divisor de n#, y es claro que este, a su vez, es un divisor de n!. Esto nos lleva a unas acotaciones claras:

G(n) divide a n# y este a n!

Los cocientes tienen valores altos en el caso de los factoriales, como vemos en esta tabla.



Sin embargo, los correspondientes a N#/G(N) parecen más asequibles a nuestro estudio. Sabemos que los logaritmos de los primoriales se ajustan bien al valor de N. Veamos el ajuste del logaritmo del cociente N#/G(N)



Así que log(N#/G(N)) se acerca a 0,2928N y log(N#) a N. Se tendrá entonces:

Log(G(N)) » log(N#)-0,2928N » N-0,29N » 0,7072N >» Nlog(2)

Hemos llegado a un ajuste muy cercano al que obtuvimos anteriormente, pero por exceso. Lo más llamativo es que los distintos logaritmos presentan una tendencia lineal.




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.


jueves, 4 de diciembre de 2014

Factores primos de la parte libre de cuadrados (1)

Esta entrada es la primera de cuatro consecutivas que dedicaremos al mismo tema. Introduciremos las funciones P(n), Q(n) y G(n), que nos servirán como excusa para profundizar en el conteo y producto de los factores primos de la parte libre de un número y de su factorial. Un apartado interesante es el de sus ajustes, pues revisaremos técnicas de hoja de cálculo,


Factores de la parte libre y de la parte cuadrada

Ya vimos en otra entrada

http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre.html

que todos los números naturales poseen una parte cuadrada PC(N) y otra libre de cuadrados PL(N). La primera contiene como divisores todos los de N que son cuadrados. Si un factor primo está elevado a un exponente par pertenecerá a la parte cuadrada, pero si es impar, el par mayor contenido en él pasará a la parte cuadrada, y quedará en la parte libre el mismo factor elevado a la unidad.

Todos los factores primos de la parte libre de cuadrados están elevados a la unidad.

Puedes seguir la teoría en la citada entrada y también en nuestra publicación sobre funciones multiplicativas.

http://www.hojamat.es/publicaciones/multifun.pdf

También puede ser interesante contar los factores primos de la parte cuadrada, sin repetición.

Llamaremos  función Q(N) al resultado de contar esos primos. Así, por ejemplo, en el número 2520=23×32×5×7 tendríamos:

Parte cuadrada 22×32=36, Parte libre de cuadrados: 2×5×7=70, Q(2520)= 2, porque la parte cuadrada contiene dos primos distintos.

Los valores de esta función Q(N) los tienes en http://oeis.org/A056170

0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0,…

Puedes leer ahí algunos comentarios y desarrollos. El valor 0 aparece en los números libres de cuadrados. Verifícalo en la sucesión. Es sencillo de entender.

Presentarán valor 1 aquellos números cuya parte cuadrada posee un solo factor primo, como 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28,…( http://oeis.org/A190641). El primer valor Q(n)=2 ocurre en el 36, y, en general, esta función cuenta los factores no unitarios de N.

Aprenderás bastante si ejecutas y analizas este código PARI que engendra esos valores. Ahí te lo dejamos. Recuerda que OMEGA cuenta los factores primos sin repetirlos y que CORE es la parte libre.

{for(i=2,36,print1(omega(i/core(i)),", "))}

Podíamos efectuar idéntica operación con la parte libre, contar sus factores primos. Llamaremos al resultado P(N). Sus valores son:

0, 1, 1, 0, 1, 2, 1, 1, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2,…

y están contenidos en la sucesión OEIS http://oeis.org/A162642. En ella los valores 0 se corresponden con los cuadrados, porque en ellos la parte libre es 1 y no tiene factores primos.
Como en la anterior recomendamos la lectura del desarrollo de este enlace de OEIS y el que generes la sucesión mediante el código PARI

{for(i=1,36,print1(omega(core(i)),", "))}

Recuerda que core es la parte libre de cuadrados

Las funciones P(N) y Q(N) no actúan sobre conjuntos disjuntos de factores y pueden contar ambas el mismo factor, como ocurría con el 2 en el ejemplo de más arriba, el del 2520, que pertenecía a la parte cuadrada y también a la libre. Por tanto, la suma  P(N)+Q(N) es igual o mayor que OMEGA(N).

En la tabla siguiente podemos observar que en los números que contienen cubos, como 8, 24 y 27, presentan esa desigualdad P(N)+Q(N) > OMEGA(N).


Puedes reflexionar sobre qué números presentan esa desigualdad además de los cubos.

P y Q como funciones aditivas

En Teoría de Números una función f(n) se llama aditiva cuando se cumple

F(ab) = f(a) + f(b) siempre que a y b sean coprimos

En efecto, si a y b son coprimos, tanto su parte cuadrada como su parte libre poseerán factores primos diferentes en ambos números. Por tanto,  P y Q aportarán al producto factores que no pertenecerán a la otra función. En ese producto figurarán los que aporta cada uno sin coincidencias, por lo que sus cuentas se sumarán. Lo puedes verificar en la tabla de más arriba, por ejemplo:

P(2)=1, P(9)=0 y P(2*9)=P(18)=1=P(2)+P(9)

Prueba también con otros pares (coprimos) y con Q(n), y comprobarás la aditividad.

Al igual que las funciones multiplicativas, las aditivas se definen sólo para potencias de primos. En este caso la definición adecuada de Q(pm) sería

Q(pm)=0 si m=1, y Q(pm)=1 en los demás casos. 

Lo puedes expresar también como psg(m-1), donde sg es la función signo, que vale 1 en los positivos y 0 en el cero.

Para la función P tendríamos la situación opuesta:

P(pm)=1 si m es impar, y P(pm)=0 si m es par. 

También se puede resumir como P(pm)=(m mod 2)

La falta de simetría en las definiciones viene dada por el hecho de que si un primo está elevado a exponente 2 o mayor, se cuenta en Q y no en P, tanto si es par o impar.

Sobre estas funciones volveremos en las siguientes entradas, cuando estudiemos los factores primos de las parte libre de cuadrados en el caso del factorial.