{"id":7747,"date":"2022-06-05T17:19:11","date_gmt":"2022-06-05T15:19:11","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7747"},"modified":"2022-06-05T17:19:11","modified_gmt":"2022-06-05T15:19:11","slug":"pfh-la-semana-en-exercitium-del-30-de-mayo-al-3-de-junio-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-del-30-de-mayo-al-3-de-junio-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (del 30 de mayo al 3 de junio de 2022)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Ordenaci\u00f3n de los racionales<\/a><\/li>\n<li><a href=\"#ej2\">2. Polinomios de Bell<\/a><\/li>\n<li><a href=\"#ej3\">3. T\u00e9rmino ausente en una progresi\u00f3n aritm\u00e9tica<\/a><\/li>\n<li><a href=\"#ej4\">4. Suma de los elementos de las diagonales matrices espirales<\/a><\/li>\n<li><a href=\"#ej5\">5. Descomposiciones con sumandos 1 \u00f3 2<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Ordenaci\u00f3n de los racionales<\/h3>\n<p>En este ejercicio, representamos las fracciones mediante pares de n\u00fameros de enteros.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   fraccionesOrd :: Integer -> [(Integer,Integer)]\n<\/pre>\n<p>tal que <code>(fraccionesOrd n)<\/code> es la lista con las fracciones propias positivas ordenadas, con denominador menor o igual que <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> fraccionesOrd 4\n   [(1,4),(1,3),(1,2),(2,3),(3,4)]\n   \u03bb> fraccionesOrd 5\n   [(1,5),(1,4),(1,3),(2,5),(1,2),(3,5),(2,3),(3,4),(4,5)]\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort, sortBy)\nimport Data.Ratio ((%), numerator, denominator)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nfraccionesOrd1 :: Integer -> [(Integer,Integer)]\nfraccionesOrd1 n = \n  [(x,y) | (_,(x,y)) <- sort [(fromIntegral x\/fromIntegral y,(x,y))\n                              | y <- [2..n], \n                                x <- [1..y-1], \n                                gcd x y == 1]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfraccionesOrd2 :: Integer -> [(Integer,Integer)]\nfraccionesOrd2 n = \n  map snd (sort [(fromIntegral x\/fromIntegral y,(x,y))\n                 | y <- [2..n], \n                   x <- [1..y-1], \n                   gcd x y == 1])\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nfraccionesOrd3 :: Integer -> [(Integer,Integer)]\nfraccionesOrd3 n = \n  sortBy comp [(x,y) | y <- [2..n], x <- [1..y-1], gcd x y == 1]\n  where comp (a,b) (c,d) = compare (a*d) (b*c)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nfraccionesOrd4 :: Integer -> [(Integer,Integer)]\nfraccionesOrd4 n = \n  [(numerator x, denominator x) | x <- racionalesOrd4 n]\n  \n-- (racionalesOrd4 n) es la lista con los racionales ordenados, con\n-- denominador menor o igual que n. Por ejemplo,\n--    \u03bb> racionalesOrd4 4\n--    [1 % 4,1 % 3,1 % 2,2 % 3,3 % 4]\nracionalesOrd4 :: Integer -> [Rational]\nracionalesOrd4 n =\n  sort [x % y | y <- [2..n], x <- [1..y-1], gcd x y == 1]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_fraccionesOrd :: Positive Integer -> Bool \nprop_fraccionesOrd (Positive n) =\n  all (== fraccionesOrd1 n)\n      [fraccionesOrd2 n,\n       fraccionesOrd3 n,\n       fraccionesOrd4 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_fraccionesOrd\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (fraccionesOrd1 2000)\n--    1216587\n--    (3.65 secs, 2,879,842,368 bytes)\n--    \u03bb> length (fraccionesOrd2 2000)\n--    1216587\n--    (3.36 secs, 2,870,109,640 bytes)\n--    \u03bb> length (fraccionesOrd3 2000)\n--    1216587\n--    (8.83 secs, 5,700,519,584 bytes)\n--    \u03bb> length (fraccionesOrd4 2000)\n--    1216587\n--    (4.12 secs, 5,181,904,336 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Ordenacion_de_los_racionales.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Polinomios de Bell<\/h3>\n<p>Los polinomios de Bell forman una sucesi\u00f3n de polinomios, definida como sigue:<\/p>\n<ul>\n<li>B\u2080(x) = 1 (polinomio unidad)<\/li>\n<li>B\u2099(x) = x\u00b7[B\u2099(x) + B\u2099'(x)] (donde B\u2099'(x) es la derivada de B\u2099(x))<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   B\u2080(x) = 1                     = 1\n   B\u2081(x) = x\u00b7(1+0)               = x     \n   B\u2082(x) = x\u00b7(x+1)               = x\u00b2+x         \n   B\u2083(x) = x\u00b7(x\u00b2+x+2x+1)         = x\u00b3+3x\u00b2+x    \n   B\u2084(x) = x\u00b7(x\u00b3+3x\u00b2+x+3x\u00b2+6x+1) = x\u2074+6x\u00b3+7x\u00b2+x       \n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   polBell :: Integer -> Polinomio Integer\n<\/pre>\n<p>tal que <code>(polBell n)<\/code> es el polinomio de Bell de grado <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   polBell 4                    ==  x^4 + 6*x^3 + 7*x^2 + 1*x\n   coeficiente 2 (polBell 4)    ==  7\n   coeficiente 2 (polBell 30)   ==  536870911\n   coeficiente 1 (polBell 1000) == 1\n   length (show (coeficiente 9 (polBell 2000)))  ==  1903\n<\/pre>\n<p><strong>Notas<\/strong>: Se usa la librer\u00eda <code>I1M.PolOperaciones<\/code> que se encuentra  <a href=\"http:\/\/bit.ly\/1AKmUQB\">aqu\u00ed<\/a> y se describe <a href=\"http:\/\/bit.ly\/1NZ0NKo\">aqu\u00ed<\/a>. Adem\u00e1s, en el \u00faltimo ejemplo se usa la funci\u00f3n <code>coeficiente<\/code> tal que <code>(coeficiente k p)<\/code> es el coeficiente del t\u00e9rmino de grado <code>k<\/code> en el polinomio <code>p<\/code> definida por<\/p>\n<pre lang=\"text\">\n   coeficiente :: Num a => Int -> Polinomio a -> a\n   coeficiente k p | k == n                 = coefLider p\n                   | k > grado (restoPol p) = 0\n                   | otherwise              = coeficiente k (restoPol p)\n                   where n = grado p\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List          (genericIndex)\nimport I1M.PolOperaciones (Polinomio, coefLider, consPol, derivada,\n                           grado, multPol, polCero, polUnidad, restoPol,\n                           sumaPol) \nimport Test.QuickCheck    (Positive (Positive), quickCheck)\n\n-- Funci\u00f3n auxiliar\n-- ================\n\n-- (coeficiente k p) es el coeficiente del t\u00e9rmino de grado k en el\n-- polinomio p.\ncoeficiente :: Num a => Int -> Polinomio a -> a\ncoeficiente k p | k == n                 = coefLider p\n                | k > grado (restoPol p) = 0\n                | otherwise              = coeficiente k (restoPol p)\n                where n = grado p\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\npolBell1 :: Integer -> Polinomio Integer\npolBell1 0 = polUnidad\npolBell1 n = multPol (consPol 1 1 polCero) (sumaPol p (derivada p))\n  where p = polBell1 (n-1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\npolBell2 :: Integer -> Polinomio Integer\npolBell2 n = sucPolinomiosBell `genericIndex` n\n\nsucPolinomiosBell :: [Polinomio Integer]\nsucPolinomiosBell = iterate f polUnidad\n  where f p = multPol (consPol 1 1 polCero) (sumaPol p (derivada p))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_polBell :: Positive Integer -> Bool \nprop_polBell (Positive n) =\n  polBell1 n == polBell2 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_polBell\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (coeficiente 9 (polBell1 2000)))\n--    1903\n--    (5.37 secs, 4,829,322,368 bytes)\n--    \u03bb> length (show (coeficiente 9 (polBell2 2000)))\n--    1903\n--    (4.03 secs, 4,825,094,064 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Polinomios_de_Bell.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. T\u00e9rmino ausente en una progresi\u00f3n aritm\u00e9tica<\/h3>\n<p>Una progresi\u00f3n aritm\u00e9tica es una sucesi\u00f3n de n\u00fameros tales que la diferencia de dos t\u00e9rminos sucesivos cualesquiera de la sucesi\u00f3n es constante.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ausente :: Integral a => [a] -> a\n<\/pre>\n<p>tal que <code>(ausente xs)<\/code> es el \u00fanico t\u00e9rmino ausente de la progresi\u00f3n aritm\u00e9tica <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ausente [3,7,9,11]               ==  5\n   ausente [3,5,9,11]               ==  7\n   ausente [3,5,7,11]               ==  9\n   ausente ([1..9]++[11..])         ==  10\n   ausente ([1..10^6] ++ [2+10^6])  ==  1000001\n<\/pre>\n<p><strong>Nota.<\/strong> Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que s\u00f3lo hay un t\u00e9rmino de la progresi\u00f3n aritm\u00e9tica que no est\u00e1 en la lista.<\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (group, genericLength)\nimport Test.QuickCheck (Arbitrary, Gen,\n                        arbitrary, frequency, suchThat, quickCheck) \n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nausente1 :: Integral a => [a] -> a\nausente1 (x1:xs@(x2:x3:_))\n  | d1 == d2     = ausente1 xs\n  | d1 == 2 * d2 = x1 + d2\n  | d2 == 2 * d1 = x2 + d1\n  where d1 = x2 - x1\n        d2 = x3 - x2          \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nausente2 :: Integral a => [a] -> a\nausente2 s@(x1:x2:x3:_) \n  | x1 + x3 \/= 2 * x2 = x1 + (x3 - x2)\n  | otherwise         = head [a | (a,b) <- zip [x1,x2..] s\n                                , a \/= b]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nausente3 :: Integral a => [a] -> a\nausente3  xs@(x1:x2:_) \n  | null us   = x1 + v\n  | otherwise = x2 + u * genericLength (u:us) \n  where ((u:us):(v:_):_) = group (zipWith (-) (tail xs) xs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Tipo de progresiones aritm\u00e9ticas con un t\u00e9rmino ausente.\nnewtype PAconAusente = PA [Integer]\n  deriving Show\n\n-- Generaci\u00f3n de progresiones aritm\u00e9ticas con un t\u00e9rmino ausente. \nprogresionConAusenteArbitraria :: Gen PAconAusente\nprogresionConAusenteArbitraria = do\n  x <- arbitrary\n  d <- arbitrary `suchThat` (\/= 0)\n  n <- arbitrary `suchThat` (> 2)\n  k <- arbitrary `suchThat` (> 0)\n  let (as,_:bs) = splitAt k [x,x+d..]\n  frequency [(1,return (PA (as ++ bs))),\n             (1,return (PA (take (length as + n) (as ++ bs))))]\n\n-- Inclusi\u00f3n del tipo PAconAusente en Arbitrary.\ninstance Arbitrary PAconAusente where\n  arbitrary = progresionConAusenteArbitraria\n\n-- La propiedad es\nprop_ausente :: PAconAusente -> Bool \nprop_ausente (PA xs) =\n  all (== ausente1 xs)\n      [ausente2 xs,\n       ausente3 xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ausente\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> let n = 10^6 in ausente1 ([1..n] ++ [n+2])\n--    1000001\n--    (1.15 secs, 560,529,520 bytes)\n--    \u03bb> let n = 10^6 in ausente2 ([1..n] ++ [n+2])\n--    1000001\n--    (0.33 secs, 336,530,680 bytes)\n--    \u03bb> let n = 10^6 in ausente3 ([1..n] ++ [n+2])\n--    1000001\n--    (0.50 secs, 498,047,584 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Termino_ausente_en_una_progresion_aritmetica.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Suma de los elementos de las diagonales matrices espirales<\/h3>\n<p>Empezando con el n\u00famero 1 y movi\u00e9ndose en el sentido de las agujas del reloj se obtienen las matrices espirales<\/p>\n<pre lang=\"text\">\n   |1 2|   |7 8 9|   | 7  8  9 10|   |21 22 23 24 25|\n   |4 3|   |6 1 2|   | 6  1  2 11|   |20  7  8  9 10|\n           |5 4 3|   | 5  4  3 12|   |19  6  1  2 11|\n                     |16 15 14 13|   |18  5  4  3 12|\n                                     |17 16 15 14 13|\n<\/pre>\n<p>La suma los elementos de sus diagonales es<\/p>\n<pre lang=\"text\">\n   + en la 2x2: 1+3+2+4               =  10\n   + en la 3x3: 1+3+5+7+9             =  25\n   + en la 4x4: 1+2+3+4+7+10+13+16    =  56\n   + en la 5x5: 1+3+5+7+9+13+17+21+25 = 101\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   sumaDiagonales :: Integer -> Integer\n<\/pre>\n<p>tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.<\/p>\n<pre lang=\"text\">\n   sumaDiagonales 1         ==  1\n   sumaDiagonales 2         ==  10\n   sumaDiagonales 3         ==  25\n   sumaDiagonales 4         ==  56\n   sumaDiagonales 5         ==  101\n   sumaDiagonales (10^6)    ==  666667166668000000\n   sumaDiagonales (1+10^6)  ==  666669166671000001\n\n   sumaDiagonales (10^2)  ==         671800\n   sumaDiagonales (10^3)  ==        667168000\n   sumaDiagonales (10^4)  ==       666716680000\n   sumaDiagonales (10^5)  ==      666671666800000\n   sumaDiagonales (10^6)  ==     666667166668000000\n   sumaDiagonales (10^7)  ==    666666716666680000000\n   sumaDiagonales (10^8)  ==   666666671666666800000000\n   sumaDiagonales (10^9)  ==  666666667166666668000000000\n<\/pre>\n<p>Comprobar con QuickCheck que el \u00faltimo d\u00edgito de (sumaDiagonales n) es 0, 4 \u00f3 6 si n es par y es 1, 5 \u00f3 7 en caso contrario.<\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumaDiagonales1 :: Integer -> Integer\nsumaDiagonales1 = sum . elementosEnDiagonales\n\n-- (elementosEnDiagonales n) es la lista de los elementos en las\n-- diagonales de la matriz espiral de orden nxn. Por ejemplo,\n--    elementosEnDiagonales 1  ==  [1]\n--    elementosEnDiagonales 2  ==  [1,2,3,4]\n--    elementosEnDiagonales 3  ==  [1,3,5,7,9]\n--    elementosEnDiagonales 4  ==  [1,2,3,4,7,10,13,16]\n--    elementosEnDiagonales 5  ==  [1,3,5,7,9,13,17,21,25]\nelementosEnDiagonales :: Integer -> [Integer]\nelementosEnDiagonales n \n  | even n    = tail (scanl (+) 0 (concatMap (replicate 4) [1,3..n-1]))\n  | otherwise = scanl (+) 1 (concatMap (replicate 4) [2,4..n-1])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumaDiagonales2 :: Integer -> Integer\nsumaDiagonales2 n\n  | even n    = (-1) + n `div` 2 + sum [2*k^2-k+1 | k <- [0..n]]\n  | otherwise = 1 + sum [4*k^2-6*k+6 | k <- [3,5..n]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsumaDiagonales3 :: Integer -> Integer\nsumaDiagonales3 n\n  | even n    = n * (4*n^2 + 3*n + 8) `div` 6\n  | otherwise = (4*n^3 + 3*n^2 + 8*n - 9) `div` 6\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_sumaDiagonales :: Positive Integer -> Bool\nprop_sumaDiagonales (Positive n) =\n  all (== sumaDiagonales1 n)\n      [sumaDiagonales2 n,\n       sumaDiagonales3 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumaDiagonales_equiv\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sumaDiagonales (2*10^6)\n--    5333335333336000000\n--    (2.30 secs, 1,521,955,848 bytes)\n--    \u03bb> sumaDiagonales2 (2*10^6)\n--    5333335333336000000\n--    (2.77 secs, 1,971,411,440 bytes)\n--    \u03bb> sumaDiagonales3 (2*10^6)\n--    5333335333336000000\n--    (0.01 secs, 139,520 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_sumaDiagonales2 :: Positive Integer -> Bool\nprop_sumaDiagonales2 (Positive n) \n  | even n    = x `elem` [0,4,6] \n  | otherwise = x `elem` [1,5,7] \n  where x = sumaDiagonales1 n `mod` 10\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumaDiagonales2\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Suma_de_los_elementos_de_las_diagonales_matrices_espirales.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Descomposiciones con sumandos 1 \u00f3 2<\/h3>\n<p>Definir la funciones<\/p>\n<pre lang=\"text\">\n   sumas  :: Int -> [[Int]]\n   nSumas :: Int -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>(sumas n)<\/code> es la lista de las descomposiciones de <code>n<\/code> como sumas cuyos sumandos son 1 \u00f3 2. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n      sumas 1            ==  [[1]]\n      sumas 2            ==  [[1,1],[2]]\n      sumas 3            ==  [[1,1,1],[1,2],[2,1]]\n      sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]\n      length (sumas 26)  ==  196418\n      length (sumas 33)  ==  5702887\n<\/pre>\n<ul>\n<li><code>(nSumas n)<\/code> es el n\u00famero de descomposiciones de <code>n<\/code> como sumas cuyos sumandos son 1 \u00f3 2. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n      nSumas 4                      ==  5\n      nSumas 123                    ==  36726740705505779255899443\n      length (show (nSumas 123456)) ==  25801\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List  (genericIndex, genericLength)\nimport Data.Array ((!), array)\nimport Test.QuickCheck (Positive(Positive), quickCheckWith)\n\n-- 1\u00aa soluci\u00f3n de sumas\n-- ====================\n\nsumas1 :: Int -> [[Int]]\nsumas1 0 = [[]]\nsumas1 1 = [[1]]\nsumas1 n = [1:xs | xs <- sumas1 (n-1)] ++ [2:xs | xs <- sumas1 (n-2)]\n\n-- 2\u00aa soluci\u00f3n de sumas\n-- ====================\n\nsumas2 :: Int -> [[Int]]\nsumas2 0 = [[]]\nsumas2 1 = [[1]]\nsumas2 n = map (1:) (sumas2 (n-1)) ++ map (2:) (sumas2 (n-2))\n\n-- 3\u00aa soluci\u00f3n de sumas\n-- ====================\n\nsumas3 :: Int -> [[Int]]\nsumas3 n = v ! n\n  where v = array (0,n) [(i, f i) | i <- [0..n]]\n        f 0 = [[]]\n        f 1 = [[1]]\n        f k = map (1:) (v!(k-1)) ++ map (2:) (v!(k-2))\n \n-- 4\u00aa soluci\u00f3n de sumas\n-- ====================\n\nsumas4 :: Int -> [[Int]]\nsumas4 n = sucSumas !! n\n\n-- sucSumas es la sucesi\u00f3n cuyo n-\u00e9simo elemento es la lista de las\n-- descomposiciones de n como sumas cuyos sumandos son 1 \u00f3 2. Por\n-- ejemplo,\n--    \u03bb> take 4 sucSumas\n--    [[[]],[[1]],[[1,1],[2]],[[1,1,1],[1,2],[2,1]]]\n--    \u03bb> mapM_ print (take 5 sucSumas)\n--    [[]]\n--    [[1]]\n--    [[1,1],[2]]\n--    [[1,1,1],[1,2],[2,1]]\n--    [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]\nsucSumas :: [[[Int]]]\nsucSumas = [[]] : [[1]] : zipWith f (tail sucSumas) sucSumas\n  where f xs ys = map (1:) xs ++ map (2:) ys\n\n-- Comprobaci\u00f3n de equivalencia de sumas\n-- =====================================\n\n-- La propiedad es\nprop_sumas :: Positive Int -> Bool\nprop_sumas (Positive n) =\n  all (== sumas1 n)\n      [sumas2 n,\n       sumas3 n,\n       sumas4 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_sumas\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de sumas\n-- ==================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (sumas1 28)\n--    514229\n--    (2.79 secs, 1,739,784,512 bytes)\n--    \u03bb> length (sumas2 28)\n--    514229\n--    (1.33 secs, 1,512,291,248 bytes)\n--    \u03bb> length (sumas3 28)\n--    514229\n--    (0.20 secs, 165,215,800 bytes)\n--    \u03bb> length (sumas4 28)\n--    514229\n--    (0.17 secs, 165,201,592 bytes)\n--\n--    \u03bb> length (sumas3 33)\n--    5702887\n--    (2.16 secs, 1,830,761,864 bytes)\n--    \u03bb> length (sumas4 33)\n--    5702887\n--    (1.44 secs, 1,830,749,832 bytes)\n\n-- Definici\u00f3n de sumas\n-- ===================\n\n-- La cuarta soluci\u00f3n es m\u00e1s eficiente y es la que usaremos en lo\n-- sucesivo:\nsumas :: Int -> [[Int]]\nsumas = sumas4\n\n-- 1\u00aa soluci\u00f3n de nSumas\n-- =====================\n\nnSumas1 :: Int -> Integer\nnSumas1 = genericLength . sumas2\n\n-- 2\u00aa soluci\u00f3n de nSumas\n-- =====================\n\nnSumas2 :: Int -> Integer\nnSumas2 0 = 1\nnSumas2 1 = 1\nnSumas2 n = nSumas2 (n-1) + nSumas2 (n-2)\n\n-- 3\u00aa soluci\u00f3n de nSumas\n-- =====================\n\nnSumas3 :: Int -> Integer\nnSumas3 n = v ! n\n  where v = array (0,n) [(i,f i) | i <- [0..n]]\n        f 0 = 1\n        f 1 = 1\n        f k = v ! (k-1) + v ! (k-2)\n\n-- 4\u00aa soluci\u00f3n de nSumas\n-- =====================\n\nnSumas4 :: Int -> Integer\nnSumas4 n = aux `genericIndex` n\n  where aux = 1 : 1 : zipWith (+) aux (tail aux) \n\n-- Comprobaci\u00f3n de equivalencia de nSumas\n-- ======================================\n\n-- La propiedad es\nprop_nSumas :: Positive Int -> Bool\nprop_nSumas (Positive n) =\n  all (== nSumas1 n)\n      [nSumas2 n,\n       nSumas3 n,\n       nSumas4 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_nSumas\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de nSumas\n-- ===================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> nSumas1 33\n--    5702887\n--    (17.32 secs, 23,140,562,600 bytes)\n--    \u03bb> nSumas2 33\n--    5702887\n--    (3.48 secs, 1,870,676,904 bytes)\n--    \u03bb> nSumas3 33\n--    5702887\n--    (0.00 secs, 152,960 bytes)\n--    \u03bb> nSumas4 33\n--    5702887\n--    (0.00 secs, 139,456 bytes)\n--    \n--    \u03bb> length (show (nSumas3 (2*10^5)))\n--    41798\n--    (1.41 secs, 1,895,295,528 bytes)\n--    \u03bb> length (show (nSumas4 (2*10^5)))\n--    41798\n--    (2.39 secs, 1,834,998,800 bytes)\n\n-- Nota. El valor de (nSumas n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n-- Fibonacci 1, 1, 2, 3, 5, 8, ...\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Descomposiciones_con_sumandos_1_o_2.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Ordenaci\u00f3n de los racionales 2. Polinomios de Bell 3. T\u00e9rmino ausente en una progresi\u00f3n aritm\u00e9tica 4. Suma de los elementos de las diagonales matrices espirales 5. Descomposiciones con sumandos 1 \u00f3 2 A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7747"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7747"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7747\/revisions"}],"predecessor-version":[{"id":7748,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7747\/revisions\/7748"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7747"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7747"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7747"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}