{"id":7165,"date":"2022-08-02T06:00:55","date_gmt":"2022-08-02T04:00:55","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7165"},"modified":"2022-07-24T12:19:47","modified_gmt":"2022-07-24T10:19:47","slug":"factorizaciones-de-numeros-de-hilbert","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/factorizaciones-de-numeros-de-hilbert\/","title":{"rendered":"Factorizaciones de n\u00fameros de Hilbert"},"content":{"rendered":"

Un 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, …<\/p>\n

Un 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, …<\/p>\n

Definir la funci\u00f3n<\/p>\n

\n   factorizacionesH :: Integer -> [[Integer]]\n<\/pre>\n
tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el n\u00famero de Hilbert n. Por ejemplo,<\/p>\n
\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
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
Soluciones<\/h4>\n
\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 && 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
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
Referencias<\/h4>\n
Basado en el art\u00edculo Failure of unique factorization (A  example of the failure of the fundamental theorem of arithmetic)<\/a> de R.J. Lipton en el blog G\u00f6del’s Lost Letter and P=NP<\/a>.<\/p>\n
Otras  referencias<\/p>\n