sumasDeDosPrimos :: [Integer]

   λ> take 23 sumasDeDosPrimos
   [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]
   λ> sumasDeDosPrimos !! (5*10^5)
   862878

module Sumas_de_dos_primos where

import Data.Numbers.Primes (isPrime, primes)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª solución
-- ===========

sumasDeDosPrimos1 :: [Integer]
sumasDeDosPrimos1 =
  [n | n <- [1..], not (null (sumaDeDosPrimos1 n))]

-- (sumaDeDosPrimos1 n) es la lista de pares de primos cuya suma es
-- n. Por ejemplo,
--    sumaDeDosPrimos  9  ==  [(2,7),(7,2)]
--    sumaDeDosPrimos 16  ==  [(3,13),(5,11),(11,5),(13,3)]
--    sumaDeDosPrimos 17  ==  []
sumaDeDosPrimos1 :: Integer -> [(Integer,Integer)]
sumaDeDosPrimos1 n =
  [(x,n-x) | x <- primosN, isPrime (n-x)]
  where primosN = takeWhile (< n) primes

-- 2ª solución
-- ===========

sumasDeDosPrimos2 :: [Integer]
sumasDeDosPrimos2 =
  [n | n <- [1..], not (null (sumaDeDosPrimos2 n))]

-- (sumasDeDosPrimos2 n) es la lista de pares (x,y) de primos cuya suma
-- es n y tales que x <= y. Por ejemplo,
--    sumaDeDosPrimos2  9  ==  [(2,7)]
--    sumaDeDosPrimos2 16  ==  [(3,13),(5,11)]
--    sumaDeDosPrimos2 17  ==  []
sumaDeDosPrimos2 :: Integer -> [(Integer,Integer)]
sumaDeDosPrimos2 n =
  [(x,n-x) | x <- primosN, isPrime (n-x)]
  where primosN = takeWhile (<= (n `div` 2)) primes

-- 3ª solución
-- ===========

sumasDeDosPrimos3 :: [Integer]
sumasDeDosPrimos3 = filter esSumaDeDosPrimos3 [4..]

-- (esSumaDeDosPrimos3 n) se verifica si n es suma de dos primos. Por
-- ejemplo,
--    esSumaDeDosPrimos3  9  ==  True
--    esSumaDeDosPrimos3 16  ==  True
--    esSumaDeDosPrimos3 17  ==  False
esSumaDeDosPrimos3 :: Integer -> Bool
esSumaDeDosPrimos3 n
  | odd n     = isPrime (n-2)
  | otherwise = any isPrime [n-x | x <- takeWhile (<= (n `div` 2)) primes]

-- 4ª solución
-- ===========

-- Usando la conjetura de Goldbach que dice que "Todo número par mayor
-- que 2 puede escribirse como suma de dos números primos" .

sumasDeDosPrimos4 :: [Integer]
sumasDeDosPrimos4 = filter esSumaDeDosPrimos4 [4..]

-- (esSumaDeDosPrimos4 n) se verifica si n es suma de dos primos. Por
-- ejemplo,
--    esSumaDeDosPrimos4  9  ==  True
--    esSumaDeDosPrimos4 16  ==  True
--    esSumaDeDosPrimos4 17  ==  False
esSumaDeDosPrimos4 :: Integer -> Bool
esSumaDeDosPrimos4 n = even n || isPrime (n-2)

-- Verificación                                                     --
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: [Integer] -> Spec
specG sumasDeDosPrimos = do
  it "e1" $
    take 23 sumasDeDosPrimos `shouldBe`
    [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]

spec :: Spec
spec = do
  describe "def. 1" $ specG sumasDeDosPrimos1
  describe "def. 2" $ specG sumasDeDosPrimos2
  describe "def. 3" $ specG sumasDeDosPrimos3
  describe "def. 4" $ specG sumasDeDosPrimos4

-- La verificación es
--    λ> verifica
--
--    4 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_sumasDeDosPrimos :: NonNegative Int -> Bool
prop_sumasDeDosPrimos (NonNegative n) =
  all (== sumasDeDosPrimos1 !! n)
      [sumasDeDosPrimos2 !! n,
       sumasDeDosPrimos3 !! n,
       sumasDeDosPrimos4 !! n]

-- La comprobación es
--    λ> quickCheck prop_sumasDeDosPrimos
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> sumasDeDosPrimos1 !! 5000
--    7994
--    (2.61 secs, 9,299,106,792 bytes)
--    λ> sumasDeDosPrimos2 !! 5000
--    7994
--    (1.48 secs, 5,190,651,760 bytes)
--    λ> sumasDeDosPrimos3 !! 5000
--    7994
--    (0.12 secs, 351,667,104 bytes)
--    λ> sumasDeDosPrimos4 !! 5000
--    7994
--    (0.04 secs, 63,464,320 bytes)
--
--    λ> sumasDeDosPrimos3 !! (5*10^4)
--    83674
--    (2.23 secs, 7,776,049,264 bytes)
--    λ> sumasDeDosPrimos4 !! (5*10^4)
--    83674
--    (0.34 secs, 1,183,604,984 bytes)

from itertools import count, islice, takewhile
from timeit import Timer, default_timer
from typing import Iterator

from hypothesis import given
from hypothesis import strategies as st
from sympy import isprime

# 1ª solución
# ===========

# primos() genera la lista de los primos. Por ejemplo,
#    >>> list(islice(primos(), 10))
#    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
def primos() -> Iterator[int]:
    return (n for n in count() if isprime(n))

# sumaDeDosPrimos1(n) es la lista de pares de primos cuya suma es
# n. Por ejemplo,
#    sumaDeDosPrimos1(9)   ==  [(2,7),(7,2)]
#    sumaDeDosPrimos1(16)  ==  [(3,13),(5,11),(11,5),(13,3)]
#    sumaDeDosPrimos1(17)  ==  []
def sumaDeDosPrimos1(n: int) -> list[tuple[int, int]]:
    primosN = takewhile(lambda x: x< n, primos())
    return [(x,n-x) for x in primosN if isprime(n-x)]

def sumasDeDosPrimos1() -> Iterator[int]:
    return (n for n in count(1) if sumaDeDosPrimos1(n))

# 2ª solución
# ===========

# sumasDeDosPrimos2(n) es la lista de pares (x,y) de primos cuya suma
# es n y tales que x <= y. Por ejemplo,
#    sumaDeDosPrimos2(9)   ==  [(2,7)]
#    sumaDeDosPrimos2(16)  ==  [(3,13),(5,11)]
#    sumaDeDosPrimos2(17)  ==  []
def sumaDeDosPrimos2(n: int) -> list[tuple[int, int]]:
    primosN = takewhile(lambda x : x <= n // 2, primos())
    return [(x,n-x) for x in primosN if isprime(n-x)]

def sumasDeDosPrimos2() -> Iterator[int]:
    return (n for n in count(1) if sumaDeDosPrimos2(n))

# 3ª solución
# ===========

# esSumaDeDosPrimos3(n) se verifica si n es suma de dos primos. Por
# ejemplo,
#    esSumaDeDosPrimos3(9)   ==  True
#    esSumaDeDosPrimos3(16)  ==  True
#    esSumaDeDosPrimos3(17)  ==  False
def esSumaDeDosPrimos3(n: int) -> bool:
    if n % 2 == 1:
        return isprime(n-2)
    return any(isprime(n-x)
               for x in takewhile(lambda x : x <= n // 2, primos()))

def sumasDeDosPrimos3() -> Iterator[int]:
    return filter(esSumaDeDosPrimos3, count(4))

# 4ª solución
# ===========

# Usando la conjetura de Goldbach que dice que "Todo número par mayor
# que 2 puede escribirse como suma de dos números primos" .

# esSumaDeDosPrimos4(n) se verifica si n es suma de dos primos. Por
# ejemplo,
#    esSumaDeDosPrimos4(9)   ==  True
#    esSumaDeDosPrimos4(16)  ==  True
#    esSumaDeDosPrimos4(17)  ==  False
def esSumaDeDosPrimos4(n: int) -> bool:
    return n % 2 == 0 or isprime(n-2)

def sumasDeDosPrimos4() -> Iterator[int]:
    return filter(esSumaDeDosPrimos4, count(4))

# Verificación                                                     --
# ============

# La propiedad es
def test_sumasDeDosPrimos() -> None:
    r = [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]
    assert list(islice(sumasDeDosPrimos1(), 23)) == r
    assert list(islice(sumasDeDosPrimos2(), 23)) == r
    assert list(islice(sumasDeDosPrimos3(), 23)) == r
    assert list(islice(sumasDeDosPrimos4(), 23)) == r
    print("Verificado")

# La comprobación es
#    >>> test_sumasDeDosPrimos()
#    Verificado

# Comprobación de equivalencia
# ============================

# nth(i, n) es el n-ésimo elemento del iterador i. Por ejemplo,
#    nth(primos(), 4) == 11
def nth(i: Iterator[int], n: int) -> int:
    return list(islice(i, n, n+1))[0]

# La propiedad es
@given(st.integers(min_value=1, max_value=200))
def test_sumasDeDosPrimos_equiv(n: int) -> None:
    r = nth(sumasDeDosPrimos1(), n)
    assert nth(sumasDeDosPrimos2(), n) == r
    assert nth(sumasDeDosPrimos3(), n) == r
    assert nth(sumasDeDosPrimos4(), n) == r

# La comprobación es
#    >>> test_sumasDeDosPrimos_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('nth(sumasDeDosPrimos1(), 1000)')
#    3.02 segundos
#    >>> tiempo('nth(sumasDeDosPrimos2(), 1000)')
#    1.53 segundos
#    >>> tiempo('nth(sumasDeDosPrimos3(), 1000)')
#    0.03 segundos
#    >>> tiempo('nth(sumasDeDosPrimos4(), 1000)')
#    0.00 segundos
#
#    >>> tiempo('nth(sumasDeDosPrimos3(), 5*10**4)')
#    3.76 segundos
#    >>> tiempo('nth(sumasDeDosPrimos4(), 5*10**4)')
#    0.33 segundos