jueves, 27 de noviembre de 2014

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 n2+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 n2+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 n2+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 n2+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 n2+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  n2+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  n2+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  N2+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

lunes, 17 de noviembre de 2014

Sucesión de Perrin


En la pasada temporada dedicamos varias entradas a las sucesiones definidas mediante una recurrencia de segundo orden. Ahora comenzaremos una serie sobre las de tercer orden. Entre ellas son muy populares las de Perrin y Padovan. Como en las anteriores, nuestro planteamiento no será teórico, pues ya existe mucho publicado sobre ellas. El objetivo será crear esquemas y cálculos que faciliten  la comprensión de sus propiedades.

Sucesión de Perrin

La teoría fundamental sobre esta serie la puedes consultar en

http://mathworld.wolfram.com/PerrinSequence.html
http://en.wikipedia.org/wiki/Perrin_number

Aquí la describiremos con la ayuda de la herramienta que hemos ofrecido en entradas anteriores, alojada en

http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2

Definición

Esta sucesión es recursiva de tercer orden homogénea, por lo que necesita tres valores iniciales y que X(n) dependa de los tres valores anteriores X(n-1), X(n-2) y X(n-3) mediante la relación

Xn= A*Xn-1+B*Xn-2+C*Xn-3

En este caso particular sólo depende de los dos últimos, y no de X(n-1). Concretando:

Condiciones iniciales: X0=3   X1=0  X2=2 Ecuación de recurrencia: Xn= Xn-2+Xn-3

Es como una sucesión del tipo Fibonacci pero “con retraso”, pues los que se suman no son los dos anteriores, sino los que están un paso más atrás.

En nuestra hoja de cálculo se define así (segunda hoja del libro):



El primer coeficiente es nulo, que es lo que produce el “retraso”, y debajo tienes los tres valores iniciales.

La sucesión resultante la vemos pulsando el botón correspondiente:


Esta popular sucesión la tienes disponible en http://oeis.org/A001608, donde les llaman números skiponacci, quizás por los saltos o retardos que presentan: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853,…

Ecuación característica

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



Coinciden con las soluciones que da WxMaxima



La solución real 1,32471…(aquí sólo aproximada) es el número plástico y, cuyo nombre se eligió como afín al número de oro o el de plata. En estas páginas puedes estudiarlo más a fondo:

http://es.wikipedia.org/wiki/N%C3%BAmero_pl%C3%A1stico
http://revistasuma.es/IMG/pdf/57/055-064.pdf http://cscmates.blogspot.com.es/2010/11/el-numero-de-plastico.html

Recordemos que, como en sucesiones anteriores, todo número de Perrin es combinación lineal de las potencias de las tres soluciones de la ecuación característica, pero las dos complejas tienen módulo menor que la unidad, por lo que sus potencias tenderán a cero en valor absoluto. Por tanto, X(n) se acercará asintóticamente a yn

Se puede construir una tabla doble en la que se observe este acercamiento:



A partir de un cierto orden basta redondear la potencia para obtener el número de Perrin  correspondiente. Lo puedes comprobar en las últimas filas de la tabla.

Función generatriz

Usando procedimientos similares a los que explicamos para las recurrentes de segundo orden, se puede demostrar que la función generatriz es

Puedes comprobar que esta es la F.G. adecuada efectuando este desarrollo en PARI

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

Te escribirá en un archivo sucesión.txt su desarrollo, y aparecerán como coeficientes los términos de la sucesión de Perrin:

3 + 2*x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 12*x^9 + 17*x^10 + 22*x^11 + 29*x^12 + 39*x^13 + 51*x^14 + 68*x^15 + 90*x^16 + 119*x^17 + 158*x^18 + 209*x^19 + O(x^20)

Sucesión de Perrin y números primos

La propiedad más conocida de estos números es que si p es primo, p divide a X(p). Por ejemplo, X(11)=22, que es múltiplo de 11. Podemos construir una tabla en la que dividamos X(n) entre n y los cocientes enteros se corresponderán con los números primos:



A pesar de su carácter algo extraño, la propiedad ha sido demostrada para todos los números primos. La contraria no es cierta. X(n) puede ser múltiplo de n sin que este sea primo. A estos términos se les suele llamar pseudoprimos de Perrin (http://oeis.org/A013998):

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291,…

Otras propiedades

La paridad de X(n) recorre el ciclo {1, 0, 0, 1, 0, 1, 1} Es fácil de ver: las tres primeras vienen determinadas por la definición (en color rojo en la imagen). Las siguientes dependen de dos anteriores. Por tanto, existirá ciclo si se vuelve a repetir el par 1 0, y esto ocurre siete lugares más adelante (color verde):


Para ampliar el tema puedes visitar http://www.mathpages.com/home/kmath345/kmath345.htm en el que se incluye la espiral triangular creada con estos números.


Propiedades matriciales

Estas entradas sobre sucesiones recurrentes también se plantean el objetivo de un mayor conocimiento de las hojas de cálculo. Por eso vamos a aprovechar las propiedades matriciales de la sucesión de Perrin para  repasar este tipo de funciones.

La primera propiedad matricial se resume en la siguiente fórmula para n>2:


Recuerda que la traza es la suma de los elementos de la diagonal principal de una matriz cuadrada.
Para comprobarlo con una hoja de cálculo organizaremos este esquema:


Comenzamos escribiendo a la izquierda la matriz M dos veces, y a la derecha las multiplicamos.
Para ello usaremos la función matricial MMULT, pero como es de tipo matricial deberás seleccionar la matriz de la derecha (debajo del rótulo “Potencia n de M), después escribir una fórmula similar a esta: =MMULT(C3:E5;G3:I5), tomando como rangos los de las matrices de la izquierda. Cuando escribas la fórmula no termines con Intro, sino con la combinación Ctrl+Mayúsc+Intro, para indicar que la fórmula es de tipo matricial. Notarás que lo has escrito bien porque la fórmula se verá entre corchetes.

A la derecha de las matrices puedes incluir la traza de la tercera, que en la imagen te da 2. Después copia la tercera sobre la primera matriz con copia sólo de valores, y te resultará el siguiente número de Perrin, en este caso 3, porque esta propiedad genera la sucesión a partir del tercer término.
Seguirían 2, 5, 5, 7, 10,…

Variante de la anterior expresión

Si en lugar de usar la traza empleamos un producto por la matriz (en vertical) (3, 0, 2), obtenemos tres términos en lugar de uno. La expresión sería ahora:



Bastaría borrar la traza en el anterior esquema y sustituirla por otro nuevo producto matricial con la (3, 0, 2). Lo dejamos como ejercicio. Aquí tienes la generación de los términos 5, 7 y 10






martes, 4 de noviembre de 2014

Comprobar conjeturas con hoja de cálculo. Goldbach.


La formulación más simple de la Conjetura de Goldbach es:

Todo número par mayor que 2 es suma de dos primos

Fue propuesta por Goldbach el 7 de Junio de 1742, en una carta dirigida a Euler.  En realidad, su propuesta se refería a la conjetura ternaria: " Todo número impar es la suma de tres primos" y Euler le respondió con la propuesta binaria que todos conocemos.

Ha sido comprobada hasta números muy grandes, pero no se ha podido demostrar. No obstante, se han logrado resultados provisionales:

Cualquier número par es suma de 6 o menos números primos.(Ramaré 1995)

Todo número par suficientemente grande es suma de un primo y del producto de dos primos.(Chen 1966)

Todo número impar N mayor que 5 es suma de tres primos. (Demostración de la conjetura ternaria a cargo de Vinogradov en 1937).

En esta entrada sólo nos plantearemos, como en toda la serie que vamos desarrollando sobre conjeturas, la comprobación de algunos aspectos de la misma mediante el uso de la hoja de cálculo.

Primer nivel

Comprobaremos la conjetura en tres niveles distintos, según el uso que se haga del lenguaje de macros. En primer lugar lo efectuaremos con las técnicas usuales de las hojas de cálculo. Usaremos la hoja Conjeturas, alojada en la página

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

(Búscala en la relación de herramientas)

Organizaremos la comprobación según un esquema similar a este:





Escribimos un número par mayor que 2 en una celda. En la imagen es el 612. Después ordenamos los números primos en columna, hasta el límite que queramos. Para ello escribimos el 2, debajo primprox(2) (función implementada en esta hoja, y que encuentra el primo siguiente a uno dado).

Rellenamos hacia abajo y nos resultará la lista de primos.

En una segunda columna escribiremos una fórmula similar a a siguiente, que copiaremos de arriba a abajo:

=SI(Y(F15<=H$11/2;esprimo(H$11-F15));H$11-F15;"")

En ella H11 es la celda donde hemos escrito el 612. En tu caso podrá ser otra. La F15 en nuestro esquema apunta al número primo que tiene a su izquierda. De esa forma, la podemos interpretar así: “Si el primo no llega a la mitad del número par probado (aquí el 612) y su diferencia con él es otro primo, escribo esa diferencia, pero en caso contrario dejo la celda en blanco”.

Es sencillo de entender y funciona escribiendo los pares de primos en los que se descompone el 612. En la imagen 5+607, 11+601, 19+593,…hasta un total de 26 pares. Si no logras ese número, deberás rellenar hacia abajo las dos columnas hasta llegar a la mitad de 612

Este esquema puede aclarar, probando con varios pares, el sentido de la conjetura. También te da confianza en ella, pues no sólo existe un par de primos para cada número par, sino muchos. ¡Pero no se ha probado aún!

Nivel 2

Ya que con el esquema anterior nos han resultado varias descomposiciones en primos para cada número par, podíamos simplificar mucho si lo plasmáramos en una función. En la hoja de cálculo que estamos usando hemos implementado NUMGOLDBACH(N), que devuelve un cero si N no es par y el número de descomposiciones si es par. En el caso del 612 devuelve correctamente 26.



Aquí tienes los primeros resultados. Si la conjetura es cierta, deberán ser todos mayores que 0. Están recogidos en http://oeis.org/A045917

Merece la pena recorrer la codificación de esta función y así entenderás mejor las cuestiones.

Public Function numgoldbach(n)
Dim ng, i

If n <> 2 * Int(n / 2) Then  ‘si es impar devuelve un cero (valor de ng
ng = 0
Else
i = 2: ng = 0
While i <= n / 2  ‘si es par recorre todas las posibles sumas de primos
If esprimo(n - i) Then ng = ng + 1 ‘si el segundo sumando es primo, incrementa el contador ng
i = primprox(i) ‘esta línea asegura que el primer sumando sea primo
Wend
End If
numgoldbach = ng
End Function

Nivel 3

Podemos dejar que sea la hoja de cálculo la que recorra automáticamente los primeros números hasta un tope o hasta que numgoldbach dé un cero. Como lo segundo es imposible para números pequeños (ya está comprobada la conjetura), el resultado final será siempre un cero.

Podíamos usar un esquema similar al siguiente:



Escribimos un tope, pulsamos el botón e irán apareciendo valores de Numgoldbach, ninguno nulo, hasta finalizar la búsqueda. Si uno fuera cero, se interrumpiría el proceso con un solemne mensaje. La programación del botón podría ser similar a esta:

Sub buscagoldbach()
Dim i, g, p

p = ActiveWorkbook.Sheets(1).Cells(5, 3).Value ‘lee el tope
i = 4 ‘inicio búsqueda
g = 1’inicio valor de numgolbach
While g <> 0 And i <= p
i = i + 2 ‘busca de 2 en 2
g = numgoldbach(i)
ActiveWorkbook.Sheets(1).Cells(6, 3).Value = g ‘escribe el valor de g
If g = 0 Then MsgBox ("¡Contraejemplo!") ‘Esto no va a ocurrir
Wend
End Sub

Variantes

Variante ternaria

“Todo número impar mayor que 5 es la suma de tres primos"

No vamos a repetir con ella los tres niveles anteriores. El primer nivel necesitaría un estructura de datos tridimensional, poco intuitiva en una hoja de dos dimensiones. El tercero sería semejante al del primer caso. Así que sólo desarrollaremos un esquema con todas las posibles descomposiciones en tres sumandos primos:








Como en el caso anterior, no vamos a analizar si el número es impar o no. Simplemente hemos programado un botón que lo descompone en esos sumandos de todas las formas posibles (lo haremos con sumandos decrecientes)

Para quien le guste la programación, ahí tiene explicado el algoritmo que hemos usado:

Sub goldbach3()
Dim fila, a, b, c, n

fila = 7
n = ActiveWorkbook.Sheets(1).Cells(fila, 3).Value ‘lee el número, que se encuentra en C7
a = 2 ‘primer sumando primo
While a < n ‘ el primer sumando llega hasta n en lo posible
b = 2
While b < a ‘ el segundo es inferior al primero
c = n - a – b ‘tercer sumando
If esprimo(c) And c <= b Then ‘si el tercer sumando también es primo, se presenta el resultado
fila = fila + 1
ActiveWorkbook.Sheets(1).Cells(fila, 3).Value = a
ActiveWorkbook.Sheets(1).Cells(fila, 4).Value = b
ActiveWorkbook.Sheets(1).Cells(fila, 5).Value = c
End If
b = primprox(b) ‘se incrementa el segundo primo
Wend
a = primprox(a) 'se incrementa el primero
Wend
End Sub 

Como era de esperar, siempre aparecen los tres sumandos primos. Se deja a los lectores el definir una función que cuente las soluciones. Siempre existirá al menos una.

Expresión mediante equidistancia

Un comentario a la entrada http://culturacientifica.com/2013/06/26/la-conjetura-de-goldbach/ me ha dado la idea de organizar una comprobación distinta.

Si la conjetura es cierta, para todo número par 2N, si es la suma de dos primos p y q, con p>q, cumplirán que p+q=2N, o bien que p-N=N-q:

Todo número entero positivo mayor que 4 es equidistante de dos primos

Es fácil ver que es otra formulación distinta de la conjetura de Goldbach. En los párrafos anteriores hemos visto la consecuencia directa. A la inversa, si es cierto que todo N equidista de dos primos, dado un par 2N aplicamos p-N=N-q para cierto par de primos, con lo que 2N=p+q. El exigir que sea mayor que 4 es porque no habría primos inferiores para números menores.

Es muy fácil organizar la comprobación con esta variante. Lo efectuaremos en el Nivel 1, de cálculo manual:



Escribimos la lista de números consecutivos 1, 2, 3,…y los sumamos y restamos con el número dado. Después, en la tercera columna, escribimos una fórmula similar a

=SI(Y(ESPRIMO(D9);ESPRIMO(E9));"SI";"") 

que nos devuelve un “SI” si los equidistantes son primos.

En la imagen, 17=29-12 y 41=29+12.