{"id":7056,"date":"2022-05-27T11:28:33","date_gmt":"2022-05-27T09:28:33","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7056"},"modified":"2022-05-27T11:28:33","modified_gmt":"2022-05-27T09:28:33","slug":"polinomios-cuadraticos-generadores-de-primos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/polinomios-cuadraticos-generadores-de-primos\/","title":{"rendered":"Polinomios cuadr\u00e1ticos generadores de primos"},"content":{"rendered":"<p>En 1772, Euler public\u00f3 que el polinomio n\u00b2 + n + 41 genera 40 n\u00fameros primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n = 40, 40\u00b2+40+41 = 40(40+1)+41 es divisible por 41.<\/p>\n<p>Usando ordenadores, se descubri\u00f3 que el polinomio n\u00b2 &#8211; 79n + 1601 genera 80 n\u00fameros primos para todos los valores de n entre 0 y 79.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])\n<\/pre>\n<p>tal que <code>(generadoresMaximales n)<\/code> es el par <code>(m,xs)<\/code> donde<\/p>\n<ul>\n<li><code>xs<\/code> es la lista de pares <code>(x,y)<\/code> tales que <code>n\u00b2+xn+y<\/code> es uno de  polinomios que genera un n\u00famero m\u00e1ximo de n\u00fameros primos consecutivos a partir de cero entre todos los polinomios de la forma <code>n\u00b2+an+b<\/code>, con <code>|a| \u2264 n<\/code> y <code>|b| \u2264 n<\/code> y<\/li>\n<li><code>m<\/code> es dicho n\u00famero m\u00e1ximo.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   generadoresMaximales    4  ==  ( 3,[(-2,3),(-1,3),(3,3)])\n   generadoresMaximales    6  ==  ( 5,[(-1,5),(5,5)])\n   generadoresMaximales   41  ==  (41,[(-1,41)])\n   generadoresMaximales   50  ==  (43,[(-5,47)])\n   generadoresMaximales  100  ==  (48,[(-15,97)])\n   generadoresMaximales  200  ==  (53,[(-25,197)])\n   generadoresMaximales 1650  ==  (80,[(-79,1601)])\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort)\nimport Data.Numbers.Primes (primes, isPrime)\nimport I1M.PolOperaciones (valor, consPol, polCero)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ngeneradoresMaximales1 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales1 n =\n  (m,[(a,b) | a <- [-n..n], b <- [-n..n], nPrimos a b == m])\n  where m = maximum [nPrimos a b | a <- [-n..n], b <- [-n..n]]\n\n-- (nPrimos a b) es el n\u00famero de primos consecutivos generados por el\n-- polinomio n\u00b2 + an + b a partir de n=0. Por ejemplo,\n--    nPrimos (-1) 41     ==  41\n--    nPrimos (-79) 1601  ==  80\nnPrimos :: Integer -> Integer -> Int\nnPrimos a b =\n  length (takeWhile isPrime [n*n+a*n+b | n <- [0..]])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Notas:\n-- 1. Se tiene que b es primo, ya que para n = 0, se tiene que\n--    0\u00b2+a*0+b = b es primo.\n-- 2. Se tiene que 1+a+b es primo, ya que es el valor del polinomio para\n--    n = 1.\n\ngeneradoresMaximales2 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales2 n = (m,map snd zs)\n  where xs = [(nPrimos a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                    a <- [-n..n],\n                                    isPrime(1+a+b)]\n        ys = reverse (sort xs)\n        m  = fst (head ys)\n        zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ngeneradoresMaximales3 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales3 n = (m,map snd zs)\n  where xs = [(nPrimos a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                    p <- takeWhile (<=1+2*n) primes,\n                                    let a = p-b-1]\n        ys = reverse (sort xs)\n        m  = fst (head ys)\n        zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- 4\u00aa soluci\u00f3n (con la librer\u00eda de polinomios)\n-- ===========================================\n\ngeneradoresMaximales4 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales4 n = (m,map snd zs)\n  where xs = [(nPrimos2 a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                     p <- takeWhile (<=1+2*n) primes,\n                                     let a = p-b-1]\n        ys = reverse (sort xs)\n        m  = fst (head ys)\n        zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- (nPrimos2 a b) es el n\u00famero de primos consecutivos generados por el\n-- polinomio n\u00b2 + an + b a partir de n=0. Por ejemplo,\n--    nPrimos2 (-1) 41     ==  41\n--    nPrimos2 (-79) 1601  ==  80\nnPrimos2 :: Integer -> Integer -> Int\nnPrimos2 a b =\n  length (takeWhile isPrime [valor p n | n <- [0..]])\n  where p = consPol 2 1 (consPol 1 a (consPol 0 b polCero))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_generadoresMaximales :: Positive Integer -> Bool\nprop_generadoresMaximales (Positive n) =\n  all (equivalentes (generadoresMaximales1 n'))\n      [generadoresMaximales2 n',\n       generadoresMaximales3 n',\n       generadoresMaximales4 n']\n  where n' = n+1\n\nequivalentes :: (Int,[(Integer,Integer)]) -> (Int,[(Integer,Integer)]) -> Bool\nequivalentes (n,xs) (m,ys) =\n  n == m && sort xs == sort ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_generadoresMaximales\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> generadoresMaximales1 300\n--    (56,[(-31,281)])\n--    (2.10 secs, 2,744,382,760 bytes)\n--    \u03bb> generadoresMaximales2 300\n--    (56,[(-31,281)])\n--    (0.17 secs, 382,103,656 bytes)\n--    \u03bb> generadoresMaximales3 300\n--    (56,[(-31,281)])\n--    (0.19 secs, 346,725,872 bytes)\n--    \u03bb> generadoresMaximales4 300\n--    (56,[(-31,281)])\n--    (0.20 secs, 388,509,808 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Polinomios_cuadraticos_generadores_de_primos.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En 1772, Euler public\u00f3 que el polinomio n\u00b2 + n + 41 genera 40 n\u00fameros primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n = 40, 40\u00b2+40+41 = 40(40+1)+41 es divisible por 41. Usando ordenadores, se descubri\u00f3 que el polinomio n\u00b2 &#8211; 79n + 1601 genera 80 n\u00fameros primos&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7056"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7056"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7056\/revisions"}],"predecessor-version":[{"id":7057,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7056\/revisions\/7057"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}