{"id":1849,"date":"2012-01-18T17:44:36","date_gmt":"2012-01-18T17:44:36","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1849"},"modified":"2013-03-08T05:48:56","modified_gmt":"2013-03-08T05:48:56","slug":"i1m2011-el-2011-y-los-numeros-primos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-el-2011-y-los-numeros-primos\/","title":{"rendered":"I1M2011: El 2011 y los n\u00fameros primos"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_12.hs\">14\u00aa relaci\u00f3n<\/a> sobre propiedades del n\u00famero 2011 relacionadas con n\u00fameros primos.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Cada comienzo de a\u00f1o se suelen buscar propiedades num\u00e9ricas del\r\n-- n\u00famero del a\u00f1o. En el 2011 se han buscado propiedades que relacionan\r\n-- el 2011 y los n\u00fameros primos. En este ejercicio vamos a realizar la\r\n-- b\u00fasqueda de dichas propiedades con Haskell.\r\n\r\nimport Data.List (sort)\r\n\r\n-- La criba de Erast\u00f3tenes es un m\u00e9todo para calcular n\u00fameros primos. Se\r\n-- comienza escribiendo todos los n\u00fameros desde 2 hasta (supongamos)\r\n-- 100. El primer n\u00famero (el 2) es primo. Ahora eliminamos todos los\r\n-- m\u00faltiplos de 2. El primero de los n\u00fameros restantes (el 3) tambi\u00e9n es\r\n-- primo. Ahora eliminamos todos los m\u00faltiplos de 3. El primero de los\r\n-- n\u00fameros restantes (el 5) tambi\u00e9n es primo ... y as\u00ed\r\n-- sucesivamente. Cuando no quedan n\u00fameros, se han encontrado todos los\r\n-- n\u00fameros primos en el rango fijado. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    elimina :: Int -> [Int] -> [Int]\r\n-- tal que (elimina n xs) es la lista obtenida eliminando en la lista xs\r\n-- los m\u00faltiplos de n. Por ejemplo,  \r\n--    elimina 3 [2,3,8,9,5,6,7]  ==  [2,8,5,7]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por comprensi\u00f3n:\r\nelimina :: Int -> [Int] -> [Int]\r\nelimina n xs = [ x | x <- xs, x `mod` n \/= 0 ]\r\n\r\n-- Por recursi\u00f3n:\r\neliminaR :: Int -> [Int] -> [Int]\r\neliminaR n [] = []\r\neliminaR n (x:xs) | mod x n == 0 = eliminaR n xs\r\n                  | otherwise    = x : eliminaR n xs\r\n\r\n-- Por plegado:\r\neliminaP :: Int -> [Int] -> [Int]\r\neliminaP n = foldr f [] \r\n             where f x y | mod x n == 0 = y\r\n                         | otherwise    = x:y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    criba :: [Int] -> [Int]\r\n-- tal que (criba xs) es la lista obtenida cribando la lista xs con el\r\n-- m\u00e9todo descrito anteriormente. Por ejemplo, \r\n--    criba [2..20]          ==  [2,3,5,7,11,13,17,19]\r\n--    take 10 (criba [2..])  ==  [2,3,5,7,11,13,17,19,23,29]\r\n-- ---------------------------------------------------------------------\r\n\r\ncriba :: [Int] -> [Int]\r\ncriba []     = []\r\ncriba (n:ns) = n : criba (elimina n ns)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    primos :: [Int]\r\n-- cuyo valor es la lista de los n\u00fameros primos. Por ejemplo,\r\n--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]\r\n-- ---------------------------------------------------------------------\r\n\r\nprimos :: [Int]\r\nprimos = criba [2..]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    esPrimo :: Int -> Bool\r\n-- tal que (esPrimo n) se verifica si n es primo. Por ejemplo,\r\n--    esPrimo 7  ==  True\r\n--    esPrimo 9  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesPrimo :: Int -> Bool\r\nesPrimo n = head (dropWhile (<n) primos) == n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar que 2011 es primo.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--     ghci> esPrimo 2011\r\n--     True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n \r\n--    prefijosConSuma :: [Int] -> Int -> [[Int]]\r\n-- tal que (prefijosConSuma xs n) es la lista de los prefijos de xs cuya\r\n-- suma es n. Por ejemplo, \r\n--    prefijosConSuma [1..10] 3  == [[1,2]]\r\n--    prefijosConSuma [1..10] 4  == []\r\n-- ---------------------------------------------------------------------\r\n\r\nprefijosConSuma :: [Int] -> Int -> [[Int]]\r\nprefijosConSuma [] 0 = [[]]\r\nprefijosConSuma [] n = []\r\nprefijosConSuma (x:xs) n \r\n    | x < n  = [x:ys | ys <- prefijosConSuma xs (n-x)]\r\n    | x == n = [[x]]\r\n    | x > n  = []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    consecutivosConSuma :: [Int] -> Int -> [[Int]]\r\n-- (consecutivosConSuma xs n) es la lista de los elementos consecutivos\r\n-- de xs cuya suma es n. Por ejemplo, \r\n--    consecutivosConSuma [1..10] 9  == [[2,3,4],[4,5],[9]]\r\n-- ---------------------------------------------------------------------\r\n\r\nconsecutivosConSuma :: [Int] -> Int -> [[Int]]\r\nconsecutivosConSuma [] 0 = [[]]\r\nconsecutivosConSuma [] n = []\r\nconsecutivosConSuma (x:xs) n =\r\n    (prefijosConSuma (x:xs) n) ++ (consecutivosConSuma xs n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    primosConsecutivosConSuma :: Int -> [[Int]]\r\n-- tal que (primosConsecutivosConSuma n) es la lista de los n\u00fameros\r\n-- primos consecutivos cuya suma es n. Por ejemplo,\r\n--    ghci> primosConsecutivosConSuma 41\r\n--    [[2,3,5,7,11,13],[11,13,17],[41]]\r\n-- ---------------------------------------------------------------------\r\n\r\nprimosConsecutivosConSuma :: Int -> [[Int]]\r\nprimosConsecutivosConSuma n = \r\n    consecutivosConSuma (takeWhile (<=n) primos) n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Calcular las descomposiciones de 2011 como sumas de\r\n-- primos consecutivos. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> primosConsecutivosConSuma 2011\r\n--    [[157,163,167,173,179,181,191,193,197,199,211],[661,673,677],[2011]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    propiedad1 :: Int -> Bool\r\n-- tal que (propiedad1 n) se verifica si n s\u00f3lo se puede expresar como\r\n-- sumas de 1, 3 y 11 primos consecutivos. Por ejemplo,\r\n--    propiedad1 2011  ==  True\r\n--    propiedad1 2010  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\npropiedad1 :: Int -> Bool\r\npropiedad1 n =\r\n    sort (map length (primosConsecutivosConSuma n)) == [1,3,11]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Calcular los a\u00f1os hasta el 3000 que cumplen la\r\n-- propiedad1. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> [n | n <- [1..3000], propiedad1 n]\r\n--    [883,2011]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    sumaCifras :: Int -> Int\r\n-- tal que (sumaCifras x) es la suma de las cifras del n\u00famero x. Por\r\n-- ejemplo, \r\n--    sumaCifras 254  ==  11\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCifras :: Int -> Int\r\nsumaCifras x = sum [read [y] | y <- show x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    sumaCifrasLista :: [Int] -> Int\r\n-- tal que (sumaCifrasLista xs) es la suma de las cifras de la lista de\r\n-- n\u00fameros xs. Por ejemplo, \r\n--    sumaCifrasLista [254, 61]  ==  18\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por comprensi\u00f3n:\r\nsumaCifrasLista :: [Int] -> Int\r\nsumaCifrasLista xs = sum [sumaCifras y | y <- xs]\r\n\r\n-- Por recursi\u00f3n:\r\nsumaCifrasListaR :: [Int] -> Int\r\nsumaCifrasListaR [] = 0\r\nsumaCifrasListaR (x:xs) = sumaCifras x + sumaCifrasListaR xs\r\n\r\n-- Por plegado:\r\nsumaCifrasListaP :: [Int] -> Int\r\nsumaCifrasListaP = foldr f 0\r\n                   where f x y = sumaCifras x + y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la funci\u00f3n\r\n--    propiedad2 :: Int -> Bool\r\n-- tal que (propiedad2 n) se verifica si n puede expresarse como suma de\r\n-- 11 primos consecutivos y la suma de las cifras de los 11 sumandos es\r\n-- un n\u00famero primo. Por ejemplo,\r\n--    propiedad2 2011  ==  True\r\n--    propiedad2 2000  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\npropiedad2 :: Int -> Bool\r\npropiedad2 n = [xs | xs <- primosConsecutivosConSuma n, \r\n                     length xs == 11,\r\n                     esPrimo (sumaCifrasLista xs)] \r\n               \/= []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Calcular el primer a\u00f1o que cumple la propiedad1 y la\r\n-- propiedad2. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [1..], propiedad1 n, propiedad2 n]\r\n--    2011\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    propiedad3 :: Int -> Bool\r\n-- tal que (propiedad3 n) se verifica si n puede expresarse como suma de\r\n-- tantos n\u00fameros primos consecutivos como indican sus dos \u00faltimas\r\n-- cifras. Por ejemplo, \r\n--    propiedad3 2011  ==  True\r\n--    propiedad3 2000  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\npropiedad3 :: Int -> Bool\r\npropiedad3 n = [xs | xs <- primosConsecutivosConSuma n,\r\n                     length xs == a]\r\n               \/= []\r\n    where a = mod n 100\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Calcular el primer a\u00f1o que cumple la propiedad1 y la\r\n-- propiedad3. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [1..], propiedad1 n, propiedad3 n]\r\n--    2011\r\n\r\n-- Hemos comprobado que 2011 es el menor n\u00famero que cumple las\r\n-- propiedades 1 y 2 y tambi\u00e9n es el menor n\u00famero que cumple las\r\n-- propiedades 1 y 3.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios de la 14\u00aa relaci\u00f3n sobre propiedades del n\u00famero 2011 relacionadas con n\u00fameros primos. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/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":[186],"tags":[295],"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\/1849"}],"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=1849"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1849\/revisions"}],"predecessor-version":[{"id":2867,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1849\/revisions\/2867"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1849"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1849"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1849"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}