lunes, 9 de julio de 2018

Conjetura de Goldbach (Prime sum)

En matemáticas, la Conjetura de Goldbach es uno de los problemas más famosos que existe y que aun están por demostrarse (De ahí que sea conjetura y no teorema), el cual, en resumen dice:

Todo número par mayor que dos, puede escribirse como la suma de dos números primos.

Pero el día de hoy no vengo a hablarles sobre ésta, sino a traer un código que obtiene esos dos números.

Realmente, el código lo utilicé como respuesta para éste problema de interviewbit.com, y me gustó cómo quedó.

El código completo lo pueden encontrar en ésta dirección. Aquí sólo iré explicando lo que hacen los diferentes bloques.

Primero que nada, hay que explicar que para resolver el problema, se necesita usar la Criba de Eratóstenes para obtener todos los números primos entre 1 y n, donde n es un número par mayor a dos.

Sin embargo, como hay que hacerlo de manera óptima, no podemos guardar todos los números primos como enteros, ya que se necesitaría mucha memoria, por lo que los vamos a representar como un array de bits. En C++ (el lenguaje que usé), esto se logra con un bitset o con un vector<bool>

¿Cómo funciona esto del array de bits? Bueno, en esta propuesta de solución, cada elemento del array representa un número impar mayor a 2. ¿Por qué un número impar y mayor a dos? Porque todos los números primos, salvo el 2, son impares. Así que la posición 0 del array representa el 3, la 1 al 5, y así sucesivamente. Además, vamos a considerar que la posición -1 es 2.

Teniendo lo anterior, podemos obtener el valor de cada posición con la siguiente fórmula:

f(x) = 2            si x = -1
f(x) = 2 * x + 3    si x >= 0

donde x es la posición del elemento en el array. Por lo que:

f(-1) = 2
f(0)  = 3
f(1)  = 5
f(2)  = 7
f(3)  = 9
...
f(10) = 23
...

Aquí no hay mucho más qué decir, la función para obtener el valor es la siguiente:

Lo siguiente es implementar la criba de Eratóstenes. Para esto, crearemos un array de tamaño n / 2 + 1, ya que la mitad de los números son pares y, como especificamos antes, no los vamos a considerar.

Para obtener los números primos, vamos a asumir que todos los números impares lo son, así que nuestra tarea es encontrar y marcar aquellos que no. Para esto, vamos a asumir que toda posición con valor 0 en el vector de números impares, pertenece a un primo. Por lo que la posición 0, es decir, el 3, es primo. Ahora, vamos a marcar todos sus múltiplos como no-primos.

Podría parecer algo poco óptimo revisar cada posición del vector, obtener su valor y luego ver si es divisible entre el número primo que encontramos para saber si es múltiplo o no. Pero, si nos detenemos un poco a observar, notaremos que en este array de números impares, los multiplos impares de un número k, están separados k posiciones entre sí. Es decir, si el 3 está en la posición 0, el 9 está en posición 3 y el 15 en la posición 6. ¡Y esto ocurre para todos los números impares!

Si k = 3 se encuentra en i = 0
f(3) = 9
f(6) = 15
f(9) = 21

Si k = 7 se encuentra en i = 2
f(9)  = 21
f(16) = 35
f(23) = 49

Si k = 13 se encuentra en i = 5
f(18) = 39
f(31) = 65
f(44) = 91

Impresionante, ¿no? Cuando noté ésta relación, no lo creía. Tuve que hacer varios ejemplos para corroborarla. Obviamente no la demostré, pero seguro no es tan dificil (Para alguien que sepa demostrar).

Teniendo lo anterior, ahora sólo debemos encontrar el siguiente 0 en el array, y marcar todos sus múltiplos hasta n como no-primos, es decir, con un 1.

Nota: En el siguiente código, se utiliza el 0 para indicar algo donde intuitivamente usaríamos 1. Esto se debe a que inicialmente usaba un bitset, y éste se inicia en ceros. Al reemplazar el bitset con el vector, no hice el cambio, pero no debería haber mayor problema para realizarlo. Lo mismo pasa con la variable "last". El tamaño del bitset no se asigna en runtime, sino en compilación. Esta variable la utilizaba para marcar hasta dónde debía buscar en un bitset de 10,000,000 posiciones.

En el código anterior, numbers es el vector de booleanos.

Ya que obtuvimos todos los números primos entre 1 y n, debemos regresar los dos números primos cuya suma es igual a n. Tristemente, lo que sigue es fuerza bruta. Vamos a recorrer de 2 hasta n todos los números primos (llamaremos a este primer número k), y para cada k, vamos a tomar desde el número primo más grande menor a n (al cual llamaremos h) e iremos iterando hacia números primos más pequeños mientras que k + h >= n. Si resulta que k + h = n, regresamos esos dos números, en caso contrario, tomaremos el siguiente número primo más grande que k, y repetiremos el procedimiento con h de iterar desde el primo más grande menor a n.

Aunque la conjetura de Goldbach no se ha demostrado, para efectos prácticos asumimos que es verdadera, por lo que siempre encontraremos un par (k, h) cuya suma es igual n.

Un caso más a considerar es cuando n = 4, por simplicidad, si recibimos ese número, regresamos k = 2 y h = 2.

Con lo anterior, tenemos la solución al problema de interviewbit.

Espero que la explicación haya sido lo suficientemente clara. En caso de que no, pueden dejar comentarios. Recuerden que el enlace al código completo está en la parte de arriba.

Saludos.

PD. Este post se veía mucho mejor cuando lo escribí en markdown que cuando lo convertí a HTML.

No hay comentarios:

Publicar un comentario