Los n\u00fameros de Hamming forman una sucesi\u00f3n estrictamente creciente de n\u00fameros que cumplen las siguientes condiciones:<\/p>\n
Los primeros n\u00fameros de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, …<\/p>\n
Los exponentes de un n\u00famero de Hamming n es una terna (x,y,z) tal que Definir la sucesi\u00f3n<\/p>\n cuyos elementos son los exponentes de los n\u00fameros de Hamming. Por ejemplo,<\/p>\n Los n\u00fameros de Hamming forman una sucesi\u00f3n estrictamente creciente de n\u00fameros que cumplen las siguientes condiciones: El n\u00famero 1 est\u00e1 en la sucesi\u00f3n. Si x est\u00e1 en la sucesi\u00f3n, entonces 2x, 3x y 5x tambi\u00e9n est\u00e1n. Ning\u00fan otro n\u00famero est\u00e1 en la sucesi\u00f3n. Los primeros n\u00fameros de Hamming son 1, 2, 3, 4, 5, 6,…<\/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":[4],"tags":[8,28,415,10,11,247,6,60],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3680"}],"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=3680"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3680\/revisions"}],"predecessor-version":[{"id":3724,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3680\/revisions\/3724"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3680"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3680"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3680"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}n = 2^x*3^y*5^z<\/code>. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z<\/code>.<\/p>\n\n sucExponentesHamming :: [(Int,Int,Int)]\n<\/pre>\n
\n \u03bb> take 21 sucExponentesHamming\n [(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),\n (0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),\n (3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]\n \u03bb> sucExponentesHamming !! (5*10^5)\n (74,82,7)\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.Numbers.Primes (primeFactors)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsucExponentesHamming :: [(Int,Int,Int)]\nsucExponentesHamming = map exponentes hamming\n\n-- (exponentes n) es la terna de exponentes del n\u00famero de Hamming n. Por\n-- ejemplo, \n-- exponentes 600 == (3,1,2)\nexponentes :: Integer -> (Int,Int,Int)\nexponentes x = (length as, length cs, length ds)\n where xs = primeFactors x\n (as,bs) = span (==2) xs\n (cs,ds) = span (==3) bs\n\n-- hamming es la sucesi\u00f3n de los n\u00fameros de Hamming. Por ejemplo,\n-- \u03bb> take 21 hamming\n-- [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40]\nhamming :: [Integer]\nhamming = 1 : mezcla3 [2*i | i <- hamming] \n [3*i | i <- hamming] \n [5*i | i <- hamming] \n\n-- mezcla3 xs ys zs es la lista obtenida mezclando las listas ordenadas\n-- xs, ys y zs y eliminando los elementos duplicados. Por ejemplo, \n-- mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10] == [2,3,4,5,6,8,9,10,12]\nmezcla3 :: Ord a => [a] -> [a] -> [a] -> [a]\nmezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs) \n\n-- mezcla2 xs ys zs es la lista obtenida mezclando las listas ordenadas\n-- xs e ys y eliminando los elementos duplicados. Por ejemplo, \n-- mezcla2 [2,4,6,8,10,12] [3,6,9,12] == [2,3,4,6,8,9,10,12]\nmezcla2 :: Ord a => [a] -> [a] -> [a] \nmezcla2 p@(x:xs) q@(y:ys) | x < y = x:mezcla2 xs q\n | x > y = y:mezcla2 p ys \n | otherwise = x:mezcla2 xs ys\nmezcla2 [] ys = ys\nmezcla2 xs [] = xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsucExponentesHamming2 :: [(Int,Int,Int)]\nsucExponentesHamming2 = map exponentes2 hamming\n\nexponentes2 :: Integer -> (Int,Int,Int)\nexponentes2 = aux (0,0,0)\n where aux (a,b,c) 1 = (a,b,c)\n aux (a,b,c) x | mod x 2 == 0 = aux (a+1,b,c) (div x 2)\n | mod x 3 == 0 = aux (a,b+1,c) (div x 3)\n | otherwise = aux (a,b,c+1) (div x 5)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsucExponentesHamming3 :: [(Int,Int,Int)]\nsucExponentesHamming3 = map exponentes3 hamming\n\nexponentes3 :: Integer -> (Int,Int,Int)\nexponentes3 1 = (0,0,0)\nexponentes3 x\n | x `mod` 2 == 0 = suma (1,0,0) (descomposicion (x `div` 2))\n | x `mod` 3 == 0 = suma (0,1,0) (descomposicion (x `div` 3))\n | otherwise = suma (0,0,1) (descomposicion (x `div` 5))\n where suma (x,y,z) (a,b,c) = (x+a,y+b,z+c)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ntype Terna = (Int,Int,Int)\n\nsucExponentesHamming4 :: [Terna]\nsucExponentesHamming4 =\n (0,0,0) : mezclaT3 [(x+1,y,z) | (x,y,z) <- sucExponentesHamming4]\n [(x,y+1,z) | (x,y,z) <- sucExponentesHamming4]\n [(x,y,z+1) | (x,y,z) <- sucExponentesHamming4]\n \nmezclaT3 :: [Terna] -> [Terna] -> [Terna] -> [Terna]\nmezclaT3 t1 t2 t3 = mezclaT2 t1 (mezclaT2 t2 t3)\n\nmezclaT2 :: [Terna] -> [Terna] -> [Terna]\nmezclaT2 ts1@((i,j,k):xs) ts2@((a,b,c):ys)\n | x < y = (i,j,k) : mezclaT2 xs ts2\n | x > y = (a,b,c) : mezclaT2 ts1 ys\n | otherwise = (i,j,k) : mezclaT2 xs ys\n where x = 2^i*3^j*5^k\n y = 2^a*3^b*5^c\n<\/pre>\n","protected":false},"excerpt":{"rendered":"