{"id":2138,"date":"2016-02-19T06:31:13","date_gmt":"2016-02-19T04:31:13","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2138"},"modified":"2016-03-02T08:16:50","modified_gmt":"2016-03-02T06:16:50","slug":"digitos-en-la-factorizacion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/digitos-en-la-factorizacion\/","title":{"rendered":"D\u00edgitos en la factorizaci\u00f3n"},"content":{"rendered":"<p>El enunciado del <a href=\"http:\/\/bit.ly\/1Vrbckh\">problema 652<\/a> de  <a href=\"http:\/\/simplementenumeros.blogspot.com.es\">N\u00fameros y algo m\u00e1s<\/a> es el siguiente<\/p>\n<blockquote><p>\n  Si factorizamos los factoriales de un n\u00famero en funci\u00f3n de sus divisores primos y sus potencias, \u00bfCu\u00e1l es el menor n\u00famero n tal que entre los factores primos y los exponentes de estos, n! contiene los d\u00edgitos del cero al nueve? Por ejemplo<\/p>\n<ul>\n<li>6! = 2\u2074x3\u00b2x5\u00b9, le faltan los d\u00edgitos 0,6,7,8 y 9<\/li>\n<li>12! = 2\u00b9\u2070x3\u2075x5\u00b2x7\u00b9x11\u00b9, le faltan los d\u00edgitos 4,6,8 y 9<\/li>\n<\/ul>\n<\/blockquote>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   digitosDeFactorizacion :: Integer -> [Integer]\n<\/pre>\n<p>tal que (digitosDeFactorizacion n) es el conjunto de los d\u00edgitos que aparecen en la factorizaci\u00f3n de n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   digitosDeFactorizacion (factorial 6)   ==  [1,2,3,4,5]\n   digitosDeFactorizacion (factorial 12)  ==  [0,1,2,3,5,7]\n<\/pre>\n<p>Usando la funci\u00f3n anterior, calcular la soluci\u00f3n del problema.<\/p>\n<p>Comprobar con QuickCheck que si n es mayor que 100, entonces<\/p>\n<pre lang=\"text\">\n   digitosDeFactorizacion (factorial n) == [0..9]  \n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group, nub, sort)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\ndigitosDeFactorizacion1 :: Integer -> [Integer]\ndigitosDeFactorizacion1 n =\n   sort (nub (concat [digitos x | x <- numerosDeFactorizacion n]))\n\n-- (digitos n) es la lista de los digitos del n\u00famero n. Por ejemplo, \n--    digitos 320274  ==  [3,2,0,2,7,4]\ndigitos :: Integer -> [Integer]\ndigitos n = [read [x] | x <- show n]\n\n-- (numerosDeFactorizacion n) es el conjunto de los n\u00fameros en la\n-- factorizaci\u00f3n de n. Por ejemplo,\n--    numerosDeFactorizacion 60  ==  [1,2,3,5]\nnumerosDeFactorizacion :: Integer -> [Integer]\nnumerosDeFactorizacion n = \n   sort (nub (aux (factorizacion n)))\n   where aux [] = []\n         aux ((x,y):zs) = x : y : aux zs\n\n-- (factorizaci\u00f3n n) es la factorizaci\u00f3n de n. Por ejemplo,\n--    factorizacion 300  ==  [(2,2),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n = \n    [(head xs, genericLength xs) | xs <- group (factorizacion' n)]\n\n-- (factorizacion' n) es la lista de todos los factores primos de n; es\n-- decir, es una lista de n\u00fameros primos cuyo producto es n. Por ejemplo,\n--    factorizacion 300  ==  [2,2,3,5,5]\nfactorizacion' :: Integer -> [Integer]\nfactorizacion' n | n == 1    = []\n                 | otherwise = x : factorizacion' (div n x)\n                 where x = menorFactor n\n\n-- (menorFactor n) es el menor factor primo de n. Por ejemplo,\n--    menorFactor 15  ==  3\nmenorFactor :: Integer -> Integer\nmenorFactor n = head [x | x <- [2..], rem n x == 0]\n\n-- (factorial n) es el factorial de n. Por ejemplo,\n--    factorial 5  ==  120\nfactorial :: Integer -> Integer\nfactorial n = product [1..n]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\ndigitosDeFactorizacion2 :: Integer -> [Integer]\ndigitosDeFactorizacion2 n =\n   sort (nub (concat [digitos x | x <- numerosDeFactorizacion2 n]))\n\n-- (numerosDeFactorizacion2 n) es el conjunto de los n\u00fameros en la\n-- factorizaci\u00f3n de n. Por ejemplo,\n--    numerosDeFactorizacion2 60  ==  [1,2,3,5]\nnumerosDeFactorizacion2 :: Integer -> [Integer]\nnumerosDeFactorizacion2 n = \n    sort (nub (aux (factorizacion2 n)))\n    where aux xs = concat [[a,b] | (a,b) <- xs]\n\n-- (factorizaci\u00f3n2 n) es la factorizaci\u00f3n de n. Por ejemplo,\n--    factorizacion2 300  ==  [(2,2),(3,1),(5,2)]\nfactorizacion2 :: Integer -> [(Integer,Integer)]\nfactorizacion2 n =\n    [(head xs, genericLength xs) | xs <- group (primeFactors n)]\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\ndigitosDeFactorizacion3 :: Integer -> [Integer]\ndigitosDeFactorizacion3 n =\n    sort (nub (concat [digitos x | x <- aux (group (primeFactors n))]))\n    where aux  []            = []\n          aux (ys@(y:_):xss) = y : genericLength ys : aux xss\n\n-- Definici\u00f3n\n-- ==========\n\ndigitosDeFactorizacion :: Integer -> [Integer]\ndigitosDeFactorizacion = digitosDeFactorizacion3\n\n-- Soluci\u00f3n\n-- ========\n\n-- Para calcular la soluci\u00f3n, se define la constante\nsolucion :: Integer\nsolucion = \n    head [n | n <- [1..], digitosDeFactorizacion (factorial n) == [0..9]]\n\n-- El c\u00e1lculo de la soluci\u00f3n es\n--    ghci> solucion2\n--    49\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_completa :: Integer -> Bool\nprop_completa n =\n    digitosDeFactorizacion (factorial n1) == [0..9]\n    where n1 = 101 + abs n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_completa\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>La soluci\u00f3n en Maxima<\/h4>\n<pre lang=\"maxima\">\n\/* digitos(n) es la lista de los digitos del n\u00famero n. Por ejemplo, \n      digitos (320274) == [3,2,0,2,7,4]\n*\/      \ndigitos (n) := charlist (string (n))$\n\ndigitosDeFactorizacion (n) :=\n   unique (apply (append, map (digitos, apply (append, ifactors (n))))) $\n\nsolucion () := block ([n:1],\n  while length (digitosDeFactorizacion (n!)) < 10 do\n     n : n+1,\n  n)$   \n\n\/*\n   (%i5) digitosDeFactorizacion (6!);\n   (%o5) [1, 2, 3, 4, 5]\n\n   (%i6) solucion ();\n   (%o6) 49\n*\/\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El enunciado del problema 652 de N\u00fameros y algo m\u00e1s es el siguiente Si factorizamos los factoriales de un n\u00famero en funci\u00f3n de sus divisores primos y sus potencias, \u00bfCu\u00e1l es el menor n\u00famero n tal que entre los factores primos y los exponentes de estos, n! contiene los d\u00edgitos del cero al nueve? Por&#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":[2],"tags":[8,12,30,258,13,71,24,247,157,95,6,31,33,14],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2138"}],"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=2138"}],"version-history":[{"count":10,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2138\/revisions"}],"predecessor-version":[{"id":2188,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2138\/revisions\/2188"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}