{"id":2582,"date":"2016-11-16T06:00:10","date_gmt":"2016-11-16T04:00:10","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2582"},"modified":"2016-11-23T07:05:32","modified_gmt":"2016-11-23T05:05:32","slug":"maximo-producto-en-la-particion-de-un-numero","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maximo-producto-en-la-particion-de-un-numero\/","title":{"rendered":"M\u00e1ximo producto en la partici\u00f3n de un n\u00famero"},"content":{"rendered":"

El art\u00edculo de esta semana de Antonio Rold\u00e1n en su blog N\u00fameros y hoja de c\u00e1lculo<\/a> es M\u00e1ximo producto en la partici\u00f3n de un n\u00famero (1)<\/a><\/p>\n

Una partici\u00f3n<\/a> de un entero positivo n es una forma de descomponer n como suma de enteros positivos. Dos sumas se considerar\u00e1n iguales si solo difieren en el orden de los sumandos. Por ejemplo, las 11 particiones de 6 (con sus correspondientes productos) son<\/p>\n

 \n   6 = 6                      |  6                     = 6\n   6 = 5 + 1                  |  5 x 1                 = 5\n   6 = 4 + 2                  |  4 x 2                 = 8\n   6 = 4 + 1 + 1              |  4 x 1 x 1             = 4\n   6 = 3 + 3                  |  3 x 3                 = 9\n   6 = 3 + 2 + 1              |  3 x 2 x 1             = 6\n   6 = 3 + 1 + 1 + 1          |  3 x 1 x 1 x 1         = 3\n   6 = 2 + 2 + 2              |  2 x 2 x 2             = 8\n   6 = 2 + 2 + 1 + 1          |  2 x 2 x 1 x 1         = 4\n   6 = 2 + 1 + 1 + 1 + 1      |  2 x 1 x 1 x 1 x 1     = 2\n   6 = 1 + 1 + 1 + 1 + 1 + 1  |  1 x 1 x 1 x 1 x 1 x 1 = 1\n<\/pre>\n
Se observa que el m\u00e1ximo producto de las particiones de 6 es 9.<\/p>\n
Definir la funci\u00f3n<\/p>\n
 \n   maximoProductoParticiones :: Int -> Int\n<\/pre>\n
tal que (maximoProductoParticiones n) es el m\u00e1ximo de los productos de las particiones de n. Por ejemplo,<\/p>\n
 \n   maximoProductoParticiones 4     ==  4\n   maximoProductoParticiones 5     ==  6\n   maximoProductoParticiones 6     ==  9\n   maximoProductoParticiones 7     ==  12\n   maximoProductoParticiones 8     ==  18\n   maximoProductoParticiones 9     ==  27\n   maximoProductoParticiones 50    ==  86093442\n   maximoProductoParticiones 100   ==  7412080755407364\n   maximoProductoParticiones 200   ==  61806308765265224723841283607058\n   length (show (maximoProductoParticiones (10^7)))  ==  1590405\n<\/pre>\n
Comprobar con QuickChek que los \u00fanicos posibles factores de (maximoProductoParticiones n) son 2 y 3.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.List (genericIndex, sort)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nmaximoProductoParticiones1 :: Integer -> Integer\nmaximoProductoParticiones1 n =\n  maximum [product xs | xs <- particiones1 n]\n\n-- (particiones1 n) es la lista de las particiones de n. Por ejemplo,  \n--    \u03bb> particiones1 4\n--    [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]\n--    \u03bb> particiones1 5\n--    [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]\nparticiones1 :: Integer -> [[Integer]]\nparticiones1 0 = [[]]\nparticiones1 n = [x:y | x <- [n,n-1..1]\n                      , y <- particiones1 (n-x) \n                      , [x] >= take 1 y]\n \n-- 2\u00aa definici\u00f3n\n-- =============\n\nmaximoProductoParticiones2 :: Integer -> Integer\nmaximoProductoParticiones2 n =\n  maximum [product xs | xs <- particiones2 n]\n\n-- (particiones2 n) es la lista de las particiones de n. Por ejemplo,  \n--    \u03bb> particiones2 4\n--    [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]\n--    \u03bb> particiones2 5\n--    [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]\nparticiones2 :: Integer -> [[Integer]]\nparticiones2 n = aux `genericIndex` n\n  where aux = [] : map particiones [1..]\n          where particiones n = [n] : [x:p | x <- [n,n-1..1]\n                                           , p <- aux `genericIndex` (n-x) \n                                           , x >= head p]\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nmaximoProductoParticiones3 :: Integer -> Integer\nmaximoProductoParticiones3 0 = 1\nmaximoProductoParticiones3 n =\n  maximum [(n-i) * maximoProductoParticiones3 i | i <- [0..n-1]]\n\n-- 4\u00aa definici\u00f3n\n-- =============\n\nmaximoProductoParticiones4 :: Integer -> Integer\nmaximoProductoParticiones4 n =\n  maximosProductosParticiones `genericIndex` n\n\nmaximosProductosParticiones :: [Integer]\nmaximosProductosParticiones = 1 : f [1]\n  where f xs = y : f (y:xs)\n          where y = maximum (zipWith (*) [1..] xs)\n\n-- 5\u00aa definici\u00f3n\n-- =============\n\nmaximoProductoParticiones5 :: Integer -> Integer\nmaximoProductoParticiones5 1 = 1\nmaximoProductoParticiones5 n\n  | r == 0 = 3^q\n  | r == 1 = 4 * 3^(q-1)\n  | r == 2 = 2 * 3 ^q\n  where (q,r) = quotRem n 3\n        \n-- Comparaci\u00f3n de eficiencia                                        \n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximoProductoParticiones1 20\n--    1458\n--    (5.42 secs, 832,283,184 bytes)\n--    \u03bb> maximoProductoParticiones2 20\n--    1458\n--    (0.02 secs, 0 bytes)\n--    \u03bb> maximoProductoParticiones3 20\n--    1458\n--    (3.18 secs, 524,500,000 bytes)\n--    \u03bb> maximoProductoParticiones4 20\n--    1458\n--    (0.00 secs, 0 bytes)\n--    \n--    \u03bb> maximoProductoParticiones2 50\n--    86093442\n--    (9.18 secs, 980,524,320 bytes)\n--    \u03bb> maximoProductoParticiones4 50\n--    86093442\n--    (0.01 secs, 1,381,192 bytes)\n--    \u03bb> maximoProductoParticiones5 50\n--    86093442\n--    (0.00 secs, 0 bytes)\n--    \n--    \u03bb> length (show (maximoProductoParticiones4 2000))\n--    319\n--    (2.93 secs, 638,270,872 bytes)\n--    \u03bb> length (show (maximoProductoParticiones5 2000))\n--    319\n--    (0.01 secs, 0 bytes)\n\n-- Comprobaci\u00f3n\n-- ============\n\n-- La propiedad es\nprop_factores :: Integer -> Property\nprop_factores n =\n  n > 0 ==> primeFactors (maximoProductoParticiones5 n) `contenido` [2,3]\n\ncontenido :: Eq a => [a] -> [a] -> Bool\ncontenido xs ys = all (`elem` ys) xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_factores\n--    +++ OK, passed 100 tests.\n<\/pre>\n
Referencia<\/h4>\n