Factorizaciones de números de Hilbert
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número 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, …
Definir la función
1 |
factorizacionesH :: Integer -> [[Integer]] |
tal que factorizacionesH n
es la listas de primos de Hilbert cuyo producto es el número de Hilbert n
. Por ejemplo,
1 2 3 4 |
factorizacionesH 25 == [[5,5]] factorizacionesH 45 == [[5,9]] factorizacionesH 441 == [[9,49],[21,21]] factorizacionesH 80109 == [[9,9,989],[9,69,129]] |
Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorización, como para el 441, puede no ser única).
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
module Factorizaciones_de_numeros_de_Hilbert where import Data.Numbers.Primes (isPrime, primeFactors) import Test.QuickCheck (Positive (Positive), quickCheck) import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Numeros_primos_de_Hilbert (primosH1, primosH2, primosH3) import Data.Traversable (forM) -- 1ª solución -- =========== factorizacionesH1 :: Integer -> [[Integer]] factorizacionesH1 = aux primosH1 where aux (x:xs) n | x == n = [[n]] | x > n = [] | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n | otherwise = aux xs n -- 2ª solución -- =========== factorizacionesH2 :: Integer -> [[Integer]] factorizacionesH2 = aux primosH2 where aux (x:xs) n | x == n = [[n]] | x > n = [] | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n | otherwise = aux xs n -- 3ª solución -- =========== -- Basada en la siguiente propiedad: Un primo de Hilbert es un primo -- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) × (4b + 3) -- (ver en https://bit.ly/3zq7h4e ). factorizacionesH3 :: Integer -> [[Integer]] factorizacionesH3 = aux primosH3 where aux (x:xs) n | x == n = [[n]] | x > n = [] | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n | otherwise = aux xs n -- Verificación -- -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> [[Integer]]) -> Spec specG factorizacionesH = do it "e1" $ factorizacionesH 25 `shouldBe` [[5,5]] it "e2" $ factorizacionesH 45 `shouldBe` [[5,9]] it "e3" $ factorizacionesH 441 `shouldBe` [[9,49],[21,21]] spec :: Spec spec = do describe "def. 1" $ specG factorizacionesH1 describe "def. 2" $ specG factorizacionesH2 describe "def. 3" $ specG factorizacionesH3 -- La verificación es -- λ> verifica -- -- 9 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_factorizacionesH :: Positive Integer -> Bool prop_factorizacionesH (Positive n) = all (== factorizacionesH1 m) [factorizacionesH2 m, factorizacionesH3 m] where m = 1 + 4 * n -- La comprobación es -- λ> quickCheck prop_factorizacionesH -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> factorizacionesH1 80109 -- [[9,9,989],[9,69,129]] -- (42.77 secs, 14,899,787,640 bytes) -- λ> factorizacionesH2 80109 -- [[9,9,989],[9,69,129]] -- (0.26 secs, 156,051,104 bytes) -- λ> factorizacionesH3 80109 -- [[9,9,989],[9,69,129]] -- (0.35 secs, 1,118,236,536 bytes) -- Propiedad de factorización -- ========================== -- La propiedad es prop_factorizable :: Positive Integer -> Bool prop_factorizable (Positive n) = not (null (factorizacionesH1 (1 + 4 * n))) -- La comprobación es -- λ> quickCheck prop_factorizable -- +++ OK, passed 100 tests. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
from itertools import takewhile from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st from src.Numeros_primos_de_Hilbert import primosH1, primosH2 setrecursionlimit(10**6) # 1ª solución # =========== def factorizacionesH1(m: int) -> list[list[int]]: ys = list(takewhile(lambda y: y <= m, primosH1())) def aux(zs: list[int], n: int) -> list[list[int]]: if not zs: return [] x, *xs = zs if x == n: return [[n]] if x > n: return [] if n % x == 0: return [[x] + ns for ns in aux(zs, n // x)] + aux(xs, n) return aux(xs, n) return aux(ys, m) # 2ª solución # =========== def factorizacionesH2(m: int) -> list[list[int]]: ys = list(takewhile(lambda y: y <= m, primosH2())) def aux(zs: list[int], n: int) -> list[list[int]]: if not zs: return [] x, *xs = zs if x == n: return [[n]] if x > n: return [] if n % x == 0: return [[x] + ns for ns in aux(zs, n // x)] + aux(xs, n) return aux(xs, n) return aux(ys, m) # Verificación # ============ def test_factorizacionesH() -> None: for factorizacionesH in [factorizacionesH1, factorizacionesH2]: assert factorizacionesH(25) == [[5,5]] assert factorizacionesH(45) == [[5,9]] assert factorizacionesH(441) == [[9,49],[21,21]] print("Verificado") # La verificación es # >>> test_factorizacionesH() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_factorizacionesH_equiv(n: int) -> None: m = 1 + 4 * n assert factorizacionesH1(m) == factorizacionesH2(m) # La comprobación es # >>> test_factorizacionesH_equiv() # >>> # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('factorizacionesH1(80109)') # 25.40 segundos # >>> tiempo('factorizacionesH2(80109)') # 0.27 segundos # Propiedad de factorización # ========================== # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_factorizable(n: int) -> None: assert factorizacionesH2(1 + 4 * n) != [] # La comprobación es # >>> test_factorizable() # >>> # Comprobación de todas las propiedades # ===================================== # La comprobación es # src> poetry run pytest -v Factorizaciones_de_numeros_de_Hilbert.py # ===== test session starts ===== # test_factorizacionesH PASSED # test_factorizacionesH_equiv PASSED # test_factorizable PASSED # ===== 3 passed in 2.25s ===== |
Referencias —
Basado en el artículo Failure of unique factorization (A simple example of the failure of the fundamental theorem of arithmetic) de R.J. Lipton en el blog Gödel’s Lost Letter and P=NP.
Otras referencias
- Wikipedia, Hilbert number.
- E.W. Weisstein, Hilbert number en MathWorld.
- N.J.A. Sloane, Sucesión A057948 en la OEIS.
- N.J.A. Sloane, Sucesión A057949 en la OEIS.