{"id":8365,"date":"2023-12-29T13:05:36","date_gmt":"2023-12-29T11:05:36","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8365"},"modified":"2024-02-02T17:07:57","modified_gmt":"2024-02-02T15:07:57","slug":"29-dic-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/29-dic-23\/","title":{"rendered":"Sumas de dos primos"},"content":{"rendered":"

Definir la sucesi\u00f3n<\/p>\n

\n   sumasDeDosPrimos :: [Integer]\n<\/pre>\n
cuyos elementos son los n\u00fameros que se pueden escribir como suma de dos n\u00fameros primos. Por ejemplo,<\/p>\n
\n   \u03bb> take 23 sumasDeDosPrimos\n   [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]\n   \u03bb> sumasDeDosPrimos !! (5*10^5)\n   862878\n<\/pre>\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 Sumas_de_dos_primos where\n\nimport Data.Numbers.Primes (isPrime, primes)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumasDeDosPrimos1 :: [Integer]\nsumasDeDosPrimos1 =\n  [n | n <- [1..], not (null (sumaDeDosPrimos1 n))]\n\n-- (sumaDeDosPrimos1 n) es la lista de pares de primos cuya suma es\n-- n. Por ejemplo,\n--    sumaDeDosPrimos  9  ==  [(2,7),(7,2)]\n--    sumaDeDosPrimos 16  ==  [(3,13),(5,11),(11,5),(13,3)]\n--    sumaDeDosPrimos 17  ==  []\nsumaDeDosPrimos1 :: Integer -> [(Integer,Integer)]\nsumaDeDosPrimos1 n =\n  [(x,n-x) | x <- primosN, isPrime (n-x)]\n  where primosN = takeWhile (< n) primes\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumasDeDosPrimos2 :: [Integer]\nsumasDeDosPrimos2 =\n  [n | n <- [1..], not (null (sumaDeDosPrimos2 n))]\n\n-- (sumasDeDosPrimos2 n) es la lista de pares (x,y) de primos cuya suma\n-- es n y tales que x <= y. Por ejemplo,\n--    sumaDeDosPrimos2  9  ==  [(2,7)]\n--    sumaDeDosPrimos2 16  ==  [(3,13),(5,11)]\n--    sumaDeDosPrimos2 17  ==  []\nsumaDeDosPrimos2 :: Integer -> [(Integer,Integer)]\nsumaDeDosPrimos2 n =\n  [(x,n-x) | x <- primosN, isPrime (n-x)]\n  where primosN = takeWhile (<= (n `div` 2)) primes\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsumasDeDosPrimos3 :: [Integer]\nsumasDeDosPrimos3 = filter esSumaDeDosPrimos3 [4..]\n\n-- (esSumaDeDosPrimos3 n) se verifica si n es suma de dos primos. Por\n-- ejemplo,\n--    esSumaDeDosPrimos3  9  ==  True\n--    esSumaDeDosPrimos3 16  ==  True\n--    esSumaDeDosPrimos3 17  ==  False\nesSumaDeDosPrimos3 :: Integer -> Bool\nesSumaDeDosPrimos3 n\n  | odd n     = isPrime (n-2)\n  | otherwise = any isPrime [n-x | x <- takeWhile (<= (n `div` 2)) primes]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Usando la conjetura de Goldbach que dice que \"Todo n\u00famero par mayor\n-- que 2 puede escribirse como suma de dos n\u00fameros primos\" .\n\nsumasDeDosPrimos4 :: [Integer]\nsumasDeDosPrimos4 = filter esSumaDeDosPrimos4 [4..]\n\n-- (esSumaDeDosPrimos4 n) se verifica si n es suma de dos primos. Por\n-- ejemplo,\n--    esSumaDeDosPrimos4  9  ==  True\n--    esSumaDeDosPrimos4 16  ==  True\n--    esSumaDeDosPrimos4 17  ==  False\nesSumaDeDosPrimos4 :: Integer -> Bool\nesSumaDeDosPrimos4 n = even n || isPrime (n-2)\n\n-- Verificaci\u00f3n                                                     --\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: [Integer] -> Spec\nspecG sumasDeDosPrimos = do\n  it \"e1\" $\n    take 23 sumasDeDosPrimos `shouldBe`\n    [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG sumasDeDosPrimos1\n  describe \"def. 2\" $ specG sumasDeDosPrimos2\n  describe \"def. 3\" $ specG sumasDeDosPrimos3\n  describe \"def. 4\" $ specG sumasDeDosPrimos4\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    4 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sumasDeDosPrimos :: NonNegative Int -> Bool\nprop_sumasDeDosPrimos (NonNegative n) =\n  all (== sumasDeDosPrimos1 !! n)\n      [sumasDeDosPrimos2 !! n,\n       sumasDeDosPrimos3 !! n,\n       sumasDeDosPrimos4 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumasDeDosPrimos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sumasDeDosPrimos1 !! 5000\n--    7994\n--    (2.61 secs, 9,299,106,792 bytes)\n--    \u03bb> sumasDeDosPrimos2 !! 5000\n--    7994\n--    (1.48 secs, 5,190,651,760 bytes)\n--    \u03bb> sumasDeDosPrimos3 !! 5000\n--    7994\n--    (0.12 secs, 351,667,104 bytes)\n--    \u03bb> sumasDeDosPrimos4 !! 5000\n--    7994\n--    (0.04 secs, 63,464,320 bytes)\n--\n--    \u03bb> sumasDeDosPrimos3 !! (5*10^4)\n--    83674\n--    (2.23 secs, 7,776,049,264 bytes)\n--    \u03bb> sumasDeDosPrimos4 !! (5*10^4)\n--    83674\n--    (0.34 secs, 1,183,604,984 bytes)\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import count, islice, takewhile\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom sympy import isprime\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# primos() genera la lista de los primos. Por ejemplo,\n#    >>> list(islice(primos(), 10))\n#    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\ndef primos() -> Iterator[int]:\n    return (n for n in count() if isprime(n))\n\n# sumaDeDosPrimos1(n) es la lista de pares de primos cuya suma es\n# n. Por ejemplo,\n#    sumaDeDosPrimos1(9)   ==  [(2,7),(7,2)]\n#    sumaDeDosPrimos1(16)  ==  [(3,13),(5,11),(11,5),(13,3)]\n#    sumaDeDosPrimos1(17)  ==  []\ndef sumaDeDosPrimos1(n: int) -> list[tuple[int, int]]:\n    primosN = takewhile(lambda x: x< n, primos())\n    return [(x,n-x) for x in primosN if isprime(n-x)]\n\ndef sumasDeDosPrimos1() -> Iterator[int]:\n    return (n for n in count(1) if sumaDeDosPrimos1(n))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# sumasDeDosPrimos2(n) es la lista de pares (x,y) de primos cuya suma\n# es n y tales que x <= y. Por ejemplo,\n#    sumaDeDosPrimos2(9)   ==  [(2,7)]\n#    sumaDeDosPrimos2(16)  ==  [(3,13),(5,11)]\n#    sumaDeDosPrimos2(17)  ==  []\ndef sumaDeDosPrimos2(n: int) -> list[tuple[int, int]]:\n    primosN = takewhile(lambda x : x <= n \/\/ 2, primos())\n    return [(x,n-x) for x in primosN if isprime(n-x)]\n\ndef sumasDeDosPrimos2() -> Iterator[int]:\n    return (n for n in count(1) if sumaDeDosPrimos2(n))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# esSumaDeDosPrimos3(n) se verifica si n es suma de dos primos. Por\n# ejemplo,\n#    esSumaDeDosPrimos3(9)   ==  True\n#    esSumaDeDosPrimos3(16)  ==  True\n#    esSumaDeDosPrimos3(17)  ==  False\ndef esSumaDeDosPrimos3(n: int) -> bool:\n    if n % 2 == 1:\n        return isprime(n-2)\n    return any(isprime(n-x)\n               for x in takewhile(lambda x : x <= n \/\/ 2, primos()))\n\ndef sumasDeDosPrimos3() -> Iterator[int]:\n    return filter(esSumaDeDosPrimos3, count(4))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\n# Usando la conjetura de Goldbach que dice que \"Todo n\u00famero par mayor\n# que 2 puede escribirse como suma de dos n\u00fameros primos\" .\n\n# esSumaDeDosPrimos4(n) se verifica si n es suma de dos primos. Por\n# ejemplo,\n#    esSumaDeDosPrimos4(9)   ==  True\n#    esSumaDeDosPrimos4(16)  ==  True\n#    esSumaDeDosPrimos4(17)  ==  False\ndef esSumaDeDosPrimos4(n: int) -> bool:\n    return n % 2 == 0 or isprime(n-2)\n\ndef sumasDeDosPrimos4() -> Iterator[int]:\n    return filter(esSumaDeDosPrimos4, count(4))\n\n# Verificaci\u00f3n                                                     --\n# ============\n\n# La propiedad es\ndef test_sumasDeDosPrimos() -> None:\n    r = [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]\n    assert list(islice(sumasDeDosPrimos1(), 23)) == r\n    assert list(islice(sumasDeDosPrimos2(), 23)) == r\n    assert list(islice(sumasDeDosPrimos3(), 23)) == r\n    assert list(islice(sumasDeDosPrimos4(), 23)) == r\n    print(\"Verificado\")\n\n# La comprobaci\u00f3n es\n#    >>> test_sumasDeDosPrimos()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# nth(i, n) es el n-\u00e9simo elemento del iterador i. Por ejemplo,\n#    nth(primos(), 4) == 11\ndef nth(i: Iterator[int], n: int) -> int:\n    return list(islice(i, n, n+1))[0]\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=200))\ndef test_sumasDeDosPrimos_equiv(n: int) -> None:\n    r = nth(sumasDeDosPrimos1(), n)\n    assert nth(sumasDeDosPrimos2(), n) == r\n    assert nth(sumasDeDosPrimos3(), n) == r\n    assert nth(sumasDeDosPrimos4(), n) == r\n\n# La comprobaci\u00f3n es\n#    >>> test_sumasDeDosPrimos_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('nth(sumasDeDosPrimos1(), 1000)')\n#    3.02 segundos\n#    >>> tiempo('nth(sumasDeDosPrimos2(), 1000)')\n#    1.53 segundos\n#    >>> tiempo('nth(sumasDeDosPrimos3(), 1000)')\n#    0.03 segundos\n#    >>> tiempo('nth(sumasDeDosPrimos4(), 1000)')\n#    0.00 segundos\n#\n#    >>> tiempo('nth(sumasDeDosPrimos3(), 5*10**4)')\n#    3.76 segundos\n#    >>> tiempo('nth(sumasDeDosPrimos4(), 5*10**4)')\n#    0.33 segundos\n<\/pre>\n
Referencia<\/b><\/p>\n