{"id":7767,"date":"2022-08-06T18:04:03","date_gmt":"2022-08-06T16:04:03","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7767"},"modified":"2022-08-06T18:08:14","modified_gmt":"2022-08-06T16:08:14","slug":"pfh-la-semana-en-exercitium-5-de-agosto-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-5-de-agosto-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (5 de agosto 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. N\u00fameros primos de Hilbert<\/a><\/li>\n<li><a href=\"#ej2\">2. Factorizaciones de n\u00fameros de Hilbert<\/a><\/li>\n<li><a href=\"#ej3\">3. Representaciones de un n\u00famero como suma de dos cuadrados<\/a><\/li>\n<li><a href=\"#ej4\">4. N\u00famero de representaciones de n como suma de dos cuadrados<\/a><\/li>\n<li><a href=\"#ej5\">5. N\u00fameros de Pentanacci<\/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. N\u00fameros primos de Hilbert<\/h3>\n<p>Un <a href=\"http:\/\/bit.ly\/204SW1p\"><strong>n\u00famero de Hilbert<\/strong><\/a> es un  positivo de la forma 4n+1. Los primeros n\u00fameros de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, &#8230;<\/p>\n<p>Un <strong>primo de Hilbert<\/strong> es un n\u00famero de Hilbert n que no es  por ning\u00fan n\u00famero de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, &#8230;<\/p>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   primosH :: [Integer]\n<\/pre>\n<p>tal que sus elementos son los primos de Hilbert. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   take 15 primosH     == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]\n   primosH !! (3*10^4) == 313661\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime, primeFactors)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosH1 :: [Integer]\nprimosH1 = [n | n <- tail numerosH,\n                divisoresH n == [1,n]]\n\n-- numerosH es la sucesi\u00f3n de los n\u00fameros de Hilbert. Por ejemplo,\n--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]\nnumerosH :: [Integer]\nnumerosH = [1,5..]\n\n-- (divisoresH n) es la lista de los n\u00fameros de Hilbert que dividen a\n-- n. Por ejemplo,\n--   divisoresH 117  ==  [1,9,13,117]\n--   divisoresH  21  ==  [1,21]\ndivisoresH :: Integer -> [Integer]\ndivisoresH n = [x | x <- takeWhile (<=n) numerosH,\n                    n `mod` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosH2 :: [Integer]\nprimosH2 = filter esPrimoH (tail numerosH)\n  where esPrimoH n = all noDivideAn [5,9..m]\n          where noDivideAn x = n `mod` x \/= 0\n                m            = ceiling (sqrt (fromIntegral n))\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\n-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo\n-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) \u00d7 (4b + 3)\n-- (ver en https:\/\/bit.ly\/3zq7h4e ).\n\nprimosH3 :: [Integer]\nprimosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]\n  where semiPrimoH n = length xs == 2 &#038;&#038; all (\\x -> (x-3) `mod` 4 == 0) xs\n          where xs = primeFactors n\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosH :: NonNegative Int -> Bool\nprop_primosH (NonNegative n) =\n  all (== primosH1 !! n)\n      [primosH2 !! n,\n       primosH3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_primosH\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosH1 !! 2000\n--    16957\n--    (2.16 secs, 752,085,752 bytes)\n--    \u03bb> primosH2 !! 2000\n--    16957\n--    (0.03 secs, 19,771,008 bytes)\n--    \u03bb> primosH3 !! 2000\n--    16957\n--    (0.07 secs, 152,029,168 bytes)\n--\n--    \u03bb> primosH2 !! (3*10^4)\n--    313661\n--    (1.44 secs, 989,761,888 bytes)\n--    \u03bb> primosH3 !! (3*10^4)\n--    313661\n--    (2.06 secs, 6,554,068,992 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numeros_primos_de_Hilbert.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Factorizaciones de n\u00fameros de Hilbert<\/h3>\n<p>Un <a href=\"http:\/\/bit.ly\/204SW1p\"><strong>n\u00famero de Hilbert<\/strong><\/a> es un entero positivo de la forma 4n+1. Los primeros n\u00fameros de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, &#8230;<\/p>\n<p>Un <strong>primo de Hilbert<\/strong> es un n\u00famero de Hilbert n que no es  por ning\u00fan n\u00famero de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, &#8230;<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   factorizacionesH :: Integer -> [[Integer]]\n<\/pre>\n<p>tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el n\u00famero de Hilbert n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n  factorizacionesH  25    ==  [[5,5]]\n  factorizacionesH  45    ==  [[5,9]]\n  factorizacionesH 441    ==  [[9,49],[21,21]]\n  factorizacionesH 80109  ==  [[9,9,989],[9,69,129]]\n<\/pre>\n<p>Comprobar con QuickCheck que todos los n\u00fameros de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorizaci\u00f3n, como para el 441, puede no ser \u00fanica).<\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime, primeFactors)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nfactorizacionesH1 :: Integer -> [[Integer]]\nfactorizacionesH1 = aux primosH1\n  where\n    aux (x:xs) n\n      | x == n         = [[n]]\n      | x > n          = []\n      | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n\n      | otherwise      = aux xs n\n\nprimosH1 :: [Integer]\nprimosH1 = [n | n <- tail numerosH,\n                divisoresH n == [1,n]]\n\n-- numerosH es la sucesi\u00f3n de los n\u00fameros de Hilbert. Por ejemplo,\n--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]\nnumerosH :: [Integer]\nnumerosH = [1,5..]\n\n-- (divisoresH n) es la lista de los n\u00fameros de Hilbert que dividen a\n-- n. Por ejemplo,\n--   divisoresH 117  ==  [1,9,13,117]\n--   divisoresH  21  ==  [1,21]\ndivisoresH :: Integer -> [Integer]\ndivisoresH n = [x | x <- takeWhile (<=n) numerosH,\n                    n `mod` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfactorizacionesH2 :: Integer -> [[Integer]]\nfactorizacionesH2 = aux primosH2\n  where\n    aux (x:xs) n\n      | x == n         = [[n]]\n      | x > n          = []\n      | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n\n      | otherwise      = aux xs n\n\nprimosH2 :: [Integer]\nprimosH2 = filter esPrimoH (tail numerosH)\n  where esPrimoH n = all noDivideAn [5,9..m]\n          where noDivideAn x = n `mod` x \/= 0\n                m            = ceiling (sqrt (fromIntegral n))\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\n-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo\n-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) \u00d7 (4b + 3)\n-- (ver en https:\/\/bit.ly\/3zq7h4e ).\n\nfactorizacionesH3 :: Integer -> [[Integer]]\nfactorizacionesH3 = aux primosH3\n  where\n    aux (x:xs) n\n      | x == n         = [[n]]\n      | x > n          = []\n      | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n\n      | otherwise      = aux xs n\n\nprimosH3 :: [Integer]\nprimosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]\n  where semiPrimoH n = length xs == 2 &#038;&#038; all (\\x -> (x-3) `mod` 4 == 0) xs\n          where xs = primeFactors n\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_factorizacionesH :: Positive Integer -> Bool\nprop_factorizacionesH (Positive n) =\n  all (== factorizacionesH1 m)\n      [factorizacionesH2 m,\n       factorizacionesH3 m]\n  where m = 1 + 4 * n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_factorizacionesH\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> factorizacionesH1 80109\n--    [[9,9,989],[9,69,129]]\n--    (42.77 secs, 14,899,787,640 bytes)\n--    \u03bb> factorizacionesH2 80109\n--    [[9,9,989],[9,69,129]]\n--    (0.26 secs, 156,051,104 bytes)\n--    \u03bb> factorizacionesH3 80109\n--    [[9,9,989],[9,69,129]]\n--    (0.35 secs, 1,118,236,536 bytes)\n\n-- Propiedad de factorizaci\u00f3n\n-- ==========================\n\n-- La propiedad es\nprop_factorizable :: Positive Integer -> Bool\nprop_factorizable (Positive n) =\n  not (null (factorizacionesH1 (1 + 4 * n)))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_factorizable\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\/Factorizaciones_de_numeros_de_Hilbert.hs\">GitHub<\/a>.<\/p>\n<h4>Referencias<\/h4>\n<p>Basado en el art\u00edculo <a href=\"http:\/\/bit.ly\/20A2Nyc\">Failure of unique factorization (A  example of the failure of the fundamental theorem of arithmetic)<\/a> de R.J. Lipton en el blog <a href=\"https:\/\/rjlipton.wordpress.com\">G\u00f6del&#8217;s Lost Letter and P=NP<\/a>.<\/p>\n<p>Otras  referencias<\/p>\n<ul>\n<li>Wikipedia, <a href=\"http:\/\/bit.ly\/204SW1p\">Hilbert number<\/a>.<\/li>\n<li>E.W. Weisstein, <a href=\"http:\/\/bit.ly\/204T8O4\">Hilbert number<\/a> en MathWorld.<\/li>\n<li>N.J.A. Sloane, <a href=\"https:\/\/oeis.org\/A057948\">Sucesi\u00f3n A057948<\/a> en la OEIS.<\/li>\n<li>N.J.A. Sloane, <a href=\"https:\/\/oeis.org\/A057949\">Sucesi\u00f3n A057949<\/a> en la OEIS.<\/li>\n<\/ul>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Representaciones de un n\u00famero como suma de dos cuadrados<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   representaciones :: Integer -> [(Integer,Integer)]\n<\/pre>\n<p>tal que (representaciones n) es la lista de pares de n\u00fameros naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.<\/p>\n<pre lang=\"text\">\n   representaciones  20              ==  [(2,4)]\n   representaciones  25              ==  [(0,5),(3,4)]\n   representaciones 325              ==  [(1,18),(6,17),(10,15)]\n   length (representaciones (10^14)) == 8\n<\/pre>\n<p>Comprobar con QuickCheck que un n\u00famero natural n se puede  como suma de dos cuadrados si, y s\u00f3lo si, en la factorizaci\u00f3n prima de n todos los exponentes de sus factores primos congruentes con 3 m\u00f3dulo 4 son pares.<\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones1 :: Integer -> [(Integer,Integer)]\nrepresentaciones1 n =\n  [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones2 :: Integer -> [(Integer,Integer)]\nrepresentaciones2 n =\n  [(x,raiz z) | x <- [0..raiz (n `div` 2)],\n                let z = n - x*x,\n                esCuadrado z]\n\n-- (raiz x) es la ra\u00edz cuadrada entera de x. Por ejemplo,\n--    raiz 25  ==  5\n--    raiz 24  ==  4\n--    raiz 26  ==  5\nraiz :: Integer -> Integer\nraiz = floor . sqrt . fromIntegral\n\n-- (esCuadrado x) se verifica si x es un n\u00famero al cuadrado. Por\n-- ejemplo,\n--    esCuadrado 25  ==  True\n--    esCuadrado 26  ==  False\nesCuadrado :: Integer -> Bool\nesCuadrado x = x == y * y\n  where y = raiz x\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones3 :: Integer -> [(Integer, Integer)]\nrepresentaciones3 n = aux 0 (raiz n)\n  where aux x y\n          | x > y     = []\n          | otherwise = case compare (x*x + y*y) n of\n                          LT -> aux (x + 1) y\n                          EQ -> (x, y) : aux (x + 1) (y - 1)\n                          GT -> aux x (y - 1)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_representaciones :: Positive Integer -> Bool\nprop_representaciones (Positive n) =\n  all (== representaciones1 n)\n      [representaciones2 n,\n       representaciones3 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representaciones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> representaciones1 4000\n--    [(20,60),(36,52)]\n--    (4.95 secs, 2,434,929,624 bytes)\n--    \u03bb> representaciones2 4000\n--    [(20,60),(36,52)]\n--    (0.00 secs, 599,800 bytes)\n--    \u03bb> representaciones3 4000\n--    [(20,60),(36,52)]\n--    (0.01 secs, 591,184 bytes)\n--\n--    \u03bb> length (representaciones2 (10^14))\n--    8\n--    (6.64 secs, 5,600,837,088 bytes)\n--    \u03bb> length (representaciones3 (10^14))\n--    8\n--    (9.37 secs, 4,720,548,264 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_representacion :: Positive Integer -> Bool\nprop_representacion (Positive n) =\n  not (null (representaciones2 n)) ==\n  all (\\(p,e) -> p `mod` 4 \/= 3 || even e) (factorizacion n)\n\n-- (factorizacion n) es la factorizaci\u00f3n prima de n. Por ejemplo,\n--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n  map (\\xs -> (head xs, genericLength xs)) (group (primeFactors n))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representacion\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\/Representaciones_de_un_numero_como_suma_de_dos_cuadrados.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. N\u00famero de representaciones de n como suma de dos cuadrados<\/h3>\n<p><br \/>\nSea <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> un n\u00famero natural cuya factorizaci\u00f3n prima es<br \/>\n$$n = 2^{a} \\times p(1)^{b(1)} \\times \\dots \\times p(n)^{b(n)} \\times q(1)^{c(1)} \\times \\dots \\times q(m)^{c(m)}$$<br \/>\ndonde los <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=p%28i%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"p(i)\" class=\"latex\" \/> son los divisores primos de <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> congruentes con 3 m\u00f3dulo 4 y los <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=q%28j%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"q(j)\" class=\"latex\" \/> son los divisores primos de <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> congruentes con 1 m\u00f3dulo 4. Entonces, el n\u00famero de forma de descomponer <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n\" class=\"latex\" \/> como suma de dos<br \/>\ncuadrados es 0, si alg\u00fan <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=b%28i%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"b(i)\" class=\"latex\" \/> es impar y es el techo (es decir, el n\u00famero entero m\u00e1s pr\u00f3ximo por exceso) de<br \/>\n$$\\frac{(1+c(1)) \\times \\dots \\times (1+c(m))}{2}$$<br \/>\nen caso contrario. Por ejemplo, el n\u00famero<br \/>\n$$2^{3} \\times (3^{9} \\times 7^{8}) \\times (5^{3} \\times 13^{6})$$<br \/>\nno se puede descomponer como sumas de dos cuadrados (porque el exponente de 3 es impar) y el n\u00famero<br \/>\n$$2^{3} \\times (3^{2} \\times 7^{8}) \\times (5^{3} \\times 13^{6})$$<br \/>\ntiene 14 descomposiciones como suma de dos cuadrados (porque los exponentes de 3 y 7 son pares y el techo de<br \/>\n$$\\frac{(1+3) \\times (1+6)}{2}$$<br \/>\nes 14).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   nRepresentaciones :: Integer -> Integer\n<\/pre>\n<p>tal que (nRepresentaciones n) es el n\u00famero de formas de representar n como suma de dos cuadrados. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   nRepresentaciones (2^3*3^9*5^3*7^8*13^6)        ==  0\n   nRepresentaciones (2^3*3^2*5^3*7^8*13^6)        ==  14\n   head [n | n <- [1..], nRepresentaciones n > 8]  ==  71825\n<\/pre>\n<p>Usando la funci\u00f3n representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad<\/p>\n<pre lang=\"text\">\n   prop_representacion :: Positive Integer -> Bool\n   prop_representacion (Positive n) =\n     nRepresentaciones2 n == genericLength (representaciones n)\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnRepresentaciones1 :: Integer -> Integer\nnRepresentaciones1 n =\n  ceiling (fromIntegral (product (map aux (factorizacion n))) \/ 2)\n  where aux (p,e) | p == 2         = 1\n                  | p `mod` 4 == 3 = if even e then 1 else 0\n                  | otherwise      = e+1\n\n-- (factorizacion n) es la factorizaci\u00f3n prima de n. Por ejemplo,\n--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n  map (\\xs -> (head xs, genericLength xs)) (group (primeFactors n))\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnRepresentaciones2 :: Integer -> Integer\nnRepresentaciones2 n =\n  (1 + product (map aux (factorizacion n))) `div`  2\n  where aux (p,e) | p == 2         = 1\n                  | p `mod` 4 == 3 = if even e then 1 else 0\n                  | otherwise      = e+1\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_nRepresentaciones :: Positive Integer -> Bool\nprop_nRepresentaciones (Positive n) =\n  nRepresentaciones1 n == nRepresentaciones2 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_nRepresentaciones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> head [n | n <- [1..], nRepresentaciones1 n > 8]\n--    71825\n--    (1.39 secs, 2,970,063,760 bytes)\n--    \u03bb> head [n | n <- [1..], nRepresentaciones2 n > 8]\n--    71825\n--    (1.71 secs, 2,943,788,424 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_representacion :: Positive Integer -> Bool\nprop_representacion (Positive n) =\n  nRepresentaciones2 n == genericLength (representaciones n)\n\nrepresentaciones :: Integer -> [(Integer,Integer)]\nrepresentaciones n =\n  [(x,raiz z) | x <- [0..raiz (n `div` 2)],\n                let z = n - x*x,\n                esCuadrado z]\n\nesCuadrado :: Integer -> Bool\nesCuadrado x = x == y * y\n  where y = raiz x\n\nraiz :: Integer -> Integer\nraiz x = floor (sqrt (fromIntegral x))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representacion\n--    +++ OK, passed 100 tests.\n\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numero_de_representaciones_de_n_como_suma_de_dos_cuadrados.hs\">GitHub<\/a>.<\/p>\n<h4>Referencias<\/h4>\n<ul>\n<li>W. Stein, <a href=\"http:\/\/bit.ly\/1Q193xq\">Which numbers are the sum of two squares?<\/a>.<\/li>\n<li>E.W. Weisstein, <a href=\"http:\/\/bit.ly\/1Q1c4Oe\">Sum of squares function<\/a> en MathWorld.<\/li>\n<li>N.J.A. Sloane,<a href=\"http:\/\/oeis.org\/A004018\">Sucesi\u00f3n A004018<\/a> de OEIS.<\/li>\n<li><a href=\"http:\/\/bit.ly\/20Nr1VY\">Expressing a number as a sum of two squares<\/a>.<\/li>\n<li><a href=\"http:\/\/bit.ly\/20NrWpp\">Sum of squares<\/a>.<\/li>\n<\/ul>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. N\u00fameros de Pentanacci<\/h3>\n<p>Los n\u00fameros de Fibonacci se definen mediante las ecuaciones<\/p>\n<pre lang=\"text\">\n   F(0) = 0\n   F(1) = 1\n   F(n) = F(n-1) + F(n-2), si n > 1\n<\/pre>\n<p>Los primeros n\u00fameros de Fibonacci son<\/p>\n<pre lang=\"text\">\n   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...\n<\/pre>\n<p>Una generalizaci\u00f3n de los anteriores son los n\u00fameros de Pentanacci definidos por las siguientes ecuaciones<\/p>\n<pre lang=\"text\">\n   P(0) = 0\n   P(1) = 1\n   P(2) = 1\n   P(3) = 2\n   P(4) = 4\n   P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4\n<\/pre>\n<p>Los primeros n\u00fameros de Pentanacci son<\/p>\n<pre lang=\"text\">\n  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...\n<\/pre>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   pentanacci :: [Integer]\n<\/pre>\n<p>cuyos elementos son los n\u00fameros de Pentanacci. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 15 pentanacci\n   [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]\n   \u03bb> (pentanacci !! (10^5)) `mod` (10^30)\n   482929150584077921552549215816\n   231437922897686901289110700696\n   \u03bb> length (show (pentanacci !! (10^5)))\n   29357\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (zipWith5)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\npentanacci1 :: [Integer]\npentanacci1 = [pent n | n <- [0..]]\n\npent :: Integer -> Integer\npent 0 = 0\npent 1 = 1\npent 2 = 1\npent 3 = 2\npent 4 = 4\npent n = pent (n-1) + pent (n-2) + pent (n-3) + pent (n-4) + pent (n-5)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\npentanacci2 :: [Integer]\npentanacci2 =\n  0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4)\n  where f a b c d e = a+b+c+d+e\n        r n         = drop n pentanacci2\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\npentanacci3 :: [Integer]\npentanacci3 = p (0, 1, 1, 2, 4)\n  where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\npentanacci4 :: [Integer]\npentanacci4 = 0: 1: 1: 2: 4: p pentanacci4\n  where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_pentanacci :: NonNegative Int -> Bool\nprop_pentanacci (NonNegative n) =\n  all (== pentanacci1 !! n)\n      [pentanacci1 !! n,\n       pentanacci2 !! n,\n       pentanacci3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=25}) prop_pentanacci\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> pentanacci1 !! 25\n--    5976577\n--    (3.18 secs, 1,025,263,896 bytes)\n--    \u03bb> pentanacci2 !! 25\n--    5976577\n--    (0.00 secs, 562,360 bytes)\n--\n--    \u03bb> length (show (pentanacci2 !! (10^5)))\n--    29357\n--    (1.04 secs, 2,531,259,408 bytes)\n--    \u03bb> length (show (pentanacci3 !! (10^5)))\n--    29357\n--    (1.00 secs, 2,548,868,384 bytes)\n--    \u03bb> length (show (pentanacci4 !! (10^5)))\n--    29357\n--    (0.96 secs, 2,580,065,520 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numeros_de_Pentanacci.hs\">GitHub<\/a>.<\/p>\n<h4>Referencias<\/h4>\n<ul>\n<li>Tito III Piezas y Eric Weisstein, <a href=\"https:\/\/bit.ly\/3cPJGkF\">Pentanacci number<\/a>.<\/li>\n<li>N. J. A. Sloane, <a href=\"https:\/\/oeis.org\/A001591\">Sucesi\u00f3n A001591 de la OEIS<\/a>.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. N\u00fameros primos de Hilbert 2. Factorizaciones de n\u00fameros de Hilbert 3. Representaciones de un n\u00famero como suma de dos cuadrados 4. N\u00famero de representaciones de n como suma de dos cuadrados 5. N\u00fameros de Pentanacci 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\/7767"}],"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=7767"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7767\/revisions"}],"predecessor-version":[{"id":7769,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7767\/revisions\/7769"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}