Polinomios cuadráticos generadores de primos

José A. Alonso

21-04-2016

En 1772, Euler publicó que el polinomio n² + n + 41 genera 40 números primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n=40, 40²+40+41 = 40(40+1)+41 es divisible por 41.

Usando ordenadores, se descubrió el polinomio n² - 79n + 1601 que genera 80 números primos para todos los valores de n entre 0 y 79.

Definir la función

generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])

tal que (generadoresMaximales n) es el par (m,xs) donde

xs es la lista de pares (x,y) tales que n²+xn+y es uno de los polinomios que genera un número máximo de números primos consecutivos a partir de cero entre todos los polinomios de la forma n²+an+b, con |a| ≤ n y |b| ≤ n y
m es dicho número máximo.

Por ejemplo,

generadoresMaximales    4  ==  ( 3,[(-2,3),(-1,3),(3,3)])
generadoresMaximales    6  ==  ( 5,[(-1,5),(5,5)])
generadoresMaximales   50  ==  (43,[(-5,47)])
generadoresMaximales  100  ==  (48,[(-15,97)])
generadoresMaximales  200  ==  (53,[(-25,197)])
generadoresMaximales 1650  ==  (80,[(-79,1601)])

Soluciones

import Data.List (nub, sort)
import Data.Numbers.Primes (primes, isPrime)
import I1M.PolOperaciones (valor, consPol, polCero)

-- 1ª solución
-- ===========

generadoresMaximales1 :: Integer -> (Int,[(Integer,Integer)])
generadoresMaximales1 n =
    (m,[((a,b)) | a <- [-n..n], b <- [-n..n], nPrimos a b == m])
    where m = maximum $ [nPrimos a b | a <- [-n..n], b <- [-n..n]]

-- (nPrimos a b) es el número de primos consecutivos generados por el
-- polinomio n² + an + b a partir de n=0. Por ejemplo,
--    nPrimos 1 41        ==  40
--    nPrimos (-79) 1601  ==  80
nPrimos :: Integer -> Integer -> Int
nPrimos a b =
    length $ takeWhile isPrime [n*n+a*n+b | n <- [0..]]

-- 2ª solución (reduciendo las cotas)
-- ==================================

-- Notas:
-- 1. Se tiene que b es primo, ya que para n=0, se tiene que 0²+a*0+b =
--    b es primo.
-- 2. Se tiene que 1+a+b es primo, ya que es el valor del polinomio para
--    n=1.

generadoresMaximales2 :: Integer -> (Int,[(Integer,Integer)])
generadoresMaximales2 n = (m,map snd zs)
    where xs = [(nPrimos a b,(a,b)) | b <- takeWhile (<=n) primes,
                                      a <- [-n..n],
                                      isPrime(1+a+b)]
          ys = reverse (sort xs)
          m  = fst (head ys)
          zs = takeWhile (\(k,_) -> k == m) ys

-- 3ª solución (reduciendo las cotas)
-- ==================================

generadoresMaximales3 :: Integer -> (Int,[(Integer,Integer)])
generadoresMaximales3 n = (m,map snd zs)
    where xs = [(nPrimos a b,(a,b)) | let ps = takeWhile (<=n) primes,
                                      b <- ps,
                                      let c = b+1-n,
                                      p <- dropWhile (<c) ps,
                                      let a = p-b-1]
          ys = reverse (sort xs)
          m  = fst (head ys)
          zs = takeWhile (\(k,_) -> k == m) ys

-- 4ª solución (con la librería de polinomios)
-- ===========================================

generadoresMaximales4 :: Integer -> (Int,[(Integer,Integer)])
generadoresMaximales4 n = (m,map snd zs)
    where xs = [(nPrimos2 a b,(a,b)) | let ps = takeWhile (<=n) primes,
                                       b <- ps,
                                       let c = b+1-n,
                                       p <- dropWhile (<c) ps,
                                       let a = p-b-1]
          ys = reverse (sort xs)
          m  = fst (head ys)
          zs = takeWhile (\(k,_) -> k == m) ys

-- (nPrimos2 a b) es el número de primos consecutivos generados por el
-- polinomio n² + an + b a partir de n=0. Por ejemplo,
--    nPrimos2 1 41        ==  40
--    nPrimos2 (-79) 1601  ==  80
nPrimos2 :: Integer -> Integer -> Int
nPrimos2 a b =
    length $ takeWhile isPrime [valor p n | n <- [0..]]
    where p = consPol 2 1 (consPol 1 a (consPol 0 b polCero))


-- Comparación de eficiencia
--    λ> generadoresMaximales1 200
--    (53,[(-25,197)])
--    (3.06 secs, 720683776 bytes)
--    λ> generadoresMaximales1 300
--    (56,[(-31,281)])
--    (6.65 secs, 1649274220 bytes)
--
--    λ> generadoresMaximales2 200
--    (53,[(-25,197)])
--    (0.25 secs, 94783464 bytes)
--    λ> generadoresMaximales2 300
--    (56,[(-31,281)])
--    (0.51 secs, 194776708 bytes)
--
--    λ> generadoresMaximales3 200
--    (53,[(-25,197)])
--    (0.00 secs, 84277672 bytes)
--    λ> generadoresMaximales3 300
--    (56,[(-31,281)])
--    (0.17 secs, 157788856 bytes)
--
--    λ> generadoresMaximales4 200
--    (53,[(-25,197)])
--    (0.20 secs, 105941096 bytes)
--    λ> generadoresMaximales4 300
--    (56,[(-31,281)])
--    (0.35 secs, 194858344 bytes)