{"id":5316,"date":"2020-01-01T05:30:04","date_gmt":"2020-01-01T03:30:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5316"},"modified":"2020-01-08T07:32:42","modified_gmt":"2020-01-08T05:32:42","slug":"teorema-de-carmichael","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/teorema-de-carmichael\/","title":{"rendered":"Teorema de Carmichael"},"content":{"rendered":"

La sucesi\u00f3n de Fibonacci, F(n), es la siguiente sucesi\u00f3n infinita de n\u00fameros naturales:<\/p>\n

\n   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...\n<\/pre>\n
La sucesi\u00f3n comieanza con los n\u00fameros 0 y 1. A partir de estos, cada t\u00e9rmino es la suma de los dos anteriores.<\/p>\n
El teorema de Carmichael<\/a> establece que para todo n mayor que 12, el n-\u00e9simo n\u00famero de Fibonacci F(n) tiene al menos un factor primo que no es factor de ninguno de los t\u00e9rminos anteriores de la sucesi\u00f3n.<\/p>\n
Si un n\u00famero primo p es un factor de F(n) y no es factor de ning\u00fan F(m) con m < n, entonces se dice que p es un factor caracter\u00edstico o un divisor primitivo de F(n).<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n   factoresCaracteristicos :: Int -> [Integer]\n<\/pre>\n
tal que (factoresCaracteristicos n) es la lista de los factores caracter\u00edsticos de F(n). Por ejemplo,<\/p>\n
\n   factoresCaracteristicos  4  ==  [3]\n   factoresCaracteristicos  6  ==  []\n   factoresCaracteristicos 19  ==  [37,113]\n   factoresCaracteristicos 20  ==  [41]\n   factoresCaracteristicos 37  ==  [73,149,2221]\n<\/pre>\n
Comprobar con QuickCheck el teorema de Carmichael; es decir, para todo n\u00famero entero (factoresCaracteristicos (13 + abs n)) es una lista no vac\u00eda.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.List (nub)\nimport Data.Numbers.Primes\nimport Test.QuickCheck\n\nfactoresCaracteristicos :: Int -> [Integer]\nfactoresCaracteristicos n =\n  [x | x <- factoresPrimos (fib n)\n     , and [fib m `mod` x \/= 0 | m <- [1..n-1]]]\n\n-- (fib n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci. Por\n-- ejemplo,\n--    fib 6  ==  8\nfib :: Int -> Integer\nfib n = fibs !! n\n\n-- fibs es la lista de t\u00e9rminos de la sucesi\u00f3n de Fibonacci. Por ejemplo,\n--    \u03bb> take 20 fibs\n--    [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]\nfibs :: [Integer]\nfibs = 0 : 1 : zipWith (+) fibs (tail fibs)\n\n-- (factoresPrimos n) es la lista de los factores primos de n. Por\n-- ejemplo, \n--    factoresPrimos 600  ==  [2,3,5]\nfactoresPrimos :: Integer -> [Integer]\nfactoresPrimos 0 = []\nfactoresPrimos n = nub (primeFactors n)\n\n-- Teorema\n-- =======\n\n-- El teorema es\nteorema_de_Carmichael :: Int -> Bool\nteorema_de_Carmichael n =\n  not (null (factoresCaracteristicos n'))\n  where n' = 13 + abs n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=50}) teorema_de_Carmichael\n--    +++ OK, passed 100 tests.\n<\/pre>\n
Pensamiento<\/h4>\n
\nNo puede ser
\namor de tanta fortuna:
\ndos soledades en una.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
La sucesi\u00f3n de Fibonacci, F(n), es la siguiente sucesi\u00f3n infinita de n\u00fameros naturales: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … La sucesi\u00f3n comieanza con los n\u00fameros 0 y 1. A partir de estos, cada t\u00e9rmino es la suma de los dos anteriores. El teorema de…<\/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":[7],"tags":[130,8,415,89,181,24,141,11,247,45,146,467],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5316"}],"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=5316"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5316\/revisions"}],"predecessor-version":[{"id":5354,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5316\/revisions\/5354"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}