lunes, 19 de enero de 2015

Suma con el próximo primo


En estas dos entradas anteriores sumamos dos primos consecutivos e investigamos la naturaleza de esa suma y en algunos casos de su mitad (media de ambos):

http://hojaynumeros.blogspot.com.es/2014/06/suma-de-dos-numeros-primos-consecutivos.html
http://hojaynumeros.blogspot.com.es/2014/06/suma-de-dos-numeros-primos-consecutivos_29.html


Hoy podríamos buscar propiedades similares pero sin exigir que el primer número del par sea primo, pero sí usando el primer primo que le sigue (o que le antecede). Comenzaremos sumando cada número con el primer primo que le sigue e investigaremos si también es primo.

Suma con el primo siguiente

Dado un número natural cualquiera, buscaremos menor primo superior a él. Nuestra función de hoja de cálculo PRIMPROX(N) nos serviría en este caso, por lo que en realidad estudiaremos la suma N+PRIMPROX(N). La tienes contenida en la hoja Conjeturas.xlsm

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/conjeturas.xlsm

Búsqueda de primos

Un número, si es primo, no puede formar otro primo sumado con el siguiente, salvo el caso de 2+3=5, pero sí lo forma si no es primo. Buscamos, pues, números no primos que al sumarles el mínimo primo mayor que ellos sí produzcan suma prima. Por ejemplo, el 14 con su próximo primo 17 suma otro primo, el 31.

Los números con esta propiedad son

0, 1, 2, 6, 8, 14, 18, 20, 24, 30, 34, 36, 38, 48, 50, 54, 64, 68, 78, 80, 84, 94, 96, 98, 104, 110,114,
124, 132, 134, 138, 144, 154, 156, 164, 174, 182, 188, 198, 208, 210, …

En todos ellos al sumarles su próximo primo obtendremos otro número primo. Vemos que son frecuentes, pero otros muchos no cumplen la propiedad. Así, 24 sí la cumple, porque 24+29=43, que es primo, pero 22+23=45, que es compuesto. Es trivial descubrir que todos son pares salvo el caso especial 1.

En realidad estamos exigiendo otra propiedad, y es que si llamamos D a la diferencia entre N y su próximo primo, si sumamos D a 2N también resulta otro primo (no necesariamente PRIMPROX(2N)). Es fácil justificarlo y podemos representarlo en este tipo de esquema, que usaremos más adelante también, y que hemos implementado en hoja de cálculo para realizar pruebas.

Insertamos el correspondiente al 38:


Los números de la sucesión los hemos obtenido con Excel, pero puede resultar más sencillo acudir a PARI:

{for(i=0,10^3,k=i+nextprime(i+1);if(isprime(k),print1(i,", ")))}   

Su funcionamiento se entiende fácilmente. El único detalle a explicar es que para encontrar el próximo primo hay que basarse en i+1 y no en i.

Lo hemos usado para publicar la sucesión en https://oeis.org/A249624

Es evidente que, salvo el 1 son todos pares, y algunos, como el 8 y el 64, potencias de 2. Podíamos afirmar que estos números son diferencias de primos, pero lo importante es que esas diferencias son las mínimas, ya que no existen más primos entre ellos.  Sin esa condición, estaríamos en las condiciones de la conjetura de Polignac, que afirma que para todo 2k existen dos primos tales que q-p=2k. Entonces, si la conjetura es cierta, todos los pares cumplirían la condición impuesta.

Estos son los valores de esas diferencias:

1, 1, 1, 3, 3, 1, 3, 5, 1, 3, 1, 3, 5, 3, 5, 3, 3, 1, 3, 5, 3, 1, 3, 3, 3, 13, 3, 5, 3, 1, 5, 3, 1, 3, 5, 9, 3, 1, 3, 1, 7, 3, 1, 3, 3, 5, 5, 3, 1, 9, 13, 7, 1, 3, 3, 9, 3, 1, 1, 3, 7, 1, 3, 1, 5, 7, 7, 9, 9, 5, 3, 1, 3, 7, 3, 3, 11, 5, 7, 3, 7, 1, 5, 11, 9, 3, 13, 3, 1, 5, 3, 3, 1, 3, 5, 5, 1, 1, 3, 3, 1, 3, 5, 3, 3, 5, 3, 1, 5, 1, 3, 9, 5, 7, 3, 1, 3, 3, 3, 7, 3, 7, 3, 11, 9, 5, 1, 5, 1, 9, 13, 9, 7, 3, 13, 7, 1, 3, 13, 3, 7, 7, 3, 1, 3, 5, 5, 3, 1, 5, 3, 3, 1,…

Parecen recorrer todos los números impares. En nuestra lista sólo se llega hasta el 13 ¿Aparecerán al final todos?¿Podrá ser cualquier impar diferencia entre un número par y su próximo primo si ambos suman otro primo?

Hemos implementado una función que a cada número impar (no analizamos en ella si lo es o no) le hace corresponder el mínimo número natural que sumado con él produce un primo en el que la suma de ambos también es primo

Public Function difconprim(n)
Dim i, d, dd, p
i = 2
d = 0
While d = 0 And i < 10 ^ 6
p = primprox(i)
If esprimo(p + i) And p - i = n Then d = i
i = i + 2
Wend
difconprim = d
End Function

Recorre los números pares (variable i) hasta un tope de 10^6 (para números mayores habría que aumentarlo) y estudia si el próximo primo p cumple que p+i es primo y la diferencia entre ambos es el número n dado. No está completo ni optimizado el código. Sólo pretendemos establecer una conjetura. Aquí tienes la tabla para los primeros números impares:

Por ejemplo, para la diferencia 21 el primer número par que la produce es el 1130, en el que se dan estos datos:
,


Si a 1130 le sumamos la diferencia 21 se convierte en el número primo 1151, cuya suma con el anterior 1130+1151=2281, también es un número primo.

Puedes construirte un esquema similar. La función PRIMPROX la encontrarás en la hoja Conjeturas referenciada más arriba. El problema que se presenta es que las hojas de cálculo se ralentizan cuando el valor buscado tiene muchas cifras. Así, entre los números impares menores que 100 la solución mayor es la correspondiente al 97, que es nada menos que 3240996. Lo puedes ver en este esquema:



Para paliar esta lentitud hemos realizado también la búsqueda con PARI

difconprim(n)={local(i=2,d=0,p=2);while(d==0&&i<10^7,p=nextprime(i);if(isprime(i+p)&&(p-i==n),d=i);i+=2);return(d)}
{k=1;while(k<100,write("final.txt",k," ",difconprim(k));k+=2)}

Si tienes preparado en la misma carpeta un archivo de nombre “final.txt”, este código te crea en él un listado similar al que sigue (hemos recortado la parte de los números anteriores a 100)



Parece que nos podemos atrever a expresar una conjetura:

Cualquier número impar es diferencia entre cierto número y su próximo primo, en el caso en el que la suma de ambos también sea prima.

jueves, 8 de enero de 2015

Sucesión de las vacas de Narayana


Proseguimos nuestro estudio de sucesiones recurrentes de tercer orden con la ideada por el hindú Narayana (siglo XIV), con la que intentaba calcular generaciones de vacas, al igual que Fibonacci lo hacía con conejos. Planteó lo siguiente:

Una vaca tiene anualmente una cría. Cada una de ellas, cuando ya es novilla a los cuatro años, también tiene una cría anual ¿Cuántas vacas habrá a los 20 años?

En libros y webs de Historia de las Matemáticas puedes encontrar cómo lo resolvió a partir de sumas de números consecutivos, pero a nosotros nos interesa en este momento su carácter de sucesión recurrente.

En efecto, supongamos que nace la vaca en el año 1. Se pasará tres años sin parir, por lo que la sucesión deberá comenzar con 1, 1, 1,… Al cuarto año tiene una cría, luego ya serán 2 vacas, y, como pare cada año, los siguientes números serán 3 y 4. Cuando la cría tiene 4 años, tendrá otra a su vez, y serán 6. En general, en cada generación habrá tantas vacas como las que haya actuales, más todas aquellas que ya tengan cuatro años, lo que nos lleva a que

xn=xn-1+xn-3

Según esto, la sucesión de Narayana es recurrente de tercer orden, y entra dentro del ciclo que estamos desarrollando.

Para entender mejor cómo organizaremos el estudio, puedes leer la entrada

http://hojaynumeros.blogspot.com.es/2014/11/sucesion-de-perrin.html

La definición de la sucesión, como todas las de su clase, se basa en dar la fórmula de recurrencia y las condiciones iniciales. Según lo explicado más arriba, son estas:

Condiciones iniciales: x0=1, x1=1, x2=1 Ecuación de recurrencia: xn=xn-1+xn-3

Acudiendo a la herramienta que usamos en esta serie (http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2) tendremos:

Planteamiento:










Resultado




Coincide con la sucesión publicada en http://oeis.org/A000930

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745,…

Ecuación característica

La ecuación característica correspondiente será X3-x2-1=0. Con el botón Resolver de esa hoja obtienes las tres soluciones de la ecuación, una real y dos complejas




Con wxMaxima:



Esta situación la hemos visto en sucesiones anteriores, y es que X(n) debe coincidir con la suma de las tres raíces elevadas a n, pero como el módulo de las complejas es menor que 1, X(n) se acercará para valores grandes a 1,46557^n (ver en http://oeis.org/A000930 una aproximación más precisa), y que también X(n+1)/X(n) se acercará a ese valor 1,46557. Esto segundo lo puedes ver con la hoja creando una columna de cocientes:


Función generatriz

Al igual que en las sucesiones recurrentes que ya hemos estudiado, podemos considerar una función generatriz para esta. Es la siguiente:


La comprobamos con PARI y vemos que su desarrollo contiene la sucesión en los coeficientes.

write("sucesion.txt",taylor(1/(1-x-x^3),x,20))

1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 6*x^6 + 9*x^7 + 13*x^8 + 19*x^9 + 28*x^10 + 41*x^11 + 60*x^12 + 88*x^13 + 129*x^14 + 189*x^15 + 277*x^16 + 406*x^17 + 595*x^18 + 872*x^19 + O(x^20)

En cada sucesión que estudiamos nos gusta destacar algún tipo de propiedades. En la de Narayana llaman la atención las de tipo combinatorio.

Relación con los números combinatorios

Se  X(n) equivale al número de composiciones (particiones con orden) del número n en sumandos 1 y 3. Por ejemplo, si X(7)=9, es porque existen 9 particiones ordenadas de este tipo del número 7: {1, 3, 3} {3, 1, 3} {3, 3, 1} {1, 1, 1, 1, 3} {1, 1, 1, 3, 1} {1, 1, 3, 1, 1} {1, 3, 1, 1, 1} {3, 1, 1, 1, 1} {1, 1, 1, 1, 1, 1, 1}

Con nuestra hoja “Cartesius” (no publicada) lo hemos reproducido fácilmente, con las instrucciones siguientes, que no explicaremos ahora:

XRANGO=7
XT=1,3         
SUMA=7      
REPITE        

Aquí tenemos el resultado:



Es otra forma de ver la recurrencia: estas nueve composiciones han resultado de añadir un 3 a las correspondientes a n=4, que son : {1, 3} {3, 1} y {1, 1, 1, 1} y añadir un 1 a las correspondientes a n=6: {3, 3} {1, 1, 1, 3} {1, 1, 3, 1} {1, 3, 1, 1} {3, 1, 1, 1} {1, 1, 1, 1, 1, 1}, con lo que se cumple que C(7)=C(6)+C(4). Esto ocurre para todo valor N, porque siempre podemos repartir sus composiciones entre las que terminan en 1 y las que lo hacen en 3, resultando así C(n-1) y C(n-3).

Desarrollo con binomiales

Si observas la tabla del desarrollo de X(7), entenderás que está formada por permutaciones de dos elementos (1 y 3) tomados 3, 5 o 7 veces. Las permutaciones con repetición de dos elementos equivalen a números combinatorios, por lo que podemos plantear:


En general se cumplirá:


Esto nos da un procedimiento para calcular directamente cualquier elemento de la sucesión de Narayana. La función en Basic de hoja de cálculo te lo resuelve:

Public Function narayana(n)
Dim p, q, t, s, i
 p = 0: q = n: t = 1
While p < q - 1
q = q - 2: p = p + 1 ‘Va incrementando el índice inferior y restando 2 al superior
s = 1: For i = 0 To p - 1: s = s * (q - i) / (p - i): Next i ‘Calcula el número combinatorio
t = t + s ‘Suma los números combinatorios
Wend
narayana = t
End Function

Con ella podemos responder a la cuestión de Narayana, y es que a los 20 años habría 1278 vacas.




domingo, 28 de diciembre de 2014

Bienvenida al 2015


Todos los años por estas fechas solemos saludar al nuevo año con cálculos curiosos referentes a su número. También es tradicional que nuestro colaborador Rafael Parra Machío nos envíe un estudio más profundo, acompañado de alguna explicación teórica monográfica. Este año, por circunstancias personales, no le va a ser posible, pero recordamos algunos de esos documentos, incluidos en nuestra página hojamat.es.

http://www.hojamat.es/parra/PROPIEDADES2014.pdf
http://hojamat.es/parra/prop2013.pdf
http://www.hojamat.es/parra/prop2012.pdf

Nosotros nos moveremos en un nivel más bajo, resaltando algunos desarrollos curiosos basados en el número 2015. Su único objetivo es entretener y abrir caminos para quien desee profundizar, pero con ellos no aprenderéis muchas más Matemáticas.

Nuestros desarrollos preferidos

Todos los meses de diciembre incluimos en la portada de hojamat.es el desarrollo del nuevo año que nos llame más la atención. En el 2014 fue



Para el 2015 lo tenemos muy fácil, pues su desarrollo en factores primos nos brinda un producto capicúa en sus cifras. Lo elegimos este año como el preferido:


Es simple y simétrico, construido sólo con las tres primeras cifras impares, por lo que supera en atractivo a los siguientes.

Derivado de él tenemos otro que depende de dos potencias de 2:

2015= (25-1)(26+1)

También merece ser destacado como el anterior, ya que su estructura es igualmente sencilla y simétrica, aunque en menor grado que la precedente.

Muy sintético y atractivo es este desarrollo, formado por tres números consecutivos:

2015=31×(32+33)

Presentados estos desarrollos, pasamos a capítulos ya conocidos por los años anteriores:


Curiosidades

Con cuadrados y triángulos

Como todos los números naturales, 2015 es suma de tres triangulares y de cuatro cuadrados.

http://es.wikipedia.org/wiki/Teorema_de_los_cuatro_cuadrados
http://es.wikipedia.org/wiki/N%C3%BAmero_triangular

Aquí tienes una suma con tres triangulares:

2015 = T28+T32+T46 = 28×29/2+32×33/2+46×47/2

2015 se puede expresar de muchas formas como suma de cuatro cuadrados. Presentamos algunas:

2015=152+192+232+302=142+172+212+332=152+182+252+292=…


Encontradas

Estas que siguen las he descubierto en http://oeis.org/ y después las he adaptado:

2015 equivale a la sexta parte del número triangular 12090=155*156/2. Por tanto se cumple que 2015=(1+2+3+4+…155)/6.

Esta es sorprendente: 2015 es el promedio de los 77 primeros cuadrados: 2015=(1+4+9+16+…5929)/77

Si a 2015 le restas todas las potencias de 4 que puedas (4^1, 4^2,…4^5), siempre resulta un número primo: 2011, 1999, 1951, 1759, 991.

2015 es un número de Lucas-Carmichael. Si a sus factores primos 5, 13 y 31 les sumas 1, resultan 6, 14 y 32, divisores del 2016.

2015 se puede expresar como una diferencia de cubos de números enteros positivos: 2015=14^3-9^3

La suma de las cifras de 2015 (8) coincide con el número de sus divisores, {2015, 403, 155, 65, 31, 13, 5, 1}

Si llamamos PHI a la indicatriz de Euler, 2015 cumple que PHI(2015)=PHI(2017)-PHI(2016), ya que 144=2016-576

Otras curiosidades

2015 es un número libre de cuadrados, pero la suma de sus factores primos, 13+5+31=49, es el cuadrado de 7.

El mayor divisor de 2015 es 403, número heptagonal que proviene de un producto palindrómico: 403=13×31

Todos los divisores de 2015 son impares, libres de cuadrados y suman 2688. Sus cuadrados suman 4252040.

2015 no puede ser desarrollado como suma de tres cubos

Sistemas de numeración

2015 es palindrómico en base 2: 2015(10=11111011111(2

Esto proviene de que 2015=211-25-20


2015 se expresa en base 4 como un número concatenado consigo mismo:

2015(10=133133(4

Esto es porque hemos señalado que 2015= (25-1)(26+1) . Desarrollamos:





Por una razón similar, también tiene forma de número concatenado en base 8:

2015(10=3737(8





Por último, en base 12 concatena cifras dobles: 2015=11BB(10



2015 con las cifras de números notables

En los últimos años hemos incluido, cuando ha sido posible, la expresión del año nuevo con cifras de números notables. En el presente hemos ampliado el catálogo y acompañamos cada cálculo con un enlace a la teoría de ese número notable:

PI





http://es.wikipedia.org/wiki/N%C3%BAmero_%CF%80

2015 con las primeras cifras de PI:

2015=(3+1+41)×59-(2+6+5+3)×5×8



E






http://mathworld.wolfram.com/e.html

2015 con las primeras cifras de E:

2015=271×8-(2+81)-(8+2)-(8+4)×5


PHI








http://es.wikipedia.org/wiki/N%C3%BAmero_%C3%A1ureo

2015 con las primeras cifras del número de oro PHI (solución de x2-x-1=0):

2015=1618+0+339+8×8-(7-(49+8)/(9+48))



Número de plata






Es una solución de la ecuación x2-2x-1=0

http://mathworld.wolfram.com/SilverRatio.html

Desarrollo de 2015 con sus primeras cifras:

2015=2414-(2×(1+35)×6-(23+7+3))




Número de bronce
















Es una solución de la ecuación x2-3x-1=0

http://matematicaseducativas.blogspot.com.es/2012/10/el-numero-de-oro-y-otros-numeros.html

2015 con sus primeras cifras

2015=3302-((77+56+3+7)×(7+3)/(1+9)×9)


Número plástico

Es la  solución real de la ecuación  x3-x-1=0. Lo presentamos en nuestra entrada

http://hojaynumeros.blogspot.com.es/2014/11/sucesion-de-perrin.html



Desarrollo del 2015 con sus primeras cifras:

2015=1324+718+0-(45-1×(1+2+7)-8)


Otros desarrollos curiosos


Se lleva bien con las cifras de los primeros primos 2, 3, 5, 7, 11, 13, 17, 19, 23 y 29:
2015=2357-111-(3+1)×(71+9)+2+3×29

Desarrollo con los números del 1 al 10:
2015=(1+2+3+4+5+6)×(7+89)-1-0

Al 2015 lo engendra el año anterior:
2015=2014-2+0-1+4


No podían faltar los pandigitales:

2015=(7+91+0)×(2+8+5+6)-43
2015=2×(39+0+4+5)×(8+6+7)-1
2015=(4+1+57)/2×68-(3+90)

Tampoco olvidamos los monocifra. Unos resultan más cortos y otros más largos, porque no es tarea fácil y a veces no se pueden simplificar las expresiones.

2015=999+999+9+9-9/9
2015=(8×8+8/8)×(8+8+8+8-8/8)
2015=7×7×7×7-7×7×7-7×7+7-7/7
2015= (6+6+6)×(6+666)/6-6/6
2015= (55+5×5)×5×5+(5+5+5)
2015= (4×4×4+4/4)×(4×(4+4)-4/4)
2015= (33+33-3/3)×(33-3!/3)
2015=2222-222+22-2-2-2-2/2
2015= (11×(11+1+1)+11+1)×(11+1+1)

Y, por último, autogeneraciones.
El 2015 se autogenera con más o menos truco:

2015= 2015-2×0×15
2015 =(2+0+152+0+1)×(5+2+0+1+5)
2015=(20-15)×((20+1+52+0)×(1+5)-20-15)
2015=2015×(2×(0+1+5+2)-0-15)

Feliz año 2015



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.