Ir al contenido principal

Primos cubanos

Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.

Definir la sucesión

   cubanos :: [Integer]

tal que sus elementos son los números cubanos. Por ejemplo,

   λ> take 15 cubanos
   [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]

Soluciones

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

Soluciones en Haskell

module Primos_cubanos where

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

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

cubanos1 :: [Integer]
cubanos1 = filter isPrime (zipWith (-) (tail cubos) cubos)

-- cubos es la lista de los cubos. Por ejemplo,
--    λ> take 10 cubos
--    [1,8,27,64,125,216,343,512,729,1000]
cubos :: [Integer]
cubos = map (^3) [1..]

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

cubanos2 :: [Integer]
cubanos2 = filter isPrime [(x+1)^3 - x^3 | x <- [1..]]

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

cubanos3 :: [Integer]
cubanos3 = filter isPrime [3*x^2 + 3*x + 1 | x <- [1..]]

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

verifica :: IO ()
verifica = hspec spec

specG :: [Integer] -> Spec
specG cubanos = do
  it "e1" $
    take 15 cubanos `shouldBe`
    [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]

spec :: Spec
spec = do
  describe "def. 1" $ specG cubanos1
  describe "def. 2" $ specG cubanos2
  describe "def. 3" $ specG cubanos3

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

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

-- La propiedad es
prop_cubanos :: NonNegative Int -> Bool
prop_cubanos (NonNegative n) =
  all (== cubanos1 !! n)
      [cubanos2 !! n,
       cubanos3 !! n]

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

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

-- La comparación es
--    λ> cubanos1 !! 3000
--    795066361
--    (4.21 secs, 16,953,612,192 bytes)
--    λ> cubanos2 !! 3000
--    795066361
--    (4.27 secs, 16,962,597,288 bytes)
--    λ> cubanos3 !! 3000
--    795066361
--    (4.29 secs, 16,956,085,672 bytes)

Soluciones en Python

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

from sympy import isprime

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

# cubos() es la lista de los cubos. Por ejemplo,
#    >>> list(islice(cubos(), 10))
#    [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
def cubos() -> Iterator[int]:
    return (x**3 for x in count(1))

# parejasDeCubos() es la lista de las parejas de cubos consecutivos. Por
# ejemplo,
#    >>> list(islice(parejasDeCubos(), 5))
#    [(1, 8), (8, 27), (27, 64), (64, 125), (125, 216)]
def parejasDeCubos() -> Iterator[tuple[int, int]]:
    a, b = tee(cubos())
    next(b, None)
    return zip(a, b)

# diferenciasDeCubos() es la lista de las diferencias de cubos
# consecutivos. Por ejemplo,
#    >>> list(islice(diferenciasDeCubos(), 5))
#    [7, 19, 37, 61, 91]
def diferenciasDeCubos() -> Iterator[int]:
    return (j - i for i, j in parejasDeCubos())

def cubanos1() -> Iterator[int]:
    return (x for x in diferenciasDeCubos() if isprime(x))

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

def cubanos2() -> Iterator[int]:
    return ((x+1)**3 - x**3 for x in count(1) if isprime((x+1)**3 - x**3))

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

def cubanos3() -> Iterator[int]:
    return (y for x in count(1) if isprime((y := (x+1)**3 - x**3)))

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

def cubanos4() -> Iterator[int]:
    return (y for x in count(1) if isprime((y := 3*x**2 + 3*x + 1)))

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

def test_cubanos() -> None:
    for cubanos in [cubanos1, cubanos2, cubanos3, cubanos4]:
        assert list(islice(cubanos(), 15)) == \
            [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]
    print ("Verificado")

# La verificación es
#    >>> test_cubanos()
#    Verificado

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

# La propiedad es
def test_cubanos_equiv(n: int) -> None:
    r = list(islice(cubanos1(), n))
    assert list(islice(cubanos2(), n)) == r
    assert list(islice(cubanos3(), n)) == r
    assert list(islice(cubanos4(), n)) == r
    print("Verificado")

# La comprobación es
#    >>> test_cubanos_equiv(10000)
#    Verificado

# 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('list(islice(cubanos1(), 30000))')
#    1.54 segundos
#    >>> tiempo('list(islice(cubanos1(), 40000))')
#    2.20 segundos
#    >>> tiempo('list(islice(cubanos2(), 40000))')
#    2.22 segundos
#    >>> tiempo('list(islice(cubanos3(), 40000))')
#    2.19 segundos
#    >>> tiempo('list(islice(cubanos4(), 40000))')
#    2.15 segundos