{"id":7745,"date":"2022-05-28T11:20:48","date_gmt":"2022-05-28T09:20:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7745"},"modified":"2022-05-28T11:20:48","modified_gmt":"2022-05-28T09:20:48","slug":"pfh-la-semana-en-exercitium-del-23-al-27-de-mayo-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-del-23-al-27-de-mayo-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (del 23 al 27 de mayo 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. Densidades de n\u00fameros abundantes, perfectos y deficientes<\/a><\/li>\n<li><a href=\"#ej2\">2. Matriz zigzagueante<\/a><\/li>\n<li><a href=\"#ej3\">3. Numeraci\u00f3n con base m\u00faltiple<\/a><\/li>\n<li><a href=\"#ej4\">4. El tri\u00e1ngulo de Floyd<\/a><\/li>\n<li><a href=\"#ej5\">5. Polinomios cuadr\u00e1ticos generadores de primos<\/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. Densidades de n\u00fameros abundantes, perfectos y deficientes<\/h3>\n<p>La n-\u00e9sima densidad de un tipo de n\u00famero es el cociente entre la cantidad de los n\u00fameros entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-\u00e9sima densidad de los m\u00faltiplos de 3 es 2\/7 ya que entre los 7 primeros n\u00fameros s\u00f3lo 2 son m\u00faltiplos de 3.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   densidades :: Int -> (Double,Double,Double)\n   graficas   :: Int -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>(densidades n)<\/code> es la terna formada por la n-\u00e9sima densidad\n<ul>\n<li>de los n\u00fameros <a href=\"http:\/\/bit.ly\/1BniqiY\">abundantes<\/a> (es decir, para los que la suma de sus divisores propios es mayor que el n\u00famero), <\/li>\n<li>de los n\u00fameros <a href=\"http:\/\/bit.ly\/1BniShk\">perfectos<\/a> (es decir, para los que la suma de sus divisores propios es mayor que el n\u00famero) y <\/li>\n<li>de los n\u00fameros <a href=\"http:\/\/bit.ly\/1BniQ9h\">deficientes<\/a> (es decir, para los que la suma de sus divisores propios es menor que el n\u00famero). <\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<\/li>\n<\/ul>\n<pre lang=\"text\">\n    densidades 100     ==  (0.22,    2.0e-2, 0.76)\n    densidades 1000    ==  (0.246,   3.0e-3, 0.751)\n    densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)\n    densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)\n    densidades 1000000 ==  (0.247545,4.0e-6, 0.752451)\n<\/pre>\n<ul>\n<li><code>(graficas n)<\/code> dibuja las gr\u00e1ficas de las k-\u00e9simas densidades (para k entre 1 y n) de los n\u00fameros abundantes, de los n\u00fameros perfectos y de los n\u00fameros deficientes. Por ejemplo, <code>(graficas 100)<\/code> dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/04\/Densidad_de_numeros_abundantes1.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/04\/Densidad_de_numeros_abundantes1.png?resize=640%2C480\" alt=\"\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3194\" data-recalc-dims=\"1\" \/><\/a><br \/>\ny <code>(graficas 400)<\/code> dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/04\/Densidad_de_numeros_abundantes2.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/04\/Densidad_de_numeros_abundantes2.png?resize=640%2C480\" alt=\"\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3195\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group, partition)\nimport Data.Array (accumArray, assocs)\nimport Data.Numbers.Primes (primeFactors)\nimport Graphics.Gnuplot.Simple (plotLists, Attribute (Key))\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndensidades1 :: Int -> (Double,Double,Double)\ndensidades1 n = (f a, f p, f d)\n  where a   = nAbundantes n\n        p   = nPerfectos n\n        d   = n - a - p\n        f x = fromIntegral x \/ fromIntegral n\n\n-- (nAbundantes n) es la cantidad de n\u00fameros abundantes desde 1 hasta\n-- n. Por ejemplo,\n--    nAbundantes 100 == 22\nnAbundantes :: Int -> Int\nnAbundantes n = length (filter esAbundante [1..n])\n\n-- (esAbundante n) se verifica si n es un n\u00famero abundante. Por ejemplo,\n--    esAbundante 12 == True\n--    esAbundante 22 == False\nesAbundante :: Int -> Bool\nesAbundante n = sumaDivisores n > n\n\n-- (sumaDivisores n) es la suma de los divisores propios de n. Por\n-- ejemplo,\n--    sumaDivisores 12 == 16\n--    sumaDivisores 22 == 14\nsumaDivisores :: Int -> Int\nsumaDivisores = sum . divisores\n\n-- (divisores n) es la lista de los divisores propios de n. Por ejemplo,\n--    divisores 12== [1,2,3,4,6]\n--    divisores 22== [1,2,11]\ndivisores :: Int -> [Int]\ndivisores n = [x | x <- [1..n-1],\n                   n `mod` x == 0]\n\n-- (nPerfectos n) es la cantidad de n\u00fameros perfectos desde 1 hasta\n-- n. Por ejemplo,\n--    nPerfectos 100 == 2\nnPerfectos :: Int -> Int\nnPerfectos n = length (filter esPerfecto [1..n])\n\n-- (esPerfecto n) se verifica si n es un n\u00famero perfecto. Por ejemplo,\n--    esPerfecto 28 == True\n--    esPerfecto 38 == False\nesPerfecto :: Int -> Bool\nesPerfecto n = sumaDivisores n == n\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndensidades2 :: Int -> (Double,Double,Double)\ndensidades2 n = (f as, f ps, f ds)\n  where (as,pds) = partition esAbundante [1..n]\n        (ps,ds)  = partition esPerfecto pds\n        f xs     = genericLength xs \/ fromIntegral n\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ndensidades3 :: Int -> (Double,Double,Double)\ndensidades3 n = (f as, f ps, f ds)\n  where cs       = map clasificacion [1..n]\n        (as,pds) = partition (== Abundante) cs\n        (ps,ds)  = partition (== Perfecto) pds\n        f xs     = genericLength xs \/ fromIntegral n\n\ndata Clase = Abundante | Perfecto | Deficiente\n  deriving (Eq, Show)\n\n-- (clasificacion n) es la clase de n\u00famero de n. Por ejemplo,\n--    clasificacion 12 == Abundante\n--    clasificacion 22 == Deficiente\n--    clasificacion 28 == Perfecto\nclasificacion :: Int -> Clase\nclasificacion n\n  | sd > n    = Abundante\n  | sd < n    = Deficiente\n  | otherwise = Perfecto\n  where sd = sumaDivisores n\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ndensidades4 :: Int -> (Double,Double,Double)\ndensidades4 n = (f as, f ps, f ds)\n  where cs       = map clasificacion2 [1..n]\n        (as,pds) = partition (== Abundante) cs\n        (ps,ds)  = partition (== Perfecto) pds\n        f xs     = genericLength xs \/ fromIntegral n\n\n-- 2\u00aa definici\u00f3n de clasificacion\nclasificacion2 :: Int -> Clase\nclasificacion2 n\n  | sd > n    = Abundante\n  | sd < n    = Deficiente\n  | otherwise = Perfecto\n  where sd = sumaDivisores2 n\n\n-- 2\u00aa definici\u00f3n de sumaDivisores\nsumaDivisores2 :: Int -> Int\nsumaDivisores2 x =\n  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] - x\n\n-- (factorizacion x) es la lista de las bases y exponentes de la\n-- descomposici\u00f3n prima de x. Por ejemplo,\n--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]\nfactorizacion :: Int -> [(Int,Int)]\nfactorizacion = map primeroYlongitud . group . primeFactors\n\n-- (primeroYlongitud xs) es el par formado por el primer elemento de xs\n-- y la longitud de xs. Por ejemplo,\n--    primeroYlongitud [3,2,5,7] == (3,4)\nprimeroYlongitud :: [a] -> (a,Int)\nprimeroYlongitud (x:xs) =\n  (x, 1 + length xs)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\ndensidades5 :: Int -> (Double,Double,Double)\ndensidades5 n = (f a, f p, f d)\n  where (a,p,d) = distribucion n\n        f x = fromIntegral x \/ fromIntegral n\n\n-- (distribucion n) es la terna (a,p,d) donde a es la cantidad de\n-- n\u00fameros abundantes de 1 a n, p la de los perfectos y d la de los\n-- deficientes. Por ejemplo,\n--    distribucion 100  ==  (22,2,76)\ndistribucion :: Int -> (Int,Int,Int)\ndistribucion n = aux (0,0,0) (sumaDivisoresHasta n)\n  where aux (a,p,d) [] = (a,p,d)\n        aux (a,p,d) ((x,y):xys)\n          | x < y     = aux (1+a,p,d) xys\n          | x > y     = aux (a,p,1+d) xys\n          | otherwise = aux (a,1+p,d) xys\n\n-- (sumaDivisoresHasta n) es la lista de los pares (a,b) tales que a\n-- var\u00eda entre 1 y n y b es la suma de los divisores propios de a. Por\n-- ejemplo,\n--    \u03bb> sumaDivisoresHasta 12\n--    [(1,0),(2,1),(3,1),(4,3),(5,1),(6,6),(7,1),(8,7),(9,4),(10,8),(11,1),(12,16)]\nsumaDivisoresHasta :: Int -> [(Int,Int)]\nsumaDivisoresHasta n =\n  assocs (accumArray (+) 0 (1,n) (divisoresHasta n))\n\n-- (divisoresHasta n) es la lista de los pares (a,b) tales que a est\u00e1\n-- entre 2 y n y b es un divisor propio e x. Por ejemplo,\n--    \u03bb> divisoresHasta 6\n--    [(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)]\n--    \u03bb> divisoresHasta 8\n--    [(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)]\ndivisoresHasta :: Int -> [(Int,Int)]\ndivisoresHasta n = [(a,b) | b <- [1..n `div` 2], a <- [b*2, b*3..n]]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_densidades :: Positive Int -> Bool\nprop_densidades (Positive n) =\n  all (== densidades1 n)\n      [ densidades2 n\n      , densidades3 n\n      , densidades4 n\n      , densidades5 n\n      ]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_densidades\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> densidades1 2000\n--    (0.2465,1.5e-3,0.752)\n--    (1.59 secs, 804,883,768 bytes)\n--    \u03bb> densidades2 2000\n--    (0.2465,1.5e-3,0.752)\n--    (1.39 secs, 704,749,552 bytes)\n--    \u03bb> densidades3 2000\n--    (0.2465,1.5e-3,0.752)\n--    (0.81 secs, 403,783,312 bytes)\n--    \u03bb> densidades4 2000\n--    (0.2465,1.5e-3,0.752)\n--    (0.04 secs, 34,364,960 bytes)\n--    \u03bb> densidades5 2000\n--    (0.2465,1.5e-3,0.752)\n--    (0.02 secs, 4,716,720 bytes)\n--\n--    \u03bb> densidades4 100000\n--    (0.24795,4.0e-5,0.75201)\n--    (1.61 secs, 4,826,971,624 bytes)\n--    \u03bb> densidades5 100000\n--    (0.24795,4.0e-5,0.75201)\n--    (0.43 secs, 291,989,272 bytes)\n\n-- Gr\u00e1fica\n-- =======\n\ngraficas :: Int -> IO ()\ngraficas n =\n  plotLists [Key Nothing]\n            [ [x | (x,_,_) <- ts]\n            , [y | (_,y,_) <- ts]\n            , [z | (_,_,z) <- ts]]\n  where ts = [densidades5 k | k <- [1..n]]\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Densidad_de_numeros_abundantes.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Matriz zigzagueante<\/h3>\n<p>La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n\u00b2 primeros n\u00fameros naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es<\/p>\n<pre lang=\"text\">\n    0  1  5  6 14\n    2  4  7 13 15\n    3  8 12 16 21\n    9 11 17 20 22\n   10 18 19 23 24\n<\/pre>\n<p>La colocaci\u00f3n de los elementos se puede ver gr\u00e1ficamente en esta figura<\/p>\n<p><a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png?resize=600%2C600\" alt=\"\" width=\"600\" height=\"600\" class=\"aligncenter size-full wp-image-7046\" data-recalc-dims=\"1\" \/><\/a><\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   zigZag :: Int -> Matrix Int\n<\/pre>\n<p>tal que <code>(zigZag n)<\/code> es la matriz zigzagueante de orden <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> zigZag 5\n   \u250c                \u2510\n   \u2502  0  1  5  6 14 \u2502\n   \u2502  2  4  7 13 15 \u2502\n   \u2502  3  8 12 16 21 \u2502\n   \u2502  9 11 17 20 22 \u2502\n   \u2502 10 18 19 23 24 \u2502\n   \u2514                \u2518\n   \u03bb> zigZag 4\n   \u250c             \u2510\n   \u2502  0  1  5  6 \u2502\n   \u2502  2  4  7 12 \u2502\n   \u2502  3  8 11 13 \u2502\n   \u2502  9 10 14 15 \u2502\n   \u2514             \u2518\n   \u03bb> maximum (zigZag 1500)\n   2249999\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort, sortBy)\nimport Data.Matrix (Matrix, fromList)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nzigZag1 :: Int -> Matrix Int\nzigZag1 n = fromList n n (elementosZigZag n)\n\n-- (elementosZigZag n) es la lista de los elementos de la matriz\n-- zizagueante de orden n. Por ejemplo.\n--    \u03bb> elementosZigZag 5\n--    [0,1,5,6,14,2,4,7,13,15,3,8,12,16,21,9,11,17,20,22,10,18,19,23,24]\nelementosZigZag :: Int -> [Int]\nelementosZigZag n =\n  map snd (sort (zip (ordenZigZag n) [0..]))\n\n-- (ordenZigZag n) es la lista de puntos del cuadrado nxn recorridos en\n-- zig-zag por las diagonales secundarias. Por ejemplo,\n--    \u03bb> ordenZigZag 4\n--    [(1,1), (1,2),(2,1), (3,1),(2,2),(1,3), (1,4),(2,3),(3,2),(4,1),\n--     (4,2),(3,3),(2,4), (3,4),(4,3), (4,4)]\nordenZigZag :: Int -> [(Int,Int)]\nordenZigZag n = concat [aux n m | m <- [2..2*n]]\n    where aux k m | odd m     = [(x,m-x) | x <- [max 1 (m-k)..min k (m-1)]]\n                  | otherwise = [(m-x,x) | x <- [max 1 (m-k)..min k (m-1)]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nzigZag2 :: Int -> Matrix Int\nzigZag2 n = fromList n n (elementosZigZag2 n)\n\nelementosZigZag2 :: Int -> [Int]\nelementosZigZag2 n =\n  map snd (sort (zip (ordenZigZag2 n) [0..]))\n\nordenZigZag2 :: Int -> [(Int,Int)]\nordenZigZag2 n = sortBy comp [(x,y) | x <- [1..n], y <- [1..n]]\n    where comp (x1,y1) (x2,y2) | x1+y1 < x2+y2 = LT\n                               | x1+y1 > x2+y2 = GT\n                               | even (x1+y1)  = compare y1 y2\n                               | otherwise     = compare x1 x2\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_zigZag :: Positive Int -> Bool\nprop_zigZag (Positive n) =\n  zigZag1 n == zigZag2 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_zigZag\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (zigZag1 5000)\n--    25000000\n--    (2.57 secs, 1,800,683,952 bytes)\n--    \u03bb> length (zigZag2 5000)\n--    25000000\n--    (2.20 secs, 1,800,683,952 bytes)\n--\n--    \u03bb> maximum (zigZag1 1100)\n--    1209999\n--    (2.12 secs, 1,840,095,864 bytes)\n--    \u03bb> maximum (zigZag2 1100)\n--    1209999\n--    (21.27 secs, 11,661,088,256 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Matriz_zigzagueante.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Numeraci\u00f3n con base m\u00faltiple<\/h3>\n<p>Sea (b(i) | i \u2265 1) una sucesi\u00f3n infinita de n\u00fameros enteros mayores que 1. Entonces todo entero x mayor que cero se puede escribir de forma \u00fanica como<\/p>\n<pre lang=\"text\">\n   x = x(0) + x(1)b(1) +x(2)b(1)b(2) + ... + x(n)b(1)b(2)...b(n)\n<\/pre>\n<p>donde cada x(i) satisface la condici\u00f3n 0 \u2264 x(i) &lt; b(i+1). Se dice que [x(n),x(n-1),...,x(2),x(1),x(0)] es la representaci\u00f3n de x en la base (b(i)). Por ejemplo, la representaci\u00f3n de 377 en la base (2, 6, 8, ...) es [7,5,0,1] ya que<\/p>\n<pre lang=\"text\">\n   377 = 1 + 0*2 + 5*2*4 + 7*2*4*6\n<\/pre>\n<p>y, adem\u00e1s, 0 \u2264 1 &lt; 2, 0 \u2264 0 &lt; 4, 0 \u2264 5 &lt; 6 y 0 \u2264 7 &lt; 8.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   decimalAmultiple :: [Integer] -> Integer -> [Integer]\n   multipleAdecimal :: [Integer] -> [Integer] -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(decimalAmultiple bs x) es la representaci\u00f3n del n\u00famero x en la base bs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     decimalAmultiple [2,4..] 377                      ==  [7,5,0,1]\n     decimalAmultiple [2,5..] 377                      ==  [4,5,3,1]\n     decimalAmultiple [2^n | n <- [1..]] 2015          ==  [1,15,3,3,1]\n     decimalAmultiple (repeat 10) 2015                 ==  [2,0,1,5]\n<\/pre>\n<ul>\n<li>(multipleAdecimal bs cs) es el n\u00famero decimal cuya  representaci\u00f3n en la base bs es cs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     multipleAdecimal [2,4..] [7,5,0,1]                ==  377\n     multipleAdecimal [2,5..] [4,5,3,1]                ==  377\n     multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1]  ==  2015\n     multipleAdecimal (repeat 10) [2,0,1,5]            ==  2015\n<\/pre>\n<p>Comprobar con QuickCheck que se verifican las siguientes propiedades<\/p>\n<ul>\n<li>Para cualquier base bs y cualquier entero positivo n,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     multipleAdecimal bs (decimalAmultiple bs x) == x\n<\/pre>\n<ul>\n<li>Para cualquier base bs y cualquier entero positivo n, el coefiente i-\u00e9simo de la representaci\u00f3n m\u00faltiple de n en la base bs es un entero no negativo menos que el i-\u00e9simo elemento de bs.<\/li>\n<\/ul>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\nimport Data.List (unfoldr)\n\n-- 1\u00aa soluci\u00f3n de decimalAmultiple\n-- ===============================\n\ndecimalAmultiple1 :: [Integer] -> Integer -> [Integer]\ndecimalAmultiple1 bs n = reverse (aux bs n)\n  where aux _ 0      = []\n        aux (d:ds) m = r : aux ds q\n          where (q,r) = quotRem m d\n\n-- 2\u00aa soluci\u00f3n de decimalAmultiple\n-- ===============================\n\ndecimalAmultiple2 :: [Integer] -> Integer -> [Integer]\ndecimalAmultiple2 bs n = aux bs n []\n  where aux _ 0  xs     = xs\n        aux (d:ds) m xs = aux ds q (r:xs)\n          where (q,r) = quotRem m d\n\n-- 3\u00aa soluci\u00f3n de decimalAmultiple\n-- ===============================\n\ndecimalAmultiple3 :: [Integer] -> Integer -> [Integer]\ndecimalAmultiple3 xs n = reverse (unfoldr f (xs,n))\n  where f (_     ,0) = Nothing\n        f ((y:ys),m) = Just (r,(ys,q))\n                       where (q,r) = quotRem m y\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_decimalAmultiple :: InfiniteList (Positive Integer) -> Positive Integer -> Bool\nprop_decimalAmultiple (InfiniteList xs _) (Positive n) =\n  all (== decimalAmultiple1 xs' n)\n      [decimalAmultiple2 xs' n,\n       decimalAmultiple3 xs' n]\n  where xs' = map getPositive xs\n\n-- Comparaci\u00f3n de eficiencia de decimalAmultiple\n-- =============================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (decimalAmultiple1 [2,7..] (10^(10^5)))\n--    21731\n--    (0.45 secs, 486,085,256 bytes)\n--    \u03bb> length (decimalAmultiple2 [2,7..] (10^(10^5)))\n--    21731\n--    (0.32 secs, 485,563,664 bytes)\n--    \u03bb> length (decimalAmultiple3 [2,7..] (10^(10^5)))\n--    21731\n--    (0.44 secs, 487,649,768 bytes)\n\n-- 1\u00aa soluci\u00f3n de multipleAdecimal\n-- ===============================\n\nmultipleAdecimal1  :: [Integer] -> [Integer] -> Integer\nmultipleAdecimal1 xs ns = aux xs (reverse ns)\n  where aux (y:ys) (m:ms) = m + y * (aux ys ms)\n        aux _ _           = 0\n\n-- 2\u00aa soluci\u00f3n de multipleAdecimal\n-- ===============================\n\nmultipleAdecimal2 :: [Integer] -> [Integer] -> Integer\nmultipleAdecimal2 bs xs =\n  sum (zipWith (*) (reverse xs) (1 : scanl1 (*) bs))\n\n-- Comprobaci\u00f3n de equivalencia de multipleAdecimal\n-- ================================================\n\n-- La propiedad es\nprop_multipleAdecimal :: InfiniteList (Positive Integer) -> [Positive Integer] -> Bool\nprop_multipleAdecimal (InfiniteList xs _) ys =\n  multipleAdecimal1 xs' ys' == multipleAdecimal2 xs' ys'\n  where xs' = map getPositive xs\n        ys' = map getPositive ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_multipleAdecimal\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de multipleAdecimal\n-- =============================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (multipleAdecimal1 [2,3..] [1..10^4]))\n--    35660\n--    (0.14 secs, 179,522,152 bytes)\n--    \u03bb> length (show (multipleAdecimal2 [2,3..] [1..10^4]))\n--    35660\n--    (0.22 secs, 243,368,664 bytes)\n\n-- Comprobaci\u00f3n de las propiedades\n-- ===============================\n\n-- La primera propiedad es\nprop_inversas :: InfiniteList (Positive Integer) -> Positive Integer -> Bool\nprop_inversas (InfiniteList xs _) (Positive n) =\n  multipleAdecimal1 xs' (decimalAmultiple1 xs' n) == n\n  where xs' = map getPositive xs\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_inversas\n--    +++ OK, passed 100 tests.\n\n-- la 2\u00aa propiedad es\nprop_coeficientes :: InfiniteList (Positive Integer) -> Positive Integer -> Bool\nprop_coeficientes (InfiniteList xs _) (Positive n) =\n  and [0 <= c &#038;&#038; c < b | (c,b) <- zip cs xs']\n  where xs' = map getPositive xs\n        cs = reverse (decimalAmultiple1 xs' n)\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_coeficientes\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\/Numeracion_con_multiples_base.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. El tri\u00e1ngulo de Floyd<\/h3>\n<p>El <a href=\"http:\/\/bit.ly\/1D6ZF4q\">tri\u00e1ngulo de Floyd<\/a>, llamado as\u00ed en honor a Robert Floyd, es un tri\u00e1ngulo rect\u00e1ngulo formado con n\u00fameros naturales. Para crear un tri\u00e1ngulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se contin\u00faa escribiendo la secuencia de los n\u00fameros naturales de manera que cada l\u00ednea contenga un n\u00famero m\u00e1s que la anterior. Las 5 primeras l\u00edneas del tri\u00e1ngulo de Floyd son<\/p>\n<pre lang=\"text\">\n    1\n    2   3\n    4   5   6\n    7   8   9  10\n   11  12  13  14  15\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   trianguloFloyd :: [[Integer]]\n<\/pre>\n<p>tal que <code>trianguloFloyd<\/code> es el tri\u00e1ngulo de Floyd. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 4 trianguloFloyd\n   [[1],\n    [2,3],\n    [4,5,6],\n    [7,8,9,10]]\n  (trianguloFloyd !! (10^5)) !! 0  ==  5000050001\n  (trianguloFloyd !! (10^6)) !! 0  ==  500000500001\n  (trianguloFloyd !! (10^7)) !! 0  ==  50000005000001\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd1 :: [[Integer]]\ntrianguloFloyd1 = floyd 1 [1..]\n  where floyd n xs = i : floyd (n+1) r\n          where (i,r) = splitAt n xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd2 :: [[Integer]]\ntrianguloFloyd2 = iterate siguienteF [1]\n\n-- (siguienteF xs) es la lista de los elementos de la l\u00ednea xs en el\n-- tri\u00e1ngulo de Floyd. Por ejemplo,\n--    siguienteF [2,3]    ==  [4,5,6]\n--    siguienteF [4,5,6]  ==  [7,8,9,10]\nsiguienteF :: [Integer] -> [Integer]\nsiguienteF xs = [a..a+n]\n    where a = 1 + last xs\n          n = genericLength xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd3 :: [[Integer]]\ntrianguloFloyd3 =\n  [[(n*(n-1) `div` 2) + 1 .. (n*(n+1) `div` 2)] | n <- [1..]]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd4 :: [[Integer]]\ntrianguloFloyd4 =\n  scanl (\\(x:_) y -> [x+y..x+2*y]) [1] [1..]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_trianguloFloyd :: Positive Int -> Bool\nprop_trianguloFloyd (Positive n) =\n  all (== (trianguloFloyd1 !! n))\n      [trianguloFloyd2 !! n,\n       trianguloFloyd3 !! n,\n       trianguloFloyd4 !! n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_trianguloFloyd\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> (trianguloFloyd1 !! 5000) !! 5000\n--    12507501\n--    (1.47 secs, 2,505,005,752 bytes)\n--    \u03bb> (trianguloFloyd2 !! 5000) !! 5000\n--    12507501\n--    (0.79 secs, 2,416,259,176 bytes)\n--    \u03bb> (trianguloFloyd3 !! 5000) !! 5000\n--    12507501\n--    (0.00 secs, 1,809,152 bytes)\n--    \u03bb> (trianguloFloyd4 !! 5000) !! 5000\n--    12507501\n--    (0.01 secs, 3,517,896 bytes)\n--\n--    \u03bb> (trianguloFloyd3 !! (10^7)) !! 0\n--    50000005000001\n--    (2.45 secs, 1,656,534,080 bytes)\n--    \u03bb> (trianguloFloyd4 !! (10^7)) !! 0\n--    50000005000001\n--    (10.86 secs, 5,302,760,752 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/El_triangulo_de_Floyd.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Polinomios cuadr\u00e1ticos generadores de primos<\/h3>\n<p>En 1772, Euler public\u00f3 que el polinomio n\u00b2 + n + 41 genera 40 n\u00fameros primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n = 40, 40\u00b2+40+41 = 40(40+1)+41 es divisible por 41.<\/p>\n<p>Usando ordenadores, se descubri\u00f3 que el polinomio n\u00b2 - 79n + 1601 genera 80 n\u00fameros primos para todos los valores de n entre 0 y 79.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])\n<\/pre>\n<p>tal que <code>(generadoresMaximales n)<\/code> es el par <code>(m,xs)<\/code> donde<\/p>\n<ul>\n<li><code>xs<\/code> es la lista de pares <code>(x,y)<\/code> tales que <code>n\u00b2+xn+y<\/code> es uno de  polinomios que genera un n\u00famero m\u00e1ximo de n\u00fameros primos consecutivos a partir de cero entre todos los polinomios de la forma <code>n\u00b2+an+b<\/code>, con <code>|a| \u2264 n<\/code> y <code>|b| \u2264 n<\/code> y<\/li>\n<li><code>m<\/code> es dicho n\u00famero m\u00e1ximo.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   generadoresMaximales    4  ==  ( 3,[(-2,3),(-1,3),(3,3)])\n   generadoresMaximales    6  ==  ( 5,[(-1,5),(5,5)])\n   generadoresMaximales   41  ==  (41,[(-1,41)])\n   generadoresMaximales   50  ==  (43,[(-5,47)])\n   generadoresMaximales  100  ==  (48,[(-15,97)])\n   generadoresMaximales  200  ==  (53,[(-25,197)])\n   generadoresMaximales 1650  ==  (80,[(-79,1601)])\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort)\nimport Data.Numbers.Primes (primes, isPrime)\nimport I1M.PolOperaciones (valor, consPol, polCero)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ngeneradoresMaximales1 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales1 n =\n  (m,[(a,b) | a <- [-n..n], b <- [-n..n], nPrimos a b == m])\n  where m = maximum [nPrimos a b | a <- [-n..n], b <- [-n..n]]\n\n-- (nPrimos a b) es el n\u00famero de primos consecutivos generados por el\n-- polinomio n\u00b2 + an + b a partir de n=0. Por ejemplo,\n--    nPrimos (-1) 41     ==  41\n--    nPrimos (-79) 1601  ==  80\nnPrimos :: Integer -> Integer -> Int\nnPrimos a b =\n  length (takeWhile isPrime [n*n+a*n+b | n <- [0..]])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Notas:\n-- 1. Se tiene que b es primo, ya que para n = 0, se tiene que\n--    0\u00b2+a*0+b = b es primo.\n-- 2. Se tiene que 1+a+b es primo, ya que es el valor del polinomio para\n--    n = 1.\n\ngeneradoresMaximales2 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales2 n = (m,map snd zs)\n  where xs = [(nPrimos a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                    a <- [-n..n],\n                                    isPrime(1+a+b)]\n        ys = reverse (sort xs)\n        m  = fst (head ys)\n        zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ngeneradoresMaximales3 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales3 n = (m,map snd zs)\n  where xs = [(nPrimos a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                    p <- takeWhile (<=1+2*n) primes,\n                                    let a = p-b-1]\n        ys = reverse (sort xs)\n        m  = fst (head ys)\n        zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- 4\u00aa soluci\u00f3n (con la librer\u00eda de polinomios)\n-- ===========================================\n\ngeneradoresMaximales4 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales4 n = (m,map snd zs)\n  where xs = [(nPrimos2 a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                     p <- takeWhile (<=1+2*n) primes,\n                                     let a = p-b-1]\n        ys = reverse (sort xs)\n        m  = fst (head ys)\n        zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- (nPrimos2 a b) es el n\u00famero de primos consecutivos generados por el\n-- polinomio n\u00b2 + an + b a partir de n=0. Por ejemplo,\n--    nPrimos2 (-1) 41     ==  41\n--    nPrimos2 (-79) 1601  ==  80\nnPrimos2 :: Integer -> Integer -> Int\nnPrimos2 a b =\n  length (takeWhile isPrime [valor p n | n <- [0..]])\n  where p = consPol 2 1 (consPol 1 a (consPol 0 b polCero))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_generadoresMaximales :: Positive Integer -> Bool\nprop_generadoresMaximales (Positive n) =\n  all (equivalentes (generadoresMaximales1 n'))\n      [generadoresMaximales2 n',\n       generadoresMaximales3 n',\n       generadoresMaximales4 n']\n  where n' = n+1\n\nequivalentes :: (Int,[(Integer,Integer)]) -> (Int,[(Integer,Integer)]) -> Bool\nequivalentes (n,xs) (m,ys) =\n  n == m && sort xs == sort ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_generadoresMaximales\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> generadoresMaximales1 300\n--    (56,[(-31,281)])\n--    (2.10 secs, 2,744,382,760 bytes)\n--    \u03bb> generadoresMaximales2 300\n--    (56,[(-31,281)])\n--    (0.17 secs, 382,103,656 bytes)\n--    \u03bb> generadoresMaximales3 300\n--    (56,[(-31,281)])\n--    (0.19 secs, 346,725,872 bytes)\n--    \u03bb> generadoresMaximales4 300\n--    (56,[(-31,281)])\n--    (0.20 secs, 388,509,808 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Polinomios_cuadraticos_generadores_de_primos.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Densidades de n\u00fameros abundantes, perfectos y deficientes 2. Matriz zigzagueante 3. Numeraci\u00f3n con base m\u00faltiple 4. El tri\u00e1ngulo de Floyd 5. Polinomios cuadr\u00e1ticos generadores de primos 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\/7745"}],"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=7745"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7745\/revisions"}],"predecessor-version":[{"id":7746,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7745\/revisions\/7746"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}