{"id":5975,"date":"2021-01-13T06:00:13","date_gmt":"2021-01-13T04:00:13","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5975"},"modified":"2021-01-20T09:51:32","modified_gmt":"2021-01-20T07:51:32","slug":"numeros-ciclicos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-ciclicos\/","title":{"rendered":"N\u00fameros c\u00edclicos"},"content":{"rendered":"<p>La <a href=\"http:\/\/bit.ly\/1mFwMGK\">indicatriz de Euler<\/a> (tambi\u00e9n llamada <em>funci\u00f3n \u03c6 de Euler<\/em>) es una funci\u00f3n importante en teor\u00eda de n\u00fameros. Si n es un entero positivo, entonces \u03c6(n) se define como el n\u00famero de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo,<\/p>\n<ul>\n<li>\u03c6(15) = 8 ya que los n\u00fameros menores o iguales a 36 y coprimos con 36 son ocho: 1, 2, 4, 7, 8, 11, 13 y 14.<\/li>\n<li>\u03c6(21) = 12 ya que los n\u00fameros menores o iguales a 36 y coprimos con 36 son doce: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 y 20.<\/li>\n<\/ul>\n<p>Un n\u00famero n es un <a href=\"https:\/\/bit.ly\/3b1OjoK\">n\u00famero c\u00edclico<\/a> si n y \u03c6(n) no tiene ning\u00fan divisor primo com\u00fan. Por ejemplo, el n\u00famero 15 es c\u00edclico ya que 15 y 8 (que es \u03c6(15)) no tiene ning\u00fan divisor primo com\u00fan; en cambio, el n\u00famero 21 no es c\u00edclico ya 21 y 12 (que es \u03c6(21)) son divisibles por 3.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   esCiclico :: Integer -> Bool\n   ciclicos  :: [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esCiclico n) se verifica si n es un n\u00famero c\u00edclico. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     esCiclico 15    ==  True\n     esCiclico 16    ==  False\n     esCiclico 2021  ==  True\n     esCiclico (product [1..10^4])  ==  False\n<\/pre>\n<ul>\n<li>ciclicos es la lista de los n\u00fameros c\u00edclicos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 20 ciclicos\n     [2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]\n     \u03bb> ciclicos !! (10^5)\n     336059\n<\/pre>\n<p>Comprobar con QuickCheck que todos los n\u00fameros primos mayores que 2 son c\u00edclicos.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nmodule Numeros_ciclicos where\n\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primeFactors, primes)\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nciclicos1 :: [Integer]\nciclicos1 = filter esCiclico1 [2..]\n\nesCiclico1 :: Integer -> Bool\nesCiclico1 n = gcd n (phi1 n) == 1\n\n-- (phi1 n) es igual a \u03c6(n). Por ejemplo,\n--    phi1 15    ==  8\n--    phi1 21    ==  12\n--    phi1 2021  ==  1932\nphi1 :: Integer -> Integer\nphi1 n = genericLength [x | x <- [1..n], gcd x n == 1]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nciclicos2 :: [Integer]\nciclicos2 = filter esCiclico2 [2..]\n\nesCiclico2 :: Integer -> Bool\nesCiclico2 n = gcd n (phi2 n) == 1\n\n-- (phi2 n) es igual a \u03c6(n). Por ejemplo,\n--    phi2 15    ==  8\n--    phi2 21    ==  12\n--    phi2 2021  ==  1932\nphi2 :: Integer -> Integer\nphi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]\n\n-- (factorizacion n) es la descomposici\u00f3n de n en factores primos como\n-- una lista de pares donde los primeros elementos son la base y los\n-- segundo son los exponentes. Por ejemplo,\n--    factorizacion 3000  ==  [(2,3),(3,1),(5,3)]\n-- ya que 3000 = 2^3*3*5^3\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n  [(head xs,genericLength xs) | xs <- group (primeFactors n)]\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nciclicos3 :: [Integer]\nciclicos3 = filter esCiclico3 [2..]\n\nesCiclico3 :: Integer -> Bool\nesCiclico3 n = gcd n (phi3 n) == 1\n\n-- (phi3 n) es igual a \u03c6(n). Por ejemplo,\n--    phi3 15    ==  8\n--    phi3 21    ==  12\n--    phi3 2021  ==  1932\nphi3 :: Integer -> Integer\nphi3 n =\n  product [(x-1) * product xs | (x:xs) <- group (primeFactors n)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> esCiclico1 (4*10^6)\n--    False\n--    (3.64 secs, 4,448,223,616 bytes)\n--    \u03bb> esCiclico2 (4*10^6)\n--    False\n--    (0.01 secs, 116,144 bytes)\n--    \u03bb> esCiclico3 (4*10^6)\n--    False\n--    (0.01 secs, 111,336 bytes)\n--\n--    \u03bb> esCiclico2 (product [1..3*10^4])\n--    False\n--    (2.49 secs, 5,846,361,904 bytes)\n--    \u03bb> esCiclico3 (product [1..3*10^4])\n--    False\n--    (2.50 secs, 5,947,164,552 bytes)\n\n\n-- Verificaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_ciclicos :: Int -> Property\nprop_ciclicos n =\n    n > 1 ==> esCiclico3 (primes !! n)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ciclicos\n--    +++ OK, passed 100 tests.\n\nverificacion :: IO ()\nverificacion = quickCheck prop_ciclicos\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>La indicatriz de Euler (tambi\u00e9n llamada funci\u00f3n \u03c6 de Euler) es una funci\u00f3n importante en teor\u00eda de n\u00fameros. Si n es un entero positivo, entonces \u03c6(n) se define como el n\u00famero de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo, \u03c6(15) = 8 ya que los n\u00fameros menores o iguales&#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":[5],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5975"}],"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=5975"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5975\/revisions"}],"predecessor-version":[{"id":6006,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5975\/revisions\/6006"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5975"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5975"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5975"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}