{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# De tíos, primos, teoremas y conjeturas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Esta notebook fue creada originalmente como un blog post por [Raúl E. López Briega](http://relopezbriega.com.ar/) en [Mi blog sobre Python](http://relopezbriega.github.io). El contenido esta bajo la licencia BSD.*"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## El tío Petros y la conjetura\n",
"\n",
"Hace un tiempo atrás, quede atrapado en la lectura de la apasionante novela de Apostolos Doxiadis, [El tío Petros y la conjetura de Goldbach](http://www.amazon.es/El-tio-petros-conjetura-goldbach/dp/8440694903). La novela trata basicamente de la relación entre un joven, en busca de su vocación, y su tío, quien en el pasado fue un prodigio de las matemáticas, pero que luego se recluyó de su familia y de la comunidad científica consumido por el intento solitario de demostrar uno de los problemas abiertos más difíciles de la [teoría de números](https://es.wikipedia.org/wiki/Teor%C3%ADa_de_n%C3%BAmeros), la *[Conjetura de Goldbach](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach)*. Lo que más me sorprendió del problema que consumió la vida del querido tío Petros, es lo simple que es su enunciado; la *[Conjetura de Goldbach](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach)* nos dice que ***\"Todo número par mayor que 2 puede escribirse como suma de dos números primos.\"***\n",
"\n",
"Este enunciado, junto con la otra conjetura postulada por [Goldbach](https://es.wikipedia.org/wiki/Christian_Goldbach), conocida como la *[Conjetura debil de Goldbach](https://es.wikipedia.org/wiki/Conjetura_d%C3%A9bil_de_Goldbach)*, que nos dice que ***\"Todo número impar mayor que 5 puede expresarse como suma de tres números primos.\"***; trae a colación el concepto de los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* como bloques constructores de los enteros."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Los números primos\n",
"\n",
"Pero, ¿cómo es esto de que los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* pueden ser considerados como bloques constructores de los números enteros?\n",
"\n",
"Un *[número primo](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* es un entero positivo que solo puede ser dividido en dos [factores](https://es.wikipedia.org/wiki/Divisibilidad) distintos, 1 y si mismo. De esta definición se desprende que el número 1 no es un *[número primo](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* ya que solo puede ser dividido en un solo [factor](https://es.wikipedia.org/wiki/Divisibilidad); en cambio, el número 2 si es *[primo](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)*, el único *[número primo](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* que es par.\n",
"\n",
"La idea de que los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* pueden ser considerados como bloques constructores de los números enteros surge del enunciado del [Teorema fundamental de la aritmética](https://es.wikipedia.org/wiki/Teorema_fundamental_de_la_aritm%C3%A9tica) que nos dice que ***\"Todo entero positivo puede ser representado de forma única como un producto de factores primos\"***; así por ejemplo el número $28$ puede ser representado como $2^2 * 7$; o el $60$ como $2^2 * 3 * 5$. Este teorema es un concepto fundamental en [criptografía](https://es.wikipedia.org/wiki/Criptograf%C3%ADa), los principales algoritmos de cifrado que se utilizan hoy en día residen en la [factorización de primos](https://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros), ya que es un proceso que requiere de mucho esfuerzo para calcularse mientras más grande sea el número que queremos factorizar.\n",
"\n",
"Otro aspecto interesante de los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* es que parecen surgir en forma aleatoria, hay veces que pueden aparecer en pares como (11, 13), (29, 31) o (59, 61) pero otras veces puede haber un largo intervalo entre ellos. Aún no se ha encontrado una formula que pueda predecir cual va a ser el próximo *[número primo](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)*. Como parece ser bastante difícil encontrar un patrón en los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)*, el esfuerzo de los matemáticos paso de intentar encontrar un patrón a intentar comprender la distribución de los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* dentro de todos los enteros; es decir, intentar responder la pregunta de ¿Cuál es la probabilidad de que un número sea primo si elijo un número al azar en el rango de 0 a N?. Uno de los primeros en dar una respuesta bastante aproximada a esta pregunta fue [Gauss](https://es.wikipedia.org/wiki/Carl_Friedrich_Gauss), quien con tan solo 15 años de edad propuso la formula $\\pi(x)\\approx\\frac{x}{ln(x)}$ para responder a esa pregunta. \n",
"\n",
"La formula propuesta [Gauss](https://es.wikipedia.org/wiki/Carl_Friedrich_Gauss) implica que a medida que los números se hacen cada vez más grandes, los \n",
"*[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* son cada vez más escasos. Esto es lo que se conoce como [teorema de los números primos](https://es.wikipedia.org/wiki/Teorema_de_los_n%C3%BAmeros_primos).\n",
"A pesar de que los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* son cada vez más escasos mientras más grandes, siguen surgiendo indefinidamente, son infinitos; esto esta bien demostrado por el ya famoso [teorema de Euclides](https://es.wikipedia.org/wiki/Teorema_de_Euclides); quien incluyo una de las más bellas demostraciones de las matemáticas en su obra [Elementos](https://es.wikipedia.org/wiki/Elementos_de_Euclides) en el 300 AC.\n",
"\n",
"### Encontrando los números primos\n",
"\n",
"Para encontrar todos los *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)* menores que un número N, uno de los algoritmos más eficientes y más fáciles de utilizar es lo que se conoce como la [criba de Eratóstenes](https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes), el procedimiento que se utiliza consiste en crear una tabla con todos los números naturales comprendidos entre 2 y N, y luego ir tachando los números que no son primos de la siguiente manera: Comenzando por el 2, se tachan todos sus múltiplos; comenzando de nuevo, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos, así sucesivamente. La siguiente animación describe el procedimiento graficamente.\n",
"\n",
"\n",
"### Ejemplo en Python\n",
"\n",
"Veamos un ejemplo en [Python](https://www.python.org/) de como implementar la [criba de Eratóstenes](https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes) y un proceso de [factorización de primos](https://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 7]"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Factorizando primos en Python\n",
"import numpy as np\n",
"\n",
"def criba_eratostenes(n):\n",
" \"\"\"Criba Eratostenes\"\"\"\n",
" l=[]\n",
" multiplos = set()\n",
" for i in range(2, n+1):\n",
" if i not in multiplos:\n",
" l.append(i)\n",
" multiplos.update(range(i*i, n+1, i))\n",
" return l\n",
"\n",
"def factorizar_primos(n): \n",
" \"\"\"Factoriza un entero positivo en primos\n",
" \n",
" >>>factorizar_primos(28)\n",
" [2, 2, 7]\n",
" \"\"\"\n",
" if n <=1:\n",
" return \"Ingresar un entero mayor a 1\"\n",
" \n",
" factores = []\n",
" primos = criba_eratostenes(n)\n",
" pindex = 0\n",
" p = primos[pindex]\n",
" num = n\n",
" \n",
" while p != num:\n",
" if num % p == 0:\n",
" factores.append(p)\n",
" num //= p\n",
" else:\n",
" pindex += 1\n",
" p = primos[pindex]\n",
" \n",
" factores.append(p)\n",
" \n",
" return factores\n",
"\n",
"factorizar_primos(28) # Factores primos de 28"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[2, 991]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Factores primos de 1982\n",
"factorizar_primos(1982)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[5, 13, 31]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Factores primos de 2015\n",
"factorizar_primos(2015)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## La conjetura de Goldbach y Python\n",
"\n",
"La *[Conjetura de Goldbach](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach)*, es otro ejemplo de como también podemos construir todos los números enteros con simples operaciones aritméticas como la suma y no más que tres *[números primos](https://es.wikipedia.org/wiki/N%C3%BAmero_primo)*. Al día de hoy, la [conjetura](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach) continua sin poder ser demostrada; y es considerada uno de los problemas más difíciles de las matemáticas. La mayoría de los matemáticos estiman que es verdadera, ya que se ha mostrado cierta hasta por lo menos el $10^{18}$; aunque algunos dudan que sea cierta para números extremadamente grandes, el gran [Ramanujan](https://es.wikipedia.org/wiki/Srinivasa_Aiyangar_Ramanujan) dicen que se incluía en este último grupo.\n",
"\n",
"Obviamente, como este blog esta dedicado a [Python](https://www.python.org/), no podría concluir este artículo sin incluir una implementación de la *[Conjetura de Goldbach](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach)* en uno de los lenguajes que mejor se lleva con las matemáticas!\n",
"\n",
"En esta implementación vamos a utilizar tres funciones, en primer lugar una [criba de primos](https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes) vectorizada utilizando [numpy](http://www.numpy.org/), para lograr un mejor rendimiento que con la [criba de Eratóstenes](https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes) del ejemplo anterior; y luego vamos a tener dos sencillas funciones adicionales, una que nos devuelva la composición de Goldbach para cualquier número par que le pasemos como parámetro.(esta función solo nos va a devolver la primer solución que encuentra, ya que pueden existir varias soluciones para algunos enteros pares). Por último, la restante función va a listar los resultados de la *[Conjetura de Goldbach](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach)* para un rango de números enteros."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2000 = 3 + 1997\n",
"2002 = 3 + 1999\n",
"2004 = 5 + 1999\n",
"2006 = 3 + 2003\n",
"2008 = 5 + 2003\n",
"2010 = 7 + 2003\n",
"2012 = 13 + 1999\n",
"2014 = 3 + 2011\n",
"2016 = 5 + 2011\n"
]
}
],
"source": [
"# La conjetura de Goldbach en Python\n",
"import numpy as np\n",
"\n",
"def criba_primos(n):\n",
" \"\"\"Criba generadora de números primos.\n",
" \n",
" Input n>=6, devuleve un array de primos, 2 <= p < n \n",
" \"\"\"\n",
" criba = np.ones(n / 3 + (n % 6 == 2), dtype=np.bool)\n",
" for i in range(1, int(n**0.5 / 3 + 1)):\n",
" if criba[i]:\n",
" k = 3 * i + 1 | 1\n",
" criba[k * k / 3::2 * k] = False\n",
" criba[k * (k - 2 * (i & 1) + 4) / 3::2 * k] = False\n",
" return np.r_[2, 3, ((3 * np.nonzero(criba)[0][1:] + 1) | 1)]\n",
"\n",
"def goldbach(n):\n",
" \"\"\"imprime la composición de goldbach para n.\n",
"\n",
" >>> goldbach(28)\n",
" (5, 23)\n",
" \"\"\"\n",
" primos = criba_primos(n)\n",
" lo = 0\n",
" hi = len(primos) - 1\n",
" while lo <= hi:\n",
" sum = primos[lo] + primos[hi]\n",
" if sum == n:\n",
" break\n",
" elif sum < n:\n",
" lo += 1\n",
" else:\n",
" hi -= 1\n",
" else:\n",
" print(\"No se encontro resultado de la conjetura de Goldbach para {}\".format(n))\n",
"\n",
" return primos[lo], primos[hi]\n",
"\n",
"\n",
"def goldbach_list(lower, upper):\n",
" \"\"\"Imprime la composición de Goldbach para todos los números pares\n",
" grandes que 'lower' y menores o iguales que 'upper'.\n",
" \n",
" >>> goldbach_list(9,20)\n",
" 10 = 3 + 7\n",
" 12 = 5 + 7\n",
" 14 = 3 + 11\n",
" 16 = 3 + 13\n",
" 18 = 5 + 13\n",
" 20 = 3 + 17\n",
" \"\"\"\n",
"\n",
" # La conjetura se aplica a pares mayores que 2.\n",
" if lower % 2 != 0:\n",
" lower += 1\n",
" if lower < 4:\n",
" lower = 4\n",
" if upper % 2 != 0:\n",
" upper -= 1\n",
"\n",
" for n in range(lower, upper + 1, 2):\n",
" gb = goldbach(n)\n",
" print(\"{0} = {1} + {2}\".format(n, gb[0], gb[1]))\n",
"\n",
"# Goldbach entre 2000 y 2016\n",
"goldbach_list(2000, 2016)\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"9999980 = 7 + 9999973\n",
"9999982 = 11 + 9999971\n",
"9999984 = 11 + 9999973\n",
"9999986 = 13 + 9999973\n",
"9999988 = 17 + 9999971\n",
"9999990 = 17 + 9999973\n",
"9999992 = 19 + 9999973\n",
"9999994 = 3 + 9999991\n",
"9999996 = 5 + 9999991\n",
"9999998 = 7 + 9999991\n",
"10000000 = 29 + 9999971\n"
]
}
],
"source": [
"# Goldbach entre 9.999.980 y 10.000.000\n",
"goldbach_list(9999980, 10000000)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"99999980 = 193 + 99999787\n",
"99999982 = 11 + 99999971\n",
"99999984 = 13 + 99999971\n",
"99999986 = 139 + 99999847\n",
"99999988 = 17 + 99999971\n",
"99999990 = 19 + 99999971\n",
"99999992 = 3 + 99999989\n",
"99999994 = 5 + 99999989\n",
"99999996 = 7 + 99999989\n",
"99999998 = 67 + 99999931\n",
"100000000 = 11 + 99999989\n"
]
}
],
"source": [
"# Goldbach entre 99.999.980 y 100.000.000\n",
"goldbach_list(99999980, 100000000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Con esto termino, el que quiera puede divertirse intentando comprobar la *[Conjetura de Goldbach](https://es.wikipedia.org/wiki/Conjetura_de_Goldbach)*, aunque corre el riesgo de terminar desperdiciando su tiempo como el bueno del tío Petros en la novela. Espero que les haya parecido interesante el artículo.\n",
"\n",
"Saludos!\n",
"\n",
"*Este post fue escrito utilizando IPython notebook. Pueden descargar este [notebook](https://github.com/relopezbriega/relopezbriega.github.io/blob/master/downloads/pygoldbach.ipynb) o ver su versión estática en [nbviewer](http://nbviewer.ipython.org/github/relopezbriega/relopezbriega.github.io/blob/master/downloads/pygoldbach.ipynb).*"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3+"
}
},
"nbformat": 4,
"nbformat_minor": 0
}