El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1968 es<\/p>\n
\n Sean a(0), a(1), …, a(n) (con n \u2265 1) n\u00fameros enteros positivos. Encontrar todos los n\u00fameros enteros y tales que<\/p>\n
\n a(0) | y; (a(0)+a(1)) | (y+a(1)); … ; (a(0)+a(n)) | (y+a(n)).\n <\/p><\/blockquote>\n
donde \u00abx | y\u00bb significa que \u00aby es divisible por x\u00bb.\n<\/p><\/blockquote>\n
Se dice que un n\u00famero y es divisible respecto de la sucesi\u00f3n a(0), a(1), …, a(n) si verifica la propiedad anterior; es decir,<\/p>\n
\n a(0) | y; (a(0)+a(1)) | (y+a(1)); ... ; (a(0)+a(n)) | (y+a(n)).\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n divisiblesSucesion :: [Integer] -> [Integer]\n<\/pre>\ntal que (divisiblesSucesion xs) es la lista de los n\u00fameros enteros divisibles respecto de xs. Por ejemplo,<\/p>\n
\n take 6 (divisiblesSucesion [2,5,3]) == [2,72,142,212,282,352]\n divisiblesSucesion [3,5..30] !! (10^5) == 144144000003\n divisiblesSucesion [3,5..30] !! (10^6) == 1441440000003\n divisiblesSucesion [3,5..30] !! (10^7) == 14414400000003\n<\/pre>\nSoluciones<\/h4>\n
\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndivisiblesSucesion :: [Integer] -> [Integer]\ndivisiblesSucesion xs =\n filter (esDivisibleSucesion xs) [1..]\n\n-- (esDivisibleSucesion xs y) se verifica si y es divisible respecto de\n-- la sucesi\u00f3n xs. Por ejemplo,\n-- esDivisibleSucesion [2,5,3] 72 == True\n-- esDivisibleSucesion [2,5,3] 12 == False\nesDivisibleSucesion :: [Integer] -> Integer -> Bool\nesDivisibleSucesion [] _ = True\nesDivisibleSucesion (a0:as) y =\n y `mod` a0 == 0 &&\n and [(y+a) `mod` (a0+a) == 0 | a <- as]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- En los siguientes c\u00e1lculos\n-- \u03bb> take 5 (divisiblesSucesion [2,3,5])\n-- [2,72,142,212,282]\n-- \u03bb> foldl1 lcm [2, 2+3, 2+5]\n-- 70\n-- \u03bb> take 5 (divisiblesSucesion [2,3,5,6])\n-- [2,282,562,842,1122]\n-- \u03bb> foldl1 lcm [2, 2+3, 2+5, 2+6]\n-- 280\n-- \u03bb> take 5 (divisiblesSucesion [1,3,5,6])\n-- [1,85,169,253,337]\n-- \u03bb> foldl1 lcm [1, 1+3, 1+5, 1+6]\n-- 84\n-- se observa que los resultados son progresiones aritm\u00e9ticas cuyo\n-- primer elemento es a(0) y la diferencia es el m\u00ednimo com\u00fan m\u00faltiplo\n-- de [a(0), a(0)+a(1), a(0)+a(2), ..., a(0)+a(n)]\n\ndivisiblesSucesion2 :: [Integer] -> [Integer]\ndivisiblesSucesion2 [] = [1..]\ndivisiblesSucesion2 (a0:as) = [a0,a0+m..]\n where m = mcm (a0 : [a0+a | a <- as])\n\n-- (mcm xs) es el m\u00ednimo com\u00fan m\u00faltiplo de xs. Por ejemplo,\n-- mcm [2,5,3] == 30\n-- mcm [2,2+5,2+3] == 70\nmcm :: [Integer] -> Integer\nmcm = foldl1 lcm\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_equivalencia :: [Integer] -> Bool\nprop_equivalencia xs =\n take 3 (divisiblesSucesion ys) == take 3 (divisiblesSucesion2 ys)\n where ys = take 5 [1 + (x `mod` 10) | x <- xs]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_equivalencia\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> divisiblesSucesion [3,5..30] !! 20\n-- 28828803\n-- (16.86 secs, 15,933,990,784 bytes)\n-- \u03bb> divisiblesSucesion2 [3,5..30] !! 20\n-- 28828803\n-- (0.01 secs, 112,496 bytes)\n<\/pre>\nNuevas soluciones<\/h4>\n
\n
- En los comentarios se pueden escribir nuevas soluciones.\n
- El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1968 es Sean a(0), a(1), …, a(n) (con n \u2265 1) n\u00fameros enteros positivos. Encontrar todos los n\u00fameros enteros y tales que a(0) | y; (a(0)+a(1)) | (y+a(1)); … ; (a(0)+a(n)) | (y+a(n)). donde \u00abx | y\u00bb significa que \u00aby es divisible…<\/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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6456"}],"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=6456"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6456\/revisions"}],"predecessor-version":[{"id":6508,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6456\/revisions\/6508"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}