{ "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": [ "\"De" ] }, { "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", "\"criba\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 }