factorizacionesH :: Integer -> [[Integer]]

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

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.

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