Máximo producto en la partición de un número
El artículo de esta semana de Antonio Roldán en su blog Números y hoja de cálculo es Máximo producto en la partición de un número (1)
Una partición de un entero positivo n es una forma de descomponer n como suma de enteros positivos. Dos sumas se considerarán iguales si solo difieren en el orden de los sumandos. Por ejemplo, las 11 particiones de 6 (con sus correspondientes productos) son
|
1 2 3 4 5 6 7 8 9 10 11 |
6 = 6 | 6 = 6 6 = 5 + 1 | 5 x 1 = 5 6 = 4 + 2 | 4 x 2 = 8 6 = 4 + 1 + 1 | 4 x 1 x 1 = 4 6 = 3 + 3 | 3 x 3 = 9 6 = 3 + 2 + 1 | 3 x 2 x 1 = 6 6 = 3 + 1 + 1 + 1 | 3 x 1 x 1 x 1 = 3 6 = 2 + 2 + 2 | 2 x 2 x 2 = 8 6 = 2 + 2 + 1 + 1 | 2 x 2 x 1 x 1 = 4 6 = 2 + 1 + 1 + 1 + 1 | 2 x 1 x 1 x 1 x 1 = 2 6 = 1 + 1 + 1 + 1 + 1 + 1 | 1 x 1 x 1 x 1 x 1 x 1 = 1 |
Se observa que el máximo producto de las particiones de 6 es 9.
Definir la función
|
1 |
maximoProductoParticiones :: Int -> Int |
tal que (maximoProductoParticiones n) es el máximo de los productos de las particiones de n. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
maximoProductoParticiones 4 == 4 maximoProductoParticiones 5 == 6 maximoProductoParticiones 6 == 9 maximoProductoParticiones 7 == 12 maximoProductoParticiones 8 == 18 maximoProductoParticiones 9 == 27 maximoProductoParticiones 50 == 86093442 maximoProductoParticiones 100 == 7412080755407364 maximoProductoParticiones 200 == 61806308765265224723841283607058 length (show (maximoProductoParticiones (10^7))) == 1590405 |
Comprobar con QuickChek que los únicos posibles factores de (maximoProductoParticiones n) son 2 y 3.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
import Data.List (genericIndex, sort) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª definición -- ============= maximoProductoParticiones1 :: Integer -> Integer maximoProductoParticiones1 n = maximum [product xs | xs <- particiones1 n] -- (particiones1 n) es la lista de las particiones de n. Por ejemplo, -- λ> particiones1 4 -- [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] -- λ> particiones1 5 -- [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] particiones1 :: Integer -> [[Integer]] particiones1 0 = [[]] particiones1 n = [x:y | x <- [n,n-1..1] , y <- particiones1 (n-x) , [x] >= take 1 y] -- 2ª definición -- ============= maximoProductoParticiones2 :: Integer -> Integer maximoProductoParticiones2 n = maximum [product xs | xs <- particiones2 n] -- (particiones2 n) es la lista de las particiones de n. Por ejemplo, -- λ> particiones2 4 -- [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] -- λ> particiones2 5 -- [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] particiones2 :: Integer -> [[Integer]] particiones2 n = aux `genericIndex` n where aux = [] : map particiones [1..] where particiones n = [n] : [x:p | x <- [n,n-1..1] , p <- aux `genericIndex` (n-x) , x >= head p] -- 3ª definición -- ============= maximoProductoParticiones3 :: Integer -> Integer maximoProductoParticiones3 0 = 1 maximoProductoParticiones3 n = maximum [(n-i) * maximoProductoParticiones3 i | i <- [0..n-1]] -- 4ª definición -- ============= maximoProductoParticiones4 :: Integer -> Integer maximoProductoParticiones4 n = maximosProductosParticiones `genericIndex` n maximosProductosParticiones :: [Integer] maximosProductosParticiones = 1 : f [1] where f xs = y : f (y:xs) where y = maximum (zipWith (*) [1..] xs) -- 5ª definición -- ============= maximoProductoParticiones5 :: Integer -> Integer maximoProductoParticiones5 1 = 1 maximoProductoParticiones5 n | r == 0 = 3^q | r == 1 = 4 * 3^(q-1) | r == 2 = 2 * 3 ^q where (q,r) = quotRem n 3 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximoProductoParticiones1 20 -- 1458 -- (5.42 secs, 832,283,184 bytes) -- λ> maximoProductoParticiones2 20 -- 1458 -- (0.02 secs, 0 bytes) -- λ> maximoProductoParticiones3 20 -- 1458 -- (3.18 secs, 524,500,000 bytes) -- λ> maximoProductoParticiones4 20 -- 1458 -- (0.00 secs, 0 bytes) -- -- λ> maximoProductoParticiones2 50 -- 86093442 -- (9.18 secs, 980,524,320 bytes) -- λ> maximoProductoParticiones4 50 -- 86093442 -- (0.01 secs, 1,381,192 bytes) -- λ> maximoProductoParticiones5 50 -- 86093442 -- (0.00 secs, 0 bytes) -- -- λ> length (show (maximoProductoParticiones4 2000)) -- 319 -- (2.93 secs, 638,270,872 bytes) -- λ> length (show (maximoProductoParticiones5 2000)) -- 319 -- (0.01 secs, 0 bytes) -- Comprobación -- ============ -- La propiedad es prop_factores :: Integer -> Property prop_factores n = n > 0 ==> primeFactors (maximoProductoParticiones5 n) `contenido` [2,3] contenido :: Eq a => [a] -> [a] -> Bool contenido xs ys = all (`elem` ys) xs -- La comprobación es -- λ> quickCheck prop_factores -- +++ OK, passed 100 tests. |
Referencia
- Máximo producto en la partición de un número (1) de Antonio Roldán en el blog Números y hoja de cálculo.
- Sucesión A000792 de la OEIS.