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

   factorizacionesH :: Integer -> [[Integer]]

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,

  factorizacionesH  25    ==  [[5,5]]
  factorizacionesH  45    ==  [[5,9]]
  factorizacionesH 441    ==  [[9,49],[21,21]]
  factorizacionesH 80109  ==  [[9,9,989],[9,69,129]]

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.

Soluciones en Haskell

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.

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.

Soluciones en Python

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 =====

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.

Factorizaciones de números de Hilbert

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico