Menu Close

Números de Lychrel

Un número de Lychrel es un número para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel:

  • 56, ya que en un paso se obtiene un capicúa: 56+65=121.
  • 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363
  • 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111
  • 89, ya que en 24 pasos se obtiene un capicúa.

En esta serie de ejercicios vamos a buscar el primer número de Lychrel.

Ejercicio 1. Definir la función

   esCapicua :: Integer -> Bool

tal que esCapicua x se verifica si x es capicúa. Por ejemplo,

   esCapicua 252  ==  True
   esCapicua 253  ==  False

Ejercicio 2. Definir la función

   inverso :: Integer -> Integer

tal que inverso x es el número obtenido escribiendo las cifras de x en orden inverso. Por ejemplo,

   inverso 253  ==  352

Ejercicio 3. Definir la función

   siguiente :: Integer -> Integer

tal que siguiente x es el número obtenido sumándole a x su inverso. Por ejemplo,

   siguiente 253  ==  605

Ejercicio 4. Definir la función

   busquedaDeCapicua :: Integer -> [Integer]

tal que busquedaDeCapicua x es la lista de los números tal que el primero es x, el segundo es el siguiente de x y así sucesivamente hasta que se alcanza un capicúa. Por ejemplo,

   busquedaDeCapicua 253  ==  [253,605,1111]

Ejercicio 5. Definir la función

   capicuaFinal :: Integer -> Integer

tal que capicuaFinal x es la capicúa con la que termina la búsqueda de capicúa a partir de x. Por ejemplo,

   capicuaFinal 253  ==  1111

Ejercicio 6. Definir la función

   orden :: Integer -> Integer

tal que orden x es el número de veces que se repite el proceso de calcular el inverso a partir de x hasta alcanzar un número capicúa. Por ejemplo,

   orden 253  ==  2

Ejercicio 7. Definir la función

   ordenMayor :: Integer -> Integer -> Bool

tal que ordenMayor x n se verifica si el orden de x es mayor o igual que n. Dar la definición sin necesidad de evaluar el orden de x. Por ejemplo,

   λ> ordenMayor 1186060307891929990 2
   True
   λ> orden 1186060307891929990
   261

Ejercicio 8. Definir la función

   ordenEntre :: Integer -> Integer -> [Integer]

tal que ordenEntre m n es la lista de los elementos cuyo orden esmayor o igual que m y menor que n. Por ejemplo,

   take 5 (ordenEntre 10 11)  ==  [829,928,9059,9149,9239]

Ejercicio 9. Definir la función

   menorDeOrdenMayor :: Integer -> Integer

tal que menorDeOrdenMayor n es el menor elemento cuyo orden es mayor que n. Por ejemplo,

   menorDeOrdenMayor 2   ==  19
   menorDeOrdenMayor 20  ==  89

Ejercicio 10. Definir la función

   menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]

tal que menoresdDeOrdenMayor m es la lista de los pares (n,x) tales que n es un número entre 1 y m y x es el menor elemento de orden mayor que n. Por ejemplo,

   menoresdDeOrdenMayor 5  ==  [(1,10),(2,19),(3,59),(4,69),(5,79)]

Ejercicio 11. A la vista de los resultados de menoresdDeOrdenMayor 5 conjeturar sobre la última cifra de menorDeOrdenMayor.

Ejercicio 12. Decidir con QuickCheck la conjetura.

Ejercicio 13. Calcular menoresdDeOrdenMayor 50

Ejercicio 14. A la vista de menoresdDeOrdenMayor 50, conjeturar el orden de 196.

Ejercicio 15. Comprobar con QuickCheck la conjetura sobre el orden de 196.

Soluciones en Haskell
import Test.QuickCheck
 
-- Solución de ejercicio 1
esCapicua :: Integer -> Bool
esCapicua x = x' == reverse x'
  where x' = show x
 
-- Solución de ejercicio 2
inverso :: Integer -> Integer
inverso = read . reverse . show
 
-- Solución de ejercicio 3
siguiente :: Integer -> Integer
siguiente x = x + inverso x
 
-- Solución de ejercicio 4
busquedaDeCapicua :: Integer -> [Integer]
busquedaDeCapicua x | esCapicua x = [x]
                    | otherwise   = x : busquedaDeCapicua (siguiente x)
 
-- Solución de ejercicio 5
capicuaFinal :: Integer -> Integer
capicuaFinal x = last (busquedaDeCapicua x)
 
-- Solución de ejercicio 6
orden :: Integer -> Integer
orden x | esCapicua x = 0
        | otherwise   = 1 + orden (siguiente x)
 
-- Solución de ejercicio 7
ordenMayor :: Integer -> Integer -> Bool
ordenMayor x n | esCapicua x = n == 0
               | n <= 0      = True
               | otherwise   = ordenMayor (siguiente x) (n-1)
 
-- Solución de ejercicio 8
ordenEntre :: Integer -> Integer -> [Integer]
ordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)]
 
-- Solución de ejercicio 9
menorDeOrdenMayor :: Integer -> Integer
menorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n]
 
-- Solución de ejercicio 10
menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]
menoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]]
 
-- Solución de ejercicio 11
-- La conjetura es que para n mayor que 1, la última cifra de
-- (menorDeOrdenMayor n) es 9.
 
-- Solución de ejercicio 12
-- ========================
 
-- La conjetura es
prop_menorDeOrdenMayor :: Integer -> Property
prop_menorDeOrdenMayor n =
  n > 1 ==> menorDeOrdenMayor n `mod` 10 == 9
 
-- La comprobación es
--    λ> quickCheck prop_menorDeOrdenMayor
--    *** Failed! Falsifiable (after 22 tests and 2 shrinks):
--    25
 
-- Se puede comprobar que 25 es un contraejemplo,
--    λ> menorDeOrdenMayor 25
--    196
 
-- Solución de ejercicio 13
-- El cálculo es
--    λ> menoresdDeOrdenMayor 50
--    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),
--     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),
--     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),
--     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),
--     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),
--     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),
--     (47,196),(48,196),(49,196),(50,196)]
 
-- Solución de ejercicio 14
-- La conjetura es que el orden de 196 es infinito y, por tanto,
-- 196 es un número del Lychrel.
 
-- Solución de ejercicio 15
-- ========================
 
-- La propiedad es
prop_ordenDe196 :: Integer -> Bool
prop_ordenDe196 n =
  ordenMayor 196 n
 
-- La comprobación es
--    λ> quickCheck prop_ordenDe196
--    +++ OK, passed 100 tests.
Soluciones en Python
from itertools import islice
from sys import setrecursionlimit
from typing import Generator, Iterator
 
from hypothesis import given, settings
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
# Solución del ejercicio 1
def esCapicua(x: int) -> bool:
    return x == int(str(x)[::-1])
 
# Solución del ejercicio 2
def inverso(x: int) -> int:
    return int(str(x)[::-1])
 
# Solución del ejercicio 3
def siguiente(x: int) -> int:
    return x + inverso(x)
 
# Solución del ejercicio 4
def busquedaDeCapicua(x: int) -> list[int]:
    if esCapicua(x):
        return [x]
    return [x] + busquedaDeCapicua(siguiente(x))
 
# Solución del ejercicio 5
def capicuaFinal(x: int) -> int:
    return busquedaDeCapicua(x)[-1]
 
# Solución del ejercicio 6
def orden(x: int) -> int:
    if esCapicua(x):
        return 0
    return 1 + orden(siguiente(x))
 
# Solución del ejercicio 7
def ordenMayor(x: int, n: int) -> bool:
    if esCapicua(x):
        return n == 0
    if n <= 0:
        return True
    return ordenMayor(siguiente(x), n - 1)
 
# Solución del ejercicio 8
# ========================
 
# naturales es el generador de los números naturales positivos, Por
# ejemplo,
#    >>> list(islice(naturales(), 5))
#    [1, 2, 3, 4, 5]
def naturales() -> Iterator[int]:
    i = 1
    while True:
        yield i
        i += 1
 
def ordenEntre(m: int, n: int) -> Generator[int, None, None]:
    return (x for x in naturales()
            if ordenMayor(x, m) and not ordenMayor(x, n))
 
# Solución del ejercicio 9
def menorDeOrdenMayor(n: int) -> int:
    return list(islice((x for x in naturales() if ordenMayor(x, n)), 1))[0]
 
# Solución del ejercicio 10
def menoresdDeOrdenMayor(m: int) -> list[tuple[int, int]]:
    return [(n, menorDeOrdenMayor(n)) for n in range(1, m + 1)]
 
# Solución del ejercicio 11
# La conjetura es que para n mayor que 1, la última cifra de
# menorDeOrdenMayor(n) es 9.
 
# Solución del ejercicio 12
# =========================
 
# La conjetura es
# @given(st.integers(min_value=2, max_value=200))
# def test_menorDeOrdenMayor(n: int) -> None:
#     assert menorDeOrdenMayor(n) % 10 == 9
 
# La comprobación es
#    src> poetry run pytest -q numeros_de_Lychrel.py
#    E       assert (196 % 10) == 9
#    E        +  where 196 = menorDeOrdenMayor(25)
#    E       Falsifying example: test_menorDeOrdenMayor(
#    E           n=25,
#    E       )
 
# Se puede comprobar que 25 es un contraejemplo,
#    >>> menorDeOrdenMayor(25)
#    196
 
# Solución del ejercicio 13
# El cálculo es
#    λ> menoresdDeOrdenMayor 50
#    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),
#     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),
#     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),
#     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),
#     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),
#     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),
#     (47,196),(48,196),(49,196),(50,196)]
 
# Solución del ejercicio 14
# El orden de 196 es infinito y, por tanto, 196 es un número
# de Lychrel.
 
 
# Solución del ejercicio 15
# =========================
 
# La propiedad es
@settings(deadline=None)
@given(st.integers(min_value=2, max_value=5000))
def test_ordenDe196(n: int) -> None:
    assert ordenMayor(196, n)
 
# La comprobación es
#    src> poetry run pytest -q numeros_de_Lychrel.py
#    1 passed in 7.74s

El algoritmo de Luhn

El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores numéricos como los números de algunas tarjetas de crédito; por ejemplo, las de tipo Visa o Master Card.

El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente en aplicar los siguientes pasos a los dígitos del número de la tarjeta.

  1. Se invierten los dígitos del número; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].
  2. Se duplican los dígitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].
  3. Se suman los dígitos de cada número; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.
  4. Si el último dígito de la suma es 0, el número es válido; y no lo es, en caso contrario.

A los números válidos, se les llama números de Luhn.

Definir las siguientes funciones:

   digitosInv    :: Integer -> [Integer]
   doblePosImpar :: [Integer] -> [Integer]
   sumaDigitos   :: [Integer] -> Integer
   ultimoDigito  :: Integer -> Integer
   luhn          :: Integer -> Bool

tales que

  • digitosInv n es la lista de los dígitos del número n, en orden inverso. Por ejemplo,
     digitosInv 320274  ==  [4,7,2,0,2,3]
  • doblePosImpar ns es la lista obtenida doblando los elementos de ns en las posiciones impares (empezando a contar en cero y dejando igual a los que están en posiciones pares. Por ejemplo,
     doblePosImpar [4,9,5,5]    ==  [4,18,5,10]
     doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]
  • sumaDigitos ns es la suma de los dígitos de ns. Por ejemplo,
     sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =
                             = 19
  • ultimoDigito n es el último dígito de n. Por ejemplo,
     ultimoDigito 123 == 3
     ultimoDigito   0 == 0
  • luhn n se verifica si n es un número de Luhn. Por ejemplo,
     luhn 5594589764218858  ==  True
     luhn 1234567898765432  ==  False
Soluciones en Haskell
-- Definición de digitosInv
-- ========================
 
digitosInv :: Integer -> [Integer]
digitosInv n = [read [x] | x <- reverse (show n)]
 
-- Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
-- se presentan otras definiciones.
 
-- Definiciones de doblePosImpar
-- =============================
 
-- 1ª definición
doblePosImpar :: [Integer] -> [Integer]
doblePosImpar []       = []
doblePosImpar [x]      = [x]
doblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs
 
-- 2ª definición
doblePosImpar2 :: [Integer] -> [Integer]
doblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs
doblePosImpar2 xs       = xs
 
-- 3ª definición
doblePosImpar3 :: [Integer] -> [Integer]
doblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]
  where f n x | odd n     = 2*x
              | otherwise = x
 
-- Definiciones de sumaDigitos
-- ===========================
 
sumaDigitos :: [Integer] -> Integer
sumaDigitos ns = sum [sum (digitosInv n) | n <- ns]
 
-- Nota: En el ejercicio "Suma de los dígitos de un número"
-- https://bit.ly/3U4u7WR se presentan otras definiciones.
 
-- Definición de ultimoDigito
-- ==========================
 
ultimoDigito :: Integer -> Integer
ultimoDigito n = n `rem` 10
 
-- Definiciones de luhn
-- ====================
 
-- 1ª definición
luhn1 :: Integer -> Bool
luhn1 n =
  ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0
 
-- 2ª definición
luhn2 :: Integer -> Bool
luhn2 =
  (==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv
Soluciones en Python
# Definición de digitosInv
# ========================
 
def digitosInv(n: int) -> list[int]:
    return [int(x) for x in reversed(str(n))]
 
# Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
# se presentan otras definiciones.
 
# Definiciones de doblePosImpar
# =============================
 
# 1ª definición
def doblePosImpar(xs: list[int]) -> list[int]:
    if len(xs) <= 1:
        return xs
    return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:])
 
# 2ª definición
def doblePosImpar2(xs: list[int]) -> list[int]:
    def f(n: int, x: int) -> int:
        if n % 2 == 1:
            return 2 * x
        return x
    return [f(n, x) for (n, x) in enumerate(xs)]
 
# Definiciones de sumaDigitos
# ===========================
 
def sumaDigitos(ns: list[int]) -> int:
    return sum((sum(digitosInv(n)) for n in ns))
 
# Nota: En el ejercicio "Suma de los dígitos de un número"
# https://bit.ly/3U4u7WR se presentan otras definiciones.
 
# Definición de ultimoDigito
# ==========================
 
def ultimoDigito(n: int) -> int:
    return n % 10
 
# Definiciones de luhn
# ====================
 
def luhn(n: int) -> bool:
    return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0

Subconjuntos de un conjunto

Definir la función

   subconjuntos :: [a] -> [[a]]

tal que subconjuntos xs es la lista de las subconjuntos de la lista xs. Por ejemplo,

   λ> subconjuntos [2,3,4]
   [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
   λ> subconjuntos [1,2,3,4]
   [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],
      [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]

Comprobar con QuickChek que el número de elementos de subconjuntos xs es 2 elevado al número de elementos de xs.

Soluciones en Haskell
import Data.List (sort, subsequences)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
subconjuntos1 :: [a] -> [[a]]
subconjuntos1 []     = [[]]
subconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub
  where sub = subconjuntos1 xs
 
-- 2ª solución
-- ===========
 
subconjuntos2 :: [a] -> [[a]]
subconjuntos2 []     = [[]]
subconjuntos2 (x:xs) = map (x:) sub ++ sub
  where sub = subconjuntos2 xs
 
-- 3ª solución
-- ===========
 
subconjuntos3 :: [a] -> [[a]]
subconjuntos3 = subsequences
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_subconjuntos :: [Int] -> Bool
prop_subconjuntos xs =
  all (== sort (subconjuntos1 xs))
      [sort (subconjuntos2 xs),
       sort (subconjuntos3 xs)]
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (subconjuntos1 [1..23])
--    8388608
--    (2.05 secs, 1,476,991,840 bytes)
--    λ> length (subconjuntos2 [1..23])
--    8388608
--    (0.87 secs, 1,208,555,312 bytes)
--    λ> length (subconjuntos3 [1..23])
--    8388608
--    (0.09 secs, 873,006,608 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_length_subconjuntos :: [Int] -> Bool
prop_length_subconjuntos xs =
  length (subconjuntos1 xs) == 2 ^ length xs
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos
--    +++ OK, passed 100 tests.
Soluciones en Python
from itertools import combinations
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
from sympy import FiniteSet
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def subconjuntos1(xs: list[A]) -> list[list[A]]:
    if xs:
        sub = subconjuntos1(xs[1:])
        return [[xs[0]] + ys for ys in sub] + sub
    return [[]]
 
# 2ª solución
# ===========
 
def subconjuntos2(xs: list[A]) -> list[list[A]]:
    if xs:
        sub = subconjuntos1(xs[1:])
        return list(map((lambda ys: [xs[0]] + ys), sub)) + sub
    return [[]]
 
# 3ª solución
# ===========
 
def subconjuntos3(xs: list[A]) -> list[list[A]]:
    c = FiniteSet(*xs)
    return list(map(list, c.powerset()))
 
# 4ª solución
# ===========
 
def subconjuntos4(xs: list[A]) -> list[list[A]]:
    return [list(ys)
            for r in range(len(xs)+1)
            for ys in combinations(xs, r)]
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.integers(), max_size=5))
def test_subconjuntos(xs: list[int]) -> None:
    ys = list(set(xs))
    r = sorted([sorted(zs) for zs in subconjuntos1(ys)])
    assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r
    assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r
    assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r
 
# La comprobación es
#    src> poetry run pytest -q subconjuntos_de_un_conjunto.py
#    1 passed in 0.89s
 
# 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('subconjuntos1(range(14))')
#    0.00 segundos
#    >>> tiempo('subconjuntos2(range(14))')
#    0.00 segundos
#    >>> tiempo('subconjuntos3(range(14))')
#    6.01 segundos
#    >>> tiempo('subconjuntos4(range(14))')
#    0.00 segundos
#
#    >>> tiempo('subconjuntos1(range(23))')
#    1.95 segundos
#    >>> tiempo('subconjuntos2(range(23))')
#    2.27 segundos
#    >>> tiempo('subconjuntos4(range(23))')
#    1.62 segundos
 
# Comprobación de la propiedad
# ============================
 
# La propiedad es
@given(st.lists(st.integers(), max_size=7))
def test_length_subconjuntos(xs: list[int]) -> None:
    assert len(subconjuntos1(xs)) == 2 ** len(xs)
 
# La comprobación es
#    src> poetry run pytest -q subconjuntos_de_un_conjunto.py
#    2 passed in 0.95s

Producto cartesiano de dos conjuntos

Definir la función

   producto :: [a] -> [b] -> [(a,b)]

tal que producto xs ys es el producto cartesiano de xs e ys. Por ejemplo,

   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

Comprobar con QuickCheck que el número de elementos de producto xs y es el producto del número de elementos de xs y de ys.

Soluciones en Haskell
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
producto1 :: [a] -> [a] -> [(a,a)]
producto1 xs ys = [(x,y) | x <- xs, y <- ys]
 
-- 2ª solución
-- ===========
 
producto2 :: [a] -> [a] -> [(a,a)]
producto2 []     _  = []
producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_producto :: [Int] -> [Int] -> Bool
prop_producto xs ys =
  producto1 xs ys `iguales` producto2 xs ys
 
-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,
--    iguales [3,2,3] [2,3]    ==  True
--    iguales [3,2,3] [2,3,2]  ==  True
--    iguales [3,2,3] [2,3,4]  ==  False
--    iguales [2,3] [4,5]      ==  False
iguales :: Ord a => [a] -> [a] -> Bool
iguales xs ys =
  subconjunto xs ys && subconjunto ys xs
 
-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por
-- ejemplo,
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto xs ys =
  [x | x <- xs, x `elem` ys] == xs
 
-- La comprobación es
--    λ> quickCheck prop_producto
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (producto1 [1..4000] [1..4000])
--    16000000
--    (2.33 secs, 1,537,551,208 bytes)
--    λ> length (producto2 [1..4000] [1..4000])
--    16000000
--    (2.87 secs, 2,434,095,160 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_elementos_producto :: [Int] -> [Int] -> Bool
prop_elementos_producto xs ys =
  length (producto1 xs ys) == length xs * length ys
 
-- La comprobación es
--    λ> quickCheck prop_elementos_producto
--    +++ OK, passed 100 tests.

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Producto_cartesiano_de_dos_conjuntos.hs).

Soluciones en Python
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
B = TypeVar('B')
 
# 1ª solución
# ===========
 
def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    return [(x, y) for x in xs for y in ys]
 
# 2ª solución
# ===========
 
def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    if xs:
        return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)
    return []
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_producto(xs: list[int], ys: list[int]) -> None:
    assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))
 
# La comprobación es
#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py
#    1 passed in 0.31s
 
# 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('len(producto1(range(0, 1000), range(0, 500)))')
#    0.03 segundos
#    >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')
#    2.58 segundos
 
# Comprobación de la propiedad
# ============================
 
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_elementos_producto(xs: list[int], ys: list[int]) -> None:
    assert len(producto1(xs, ys)) == len(xs) * len(ys)
 
# La comprobación es
#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py
#    2 passed in 0.48s

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/producto_cartesiano_de_dos_conjuntos.py).

Exponente de la mayor potencia de x que divide a y

Definir la función

   mayorExponente :: Integer -> Integer -> Integer

tal que mayorExponente a b es el exponente de la mayor potencia de a que divide a b. Por ejemplo,

   mayorExponente 2 8    ==  3
   mayorExponente 2 9    ==  0
   mayorExponente 5 100  ==  2
   mayorExponente 2 60   ==  2

Nota: Se supone que a > 1 y b > 0.

Soluciones en Haskell
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
mayorExponente1 :: Integer -> Integer -> Integer
mayorExponente1 a b
  | rem b a /= 0 = 0
  | otherwise    = 1 + mayorExponente1 a (b `div` a)
 
-- 2ª solución
-- ===========
 
mayorExponente2 :: Integer -> Integer -> Integer
mayorExponente2 a b = aux b 0
  where
    aux c r | rem c a /= 0 = r
            | otherwise    = aux (c `div` a) (r + 1)
 
-- 3ª solución
-- ===========
 
mayorExponente3 :: Integer -> Integer -> Integer
mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]
 
-- 4ª solución
-- ===========
 
mayorExponente4 :: Integer -> Integer -> Integer
mayorExponente4 a b =
  fst (until (\ (_,c) -> rem c a /= 0)
             (\ (r,c) -> (r+1, c `div` a))
             (0,b))
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_mayorExponente :: Integer -> Integer -> Property
prop_mayorExponente a b =
  a > 1 && b > 0 ==>
  all (== mayorExponente1 a b)
      [mayorExponente2 a b,
       mayorExponente3 a b,
       mayorExponente4 a b]
 
-- La comprobación es
--    λ> quickCheck prop_mayorExponente
--    +++ OK, passed 100 tests; 457 discarded.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> mayorExponente1 2 (2^(5*10^4))
--    50000
--    (0.12 secs, 179,578,424 bytes)
--    λ> mayorExponente2 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,533,376 bytes)
--    λ> mayorExponente3 2 (2^(5*10^4))
--    50000
--    (3.88 secs, 818,319,096 bytes)
--    λ> mayorExponente4 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,133,344 bytes)
--
--    λ> mayorExponente1 2 (2^(3*10^5))
--    300000
--    (2.94 secs, 5,762,199,064 bytes)
--    λ> mayorExponente2 2 (2^(3*10^5))
--    300000
--    (2.91 secs, 5,773,829,624 bytes)
--    λ> mayorExponente4 2 (2^(3*10^5))
--    300000
--    (3.70 secs, 5,771,396,824 bytes)

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Exponente_mayor.hs).

Soluciones en Python
from itertools import islice
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Iterator
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def mayorExponente1(a: int, b: int) -> int:
    if b % a != 0:
        return 0
    return 1 + mayorExponente1(a, b // a)
 
# 2ª solución
# ===========
 
def mayorExponente2(a: int, b: int) -> int:
    def aux(c: int, r: int) -> int:
        if c % a != 0:
            return r
        return aux(c // a, r + 1)
    return aux(b, 0)
 
# 3ª solución
# ===========
 
# naturales es el generador de los números naturales, Por ejemplo,
#    >>> list(islice(naturales(), 5))
#    [0, 1, 2, 3, 4]
def naturales() -> Iterator[int]:
    i = 0
    while True:
        yield i
        i += 1
 
def mayorExponente3(a: int, b: int) -> int:
    return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]
 
# 4ª solución
# ===========
 
def mayorExponente4(a: int, b: int) -> int:
    r = 0
    while b % a == 0:
        b = b // a
        r = r + 1
    return r
 
# Comprobación de equivalencia
# ============================
 
def prueba1() -> None:
    for x in range(2, 11):
        for y in range(1, 11):
            print(x, y, mayorExponente4(x, y))
 
 
# La propiedad es
@given(st.integers(min_value=2, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_mayorExponente(a: int, b: int) -> None:
    r = mayorExponente1(a, b)
    assert mayorExponente2(a, b) == r
    assert mayorExponente3(a, b) == r
    assert mayorExponente4(a, b) == r
 
# La comprobación es
#    src> poetry run pytest -q exponente_mayor.py
#    1 passed in 0.16s
 
# 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('mayorExponente1(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente2(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente3(2, 2**(2*10**4))')
#    1.81 segundos
#    >>> tiempo('mayorExponente4(2, 2**(2*10**4))')
#    0.12 segundos
#
#    >>> tiempo('mayorExponente4(2, 2**(2*10**5))')
#    12.19 segundos

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/exponente_mayor.py).

Número a partir de sus dígitos

Definir la función

   listaNumero :: [Integer] -> Integer

tal que listaNumero xs es el número formado por los dígitos xs. Por ejemplo,

   listaNumero [5]        == 5
   listaNumero [1,3,4,7]  == 1347
   listaNumero [0,0,1]    == 1
Soluciones en Haskell
import Data.List (foldl')
import Data.Digits (unDigits)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
listaNumero1 :: [Integer] -> Integer
listaNumero1 = aux . reverse
  where
    aux :: [Integer] -> Integer
    aux []     = 0
    aux (x:xs) = x + 10 * aux xs
 
-- 2ª solución
-- ===========
 
listaNumero2 :: [Integer] -> Integer
listaNumero2 = aux 0
  where
    aux :: Integer -> [Integer] -> Integer
    aux r []     = r
    aux r (x:xs) = aux (x+10*r) xs
 
-- 3ª solución
-- ===========
 
listaNumero3 :: [Integer] -> Integer
listaNumero3 = aux 0
  where
    aux :: Integer -> [Integer] -> Integer
    aux = foldl (\ r x -> x + 10 * r)
 
-- 4ª solución
-- ===========
 
listaNumero4 :: [Integer] -> Integer
listaNumero4 = foldl' (\ r x -> x + 10 * r) 0
 
-- 5ª solución
-- ===========
 
listaNumero5 :: [Integer] -> Integer
listaNumero5 xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]
 
-- 6ª solución
-- ===========
 
listaNumero6 :: [Integer] -> Integer
listaNumero6 xs = sum (zipWith (\ y n -> y*10^n) (reverse xs) [0..])
 
-- 7ª solución
-- ===========
 
listaNumero7 :: [Integer] -> Integer
listaNumero7 = unDigits 10
 
-- 7ª solución
-- ===========
 
listaNumero8 :: [Integer] -> Integer
listaNumero8 = read . concatMap show
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_listaNumero :: NonEmptyList Integer -> Bool
prop_listaNumero (NonEmpty xs) =
  all (== listaNumero1 ys)
      [listaNumero2 ys,
       listaNumero3 ys,
       listaNumero4 ys,
       listaNumero5 ys,
       listaNumero6 ys,
       listaNumero7 ys,
       listaNumero8 ys]
  where ys = map (`mod` 10) xs
 
-- La comprobación es
--    λ> quickCheck prop_listaNumero
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (show (listaNumero1 (replicate (10^5) 9)))
--    100000
--    (4.01 secs, 4,309,740,064 bytes)
--    λ> length (show (listaNumero2 (replicate (10^5) 9)))
--    100000
--    (4.04 secs, 4,307,268,856 bytes)
--    λ> length (show (listaNumero3 (replicate (10^5) 9)))
--    100000
--    (4.08 secs, 4,300,868,816 bytes)
--    λ> length (show (listaNumero4 (replicate (10^5) 9)))
--    100000
--    (0.42 secs, 4,288,480,208 bytes)
--    λ> length (show (listaNumero4 (replicate (10^5) 9)))
--    100000
--    (0.41 secs, 4,288,480,208 bytes)
--    λ> length (show (listaNumero5 (replicate (10^5) 9)))
--    100000
--    (43.35 secs, 10,702,827,328 bytes)
--    λ> length (show (listaNumero6 (replicate (10^5) 9)))
--    100000
--    (46.89 secs, 10,693,227,280 bytes)
--    λ> length (show (listaNumero7 (replicate (10^5) 9)))
--    100000
--    (4.33 secs, 4,297,499,344 bytes)
--    λ> length (show (listaNumero8 (replicate (10^5) 9)))
--    100000
--    (0.03 secs, 60,760,360 bytes)

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Numero_a_partir_de_sus_digitos.hs).

Soluciones en Python
from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def listaNumero1(xs: list[int]) -> int:
    def aux(ys: list[int]) -> int:
        if ys:
            return ys[0] + 10 * aux(ys[1:])
        return 0
    return aux(list(reversed(xs)))
 
# 2ª solución
# ===========
 
def listaNumero2(xs: list[int]) -> int:
    def aux(r: int, ys: list[int]) -> int:
        if ys:
            return aux(ys[0] + 10 * r, ys[1:])
        return r
    return aux(0, xs)
 
# 3ª solución
# ===========
 
def listaNumero3(xs: list[int]) -> int:
    return reduce((lambda r, x: x + 10 * r), xs)
 
# 4ª solución
# ===========
 
def listaNumero4(xs: list[int]) -> int:
    r = 0
    for x in xs:
        r = x + 10 * r
    return r
 
# 5ª solución
# ===========
 
def listaNumero5(xs: list[int]) -> int:
    return sum((y * 10**n
                for (y, n) in zip(list(reversed(xs)), range(0, len(xs)))))
 
# 6ª solución
# ===========
 
def listaNumero6(xs: list[int]) -> int:
    return int("".join(list(map(str, xs))))
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.integers(min_value=0, max_value=9), min_size=1))
def test_listaNumero(xs: list[int]) -> None:
    r = listaNumero1(xs)
    assert listaNumero2(xs) == r
    assert listaNumero3(xs) == r
    assert listaNumero4(xs) == r
    assert listaNumero5(xs) == r
    assert listaNumero6(xs) == r
 
# La comprobación es
#    src> poetry run pytest -q numero_a_partir_de_sus_digitos.py
#    1 passed in 0.27s
 
# 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('listaNumero1([9]*(10**4))')
#    0.28 segundos
#    >>> tiempo('listaNumero2([9]*(10**4))')
#    0.16 segundos
#    >>> tiempo('listaNumero3([9]*(10**4))')
#    0.01 segundos
#    >>> tiempo('listaNumero4([9]*(10**4))')
#    0.01 segundos
#    >>> tiempo('listaNumero5([9]*(10**4))')
#    0.41 segundos
#    >>> tiempo('listaNumero6([9]*(10**4))')
#    0.00 segundos
#
#    >>> tiempo('listaNumero3([9]*(2*10**5))')
#    3.45 segundos
#    >>> tiempo('listaNumero4([9]*(2*10**5))')
#    3.29 segundos
#    >>> tiempo('listaNumero6([9]*(2*10**5))')
#    0.19 segundos

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/numero_a_partir_de_sus_digitos.py).

Suma de los dígitos de un número

Definir la función

   sumaDigitos :: Integer -> Integer

tal que sumaDigitos n es la suma de los dígitos de n. Por ejemplo,

   sumaDigitos 3     ==  3
   sumaDigitos 2454  == 15
   sumaDigitos 20045 == 11
Soluciones en Haskell
import Data.List (foldl')
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaDigitos1 :: Integer -> Integer
sumaDigitos1 n = sum (digitos n)
 
-- (digitos n) es la lista de los dígitos del número n. Por ejemplo,
--    digitos 320274  ==  [3,2,0,2,7,4]
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]
 
-- Nota. En lugar de la definición anterior de digitos se puede usar
-- cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
 
-- 2ª solución
-- ===========
 
sumaDigitos2 :: Integer -> Integer
sumaDigitos2 n = foldl' (+) 0 (digitos n)
 
-- 3ª solución
-- ===========
 
sumaDigitos3 :: Integer -> Integer
sumaDigitos3 n
  | n < 10    = n
  | otherwise = n `rem` 10 + sumaDigitos3 (n `div` 10)
 
-- 4ª solución
-- ===========
 
sumaDigitos4 :: Integer -> Integer
sumaDigitos4 = aux 0
  where aux r n
          | n < 10    = r + n
          | otherwise = aux (r + n `rem` 10) (n `div` 10)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_sumaDigitos :: NonNegative Integer -> Bool
prop_sumaDigitos (NonNegative n) =
  all (== sumaDigitos1 n)
      [sumaDigitos2 n,
       sumaDigitos3 n,
       sumaDigitos4 n]
 
-- La comprobación es
--    λ> quickCheck prop_sumaDigitos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sumaDigitos1 (product [1..2*10^4])
--    325494
--    (0.64 secs, 665,965,832 bytes)
--    λ> sumaDigitos2 (product [1..2*10^4])
--    325494
--    (0.41 secs, 660,579,064 bytes)
--    λ> sumaDigitos3 (product [1..2*10^4])
--    325494
--    (1.58 secs, 1,647,082,224 bytes)
--    λ> sumaDigitos4 (product [1..2*10^4])
--    325494
--    (1.72 secs, 1,662,177,792 bytes)
--
--    λ> sumaDigitos1 (product [1..5*10^4])
--    903555
--    (2.51 secs, 3,411,722,136 bytes)
--    λ> sumaDigitos2 (product [1..5*10^4])
--    903555
--    (2.30 secs, 3,396,802,856 bytes)

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Suma_de_los_digitos_de_un_numero.hs).

Soluciones en Python
from functools import reduce
from math import factorial
from operator import add
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
# digitos(n) es la lista de los dígitos del número n. Por ejemplo,
#    digitos(320274)  ==  [3, 2, 0, 2, 7, 4]
def digitos(n: int) -> list[int]:
    return list(map(int, list(str(n))))
 
def sumaDigitos1(n: int) -> int:
    return sum(digitos(n))
 
# Nota. En lugar de la definición anterior de digitos se puede usar
# cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
 
# 2ª solución
# ===========
 
def sumaDigitos2(n: int) -> int:
    return reduce(add, digitos(n))
 
# 3ª solución
# ===========
 
def sumaDigitos3(n: int) -> int:
    if n < 10:
        return n
    return n % 10 + sumaDigitos3(n // 10)
 
# 4ª solución
# ===========
 
def sumaDigitos4(n: int) -> int:
    def aux(r: int, m: int) -> int:
        if m < 10:
            return r + m
        return aux(r + m % 10, m // 10)
    return aux(0, n)
 
# 5ª solución
# ===========
 
def sumaDigitos5(n: int) -> int:
    r = 0
    for x in digitos(n):
        r = r + x
    return r
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=1000))
def test_sumaDigitos(n: int) -> None:
    r = sumaDigitos1(n)
    assert sumaDigitos2(n) == r
    assert sumaDigitos3(n) == r
    assert sumaDigitos4(n) == r
    assert sumaDigitos5(n) == r
 
# La comprobación es
#    src> poetry run pytest -q suma_de_los_digitos_de_un_numero.py
#    1 passed in 0.35s
 
# 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('sumaDigitos1(factorial(6*10**3))')
#    0.01 segundos
#    >>> tiempo('sumaDigitos2(factorial(6*10**3))')
#    0.01 segundos
#    >>> tiempo('sumaDigitos3(factorial(6*10**3))')
#    0.13 segundos
#    >>> tiempo('sumaDigitos4(factorial(6*10**3))')
#    0.13 segundos
#    >>> tiempo('sumaDigitos5(factorial(6*10**3))')
#    0.01 segundos
#
#    >>> tiempo('sumaDigitos1(factorial(10**5))')
#    2.20 segundos
#    >>> tiempo('sumaDigitos2(factorial(10**5))')
#    2.22 segundos
#    >>> tiempo('sumaDigitos5(factorial(10**5))')
#    2.19 segundos

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/suma_de_los_digitos_de_un_numero.py)

Dígitos de un número

Definir la función

   digitos :: Integer -> [Int]

tal que digitos n es la lista de los dígitos del número n. Por ejemplo,

   digitos 320274  ==  [3,2,0,2,7,4]
Soluciones en Haskell
import Data.Char (digitToInt)
import qualified Data.Digits as D (digits)
import qualified Data.FastDigits as FD (digits)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
digitos1 :: Integer -> [Int]
digitos1 n = map fromInteger (aux n)
  where aux :: Integer -> [Integer]
        aux m
          | m < 10    = [m]
          | otherwise = aux (m `div` 10) ++ [m `rem` 10]
 
-- 2ª solución
-- ===========
 
digitos2 :: Integer -> [Int]
digitos2 n = map fromInteger (reverse (aux n))
  where aux :: Integer -> [Integer]
        aux m
          | m < 10    = [m]
          | otherwise = (m `rem` 10) : aux (m `div` 10)
 
-- 3ª solución
-- ===========
 
digitos3 :: Integer -> [Int]
digitos3 n = map fromInteger (aux [] n)
  where aux :: [Integer] -> Integer -> [Integer]
        aux ds m
          | m < 10    = m : ds
          | otherwise = aux (m `rem` 10 : ds) (m `div` 10)
 
-- 4ª solución
-- ===========
 
digitos4 :: Integer -> [Int]
digitos4 n = [read [x] | x <- show n]
 
-- 5ª solución
-- ===========
 
digitos5 :: Integer -> [Int]
digitos5 n = map (\ x -> read [x]) (show n)
 
-- 6ª solución
-- ===========
 
digitos6 :: Integer -> [Int]
digitos6 = map (read . return) . show
 
-- 7ª solución
-- ===========
 
digitos7 :: Integer -> [Int]
digitos7 n = map digitToInt (show n)
 
-- 8ª solución
-- ===========
 
digitos8 :: Integer -> [Int]
digitos8 = map digitToInt . show
 
-- 9ª solución
-- ===========
 
digitos9 :: Integer -> [Int]
digitos9 0 = [0]
digitos9 n = map fromInteger (D.digits 10 n)
 
-- 10ª solución
-- ===========
 
digitos10 :: Integer -> [Int]
digitos10 0 = [0]
digitos10 n = reverse (FD.digits 10 n)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_digitos :: NonNegative Integer -> Bool
prop_digitos (NonNegative n) =
  all (== digitos1 n)
      [digitos2 n,
       digitos3 n,
       digitos4 n,
       digitos5 n,
       digitos6 n,
       digitos7 n,
       digitos8 n,
       digitos9 n,
       digitos10 n]
 
-- La comprobación es
--    λ> quickCheck prop_digitos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> n = product [1..5000]
--    λ> length (digitos1 n)
--    16326
--    (3.00 secs, 11,701,450,912 bytes)
--    λ> length (digitos2 n)
--    16326
--    (0.13 secs, 83,393,816 bytes)
--    λ> length (digitos3 n)
--    16326
--    (0.11 secs, 83,132,552 bytes)
--    λ> length (digitos4 n)
--    16326
--    (0.01 secs, 23,054,920 bytes)
--    λ> length (digitos5 n)
--    16326
--    (0.01 secs, 22,663,088 bytes)
--    λ> length (digitos6 n)
--    16326
--    (0.06 secs, 22,663,224 bytes)
--    λ> length (digitos7 n)
--    16326
--    (0.01 secs, 22,663,064 bytes)
--    λ> length (digitos8 n)
--    16326
--    (0.03 secs, 22,663,192 bytes)
--    λ> length (digitos9 n)
--    16326
--    (0.05 secs, 82,609,944 bytes)
--    λ> length (digitos10 n)
--    16326
--    (0.01 secs, 26,295,416 bytes)
--
--    λ> n = product [1..5*10^4]
--    λ> length (digitos2 n)
--    213237
--    (10.17 secs, 12,143,633,056 bytes)
--    λ> length (digitos3 n)
--    213237
--    (10.54 secs, 12,140,221,216 bytes)
--    λ> length (digitos4 n)
--    213237
--    (1.29 secs, 2,638,199,328 bytes)
--    λ> length (digitos5 n)
--    213237
--    (2.48 secs, 2,633,081,632 bytes)
--    λ> length (digitos6 n)
--    213237
--    (2.59 secs, 2,633,081,600 bytes)
--    λ> length (digitos7 n)
--    213237
--    (2.55 secs, 2,633,081,608 bytes)
--    λ> length (digitos8 n)
--    213237
--    (2.49 secs, 2,633,081,600 bytes)
--    λ> length (digitos9 n)
--    213237
--    (7.07 secs, 12,133,397,456 bytes)
--    λ> length (digitos10 n)
--    213237
--    (2.47 secs, 2,725,182,064 bytes)

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Digitos_de_un_numero.hs).

Soluciones en Python
from math import factorial
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
from sympy.ntheory.digits import digits
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def digitos1(n: int) -> list[int]:
    if n < 10:
        return [n]
    return digitos1(n // 10) + [n % 10]
 
# 2ª solución
# ===========
 
def digitos2(n: int) -> list[int]:
    return [int(x) for x in str(n)]
 
# 3ª solución
# ===========
 
def digitos3(n: int) -> list[int]:
    r: list[int] = []
    for x in str(n):
        r.append(int(x))
    return r
 
# 4ª solución
# ===========
 
def digitos4(n: int) -> list[int]:
    return list(map(int, list(str(n))))
 
# 5ª solución
# ===========
 
def digitos5(n: int) -> list[int]:
    r: list[int] = []
    while n > 0:
        r = [n % 10] + r
        n = n // 10
    return r
 
# 6ª solución
# ===========
 
def digitos6(n: int) -> list[int]:
    r: list[int] = []
    while n > 0:
        r.append(n % 10)
        n = n // 10
    return list(reversed(r))
 
# 7ª solución
# ===========
 
def digitos7(n: int) -> list[int]:
    return digits(n)[1:]
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=1))
def test_digitos(n: int) -> None:
    r = digitos1(n)
    assert digitos2(n) == r
    assert digitos3(n) == r
    assert digitos4(n) == r
    assert digitos5(n) == r
    assert digitos6(n) == r
    assert digitos7(n) == r
 
# La comprobación es
#    src> poetry run pytest -q digitos_de_un_numero.py
#    1 passed in 0.49s
 
# Comparación de eficiencia
# =========================
 
def tiempo(ex: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(ex, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('digitos1(factorial(6000))')
#    0.58 segundos
#    >>> tiempo('digitos2(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos3(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos4(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos5(factorial(6000))')
#    0.60 segundos
#    >>> tiempo('digitos6(factorial(6000))')
#    0.17 segundos
#    >>> tiempo('digitos7(factorial(6000))')
#    0.10 segundos
#
#    >>> tiempo('digitos2(factorial(2*10**4))')
#    0.10 segundos
#    >>> tiempo('digitos3(factorial(2*10**4))')
#    0.10 segundos
#    >>> tiempo('digitos4(factorial(2*10**4))')
#    0.09 segundos
#    >>> tiempo('digitos6(factorial(2*10**4))')
#    2.33 segundos
#    >>> tiempo('digitos7(factorial(2*10**4))')
#    1.18 segundos
#
#    >>> tiempo('digitos2(factorial(10**5))')
#    3.53 segundos
#    >>> tiempo('digitos3(factorial(10**5))')
#    3.22 segundos
#    >>> tiempo('digitos4(factorial(10**5))')
#    3.02 segundos

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/digitos_de_un_numero.py).

Algoritmo de Euclides del mcd

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = mcd (b, a módulo b), si b > 0

Definir la función

   mcd :: Integer -> Integer -> Integer

tal que mcd a b es el máximo común divisor de a y b calculado mediante el algoritmo de Euclides. Por ejemplo,

   mcd 30 45  ==  15
   mcd 45 30  ==  15

Comprobar con QuickCheck que el máximo común divisor de dos números a y b (ambos mayores que 0) es siempre mayor o igual que 1 y además es menor o igual que el menor de los números a y b.

Soluciones en Haskell
import Test.QuickCheck
 
mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (a `mod` b)
 
-- La propiedad es
prop_mcd :: Positive Integer -> Positive Integer -> Bool
prop_mcd (Positive a) (Positive b) =
  m >= 1 && m <= min a b
  where m = mcd a b
 
-- La comprobación es
--    λ> quickCheck prop_mcd
--    OK, passed 100 tests.

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Algoritmo_de_Euclides_del_mcd.hs).

Soluciones en Python
from hypothesis import given
from hypothesis import strategies as st
 
def mcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return mcd(b, a % b)
 
# -- La propiedad es
@given(st.integers(min_value=1, max_value=1000),
       st.integers(min_value=1, max_value=1000))
def test_mcd(a: int, b: int) -> None:
    assert 1 <= mcd(a, b) <= min(a, b)
 
# La comprobación es
#    src> poetry run pytest -q algoritmo_de_Euclides_del_mcd.py
#    1 passed in 0.22s

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/algoritmo_de_Euclides_del_mcd.py).

Potencia entera

Definir la función

   potencia :: Integer -> Integer -> Integer

tal que potencia x n es x elevado al número natural n. Por ejemplo,

   potencia 2 3  ==  8
Soluciones en Haskell
import Data.List (foldl')
import Control.Arrow ((***))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
potencia1 :: Integer -> Integer -> Integer
potencia1 _ 0 = 1
potencia1 m n = m * potencia1 m (n-1)
 
-- 2ª solución
-- ===========
 
potencia2 :: Integer -> Integer -> Integer
potencia2 m = aux
  where aux 0 = 1
        aux n = m * aux (n-1)
 
-- 3ª solución
-- ===========
 
potencia3 :: Integer -> Integer -> Integer
potencia3 m = aux 1
  where aux r 0 = r
        aux r n = aux (r*m) (n-1)
 
-- 4ª solución
-- ===========
 
potencia4 :: Integer -> Integer -> Integer
potencia4 m = aux 1
  where aux r 0 = r
        aux r n = (aux $! (r*m)) $! (n-1)
 
-- 5ª solución
-- ===========
 
potencia5 :: Integer -> Integer -> Integer
potencia5 m n = product [m | _ <- [1..n]]
 
-- 6ª solución
-- ===========
 
potencia6 :: Integer -> Integer -> Integer
potencia6 m n = foldl' (*) 1 [m | _ <- [1..n]]
 
-- 7ª solución
-- ===========
 
potencia7 :: Integer -> Integer -> Integer
potencia7 m n =
  fst (until (\ (_,k) -> k == n)
             (\ (r,k) -> (r*m, k+1))
             (1,0))
 
-- 8ª solución
-- ===========
 
potencia8 :: Integer -> Integer -> Integer
potencia8 m n =
  fst (until ((== n) . snd)
             ((m *) *** (1 +))
             (1,0))
 
-- 9ª solución
-- ===========
 
potencia9 :: Integer -> Integer -> Integer
potencia9 m n = m^n
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_potencia :: Integer -> NonNegative Integer -> Bool
prop_potencia m (NonNegative n) =
  all (== potencia1 m n)
      [potencia2 m n,
       potencia3 m n,
       potencia4 m n,
       potencia5 m n,
       potencia6 m n,
       potencia7 m n,
       potencia8 m n,
       potencia9 m n]
 
-- La comprobación es
--    λ> quickCheck prop_potencia
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (show (potencia1 2 (2*10^5)))
--    60206
--    (2.97 secs, 2,602,252,408 bytes)
--    λ> length (show (potencia2 2 (2*10^5)))
--    60206
--    (2.63 secs, 2,624,652,624 bytes)
--    λ> length (show (potencia3 2 (2*10^5)))
--    60206
--    (3.41 secs, 2,619,606,368 bytes)
--    λ> length (show (potencia4 2 (2*10^5)))
--    60206
--    (0.64 secs, 2,636,888,928 bytes)
--    λ> length (show (potencia5 2 (2*10^5)))
--    60206
--    (2.47 secs, 2,597,108,000 bytes)
--    λ> length (show (potencia6 2 (2*10^5)))
--    60206
--    (0.35 secs, 2,582,488,824 bytes)
--    λ> length (show (potencia7 2 (2*10^5)))
--    60206
--    (2.48 secs, 2,616,406,272 bytes)
--    λ> length (show (potencia8 2 (2*10^5)))
--    60206
--    (2.40 secs, 2,608,652,736 bytes)
--    λ> length (show (potencia9 2 (2*10^5)))
--    60206
--    (0.01 secs, 4,212,968 bytes)
--
--    λ> length (show (potencia4 2 (10^6)))
--    301030
--    (10.39 secs, 63,963,999,656 bytes)
--    λ> length (show (potencia6 2 (10^6)))
--    301030
--    (8.90 secs, 63,691,999,552 bytes)
--    λ> length (show (potencia9 2 (10^6)))
--    301030
--    (0.04 secs, 19,362,032 bytes)

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Potencia_entera.hs).

Soluciones en Python
from functools import reduce
from operator import mul
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def potencia1(m: int, n: int) -> int:
    if n == 0:
        return 1
    return m * potencia1(m, n-1)
 
# 2ª solución
# ===========
 
def potencia2(m: int, n: int) -> int:
    def aux(k: int) -> int:
        if k == 0:
            return 1
        return m * aux(k-1)
    return aux(n)
 
# 3ª solución
# ===========
 
def potencia3(m: int, n: int) -> int:
    def aux(r: int, k: int) -> int:
        if k == 0:
            return r
        return aux(r*m, k-1)
    return aux(1, n)
 
# 4ª solución
# ===========
 
# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([2, 3, 5])  ==  30
def producto(xs: list[int]) -> int:
    return reduce(mul, xs, 1)
 
def potencia4(m: int, n: int) -> int:
    return producto([m]*n)
 
# 5ª solución
# ===========
 
def potencia5(m: int, n: int) -> int:
    r = 1
    for _ in range(0, n):
        r = r * m
    return r
 
# 6ª solución
# ===========
 
def potencia6(m: int, n: int) -> int:
    return m**n
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(),
       st.integers(min_value=0, max_value=100))
def test_potencia(m: int, n: int) -> None:
    r = potencia1(m, n)
    assert potencia2(m, n) == r
    assert potencia3(m, n) == r
    assert potencia4(m, n) == r
    assert potencia5(m, n) == r
    assert potencia6(m, n) == r
 
# La comprobación es
#    src> poetry run pytest -q potencia_entera.py
#    1 passed in 0.17s
 
# 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('potencia1(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia2(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia3(2, 2*10**4)')
#    0.02 segundos
#    >>> tiempo('potencia4(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia5(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia6(2, 2*10**4)')
#    0.00 segundos
#
#    >>> tiempo('potencia4(2, 5*10**5)')
#    2.87 segundos
#    >>> tiempo('potencia5(2, 5*10**5)')
#    3.17 segundos
#    >>> tiempo('potencia6(2, 5*10**5)')
#    0.00 segundos

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/potencia_entera.py).