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.