Una fórmula para contar primos recién salida del horno

La mayoría de los teoremas que se enseñan en los primeros cursos de la carrera de matemática (Álgebra I, Análisis I, etc.) son viejos, muy viejos. Y esto es necesario, no es sorprendente. Porque la matemática es como una escalera que hay que subir desde los primeros peldaños. Y además en la matemática, los viejos caminos sigue sirviendo.

Por ejemplo, la demostración  de la infinitud de los números primos de Euclides (hacia el 300 AC), no sólo sigue sirviendo hoy, sino que es fundamental en la educación de un matemático. Y el algoritmo conocido como la criba de Eratóstenes (aproximadamente de la misma época), sigue siendo el método básico para encontrar estas perlitas que son los números primos.

Esto contrasta enormemente por ejemplo con la situación en otras ciencias como la biología.  Por ejemplo, todo lo que se enseña por ejemplo en el curso de primer año de Introducción a la Biología Molecular y Celular tiene menos de 62 años. Esto se debe a que el descubrimiento de la estructura del ADN por Watson y Crick en 1953, produjo una verdadera revolución en esta ciencia; que está actualmente en una verdadera ebullición, con descubrimientos posiblemente revolucionarios todas las semanas.

Siempre me pregunté si esto no resulta desmotivante para los alumnos, y cómo podemos  transmitirles desde las primeras materias de la carrera que la matemática es algo vivo, en la cuál se está haciendo mucho, y quedan muchas cosas por descubrir.

Por ejemplo, volvamos a los números primos:  El interés de los matemáticos por ellos no disminuyó nunca, y sus secretos están lejos de haberse agotado, como hemos comentado en artículos anteriores en este blog. De hecho, algunos de los problemas abiertos más famosos de la matemática como la Hipótesis de Riemann y la conjetura de Golbach se relacionan con ellos. Sin embargo, los trabajos relacionados con estas conjeturas, usan sofisticadas técnicas analíticas; algo muy lejano de lo que podemos contar en álgebra I.

Por eso, me resultó grato entrar hace unos días en el Arxiv y encontrarme con el paper The prime counting function   (la función que cuenta primos) de Igor Turkanov. Este paper constituye un resultado nuevo e importante en el problema de contar los primos, que como hemos dicho es tan viejo como la matemática misma, ¡en 2016!. Y además, es algo que cualquier alumno de álgebra I podría entender porque no usa más que un poco de combinatoria, inducción y naturalmente, aritmética elemental. Quizás podría contarse en los cursos de esta materia, para mostrar que aún en estos problemas viejísimos hay resultados nuevos, y que están a su alcance.

¿Por qué el resultado de Turkanov es importante? Porque, si bien ya se conocían varias fórmulas para calcular la función pi(x) que cuenta los primos, como la fórmula de Legendre  y sus modificaciones: la fórmula de Lehmer la fórmula de Meissel y el  método de Mapes, estas fórmulas suelen requerir calcular y almacenar los primos hasta la raíz cuadrada de x, y tienen un carácter recursivo. En cambio, la fórmula de Tukanov no es recursiva, y sólo requiere generar listas estrictamente decrecientes de enteros menores o iguales que x, y calcular su mínimo común múltiplo. Lo que puede hacerse mediante el algoritmo de Euclides, explotando su relación con el máximo común divisor.

Para comprobar la validez de la fórmula de Turkanov, me puse a escribir una implementación en python., que transcribo más abajo.

# Implementación en Python 3 de la fórmula de Igor Turkanov
# para contar primos
# http://arxiv.org/abs/1603.02914
# Por Pablo De Nápoli <pdenapo@gmail.com> - Licencia: GPL versión 3

from math import floor,sqrt,gcd

# Esta función genera una lista cuyos elementos son todas
# las posibles listas [i_1,i_2_...,i_s]
# con 1 < i_1<i_2 < ... < i_s <= k
def generar_lista(s,k):
   L=[]
   for i in range(2,k+1):
    if s==1:
     L.append([i])
    else:
     M=generar_lista(s-1,i-1)
     for e in M:
      f=e
      f.append(i)
      L.append(f)
   return L

# Esta función calcula el mìnimo común mùltiplo de dos enteros
def lcm(n,m):
    return n*m//gcd(n,m)

# Esta función calcula el mìnimo común múltiplo de los elementos de
# una lista de enteros
def lcm_lista(L):
    if len(L)==1:
      return L[0]
    else:
      return lcm(lcm_lista(L[:-1]),L[-1])

# Esta función calcula la cantidad de primos <= n
# mediante la fòrmula de Igor Turkanov
def primes_pi(n):
    pi=n-1
    limite=floor(sqrt(n))
    for i in range(2,limite+1):
     pi=pi-(n//i-i+1)
    for s in range(2,limite+1):
     L=generar_lista(s,limite)
     t=0
     for I in L:
      lcm_I = lcm_lista(I)
      t=t+n//lcm_I - (I[-1]**2-1)//lcm_I
     if s%2==0:
      pi=pi+t
     else:
      pi=pi-t
    return pi

Para comprobar si nuestra implementación realmente funciona, escribí una serie de tests que comparan los valores calculados con los de obtenidos usando la funcíón primepi de Pari/GP (un programa muy utilizado en teoría de números), y que se pueden ejecutar utilizando pytest.

# Se puede ejecutar los tests con pytest
def test_100():
    assert primes_pi(100) == 25

def test_200():
    assert primes_pi(200) == 46

def test_300():
    assert primes_pi(300) == 62

¡Realmente funciona! (aunque es extremadamente lenta si uno quiere calcular primes_pi(n) para valores grandes de n ).