Conjetura de Polignac

Se llama Conjetura de Polignac a la enunciada por Alphonse de Polignac in 1849 y que se puede expresar así:

Hay un número infinito de números primos (p, q) tales que p - q = k, siendo k un número par.

Últimamente se ha hablado más de ella por algunos avances que se han producido y que pudieran llevar a su demostración

(Ver http://gaussianos.com/de-70000000-700-en-seis-meses/ y http://en.wikipedia.org/wiki/Polignac%27s_conjecture)

Dentro de esta conjetura, y para k=2 se incluye la de los primos gemelos:

Existen infinitos pares de primos gemelos (p, p+2)

(http://es.wikipedia.org/wiki/Conjetura_de_los_n%C3%BAmeros_primos_gemelos)
Pero también podríamos expresar lo mismo para pares del tipo (p, p+4), “cousin primes” y los del tipo (p, p+6), “sexy primes”.

Nosotros trabajaremos con el enunciado general, sobre los pares (p, p+k), con k número par. Para ello, usaremos el valor de k como entrada a algoritmos de búsqueda.

Esquema sin macros

Para buscar estos pares (p, p+k) ambos primos podemos crear en la hoja Conjeturas (http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global) una lista de números primos p en forma de columna. Para ello la iniciamos con el número que deseemos, generalmente grande, y después, en cada fila usamos la función PRIMPROX(N), siendo N el número contenido en la celda de arriba, con lo que para aumentar la lista bastará extender la fórmula hacia abajo. Después creamos una columna paralela formada por p+k. Por último, en una tercera columna usamos la función ESPRIMO. De esta forma, la aparición del primer par con ambos primos se detectará por el valor VERDADERO de esa función.

En la imagen hemos detectado el primer par de números gemelos después del número 1000000, el (1000037,1000039), Se comprende que si la conjetura es verdadera, prolongando las columnas lo que sea necesario, encontraremos un par de primos con la diferencia que hayamos fijado.

Por ejemplo, aquí tienes los primeros primos diferenciados en 1000 que siguen a 10000000:

La columna puede hacerse muy alta, y nos convendría también poder encontrar los pares buscados con una sola función.

Función Polignac

Para abreviar el proceso usaremos la función POLIGNAC(P;K), que hemos añadido a nuestra hoja cálculo conjeturas, enlazada más arriba.

Esta función actúa sobre un inicio n y una diferencia par k, y encuentra el primer número primo p posterior al inicio que forma par de primos con p+k. Basta leer los comentarios para entender su funcionamiento.

Function polignac(n, k)
Dim novale As Boolean
Dim p, q

p = n ‘Iniciamos la búsqueda en n
novale = True ‘Variable para terminar la búsqueda
If k / 2 <> k \ 2 Then polignac = 0: Exit Function ‘Si k es impar, damos valor 0 a la función
While novale
p = primprox(p) ‘Buscamos el siguiente primo
If  esprimo(p + k) Then q = p: novale = False ‘Si encontramos (p,p+k) paramos
Wend
polignac = q ‘Damos a la función el valor del primer primo del par
End Function

Por ejemplo, deseamos comprobar la conjetura encontrando el primer par de números primos diferenciados en 2000 que sigue al inicio 10^6. En la imagen, capturada de la hoja conjeturas.xslm tienes la respuesta: 1000121 es el primer primo tal que al sumarle 2000 se obtiene otro primo 1002121. El resto del esquema lo hemos organizado para que se obtengan varios pares en lugar de uno solo. A la derecha hemos incluido la prueba de que ambos son primos. Te invitamos a que construyas un esquema similar en la hoja conjeturas.

Como en todas las cuestiones, la hoja de cálculo puede fallar para números muy grandes, por lo que debemos acudir a programas más potentes. Elegimos PARI por ser gratuito. Podemos usar la siguiente función, a la que hemos añadido un “print” para que veas el resultado:

polignac(n,k)={local(p);p=nextprime(n);while(!isprime(p+k),p=nextprime(p+1)); return(p)}
{print(polignac(10^6,2000))}

Si lo ejecutas obtendrás el mismo número primo que con la hoja, 1000121:

También aquí puede fallar la función para números muy grandes, pero el margen es mayor que en Excel.

La idea es que si la conjetura es cierta (y la herramienta de cálculo lo admite), podemos elegir un número de inicio arbitrariamente grande y siempre tendremos un resultado.

Lista de números primos gemelos, “cousin”, “sexy” y otros

Con esta función puedes crearte fácilmente una lista de primos gemelos. Basta usarla de forma recurrente en columna a partir del 1, y con una diferencia dada. En el esquema que adjuntamos más arriba usamos esta técnica:

El primer par de primos gemelos (3,5) se ha construido a partir del 1. Los siguientes, a partir del anterior, con la función polignac(p,k). Las columna de la derecha la programamos para que sume el valor de k a la de la izquierda.

Si la conjetura de Polignac es cierta, esta tabla tendría una altura infinita. No terminarían de aparecer pares.

Podemos construir de esta forma los pares de primos “cousin”, que se diferencian en 4.

De igual forma, los “sexy”:

Nada nos impide crear una lista personalizada. Por ejemplo, si has nacido en el año 1962, como es par, puedes crear pares de primos con esa diferencia:

Llama la atención que el primer elemento del par no tiene que ser muy grande aunque k lo sea. Observa la lista de pares con una diferencia de 1000000:

Otras posibilidades

No podemos construir tríos de primos de este tipo, porque siempre uno de ellos sería múltiplo de 3, pero sí tríos de la forma (p, p+2, p+6), o, en general (p, p+k, p+3k). Para explorar un poco por este camino, bastaría sustituir la línea de Basic

If  esprimo(p + k) Then q = p: novale = False 

Por esta otra

If esprimo(p + k) And esprimo(p + 3 * k) Then q = p: novale = False

Si la conjetrura de Polignac es cierta, estas búsquedas terminarán por dar un resultado. Observa el caso de n=1000000 y k=1000

Casi todos estos casos están publicados y no pasan de ser curiosidades derivadas de la conjetura que estudiamos. Si eliges un ejemplo inadecuado, como (p, p+2, p+4), puede ocurrirte que se bloquee la hoja de cálculo y tengas que recurrir al Administrador de tareas para cerrarla.

Por el contrario, si consigues tríos no publicados, podrías intentar incluirlos en OEIS.

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

x_n=x_n-1+x_n-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: x₀=1, x₁=1, x₂=1 Ecuación de recurrencia: x_n=x_n-1+x_n-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á X³-x²-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.

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= 2³*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 R²=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, R²=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.

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: R²=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) » 2ⁿ. Tambié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.

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 2⁴. 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.

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=2³×3²×5×7 tendríamos:

Parte cuadrada 2²×3²=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(p^m) sería

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

Lo puedes expresar también como p^sg(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(p^m)=1 si m es impar, y P(p^m)=0 si m es par. 

También se puede resumir como P(p^m)=(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.

Conjeturas con hoja de cálculo: Primos tipo n^2+1

Es uno de los problemas de Landau, y en el momento de redactar este texto sigue sin conocerse si es verdadera o no la siguiente conjetura:

Existen infinitos primos de la forma n²+1

Hardy y Littlewood supusieron que la conjetura era verdadera, y aproximaron el número de tales números primos menores que n, P (n), asintóticamente a

Con C una constante adecuada.

El listado de los primeros primos de este tipo lo puedes consultar en http://oeis.org/A002496

2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, 1601, 2917, 3137, 4357, 5477, 7057, 8101, 8837, 12101, 13457, 14401,…

Si la conjetura es cierta, esta sucesión deberá poseer infinitos términos.

¿Qué estudios podríamos abordar sobre este tema con una hoja de cálculo?

El primer objetivo razonable es el de comprobar que, dado un número cualquiera, existe un número primo del tipo n²+1 que es mayor que él.

 Usaremos la herramienta de hoja de cálculo conjeturas, alojada en

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global

Para encontrar ese primo mayor que el dado, reiteraremos el uso de la función PRIMPROX hasta que encontremos un número primo p tal que p-1 sea un cuadrado.

(A) Planteamiento manual

Basta estudiar este esquema brevemente para descubrir su funcionamiento:

El primer número primo de la lista es el PRIMPROX(N), en la imagen 1511. Los siguientes se obtienen como los próximos primos del de la fila superior. Esta lista se puede extender hacia abajo todo lo que se desee.

En la segunda columna hemos usado una fórmula del tipo

=SI(ESCUAD(C9-1);C9;""),

es decir, si C9 u otro primo de la lista cumple que al restarle la unidad se convierte en un cuadrado, lo escribimos, y , si no, dejamos la celda en blanco. Así descubrimos que el primer primo de este tipo es 1601. Si la conjetura es cierta, siempre llegaremos a un número de ese tipo.

Este método puede necesitar muchas filas hasta dar con el primo esperado. Por eso, se puede plantear como una función:

(B) Estudio mediante una función

Si suponemos cierta la conjetura, para cada número existirá un primo mayor que él con la forma n²+1. Entonces lo podemos plantear como una función. Su listado lo entenderás fácilmente:

Public Function proxn2mas1(n)
Dim p
p = primprox(n)
While Not escuad(p - 1)
p = primprox(p)
Wend
proxn2mas1 = p
End Function

De esta forma, la búsqueda manual que emprendimos en el caso anterior la podemos reducir al planteamiento de esta función:

Se comprende que para números grandes esta función tardará algo en calcularse. Lo hemos intentado con 10^7:

Tarda unos segundos, aunque no es un retraso desesperante. Hemos añadido la raíz cuadrada del primo menos uno, 3174.

Lista de primos de este tipo

Con esa función proxn2mas1 podemos reproducir toda la lista de OEIS. Basta escribir un 2, debajo de él proxn2mas1(2) y nos resultará un 5. Le aplicamos de nuevo proxn2mas1 y obtendremos el 17, y así seguimos hasta donde deseemos.

Si en lugar de comenzar con el 2 inicias con un número cualquiera, se escribirá la continuación de la lista, salvo quizás el primero, que no tiene que ser primo de ese tipo. Aquí tienes los siguientes a 10000:

Aproximación asintótica

Para comprobar la aproximación de Hardy y Littlewood necesitamos contar los primos de este tipo anteriores a N. Algo parecido a la función PRIME(N), pero quedándonos sólo con los primos de forma n²+1

Entenderás a la primera esta definición:

Public Function ppn2mas1(n)
Dim pp, i
' para valores de n superiores s 2

i = 2: pp = 0
While i <= n
pp = pp + 1
i = proxn2mas1(i)
Wend
ppn2mas1 = pp
End Function

Esta función cuenta los primos del tipo n²+1 inferiores o iguales a N. Como nos interesan valores grandes por cuestiones asintóticas, suponemos, para simplificar la programación, que N es mayor que 2. Observa esta tabla en la que se percibe que tratamos con una función escalonada, y que los cambios ocurren en 5 y 17, primos del tipo estudiado.

Para comprobar la aproximación asintótica y evaluar la constante C crearemos una tabla a partir del 10 en progresión geométrica hasta llegar a 10000000:

Hemos evaluado la constante C como cociente entre la función de distribución de los primos de tipo  n²+1 inferiores a N y la aproximación RAIZ(N)/LN(N). No usamos una herramienta adecuada, pero se ve que los valores de C presentan una cierta convergencia.

Variante de la conjetura

La más sencilla es la que busca primos de la forma  n²+a. Podemos crear una función similar a la que hemos usado, pero añadiendo un parámetro A

Public Function proxn2masa(n,a)
Dim p

p = primprox(n)
While Not escuad(p - a)
p = primprox(p)
Wend
proxn2masa = p
End Function

Con esta función se puede comprobar que,  dado cualquier valor de N (primo o no) y elegida una constante A, existe un número primo del tipo  N²+A superior a N

Observa un posible esquema de búsqueda:

En él elegimos N y A y se nos devuelve el primo adecuado y la raíz cuadrada de N-A