{"id":8363,"date":"2023-12-24T06:00:21","date_gmt":"2023-12-24T04:00:21","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8363"},"modified":"2024-02-18T21:28:25","modified_gmt":"2024-02-18T19:28:25","slug":"24-dic-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/24-dic-23\/","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 divisible 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<\/code> es la listas de primos de Hilbert cuyo producto es el n\u00famero de Hilbert n<\/code>. 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).
\n<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Factorizaciones_de_numeros_de_Hilbert where\n\nimport Data.Numbers.Primes (isPrime, primeFactors)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Numeros_primos_de_Hilbert (primosH1, primosH2, primosH3)\n\nimport Data.Traversable (forM)\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\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\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\n-- Verificaci\u00f3n                                                     --\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> [[Integer]]) -> Spec\nspecG factorizacionesH = do\n  it \"e1\" $\n    factorizacionesH  25 `shouldBe` [[5,5]]\n  it \"e2\" $\n    factorizacionesH  45 `shouldBe` [[5,9]]\n  it \"e3\" $\n    factorizacionesH 441 `shouldBe` [[9,49],[21,21]]\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG factorizacionesH1\n  describe \"def. 2\" $ specG factorizacionesH2\n  describe \"def. 3\" $ specG factorizacionesH3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    9 examples, 0 failures\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
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import takewhile\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Numeros_primos_de_Hilbert import primosH1, primosH2\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef factorizacionesH1(m: int) -> list[list[int]]:\n    ys = list(takewhile(lambda y: y <= m, primosH1()))\n    def aux(zs: list[int], n: int) -> list[list[int]]:\n        if not zs:\n            return []\n        x, *xs = zs\n        if x == n:\n            return [[n]]\n        if x > n:\n            return []\n        if n % x == 0:\n            return [[x] + ns for ns in aux(zs, n \/\/ x)] + aux(xs, n)\n        return aux(xs, n)\n    return aux(ys, m)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef factorizacionesH2(m: int) -> list[list[int]]:\n    ys = list(takewhile(lambda y: y <= m, primosH2()))\n    def aux(zs: list[int], n: int) -> list[list[int]]:\n        if not zs:\n            return []\n        x, *xs = zs\n        if x == n:\n            return [[n]]\n        if x > n:\n            return []\n        if n % x == 0:\n            return [[x] + ns for ns in aux(zs, n \/\/ x)] + aux(xs, n)\n        return aux(xs, n)\n    return aux(ys, m)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_factorizacionesH() -> None:\n    for factorizacionesH in [factorizacionesH1, factorizacionesH2]:\n        assert factorizacionesH(25) == [[5,5]]\n        assert factorizacionesH(45) == [[5,9]]\n        assert factorizacionesH(441) == [[9,49],[21,21]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_factorizacionesH()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_factorizacionesH_equiv(n: int) -> None:\n    m = 1 + 4 * n\n    assert factorizacionesH1(m) == factorizacionesH2(m)\n\n# La comprobaci\u00f3n es\n#    >>> test_factorizacionesH_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('factorizacionesH1(80109)')\n#    25.40 segundos\n#    >>> tiempo('factorizacionesH2(80109)')\n#    0.27 segundos\n\n# Propiedad de factorizaci\u00f3n\n# ==========================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_factorizable(n: int) -> None:\n    assert factorizacionesH2(1 + 4 * n) != []\n\n# La comprobaci\u00f3n es\n#    >>> test_factorizable()\n#    >>>\n\n# Comprobaci\u00f3n de todas las propiedades\n# =====================================\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -v Factorizaciones_de_numeros_de_Hilbert.py\n#    ===== test session starts =====\n#    test_factorizacionesH PASSED\n#    test_factorizacionesH_equiv PASSED\n#    test_factorizable PASSED\n#    ===== 3 passed in 2.25s =====\n<\/pre>\n
Referencias<\/b>                                                      —<\/p>\n
Basado en el art\u00edculo Failure of unique factorization (A simple 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