{"id":7764,"date":"2022-07-30T08:48:35","date_gmt":"2022-07-30T06:48:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7764"},"modified":"2022-07-30T08:48:35","modified_gmt":"2022-07-30T06:48:35","slug":"pfh-la-semana-en-exercitium-29-de-julio-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-29-de-julio-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (29 de julio de 2022)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Huecos maximales entre primos<\/a><\/li>\n<li><a href=\"#ej2\">2. N\u00fameros belgas<\/a><\/li>\n<li><a href=\"#ej3\">3. La serie de Thue-Morse<\/a><\/li>\n<li><a href=\"#ej4\">4. La sucesi\u00f3n de Thue-Morse<\/a><\/li>\n<li><a href=\"#ej5\">5. Sumas de dos primos<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Huecos maximales entre primos<\/h3>\n<p>El <strong>hueco de un n\u00famero primo<\/strong> p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros n\u00fameros son<\/p>\n<pre lang=\"text\">\n   Primo Hueco\n    2    1\n    3    2\n    7    4\n   11    2\n<\/pre>\n<p>El hueco de un n\u00famero primo p es <strong>maximal<\/strong> si es mayor que  huecos de todos los n\u00fameros menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es<\/p>\n<pre lang=\"text\">\n   Primo Hueco\n     2    1\n     3    2\n     7    4\n    23    6\n    89    8\n   113   14\n   523   18\n   887   20\n<\/pre>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   primosYhuecosMaximales :: [(Integer,Integer)]\n<\/pre>\n<p>cuyos elementos son los n\u00fameros primos con huecos maximales junto son sus huecos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 8 primosYhuecosMaximales\n   [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]\n   \u03bb> primosYhuecosMaximales !! 20\n   (2010733,148)\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosYhuecosMaximales1 :: [(Integer,Integer)]\nprimosYhuecosMaximales1 = \n  [(p,huecoPrimo p) | p <- primes, esMaximalHuecoPrimo p]\n\n-- (siguientePrimo x) es el menor primo mayor que x. Por ejemplo,\n--    siguientePrimo 7  ==  11\n--    siguientePrimo 8  ==  11\nsiguientePrimo :: Integer -> Integer\nsiguientePrimo p =\n  head (dropWhile (<= p) primes)\n\n-- (huecoPrimo p) es la distancia del primo p hasta el siguiente\n-- primo. Por ejemplo,\n--    huecoPrimo 7  ==  4\nhuecoPrimo :: Integer -> Integer\nhuecoPrimo p = siguientePrimo p - p\n\n-- (esMaximalHuecoPrimo p) se verifica si el hueco primo de p es\n-- maximal. Por ejemplo,\n--    esMaximalHuecoPrimo  7  ==  True\n--    esMaximalHuecoPrimo 11  ==  False\nesMaximalHuecoPrimo :: Integer -> Bool\nesMaximalHuecoPrimo p =\n  and [huecoPrimo n < h | n <- takeWhile (< p) primes]\n  where h = huecoPrimo p\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosYhuecosMaximales2 :: [(Integer,Integer)]\nprimosYhuecosMaximales2 = aux primosYhuecos\n  where aux ((x,y):ps) = (x,y) : aux (dropWhile (\\(_,b) -> b <= y) ps)\n\n-- primosYhuecos es la lista de los n\u00fameros primos junto son sus\n-- huecos. Por ejemplo, \n--    \u03bb> take 10 primosYhuecos\n--    [(2,1),(3,2),(5,2),(7,4),(11,2),(13,4),(17,2),(19,4),(23,6),(29,2)]\nprimosYhuecos :: [(Integer,Integer)]\nprimosYhuecos =\n  [(x,y-x) | (x,y) <- zip primes (tail primes)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nprimosYhuecosMaximales3 :: [(Integer,Integer)]\nprimosYhuecosMaximales3 = aux 0 primes\n  where aux n (x:y:zs) | y-x > n   = (x,y-x) : aux (y-x) (y:zs)\n                       | otherwise = aux n (y:zs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosYhuecosMaximales :: NonNegative Int -> Bool\nprop_primosYhuecosMaximales (NonNegative n) =\n  all (== primosYhuecosMaximales1 !! n)\n      [primosYhuecosMaximales2 !! n,\n       primosYhuecosMaximales3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=12}) prop_primosYhuecosMaximales\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosYhuecosMaximales1 !! 10\n--    (9551,36)\n--    (2.63 secs, 7,400,316,112 bytes)\n--    \u03bb> primosYhuecosMaximales2 !! 10\n--    (9551,36)\n--    (0.01 secs, 7,060,744 bytes)\n--    \u03bb> primosYhuecosMaximales3 !! 10\n--    (9551,36)\n--    (0.01 secs, 4,000,368 bytes)\n--    \n--    \u03bb> primosYhuecosMaximales2 !! 22\n--    (17051707,180)\n--    (7.90 secs, 17,275,407,712 bytes)\n--    \u03bb> primosYhuecosMaximales3 !! 22\n--    (17051707,180)\n--    (3.78 secs, 8,808,779,096 bytes)\n<\/pre>\n<h4>Referencias<\/h4>\n<p>Basado en el ejercicio <a href=\"http:\/\/bit.ly\/22UfDJN\">Maximal prime gaps<\/a> de<br \/>\n<a href=\"http:\/\/programmingpraxis.com\">Programming Praxis<\/a>.<\/p>\n<p>Otras referencias<\/p>\n<ul>\n<li>C. Caldwell <a href=\"http:\/\/bit.ly\/1Znusp5\">The gaps between primes<\/a>.<\/li>\n<li>J.K. Andersen <a href=\"http:\/\/bit.ly\/1ZntwRi\">Maximal prime gaps<\/a>.<\/li>\n<li>N.J.A. Sloane <a href=\"http:\/\/oeis.org\/A002386\">Sequence A002386 en OEIS<\/a>.<\/li>\n<li>N.J.A. Sloane <a href=\"http:\/\/oeis.org\/A005250\">Sequence A005250 en OEIS<\/a>.<\/li>\n<li>E.W. Weisstein <a href=\"http:\/\/bit.ly\/1ZnubCq\">Prime gaps<\/a> en MathWorld.<\/li>\n<\/ul>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Huecos_maximales_entre_primos.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. N\u00fameros belgas<\/h3>\n<p>Un n\u00famero n es <strong>k-belga<\/strong> si la sucesi\u00f3n cuyo primer elemento es k y  cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n.<\/p>\n<p>El 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8, &#8230; hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, &#8230; Como se alcanza el 18, resulta que el 18 es 0-belga.<\/p>\n<p>El 19 no es 1-belga, porque a partir del 1 vamos a ir  sucesivamente 1, 9, 1, 9, &#8230; hasta llegar o sobrepasar el 18: 0, 1, 10, 11, 20, 21, &#8230; Como no se alcanza el 19, resulta que el 19 no es 1-belga.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   esBelga :: Int -> Int -> Bool\n<\/pre>\n<p>tal que (esBelga k n)  se verifica si n es k-belga. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   esBelga 0 18                              ==  True\n   esBelga 1 19                              ==  False\n   esBelga 0 2016                            ==  True\n   [x | x <- [0..30], esBelga 7 x]           ==  [7,10,11,21,27,29]\n   [x | x <- [0..30], esBelga 10 x]          ==  [10,11,20,21,22,24,26]\n   length [n | n <- [1..10^6], esBelga 0 n]  ==  272049\n<\/pre>\n<p>Comprobar con QuickCheck que para todo n\u00famero entero positivo n, si k es el resto de n entre la suma de los d\u00edgitos de n, entonces n es k-belga.<\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Char (digitToInt)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesBelga1 :: Int -> Int -> Bool\nesBelga1 k n =\n  n == head (dropWhile (<n) (scanl (+) k (cycle (digitos n))))\n\ndigitos :: Int -> [Int]\ndigitos n = map digitToInt (show n)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesBelga2 :: Int -> Int -> Bool\nesBelga2 k n =\n  k <= n &#038;&#038; n == head (dropWhile (<n) (scanl (+) (k + q * s) ds))\n  where ds = digitos n\n        s  = sum ds\n        q  = (n - k) `div` s\n\n-- Equivalencia\n-- ============\n\n-- La propiedad es\nprop_esBelga :: Positive Int -> Positive Int -> Bool\nprop_esBelga (Positive k) (Positive n) = \n  esBelga1 k n == esBelga2 k n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_esBelga\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length [n | n <- [1..2*10^4], esBelga1 0 n]\n--    6521\n--    (6.27 secs, 6,508,102,192 bytes)\n--    \u03bb> length [n | n <- [1..2*10^4], esBelga2 0 n]\n--    6521\n--    (0.07 secs, 46,741,144 bytes)\n\n-- Verificaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_Belga :: Positive Int -> Bool\nprop_Belga (Positive n) = \n  esBelga2 k n\n  where k = n `mod` sum (digitos n)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_Belga\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Referencias<\/h4>\n<p>Basado en el art\u00edculo <a href=\"http:\/\/bit.ly\/1n49fPh\">N\u00fameros belgas<\/a> del blog <a href=\"http:\/\/hojaynumeros.blogspot.com.es\">N\u00fameros y hoja de c\u00e1lculo<\/a> de <a href=\"http:\/\/bit.ly\/1nrlV3l\">Antonio Rold\u00e1n Mart\u00ednez<\/a>.<\/p>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numeros_belgas.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. La serie de Thue-Morse<\/h3>\n<p>La <a href=\"http:\/\/bit.ly\/1KvZONW\">serie de Thue-Morse<\/a> comienza con el t\u00e9rmino [0] y sus siguientes t\u00e9rminos se construyen a\u00f1adi\u00e9ndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros t\u00e9rminos de la serie son<\/p>\n<pre lang=\"text\">\n   [0]\n   [0,1]\n   [0,1,1,0]\n   [0,1,1,0,1,0,0,1]\n   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\n<\/pre>\n<p>Definir la lista<\/p>\n<pre lang=\"text\">\n   serieThueMorse :: [[Int]]\n<\/pre>\n<p>tal que sus elementos son los t\u00e9rminos de la serie de Thue-Morse. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 4 serieThueMorse\n   [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse1 :: [[Int]]\nserieThueMorse1 = map termSerieThueMorse [0..]\n\n-- (termSerieThueMorse n) es el t\u00e9rmino n-\u00e9simo de la serie de\n-- Thue-Morse. Por ejemplo, \n--    termSerieThueMorse 1  ==  [0,1]\n--    termSerieThueMorse 2  ==  [0,1,1,0]\n--    termSerieThueMorse 3  ==  [0,1,1,0,1,0,0,1]\n--    termSerieThueMorse 4  ==  [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\ntermSerieThueMorse :: Int -> [Int]\ntermSerieThueMorse 0 = [0]\ntermSerieThueMorse n = xs ++ complementaria xs\n  where xs = termSerieThueMorse (n-1)\n\n-- (complementaria xs) es la complementaria de la lista xs (formada por\n-- ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el\n-- 1 por 0. Por ejemplo, \n--    complementaria [1,0,0,1,1,0,1]  ==  [0,1,1,0,0,1,0]\ncomplementaria :: [Int] -> [Int]\ncomplementaria = map (1-)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse2 :: [[Int]]\nserieThueMorse2 = [0] : map paso serieThueMorse2\n  where paso xs = xs ++ complementaria xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse3 :: [[Int]]\nserieThueMorse3 = iterate paso [0]\n  where paso xs = xs ++ complementaria xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Observando que cada t\u00e9rmino de la serie de Thue-Morse se obtiene del\n-- anterior sustituyendo los 1 por 1, 0 y los 0 por  0, 1. \n\nserieThueMorse4 :: [[Int]]\nserieThueMorse4 = [0] : map (concatMap paso4) serieThueMorse4\n  where paso4 x = [x,1-x]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_serieThueMorse :: NonNegative Int -> Bool \nprop_serieThueMorse  (NonNegative n) =\n  all (== serieThueMorse1 !! n)\n      [serieThueMorse2 !! n,\n       serieThueMorse3 !! n,\n       serieThueMorse4 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_serieThueMorse\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> (serieThueMorse1 !! 23) !! (2^22)\n--    1\n--    (1.08 secs, 839,419,224 bytes)\n--    \u03bb> (serieThueMorse2 !! 23) !! (2^22)\n--    1\n--    (0.61 secs, 839,413,592 bytes)\n--    \u03bb> (serieThueMorse3 !! 23) !! (2^22)\n--    1\n--    (1.43 secs, 839,413,592 bytes)\n--    \u03bb> (serieThueMorse4 !! 23) !! (2^22)\n--    1\n--    (1.57 secs, 1,007,190,024 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/<\/p>\n<h4>Referencias<\/h4>\n<ul>\n<li>N.J.A. Sloane <a href=\"http:\/\/oeis.org\/A010060\">Sucesi\u00f3n A010060 en OEIS<\/a>.<\/li>\n<li>Programming Praxis <a href=\"http:\/\/bit.ly\/1n2PdFk\">Thue-Morse sequence<\/a>.<\/li>\n<li>Wikipedia <a href=\"http:\/\/bit.ly\/1KvZONW\">Thue\u2013Morse sequence<\/a><\/li>\n<\/ul>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. La sucesi\u00f3n de Thue-Morse<\/h3>\n<p>La serie de Thue-Morse comienza con el t\u00e9rmino [0] y sus siguientes t\u00e9rminos se construyen a\u00f1adi\u00e9ndole al anterior su complementario. Los primeros t\u00e9rminos de la serie son<\/p>\n<pre lang=\"text\">\n   [0]\n   [0,1]\n   [0,1,1,0]\n   [0,1,1,0,1,0,0,1]\n   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\n<\/pre>\n<p>De esta forma se va formando una sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...\n<\/pre>\n<p>que se conoce como la <a href=\"https:\/\/bit.ly\/3PE9LRJ\">sucesi\u00f3n de Thue-Morse<\/a>.<\/p>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   sucThueMorse :: [Int]\n<\/pre>\n<p>cuyos elementos son los de la sucesi\u00f3n de Thue-Morse. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 30 sucThueMorse\n   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]\n   \u03bb> map (sucThueMorse4 !!) [1234567..1234596] \n   [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0]\n   \u03bb> map (sucThueMorse4 !!) [4000000..4000030] \n   [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1]\n<\/pre>\n<p>Comprobar con QuickCheck que si s(n) representa el t\u00e9rmino n-\u00e9simo de la sucesi\u00f3n de Thue-Morse, entonces<\/p>\n<pre lang=\"text\">\n   s(2n)   = s(n)\n   s(2n+1) = 1 - s(n)\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse1 :: [Int]\nsucThueMorse1 = map termSucThueMorse1 [0..]\n\n-- (termSucThueMorse1 n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n-- Thue-Morse. Por ejemplo, \n--    termSucThueMorse1 0  ==  0\n--    termSucThueMorse1 1  ==  1\n--    termSucThueMorse1 2  ==  1\n--    termSucThueMorse1 3  ==  0\n--    termSucThueMorse1 4  ==  1\ntermSucThueMorse1 :: Int -> Int\ntermSucThueMorse1 0 = 0\ntermSucThueMorse1 n = \n  (serieThueMorse !! k) !! n\n  where k = 1 + floor (logBase 2 (fromIntegral n))\n\n-- serieThueMorse es la lista cuyos elementos son los t\u00e9rminos de la\n-- serie de Thue-Morse. Por ejemplo, \n--    \u03bb> take 4 serieThueMorse3\n--    [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]\nserieThueMorse :: [[Int]]\nserieThueMorse = iterate paso [0]\n  where paso xs = xs ++ map (1-) xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse2 :: [Int]\nsucThueMorse2 = \n  0 : intercala (map (1-) sucThueMorse2) (tail sucThueMorse2)\n\n-- (intercala xs ys) es la lista obtenida intercalando los elementos de\n-- las listas infinitas xs e ys. Por ejemplo, \n--    take 10 (intercala [1,5..] [2,4..])  ==  [1,2,5,4,9,6,13,8,17,10]\nintercala :: [a] -> [a] -> [a]\nintercala (x:xs) ys = x : intercala ys xs \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse3 :: [Int]\nsucThueMorse3 = 0 : 1 : aux (tail sucThueMorse3) \n  where aux (x : xs) = x : (1 - x) : aux xs\n\n\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse4 :: [Int]\nsucThueMorse4 = 0 : aux [1]\n  where aux xs = xs ++ aux (xs ++ map (1-) xs) \n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_termSucThueMorse :: NonNegative Int -> Bool\nprop_termSucThueMorse (NonNegative n) =\n  sucThueMorse1 !! (2*n)   == sn &&\n  sucThueMorse1 !! (2*n+1) == 1 - sn \n  where sn = sucThueMorse1 !! n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_termSucThueMorse\n--    +++ OK, passed 100 tests.\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse5 :: [Int]\nsucThueMorse5 = map termSucThueMorse5 [0..]\n\n-- (termSucThueMorse5 n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n-- Thue-Morse. Por ejemplo, \n--    termSucThueMorse5 0  ==  0\n--    termSucThueMorse5 1  ==  1\n--    termSucThueMorse5 2  ==  1\n--    termSucThueMorse5 3  ==  0\n--    termSucThueMorse5 4  ==  1\ntermSucThueMorse5 :: Int -> Int\ntermSucThueMorse5 0 = 0\ntermSucThueMorse5 n \n  | even n    = termSucThueMorse5 (n `div` 2)\n  | otherwise = 1 - termSucThueMorse5 (n `div` 2)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sucThueMorse :: NonNegative Int -> Bool\nprop_sucThueMorse (NonNegative n) =\n  all (== sucThueMorse1 !! n)\n      [sucThueMorse2 !! n,\n       sucThueMorse3 !! n,\n       sucThueMorse4 !! n,\n       sucThueMorse5 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sucThueMorse\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sucThueMorse1 !! (10^7)\n--    0\n--    (3.28 secs, 3,420,080,168 bytes)\n--    \u03bb> sucThueMorse2 !! (10^7)\n--    0\n--    (3.01 secs, 1,720,549,640 bytes)\n--    \u03bb> sucThueMorse3 !! (10^7)\n--    0\n--    (1.80 secs, 1,360,550,040 bytes)\n--    \u03bb> sucThueMorse4 !! (10^7)\n--    0\n--    (0.88 secs, 1,254,772,768 bytes)\n--    \u03bb> sucThueMorse5 !! (10^7)\n--    0\n--    (0.62 secs, 1,600,557,072 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/La_sucesion_de_Thue_Morse.hs\">GitHub<\/a>.<\/p>\n<h4>Referencias<\/h4>\n<ul>\n<li>N.J.A. Sloane <a href=\"http:\/\/oeis.org\/A010060\">Sucesi\u00f3n A010060 en OEIS<\/a>.<\/li>\n<li>Programming Praxis <a href=\"http:\/\/bit.ly\/1n2PdFk\">Thue-Morse sequence<\/a>.<\/li>\n<li>Wikipedia <a href=\"http:\/\/bit.ly\/1KvZONW\">Thue\u2013Morse sequence<\/a><\/li>\n<\/ul>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Sumas de dos primos<\/h3>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   sumasDeDosPrimos :: [Integer]\n<\/pre>\n<p>cuyos elementos son los n\u00fameros que se pueden escribir como suma de dos n\u00fameros primos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 23 sumasDeDosPrimos\n   [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]\n   \u03bb> sumasDeDosPrimos !! (5*10^5)\n   862878\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime, primes)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumasDeDosPrimos1 :: [Integer]\nsumasDeDosPrimos1 =\n  [n | n <- [1..], not (null (sumaDeDosPrimos1 n))]\n\n-- (sumaDeDosPrimos1 n) es la lista de pares de primos cuya suma es\n-- n. Por ejemplo,\n--    sumaDeDosPrimos  9  ==  [(2,7),(7,2)]\n--    sumaDeDosPrimos 16  ==  [(3,13),(5,11),(11,5),(13,3)]\n--    sumaDeDosPrimos 17  ==  []\nsumaDeDosPrimos1 :: Integer -> [(Integer,Integer)]\nsumaDeDosPrimos1 n = \n  [(x,n-x) | x <- primosN, isPrime (n-x)]\n  where primosN = takeWhile (< n) primes\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumasDeDosPrimos2 :: [Integer]\nsumasDeDosPrimos2 =\n  [n | n <- [1..], not (null (sumaDeDosPrimos2 n))]\n\n-- (sumasDeDosPrimos2 n) es la lista de pares (x,y) de primos cuya suma\n-- es n y tales que x <= y. Por ejemplo,\n--    sumaDeDosPrimos2  9  ==  [(2,7)]\n--    sumaDeDosPrimos2 16  ==  [(3,13),(5,11)]\n--    sumaDeDosPrimos2 17  ==  []\nsumaDeDosPrimos2 :: Integer -> [(Integer,Integer)]\nsumaDeDosPrimos2 n = \n  [(x,n-x) | x <- primosN, isPrime (n-x)]\n  where primosN = takeWhile (<= (n `div` 2)) primes\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsumasDeDosPrimos3 :: [Integer]\nsumasDeDosPrimos3 = filter esSumaDeDosPrimos3 [4..]\n\n-- (esSumaDeDosPrimos3 n) se verifica si n es suma de dos primos. Por\n-- ejemplo, \n--    esSumaDeDosPrimos3  9  ==  True\n--    esSumaDeDosPrimos3 16  ==  True\n--    esSumaDeDosPrimos3 17  ==  False\nesSumaDeDosPrimos3 :: Integer -> Bool\nesSumaDeDosPrimos3 n\n  | odd n     = isPrime (n-2)\n  | otherwise = any isPrime [n-x | x <- takeWhile (<= (n `div` 2)) primes]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Usando la conjetura de Goldbach que dice que \"Todo n\u00famero par mayor\n-- que 2 puede escribirse como suma de dos n\u00fameros primos\" .\n\nsumasDeDosPrimos4 :: [Integer]\nsumasDeDosPrimos4 = filter esSumaDeDosPrimos4 [4..]\n\n-- (esSumaDeDosPrimos4 n) se verifica si n es suma de dos primos. Por\n-- ejemplo, \n--    esSumaDeDosPrimos4  9  ==  True\n--    esSumaDeDosPrimos4 16  ==  True\n--    esSumaDeDosPrimos4 17  ==  False\nesSumaDeDosPrimos4 :: Integer -> Bool\nesSumaDeDosPrimos4 n = even n || isPrime (n-2)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sumasDeDosPrimos :: NonNegative Int -> Bool\nprop_sumasDeDosPrimos (NonNegative n) =\n  all (== sumasDeDosPrimos1 !! n)\n      [sumasDeDosPrimos2 !! n,\n       sumasDeDosPrimos3 !! n,\n       sumasDeDosPrimos4 !! n]\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumasDeDosPrimos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sumasDeDosPrimos1 !! 5000\n--    7994\n--    (2.61 secs, 9,299,106,792 bytes)\n--    \u03bb> sumasDeDosPrimos2 !! 5000\n--    7994\n--    (1.48 secs, 5,190,651,760 bytes)\n--    \u03bb> sumasDeDosPrimos3 !! 5000\n--    7994\n--    (0.12 secs, 351,667,104 bytes)\n--    \u03bb> sumasDeDosPrimos4 !! 5000\n--    7994\n--    (0.04 secs, 63,464,320 bytes)\n--\n--    \u03bb> sumasDeDosPrimos3 !! (5*10^4)\n--    83674\n--    (2.23 secs, 7,776,049,264 bytes)\n--    \u03bb> sumasDeDosPrimos4 !! (5*10^4)\n--    83674\n--    (0.34 secs, 1,183,604,984 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Sumas_de_dos_primos.hs\">GitHub<\/a>.<\/p>\n<h4>Referencia<\/h4>\n<ul>\n<li>N.J.A. Sloane, <a href=\"http:\/\/oeis.org\/A014091\">Sucesi\u00f3n A014091 en OEIS<\/a>.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Huecos maximales entre primos 2. N\u00fameros belgas 3. La serie de Thue-Morse 4. La sucesi\u00f3n de Thue-Morse 5. Sumas de dos primos A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7764"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7764"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7764\/revisions"}],"predecessor-version":[{"id":7765,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7764\/revisions\/7765"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}