{"id":1763,"date":"2011-12-11T20:30:43","date_gmt":"2011-12-11T20:30:43","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1763"},"modified":"2013-03-08T05:48:58","modified_gmt":"2013-03-08T05:48:58","slug":"a-un-primo-de-un-multiplo-del-inverso-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/a-un-primo-de-un-multiplo-del-inverso-en-haskell\/","title":{"rendered":"A un primo de un m\u00faltiplo del inverso en Haskell"},"content":{"rendered":"

La semana pasada en el blog N\u00fameros y algo m\u00e1s<\/a> se plante\u00f3 el problema Igual a un m\u00faltiplo del “inverso” mas\/ menos un primo<\/a> cuyo enunciado es el siguiente:<\/p>\n

\nEl n\u00famero 21 es el menor n\u00famero que es igual a un m\u00faltiplo de s\u00ed mismo dado vuelta (2 x12) m\u00e1s\/menos (-3) un primo menor que \u00e9l:
\n      21 = 12 x 2 – 3
\nEl siguiente es:
\n      31 = 13 x 2 + 5
\nEn este caso vemos que el n\u00famero original tambi\u00e9n es primo. <\/p>\n

La soluci\u00f3n 13 = 31 x 6 – 173 no es v\u00e1lida ya que 173 a pesar de ser primo es mayor que 13. <\/p>\n

Buscando s\u00f3lo primos que tengan esta propiedad el siguiente que cumple es el 41 y para el cual tenemos dos soluciones:
\n      41 = 14 x 2 + 13
\n      41 = 14 x 5 – 29<\/p>\n

El primer primo que tiene cuatro soluciones es el 61:
\n      61 = 16 x 2 + 29
\n      61 = 16 x 3 + 13
\n      61 = 16 x 4 – 3
\n      61 = 16 x 5 – 19<\/p>\n

\u00bfCu\u00e1l es el primer primo que tiene cinco soluciones? \u00bfy el primero que tiene seis?\n<\/p><\/blockquote>\n

A partir de dicho problema he escrito en L\u00f3gicaMente<\/a> dos relaciones de ejercicios. La primera usando una definici\u00f3n elemental de n\u00fameros primos y la segunda usando la librer\u00eda Data.Numbers.Primes<\/a>. Finalmente se compara la eficiencia de ambas definiciones para resolver el problema.<\/p>\n

La primera relaci\u00f3n es la siguiente
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    divisores :: Int -> [Int]\r\n-- tal que (divisores n) es la lista de los divisores de n. Por ejemplo,\r\n--    divisores 30  ==  [1,2,3,5,6,10,15,30]\r\n-- ---------------------------------------------------------------------\r\n\r\ndivisores :: Int -> [Int]\r\ndivisores n = [x | x <- [1..n], n `mod` x == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la propiedad\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 = divisores n == [1,n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la constante\r\n--    primos :: [Int]\r\n-- tal que primos es la lista de los n\u00fameros primos. Por ejemplo,\r\n--    take 15 primos  ==  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]\r\n-- ---------------------------------------------------------------------\r\n\r\nprimos :: [Int]\r\nprimos = [n | n <- [1..], esPrimo n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    primosMenores :: Int -> [Int]\r\n-- tal que (primosMenores x) es la lista de los n\u00fameros primos menores\r\n-- que x. Por ejemplo,\r\n--    primosMenores 47  ==  [2,3,5,7,11,13,17,19,23,29,31,37,41,43]\r\n-- ---------------------------------------------------------------------\r\n\r\nprimosMenores :: Int -> [Int]\r\nprimosMenores x = [n | n <- [1..x-1], esPrimo n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    inverso :: Int -> Int\r\n-- tal que (inverso x) es el n\u00famero obtenido escibiendo las cifras de x\r\n-- en orden inverso. Por ejemplo,\r\n--    inverso 325  ==  523\r\n--    inverso 320  ==  23\r\n-- ---------------------------------------------------------------------\r\n\r\ninverso :: Int -> Int\r\ninverso n = read (reverse (show n))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n \r\n--    esSolucion :: Int -> (Int,Int) -> Bool\r\n-- tal que (esSolucion x (m,p)) se verifica si se cumplen las siguientes\r\n-- condiciones: \r\n--    * x == (inverso x)*m+p\r\n--    * abs p < x\r\n--    * esPrimo (abs p)\r\n-- Por ejemplo,\r\n--    esSolucion 21 (2,-3)    ==  True\r\n--    esSolucion 31 (2,5)     ==  True\r\n--    esSolucion 13 (6,-173)  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesSolucion :: Int -> (Int,Int) -> Bool\r\nesSolucion x (m,p) =\r\n    x == (inverso x)*m+p &&\r\n    abs p < x &&\r\n    esPrimo (abs p)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    soluciones :: Int -> [(Int,Int)]\r\n-- tal que (soluciones x) es la lista de las soluciones de x. Por\r\n-- ejemplo, \r\n--    soluciones 21  ==  [(2,-3)]\r\n--    soluciones 31  ==  [(2,5)]\r\n--    soluciones 41  ==  [(2,13),(5,-29)]\r\n--    soluciones 61  ==  [(3,13),(2,29),(4,-3),(5,-19)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsoluciones :: Int -> [(Int,Int)]\r\nsoluciones x = \r\n    [(m,p) | m <- [1..2*(x-1) `div` y], \r\n             let p = x-y*m, \r\n             esPrimo (abs p)]\r\n    where y = inverso x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    prop_soluciones :: Int -> Bool\r\n-- tal que (prop_soluciones x) se verifica si para todo y menor que x,\r\n-- los elementos de (soluciones y) son soluciones de y. Por ejemplo,\r\n--    prop_soluciones 100  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_soluciones :: Int -> Bool\r\nprop_soluciones x =\r\n    and [esSolucion y p | y <- [1..x-1], p <- soluciones y]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Un n\u00famero es especial si es igual a un m\u00faltiplo de s\u00ed\r\n-- mismo dado vuelta m\u00e1s\/menos un primo menor que \u00e9l. Por ejemplo, el 21\r\n-- es especial porque  \r\n--       21 = 12 x 2 - 3\r\n-- Definir la propiedad\r\n--    especial :: Int -> Bool\r\n-- tal que (especial x) se verifica si x es un n\u00famero especial. Por\r\n-- ejemplo, \r\n--    especial 21  ==  True\r\n--    especial 22  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nespecial :: Int -> Bool\r\nespecial x = not (null (soluciones x))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Un n\u00famero es especial de grado n si tiene n soluciones.\r\n-- \r\n-- Definir la propiedad\r\n--    especialDeGrado :: Int -> Int -> Bool\r\n-- tal que (especialDeGrado x n) se verifica si x es un n\u00famero especial\r\n-- de grado n. Por ejemplo, \r\n--    especialDeGrado 21 1  ==  True\r\n--    especialDeGrado 21 2  ==  False\r\n--    especialDeGrado 41 2  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nespecialDeGrado :: Int -> Int -> Bool\r\nespecialDeGrado x n = \r\n    length (soluciones x) == n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n--    menorPrimoEspecialDeGrado :: Int -> Int\r\n-- tal que (menorPrimoEspecialDeGrado n) es el menor primo especial de\r\n-- grado n. Por ejemplo,\r\n--    menorPrimoEspecialDeGrado 1  ==  31\r\n--    menorPrimoEspecialDeGrado 2  ==  41\r\n--    menorPrimoEspecialDeGrado 3  ==  71\r\n--    menorPrimoEspecialDeGrado 4  ==  61\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorPrimoEspecialDeGrado :: Int -> Int\r\nmenorPrimoEspecialDeGrado n = \r\n    head [x | x <- primos, especialDeGrado x n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Calcular las respuestas a las dos preguntas del\r\n-- problema: \r\n--    \u00bfCu\u00e1l es el primer primo que tiene cinco soluciones? \u00bfy el\r\n--    primero que tiene seis?\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es \r\n--    ghci> menorPrimoEspecialDeGrado 5  \r\n--    6421\r\n--    ghci> menorPrimoEspecialDeGrado 6  \r\n--    8501\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Calcular los costes de los c\u00e1lculos anteriores.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--       ghci> :set +s\r\n--       ghci> menorPrimoEspecialDeGrado 5\r\n--       6421\r\n--       (2.99 secs, 335729840 bytes)\r\n--       ghci> menorPrimoEspecialDeGrado 6\r\n--       8501\r\n--       (5.46 secs, 577386544 bytes)\r\n<\/pre>\n
La segunda relaci\u00f3n es <\/p>\n
\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Numbers.Primes\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    inverso :: Int -> Int\r\n-- tal que (inverso x) es el n\u00famero obtenido escibiendo las cifras de x\r\n-- en orden inverso. Por ejemplo,\r\n--    inverso 325  ==  523\r\n--    inverso 320  ==  23\r\n-- ---------------------------------------------------------------------\r\n\r\ninverso :: Int -> Int\r\ninverso n = read (reverse (show n))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n \r\n--    esSolucion :: Int -> (Int,Int) -> Bool\r\n-- tal que (esSolucion x (m,p)) se verifica si se cumplen las siguientes\r\n-- condiciones: \r\n--    * x == (inverso x)*m+p\r\n--    * abs p < x\r\n--    * esPrimo (abs p)\r\n-- Por ejemplo,\r\n--    esSolucion 21 (2,-3)    ==  True\r\n--    esSolucion 31 (2,5)     ==  True\r\n--    esSolucion 13 (6,-173)  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesSolucion :: Int -> (Int,Int) -> Bool\r\nesSolucion x (m,p) =\r\n    x == (inverso x)*m+p &&\r\n    abs p < x &&\r\n    isPrime (abs p)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    soluciones :: Int -> [(Int,Int)]\r\n-- tal que (soluciones x) es la lista de las soluciones de x. Por\r\n-- ejemplo, \r\n--    soluciones 21  ==  [(2,-3)]\r\n--    soluciones 31  ==  [(2,5)]\r\n--    soluciones 41  ==  [(2,13),(5,-29)]\r\n--    soluciones 61  ==  [(3,13),(2,29),(4,-3),(5,-19)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsoluciones :: Int -> [(Int,Int)]\r\nsoluciones x = \r\n    [(m,p) | m <- [1..2*(x-1) `div` y], \r\n             let p = x-y*m, \r\n             isPrime (abs p)]\r\n    where y = inverso x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Un n\u00famero es especial si es igual a un m\u00faltiplo de s\u00ed\r\n-- mismo dado vuelta m\u00e1s\/menos un primo menor que \u00e9l. Por ejemplo, el 21\r\n-- es especial porque  \r\n--       21 = 12 x 2 - 3\r\n-- Definir la propiedad\r\n--    especial :: Int -> Bool\r\n-- tal que (especial x) se verifica si x es un n\u00famero especial. Por\r\n-- ejemplo, \r\n--    especial 21  ==  True\r\n--    especial 22  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nespecial :: Int -> Bool\r\nespecial x = not (null (soluciones x))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Un n\u00famero es especial de grado n si tiene n soluciones.\r\n-- \r\n-- Definir la propiedad\r\n--    especialDeGrado :: Int -> Int -> Bool\r\n-- tal que (especialDeGrado x n) se verifica si x es un n\u00famero especial\r\n-- de grado n. Por ejemplo, \r\n--    especialDeGrado 21 1  ==  True\r\n--    especialDeGrado 21 2  ==  False\r\n--    especialDeGrado 41 2  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nespecialDeGrado :: Int -> Int -> Bool\r\nespecialDeGrado x n = \r\n    length (soluciones x) == n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    menorPrimoEspecialDeGrado :: Int -> Int\r\n-- tal que (menorPrimoEspecialDeGrado n) es el menor primo especial de\r\n-- grado n. Por ejemplo,\r\n--    menorPrimoEspecialDeGrado 1  ==  31\r\n--    menorPrimoEspecialDeGrado 2  ==  41\r\n--    menorPrimoEspecialDeGrado 3  ==  71\r\n--    menorPrimoEspecialDeGrado 4  ==  61\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorPrimoEspecialDeGrado :: Int -> Int\r\nmenorPrimoEspecialDeGrado n = \r\n    head [x | x <- primes, especialDeGrado x n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Calcular las respuestas a las dos preguntas del\r\n-- problema: \r\n--    \u00bfCu\u00e1l es el primer primo que tiene cinco soluciones? \u00bfy el\r\n--    primero que tiene seis?\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es \r\n--    ghci> menorPrimoEspecialDeGrado 5  \r\n--    6421\r\n--    ghci> menorPrimoEspecialDeGrado 6  \r\n--    8501\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Calcular los costes de los c\u00e1lculos anteriores.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--       ghci> menorPrimoEspecialDeGrado 5\r\n--       6421\r\n--       (0.02 secs, 4207796 bytes)\r\n--       ghci> menorPrimoEspecialDeGrado 6\r\n--       8501\r\n--       (0.04 secs, 6299076 bytes)\r\n<\/pre>\n
La comparaci\u00f3n del espacio y tiempo utilizado es
\n\"<br<\/p>\n","protected":false},"excerpt":{"rendered":"
La semana pasada en el blog N\u00fameros y algo m\u00e1s se plante\u00f3 el problema Igual a un m\u00faltiplo del “inverso” mas\/ menos un primo cuyo enunciado es el siguiente: El n\u00famero 21 es el menor n\u00famero que es igual a un m\u00faltiplo de s\u00ed mismo dado vuelta (2 x12) m\u00e1s\/menos (-3) un primo menor que…<\/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":[5],"tags":[270],"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\/1763"}],"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=1763"}],"version-history":[{"count":12,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1763\/revisions"}],"predecessor-version":[{"id":2888,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1763\/revisions\/2888"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1763"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1763"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1763"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}