Ir al contenido principal

Números con dígitos primos

Definir la lista

   numerosConDigitosPrimos :: [Integer]

cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,

   λ> take 22 numerosConDigitosPrimos
   [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223]
   λ> numerosConDigitosPrimos !! (10^7)
   322732232572

1. Soluciones en Haskell

import Test.QuickCheck (NonNegative (NonNegative), quickCheck)
import Data.Char (intToDigit)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

numerosConDigitosPrimos1 :: [Integer]
numerosConDigitosPrimos1 = [n | n <- [2..], digitosPrimos n]

-- (digitosPrimos n) se verifica si todos los dígitos de n son
-- primos. Por ejemplo,
--    digitosPrimos 352  ==  True
--    digitosPrimos 362  ==  False
digitosPrimos :: Integer -> Bool
digitosPrimos n = subconjunto (digitos n) [2,3,5,7]

-- (digitos n) es la lista de las digitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. Por
-- ejemplo,
--    subconjunto [3,2,5,2] [2,7,3,5]  ==  True
--    subconjunto [3,2,5,2] [2,7,2,5]  ==  False
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto xs ys = and [x `elem` ys | x <- xs]

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

numerosConDigitosPrimos2 :: [Integer]
numerosConDigitosPrimos2 =
  filter (all (`elem` "2357") . show) [2..]

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

--    λ> take 60 numerosConDigitosPrimos2
--    [  2,  3,  5,  7,
--      22, 23, 25, 27,
--      32, 33, 35, 37,
--      52, 53, 55, 57,
--      72, 73, 75, 77,
--     222,223,225,227,
--     232,233,235,237,
--     252,253,255,257,
--     272,273,275,277,
--     322,323,325,327,
--     332,333,335,337,
--     352,353,355,357,
--     372,373,375,377,
--     522,523,525,527,
--     532,533,535,537]

numerosConDigitosPrimos3 :: [Integer]
numerosConDigitosPrimos3 =
  [2,3,5,7] ++ [10*n+d | n <- numerosConDigitosPrimos3, d <- [2,3,5,7]]

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

--    λ> take 60 numerosConDigitosPrimos2
--    [ 2, 3, 5, 7,
--     22,23,25,27,
--     32,33,35,37,
--     52,53,55,57,
--     72,73,75,77,
--     222,223,225,227, 232,233,235,237, 252,253,255,257, 272,273,275,277,
--     322,323,325,327, 332,333,335,337, 352,353,355,357, 372,373,375,377,
--     522,523,525,527, 532,533,535,537]

numerosConDigitosPrimos4 :: [Integer]
numerosConDigitosPrimos4 = concat (iterate siguiente [2,3,5,7])

-- (siguiente xs) es la lista obtenida añadiendo delante de cada
-- elemento de xs los dígitos 2, 3, 5 y 7. Por ejemplo,
--    λ> siguiente [5,6,8]
--    [25,26,28,
--     35,36,38,
--     55,56,58,
--     75,76,78]
siguiente :: [Integer] -> [Integer]
siguiente xs = concat [map (pega d) xs | d <- [2,3,5,7]]

-- (pega d n) es el número obtenido añadiendo el dígito d delante del
-- número n. Por ejemplo,
--    pega 3 35  ==  335
pega :: Int -> Integer -> Integer
pega d n = read (intToDigit d : show n)

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

verifica :: IO ()
verifica = hspec spec

specG :: [Integer] -> Spec
specG numerosConDigitosPrimos = do
  it "e1" $
    take 22 numerosConDigitosPrimos `shouldBe`
    [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223]

spec :: Spec
spec = do
  describe "def. 1" $ specG numerosConDigitosPrimos1
  describe "def. 2" $ specG numerosConDigitosPrimos2
  describe "def. 3" $ specG numerosConDigitosPrimos3
  describe "def. 4" $ specG numerosConDigitosPrimos4

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

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

-- La propiedad es
prop_numerosConDigitosPrimos_equiv :: NonNegative Int -> Bool
prop_numerosConDigitosPrimos_equiv (NonNegative n) =
  all (== numerosConDigitosPrimos1 !! n)
      [ numerosConDigitosPrimos2 !! n
      , numerosConDigitosPrimos3 !! n
      , numerosConDigitosPrimos4 !! n
      ]

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

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

-- La comparación es
--    λ> numerosConDigitosPrimos1 !! 5000
--    752732
--    (2.45 secs, 6,066,926,272 bytes)
--    λ> numerosConDigitosPrimos2 !! 5000
--    752732
--    (0.34 secs, 387,603,456 bytes)
--    λ> numerosConDigitosPrimos3 !! 5000
--    752732
--    (0.01 secs, 1,437,624 bytes)
--    λ> numerosConDigitosPrimos4 !! 5000
--    752732
--    (0.00 secs, 1,556,104 bytes)
--
--    λ> numerosConDigitosPrimos3 !! (10^7)
--    322732232572
--    (3.94 secs, 1,820,533,328 bytes)
--    λ> numerosConDigitosPrimos4 !! (10^7)
--    322732232572
--    (1.84 secs, 2,000,606,640 bytes)

2. Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st

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

# digitos(n) es la lista de las digitos de n. Por ejemplo,
#    digitos(325)  ==  [3,2,5]
def digitos(n: int) -> list[int]:
    return [int(x) for x in str(n)]

# subconjunto(xs, ys) se verifica si xs es un subconjunto de ys. Por
# ejemplo,
#    subconjunto([3,2,5,2], [2,7,3,5])  ==  True
#    subconjunto([3,2,5,2], [2,7,2,5])  ==  False
def subconjunto(xs: list[int],
                ys: list[int]) -> bool:
    return all(x in ys for x in xs)

# digitosPrimos(n) se verifica si todos los dígitos de n son
# primos. Por ejemplo,
#    digitosPrimos(352)  ==  True
#    digitosPrimos(362)  ==  False
def digitosPrimos(n: int) -> bool:
    return subconjunto(digitos(n), [2,3,5,7])

def numerosConDigitosPrimos1() -> Iterator[int]:
    return (n for n in count(2) if digitosPrimos(n))

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

def numerosConDigitosPrimos2() -> Iterator[int]:
    return filter(lambda n: all(d in '2357' for d in str(n)), count(2))

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

#    >>> list(islice(numerosConDigitosPrimos2(), 60))
#    [  2,  3,  5,  7,
#      22, 23, 25, 27,
#      32, 33, 35, 37,
#      52, 53, 55, 57,
#      72, 73, 75, 77,
#     222,223,225,227,
#     232,233,235,237,
#     252,253,255,257,
#     272,273,275,277,
#     322,323,325,327,
#     332,333,335,337,
#     352,353,355,357,
#     372,373,375,377,
#     522,523,525,527,
#     532,533,535,537]

def numerosConDigitosPrimos3() -> Iterator[int]:
    base = [2, 3, 5, 7]
    numeros = base.copy()
    while True:
        yield from numeros
        numeros = [10*n + d for n in numeros for d in base]

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

#    >>> list(islice(numerosConDigitosPrimos2(), 60))
#    [ 2, 3, 5, 7,
#     22,23,25,27,
#     32,33,35,37,
#     52,53,55,57,
#     72,73,75,77,
#     222,223,225,227, 232,233,235,237, 252,253,255,257, 272,273,275,277,
#     322,323,325,327, 332,333,335,337, 352,353,355,357, 372,373,375,377,
#     522,523,525,527, 532,533,535,537]

# pega(d, n) es el número obtenido añadiendo el dígito d delante del
# número n. Por ejemplo,
#    pega(3, 35)  ==  335
def pega(d: int, n: int) -> int:
    return int(str(d) + str(n))

# siguiente(xs) es la lista obtenida añadiendo delante de cada
# elemento de xs los dígitos 2, 3, 5 y 7. Por ejemplo,
#    >>> siguiente([5,6,8])
#    [25,26,28,
#     35,36,38,
#     55,56,58,
#     75,76,78]
def siguiente(xs: list[int]) -> list[int]:
    return [pega(d, x) for d in [2, 3, 5, 7] for x in xs]

def numerosConDigitosPrimos4() -> Iterator[int]:
    base = [2, 3, 5, 7]
    yield from base
    numeros = base
    while True:
        numeros = siguiente(numeros)
        yield from numeros


# numerosConDigitosPrimos4 :: [Integer]
# numerosConDigitosPrimos4 = concat (iterate siguiente [2,3,5,7])

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

def test_numerosConDigitosPrimos() -> None:
    for numerosConDigitosPrimos in [numerosConDigitosPrimos1,
                                    numerosConDigitosPrimos2,
                                    numerosConDigitosPrimos3,
                                    numerosConDigitosPrimos4]:
        assert list(islice(numerosConDigitosPrimos(), 22)) ==\
            [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223]
    print("Verificado")

# La verificación es
#    >>> test_numerosConDigitosPrimos()
#    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=100))
def test_numerosConDigitosPrimos_equiv(n: int) -> None:
    r = nth(numerosConDigitosPrimos1(), n)
    assert nth(numerosConDigitosPrimos2(), n) == r
    assert nth(numerosConDigitosPrimos3(), n) == r
    assert nth(numerosConDigitosPrimos4(), n) == r

# La comprobación es
#    >>> test_numerosConDigitosPrimos_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(numerosConDigitosPrimos1(), 5000)')
#    1.05 segundos
#    >>> tiempo('nth(numerosConDigitosPrimos2(), 5000)')
#    0.33 segundos
#    >>> tiempo('nth(numerosConDigitosPrimos3(), 5000)')
#    0.00 segundos
#    >>> tiempo('nth(numerosConDigitosPrimos4(), 5000)')
#    0.01 segundos
#
#    >>> tiempo('nth(numerosConDigitosPrimos3(), 10**7)')
#    2.67 segundos
#    >>> tiempo('nth(numerosConDigitosPrimos4(), 10**7)')
#    8.56 segundos