Sumas de dos primos

Definir la sucesión

   sumasDeDosPrimos :: [Integer]

1	sumasDeDosPrimos :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,

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

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

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

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)

Soluciones en Python

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

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

Referencia

N.J.A. Sloane Sucesión A014091 en OEIS.

Sumas de dos primos

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