Menu Close

PFH: La semana en Exercitium (23 de septiembre de 2022)

José A. Alonso

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

A continuación se muestran las soluciones.

1. Igualdad de conjuntos

Definir la función

   iguales :: Ord a => [a] -> [a] -> Bool

tal que iguales xs ys se verifica si xs e ys son iguales como conjuntos. 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

Soluciones en Haskell

import Data.List (nub, sort)
import Data.Set (fromList)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
iguales1 :: Ord a => [a] -> [a] -> Bool
iguales1 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
 
-- 2ª solución
-- ===========
 
iguales2 :: Ord a => [a] -> [a] -> Bool
iguales2 xs ys =
  nub (sort xs) == nub (sort ys)
 
-- 3ª solución
-- ===========
 
iguales3 :: Ord a => [a] -> [a] -> Bool
iguales3 xs ys =
  fromList xs == fromList ys
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_iguales :: [Int] -> [Int] -> Bool
prop_iguales xs ys =
  all (== iguales1 xs ys)
      [iguales2 xs ys,
       iguales3 xs ys]
 
-- La comprobación es
--    λ> quickCheck prop_iguales
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> iguales1 [1..2*10^4] [1..2*10^4]
--    True
--    (4.05 secs, 8,553,104 bytes)
--    λ> iguales2 [1..2*10^4] [1..2*10^4]
--    True
--    (4.14 secs, 9,192,768 bytes)
--    λ> iguales3 [1..2*10^4] [1..2*10^4]
--    True
--    (0.01 secs, 8,552,232 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import Any
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
 
# 1ª solución
# ===========
 
def subconjunto(xs: list[Any],
                ys: list[Any]) -> bool:
    return [x for x in xs if x in ys] == xs
 
def iguales1(xs: list[Any],
             ys: list[Any]) -> bool:
    return subconjunto(xs, ys) and subconjunto(ys, xs)
 
# 2ª solución
# ===========
 
def iguales2(xs: list[Any],
             ys: list[Any]) -> bool:
    return set(xs) == set(ys)
 
# Equivalencia de las definiciones
# ================================
 
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_iguales(xs, ys):
    assert iguales1(xs, ys) == iguales2(xs, ys)
 
# La comprobación es
#    src> poetry run pytest -q igualdad_de_conjuntos.py
#    1 passed in 0.28s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """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
#    >>> xs = list(range(20000))
#    >>> tiempo('iguales1(xs, xs)')
#    2.71 segundos
#    >>> tiempo('iguales2(xs, xs)')
#    0.01 segundos

El código se encuentra en GitHub

2. Unión conjuntista de listas

Definir la función

   union :: Ord a => [a] -> [a] -> [a]

tal que union xs ys es la unión de las listas, sin elementos repetidos, xs e ys. Por ejemplo,

   union [3,2,5] [5,7,3,4]  ==  [3,2,5,7,4]

Comprobar con QuickCheck que la unión es conmutativa.

Soluciones en Haskell

import Data.List (nub, sort, union)
import qualified Data.Set as S (fromList, toList, union)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
union1 :: Ord a => [a] -> [a] -> [a]
union1 xs ys = xs ++ [y | y <- ys, y `notElem` xs]
 
-- 2ª solución
-- ===========
 
union2 :: Ord a => [a] -> [a] -> [a]
union2 [] ys = ys
union2 (x:xs) ys
  | x `elem` ys = xs `union2` ys
  | otherwise   = x : xs `union2` ys
 
-- 3ª solución
-- ===========
 
union3 :: Ord a => [a] -> [a] -> [a]
union3 = union
 
-- 4ª solución
-- ===========
 
union4 :: Ord a => [a] -> [a] -> [a]
union4 xs ys =
  S.toList (S.fromList xs `S.union` S.fromList ys)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_union :: [Int] -> [Int] -> Bool
prop_union xs ys =
  all (== sort (xs' `union1` ys'))
      [sort (xs' `union2` ys'),
       sort (xs' `union3` ys'),
       xs' `union4` ys']
  where xs' = nub xs
        ys' = nub ys
 
-- La comprobación es
--    λ> quickCheck prop_union
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (union1 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (2.37 secs, 7,153,536 bytes)
--    λ> length (union2 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (2.38 secs, 6,553,752 bytes)
--    λ> length (union3 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (11.56 secs, 23,253,553,472 bytes)
--    λ> length (union4 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (0.04 secs, 10,992,056 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_union_conmutativa :: [Int] -> [Int] -> Bool
prop_union_conmutativa xs ys =
  iguales (xs `union1` ys) (ys `union1` xs)
 
-- (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 =
  S.fromList xs == S.fromList ys
 
-- La comprobación es
--    λ> quickCheck prop_union_conmutativa
--    +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def union1(xs: list[A], ys: list[A]) -> list[A]:
    return xs + [y for y in ys if y not in xs]
 
# 2ª solución
# ===========
 
def union2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return ys
    if xs[0] in ys:
        return union2(xs[1:], ys)
    return [xs[0]] + union2(xs[1:], ys)
 
# 3ª solución
# ===========
 
def union3(xs: list[A], ys: list[A]) -> list[A]:
    zs = ys[:]
    for x in xs:
        if x not in ys:
            zs.append(x)
    return zs
 
# 4ª solución
# ===========
 
def union4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) | set(ys))
 
# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_union(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(union1(xs1, ys1)) ==\
           sorted(union2(xs1, ys1)) ==\
           sorted(union3(xs1, ys1)) ==\
           sorted(union4(xs1, ys1))
 
# La comprobación es
#    src> poetry run pytest -q union_conjuntista_de_listas.py
#    1 passed in 0.36s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """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('union1(list(range(0,30000,2)), list(range(1,30000,2)))')
#    1.30 segundos
#    >>> tiempo('union2(list(range(0,30000,2)), list(range(1,30000,2)))')
#    2.84 segundos
#    >>> tiempo('union3(list(range(0,30000,2)), list(range(1,30000,2)))')
#    1.45 segundos
#    >>> tiempo('union4(list(range(0,30000,2)), list(range(1,30000,2)))')
#    0.00 segundos
 
# Comprobación de la propiedad
# ============================
 
# iguales(xs, ys) se verifica si xs e ys son iguales como conjuntos. 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
def iguales(xs: list[A], ys: list[A]) -> bool:
    return set(xs) == set(ys)
 
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_union_conmutativa(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert iguales(union1(xs1, ys1), union1(ys1, xs1))
 
# La comprobación es
#    src> poetry run pytest -q union_conjuntista_de_listas.py
#    2 passed in 0.49s

El código se encuentra en GitHub

3. Intersección conjuntista de listas

Definir la función

   interseccion :: Eq a => [a] -> [a] -> [a]

tal que interseccion xs ys es la intersección de las listas sin elementos repetidos xs e ys. Por ejemplo,

   interseccion [3,2,5] [5,7,3,4]  ==  [3,5]
   interseccion [3,2,5] [9,7,6,4]  ==  []

Soluciones en Haskell

import Data.List (nub, sort, intersect)
import qualified Data.Set as S (fromList, toList, intersection )
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
interseccion1 :: Eq a => [a] -> [a] -> [a]
interseccion1 xs ys =
  [x | x <- xs, x `elem` ys]
 
-- 2ª solución
-- ===========
 
interseccion2 :: Ord a => [a] -> [a] -> [a]
interseccion2 [] _ = []
interseccion2 (x:xs) ys
  | x `elem` ys = x : xs `interseccion2` ys
  | otherwise   = xs `interseccion2` ys
 
-- 3ª solución
-- ===========
 
interseccion3 :: Ord a => [a] -> [a] -> [a]
interseccion3 = intersect
 
-- 4ª solución
-- ===========
 
interseccion4 :: Ord a => [a] -> [a] -> [a]
interseccion4 xs ys =
  S.toList (S.fromList xs `S.intersection` S.fromList ys)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_interseccion :: [Int] -> [Int] -> Bool
prop_interseccion xs ys =
  all (== sort (xs' `interseccion1` ys'))
      [sort (xs' `interseccion2` ys'),
       sort (xs' `interseccion3` ys'),
       xs' `interseccion4` ys']
  where xs' = nub xs
        ys' = nub ys
 
-- La comprobación es
--    λ> quickCheck prop_interseccion
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (interseccion1 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (2.94 secs, 6,673,360 bytes)
--    λ> length (interseccion2 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (3.04 secs, 9,793,440 bytes)
--    λ> length (interseccion3 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (5.39 secs, 6,673,472 bytes)
--    λ> length (interseccion4 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (0.04 secs, 8,593,176 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def interseccion1(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in xs if x in ys]
 
# 2ª solución
# ===========
 
def interseccion2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return []
    if xs[0] in ys:
        return [xs[0]] + interseccion2(xs[1:], ys)
    return interseccion2(xs[1:], ys)
 
# 3ª solución
# ===========
 
def interseccion3(xs: list[A], ys: list[A]) -> list[A]:
    zs = []
    for x in xs:
        if x in ys:
            zs.append(x)
    return zs
 
# 4ª solución
# ===========
 
def interseccion4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) & set(ys))
 
# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_interseccion(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(interseccion1(xs1, ys1)) ==\
           sorted(interseccion2(xs1, ys1)) ==\
           sorted(interseccion3(xs1, ys1)) ==\
           sorted(interseccion4(xs1, ys1))
 
# La comprobación es
#    src> poetry run pytest -q interseccion_conjuntista_de_listas.py
#    1 passed in 0.33s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """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('interseccion1(list(range(0,20000)), list(range(1,20000,2)))')
#    0.98 segundos
#    >>> tiempo('interseccion2(list(range(0,20000)), list(range(1,20000,2)))')
#    2.13 segundos
#    >>> tiempo('interseccion3(list(range(0,20000)), list(range(1,20000,2)))')
#    0.87 segundos
#    >>> tiempo('interseccion4(list(range(0,20000)), list(range(1,20000,2)))')
#    0.00 segundos

El código se encuentra en GitHub.

4. Diferencia conjuntista de listas

Definir la función

   diferencia :: Eq a => [a] -> [a] -> [a]

tal que diferencia xs ys es la diferencia de las listas sin elementos repetidos xs e ys. Por ejemplo,

   diferencia [3,2,5,6] [5,7,3,4]  ==  [2,6]
   diferencia [3,2,5] [5,7,3,2]    ==  []

Soluciones en Haskell

import Data.List (nub, sort, (\\))
import qualified Data.Set as S (fromList, toList, (\\) )
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
diferencia1 :: Eq a => [a] -> [a] -> [a]
diferencia1 xs ys =
  [x | x <- xs, x `notElem` ys]
 
-- 2ª solución
-- ===========
 
diferencia2 :: Ord a => [a] -> [a] -> [a]
diferencia2 [] _ = []
diferencia2 (x:xs) ys
  | x `elem` ys = xs `diferencia2` ys
  | otherwise   = x : xs `diferencia2` ys
 
-- 3ª solución
-- ===========
 
diferencia3 :: Ord a => [a] -> [a] -> [a]
diferencia3 = (\\)
 
-- 4ª solución
-- ===========
 
diferencia4 :: Ord a => [a] -> [a] -> [a]
diferencia4 xs ys =
  S.toList (S.fromList xs S.\\ S.fromList ys)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_diferencia :: [Int] -> [Int] -> Bool
prop_diferencia xs ys =
  all (== sort (xs' `diferencia1` ys'))
      [sort (xs' `diferencia2` ys'),
       sort (xs' `diferencia3` ys'),
       xs' `diferencia4` ys']
  where xs' = nub xs
        ys' = nub ys
 
-- La comprobación es
--    λ> quickCheck prop_diferencia
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (diferencia1 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (3.39 secs, 9,553,528 bytes)
--    λ> length (diferencia2 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (2.98 secs, 9,793,528 bytes)
--    λ> length (diferencia3 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (3.61 secs, 11,622,502,792 bytes)
--    λ> length (diferencia4 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (0.02 secs, 10,092,832 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def diferencia1(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in xs if x not in ys]
 
# 2ª solución
# ===========
 
def diferencia2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return []
    if xs[0] in ys:
        return diferencia2(xs[1:], ys)
    return [xs[0]] + diferencia2(xs[1:], ys)
 
# 3ª solución
# ===========
 
def diferencia3(xs: list[A], ys: list[A]) -> list[A]:
    zs = []
    for x in xs:
        if x not in ys:
            zs.append(x)
    return zs
 
# 4ª solución
# ===========
 
def diferencia4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) - set(ys))
 
# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_diferencia(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(diferencia1(xs1, ys1)) ==\
           sorted(diferencia2(xs1, ys1)) ==\
           sorted(diferencia3(xs1, ys1)) ==\
           sorted(diferencia4(xs1, ys1))
 
# La comprobación es
#    src> poetry run pytest -q diferencia_conjuntista_de_listas.py
#    1 passed in 0.39s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """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('diferencia1(list(range(0,20000)), list(range(1,20000,2)))')
#    0.89 segundos
#    >>> tiempo('diferencia2(list(range(0,20000)), list(range(1,20000,2)))')
#    2.11 segundos
#    >>> tiempo('diferencia3(list(range(0,20000)), list(range(1,20000,2)))')
#    1.06 segundos
#    >>> tiempo('diferencia4(list(range(0,20000)), list(range(1,20000,2)))')
#    0.01 segundos

El código se encuentra en GitHub.

5. Divisores de un número

Definir la función

   divisores :: Integer -> [Integer]

tal que divisores n es la lista de los divisores de n. Por ejemplo,

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

Soluciones en Haskell

import Data.List (group, inits, nub, sort, subsequences)
import Data.Numbers.Primes (primeFactors)
import Data.Set (toList)
import Math.NumberTheory.ArithmeticFunctions (divisors)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]
 
-- 2ª solución
-- ===========
 
divisores2 :: Integer -> [Integer]
divisores2 n = [x | x <- [1..n], x `esDivisorDe` n]
 
-- (esDivisorDe x n) se verifica si x es un divisor de n. Por ejemplo,
--    esDivisorDe 2 6  ==  True
--    esDivisorDe 4 6  ==  False
esDivisorDe :: Integer -> Integer -> Bool
esDivisorDe x n = n `rem` x == 0
 
-- 3ª solución
-- ===========
 
divisores3 :: Integer -> [Integer]
divisores3 n = filter (`esDivisorDe` n) [1..n]
 
-- 4ª solución
-- ===========
 
divisores4 :: Integer -> [Integer]
divisores4 = filter <$> flip esDivisorDe <*> enumFromTo 1
 
-- 5ª solución
-- ===========
 
divisores5 :: Integer -> [Integer]
divisores5 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores1 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs
 
-- (primerosDivisores n) es la lista de los divisores del número n cuyo
-- cuadrado es menor o gual que n. Por ejemplo,
--    primerosDivisores 25  ==  [1,5]
--    primerosDivisores 30  ==  [1,2,3,5]
primerosDivisores1 :: Integer -> [Integer]
primerosDivisores1 n =
   [x | x <- [1..round (sqrt (fromIntegral n))],
        x `esDivisorDe` n]
 
-- 6ª solución
-- ===========
 
divisores6 :: Integer -> [Integer]
divisores6 n = aux [1..n]
  where aux [] = []
        aux (x:xs) | x `esDivisorDe` n = x : aux xs
                   | otherwise         = aux xs
 
-- 7ª solución
-- ===========
 
divisores7 :: Integer -> [Integer]
divisores7 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores2 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs
 
primerosDivisores2 :: Integer -> [Integer]
primerosDivisores2 n = aux [1..round (sqrt (fromIntegral n))]
  where aux [] = []
        aux (x:xs) | x `esDivisorDe` n = x : aux xs
                   | otherwise         = aux xs
 
-- 8ª solución
-- ===========
 
divisores8 :: Integer -> [Integer]
divisores8 =
  nub . sort . map product . subsequences . primeFactors
 
-- 9ª solución
-- ===========
 
divisores9 :: Integer -> [Integer]
divisores9 = sort
           . map (product . concat)
           . productoCartesiano
           . map inits
           . group
           . primeFactors
 
-- (productoCartesiano xss) es el producto cartesiano de los conjuntos
-- xss. Por ejemplo,
--    λ> productoCartesiano [[1,3],[2,5],[6,4]]
--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
productoCartesiano :: [[a]] -> [[a]]
productoCartesiano []       = [[]]
productoCartesiano (xs:xss) =
  [x:ys | x <- xs, ys <- productoCartesiano xss]
 
-- 10ª solución
-- ============
 
divisores10 :: Integer -> [Integer]
divisores10 = sort
            . map (product . concat)
            . mapM inits
            . group
            . primeFactors
 
-- 11ª solución
-- ============
 
divisores11 :: Integer -> [Integer]
divisores11 = toList . divisors
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_divisores :: Positive Integer -> Bool
prop_divisores (Positive n) =
  all (== divisores1 n)
      [ divisores2 n
      , divisores3 n
      , divisores4 n
      , divisores5 n
      , divisores6 n
      , divisores7 n
      , divisores8 n
      , divisores9 n
      , divisores10 n
      , divisores11 n
      ]
 
-- La comprobación es
--    λ> quickCheck prop_divisores
--    +++ OK, passed 100 tests.
 
-- Comparación de la eficiencia
-- ============================
 
-- La comparación es
--    λ> length (divisores1 (product [1..11]))
--    540
--    (18.55 secs, 7,983,950,592 bytes)
--    λ> length (divisores2 (product [1..11]))
--    540
--    (18.81 secs, 7,983,950,592 bytes)
--    λ> length (divisores3 (product [1..11]))
--    540
--    (12.79 secs, 6,067,935,544 bytes)
--    λ> length (divisores4 (product [1..11]))
--    540
--    (12.51 secs, 6,067,935,592 bytes)
--    λ> length (divisores5 (product [1..11]))
--    540
--    (0.03 secs, 1,890,296 bytes)
--    λ> length (divisores6 (product [1..11]))
--    540
--    (21.46 secs, 9,899,961,392 bytes)
--    λ> length (divisores7 (product [1..11]))
--    540
--    (0.02 secs, 2,195,800 bytes)
--    λ> length (divisores8 (product [1..11]))
--    540
--    (0.09 secs, 107,787,272 bytes)
--    λ> length (divisores9 (product [1..11]))
--    540
--    (0.02 secs, 2,150,472 bytes)
--    λ> length (divisores10 (product [1..11]))
--    540
--    (0.01 secs, 1,652,120 bytes)
--    λ> length (divisores11 (product [1..11]))
--    540
--    (0.01 secs, 796,056 bytes)
--
--    λ> length (divisores5 (product [1..17]))
--    10752
--    (10.16 secs, 3,773,953,128 bytes)
--    λ> length (divisores7 (product [1..17]))
--    10752
--    (9.83 secs, 4,679,260,712 bytes)
--    λ> length (divisores9 (product [1..17]))
--    10752
--    (0.06 secs, 46,953,344 bytes)
--    λ> length (divisores10 (product [1..17]))
--    10752
--    (0.02 secs, 33,633,712 bytes)
--    λ> length (divisores11 (product [1..17]))
--    10752
--    (0.03 secs, 6,129,584 bytes)
--
--    λ> length (divisores10 (product [1..27]))
--    677376
--    (2.14 secs, 3,291,277,736 bytes)
--    λ> length (divisores11 (product [1..27]))
--    677376
--    (0.56 secs, 396,042,280 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import factorial, sqrt
from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import divisors
from hypothesis import given, strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]
 
# 2ª solución
# ===========
 
# esDivisorDe(x, n) se verifica si x es un divisor de n. Por ejemplo,
#    esDivisorDe(2, 6)  ==  True
#    esDivisorDe(4, 6)  ==  False
def esDivisorDe(x: int, n: int) -> bool:
    return n % x == 0
 
def divisores2(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if esDivisorDe(x, n)]
 
# 3ª solución
# ===========
 
def divisores3(n: int) -> list[int]:
    return list(filter(lambda x: esDivisorDe(x, n), range(1, n + 1)))
 
# 4ª solución
# ===========
 
# primerosDivisores(n) es la lista de los divisores del número n cuyo
# cuadrado es menor o gual que n. Por ejemplo,
#    primerosDivisores(25)  ==  [1,5]
#    primerosDivisores(30)  ==  [1,2,3,5]
def primerosDivisores(n: int) -> list[int]:
    return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0]
 
def divisores4(n: int) -> list[int]:
    xs = primerosDivisores(n)
    zs = list(reversed(xs))
    if zs[0]**2 == n:
        return xs + [n // a for a in zs[1:]]
    return xs + [n // a for a in zs]
 
# 5ª solución
# ===========
 
def divisores5(n: int) -> list[int]:
    def aux(xs: list[int]) -> list[int]:
        if xs:
            if esDivisorDe(xs[0], n):
                return [xs[0]] + aux(xs[1:])
            return aux(xs[1:])
        return xs
 
    return aux(list(range(1, n + 1)))
 
# 6ª solución
# ============
 
def divisores6(n: int) -> list[int]:
    xs = []
    for x in range(1, n+1):
        if n % x == 0:
            xs.append(x)
    return xs
 
# 7ª solución
# ===========
 
def divisores7(n: int) -> list[int]:
    x = 1
    xs = []
    ys = []
    while x * x < n:
        if n % x == 0:
            xs.append(x)
            ys.append(n // x)
        x = x + 1
    if x * x == n:
        xs.append(x)
    return xs + list(reversed(ys))
 
# 8ª solución
# ============
 
def divisores8(n: int) -> list[int]:
    return divisors(n)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_divisores(n):
    assert divisores1(n) ==\
           divisores2(n) ==\
           divisores3(n) ==\
           divisores4(n) ==\
           divisores5(n) ==\
           divisores6(n) ==\
           divisores7(n) ==\
           divisores8(n)
 
# La comprobación es
#    src> poetry run pytest -q divisores_de_un_numero.py
#    1 passed in 0.84s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """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('divisores5(4*factorial(7))')
#    1.40 segundos
#
#    >>> tiempo('divisores1(factorial(11))')
#    1.79 segundos
#    >>> tiempo('divisores2(factorial(11))')
#    3.80 segundos
#    >>> tiempo('divisores3(factorial(11))')
#    5.22 segundos
#    >>> tiempo('divisores4(factorial(11))')
#    0.00 segundos
#    >>> tiempo('divisores6(factorial(11))')
#    3.51 segundos
#    >>> tiempo('divisores7(factorial(11))')
#    0.00 segundos
#    >>> tiempo('divisores8(factorial(11))')
#    0.00 segundos
#
#    >>> tiempo('divisores4(factorial(17))')
#    2.23 segundos
#    >>> tiempo('divisores7(factorial(17))')
#    3.22 segundos
#    >>> tiempo('divisores8(factorial(17))')
#    0.00 segundos
#
#    >>> tiempo('divisores8(factorial(27))')
#    0.28 segundos

El código se encuentra en GitHub.

6. Divisores primos

Definir la función

   divisoresPrimos :: Integer -> [Integer]

tal que divisoresPrimos x es la lista de los divisores primos de x. Por ejemplo,

   divisoresPrimos 40 == [2,5]
   divisoresPrimos 70 == [2,5,7]
   length (divisoresPrimos (product [1..20000])) == 2262

Soluciones en Haskell

import Data.List (nub)
import Data.Set (toList)
import Data.Numbers.Primes (isPrime, primeFactors)
import Math.NumberTheory.ArithmeticFunctions (divisors)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
divisoresPrimos1 :: Integer -> [Integer]
divisoresPrimos1 x = [n | n <- divisores1 x, primo1 n]
 
-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 25  ==  [1,5,25]
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `mod` x == 0]
 
-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True
primo1 :: Integer -> Bool
primo1 n = divisores1 n == [1, n]
 
-- 2ª solución
-- ===========
 
divisoresPrimos2 :: Integer -> [Integer]
divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]
 
divisores2 :: Integer -> [Integer]
divisores2 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores2 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs
 
-- (primerosDivisores n) es la lista de los divisores del número n cuyo
-- cuadrado es menor o gual que n. Por ejemplo,
--    primerosDivisores 25  ==  [1,5]
--    primerosDivisores 30  ==  [1,2,3,5]
primerosDivisores2 :: Integer -> [Integer]
primerosDivisores2 n =
   [x | x <- [1..round (sqrt (fromIntegral n))],
        n `mod` x == 0]
 
primo2 :: Integer -> Bool
primo2 1 = False
primo2 n = primerosDivisores2 n == [1]
 
-- 3ª solución
-- ===========
 
divisoresPrimos3 :: Integer -> [Integer]
divisoresPrimos3 x = [n | n <- divisores3 x, primo3 n]
 
divisores3 :: Integer -> [Integer]
divisores3 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores3 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs
 
primerosDivisores3 :: Integer -> [Integer]
primerosDivisores3 n =
   filter ((== 0) . mod n) [1..round (sqrt (fromIntegral n))]
 
primo3 :: Integer -> Bool
primo3 1 = False
primo3 n = primerosDivisores3 n == [1]
 
-- 4ª solución
-- ===========
 
divisoresPrimos4 :: Integer -> [Integer]
divisoresPrimos4 n
  | even n = 2 : divisoresPrimos4 (reducido n 2)
  | otherwise = aux n [3,5..n]
  where aux 1 _  = []
        aux _ [] = []
        aux m (x:xs) | m `mod` x == 0 = x : aux (reducido m x) xs
                     | otherwise      = aux m xs
 
-- (reducido m x) es el resultado de dividir repetidamente m por x,
-- mientras sea divisible. Por ejemplo,
--    reducido 36 2  ==  9
reducido :: Integer -> Integer -> Integer
reducido m x | m `mod` x == 0 = reducido (m `div` x) x
             | otherwise      = m
 
-- 5ª solución
-- ===========
 
divisoresPrimos5 :: Integer -> [Integer]
divisoresPrimos5 = nub . primeFactors
 
-- 6ª solución
-- ===========
 
divisoresPrimos6 :: Integer -> [Integer]
divisoresPrimos6 = filter isPrime . toList . divisors
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_divisoresPrimos :: Integer -> Property
prop_divisoresPrimos n =
  n > 1 ==>
  all (== divisoresPrimos1 n)
      [divisoresPrimos2 n,
       divisoresPrimos3 n,
       divisoresPrimos4 n,
       divisoresPrimos5 n,
       divisoresPrimos6 n]
 
-- La comprobación es
--    λ> quickCheck prop_divisoresPrimos
--    +++ OK, passed 100 tests; 108 discarded.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> divisoresPrimos1 (product [1..11])
--    [2,3,5,7,11]
--    (18.34 secs, 7,984,382,104 bytes)
--    λ> divisoresPrimos2 (product [1..11])
--    [2,3,5,7,11]
--    (0.02 secs, 2,610,976 bytes)
--    λ> divisoresPrimos3 (product [1..11])
--    [2,3,5,7,11]
--    (0.02 secs, 2,078,288 bytes)
--    λ> divisoresPrimos4 (product [1..11])
--    [2,3,5,7,11]
--    (0.02 secs, 565,992 bytes)
--    λ> divisoresPrimos5 (product [1..11])
--    [2,3,5,7,11]
--    (0.01 secs, 568,000 bytes)
--    λ> divisoresPrimos6 (product [1..11])
--    [2,3,5,7,11]
--    (0.00 secs, 2,343,392 bytes)
--
--    λ> divisoresPrimos2 (product [1..16])
--    [2,3,5,7,11,13]
--    (2.32 secs, 923,142,480 bytes)
--    λ> divisoresPrimos3 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.80 secs, 556,961,088 bytes)
--    λ> divisoresPrimos4 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.01 secs, 572,368 bytes)
--    λ> divisoresPrimos5 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.01 secs, 31,665,896 bytes)
--    λ> divisoresPrimos6 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.01 secs, 18,580,584 bytes)
--
--    λ> length (divisoresPrimos4 (product [1..30]))
--    10
--    (0.01 secs, 579,168 bytes)
--    λ> length (divisoresPrimos5 (product [1..30]))
--    10
--    (0.01 secs, 594,976 bytes)
--    λ> length (divisoresPrimos6 (product [1..30]))
--    10
--    (3.38 secs, 8,068,783,408 bytes)
--
--    λ> length (divisoresPrimos4 (product [1..20000]))
--    2262
--    (1.20 secs, 1,940,069,976 bytes)
--    λ> length (divisoresPrimos5 (product [1..20000]))
--    2262
--    (1.12 secs, 1,955,921,736 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import sqrt
from operator import mul
from functools import reduce
from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import divisors, isprime, primefactors
from hypothesis import given, strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
# divisores(n) es la lista de los divisores del número n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]
 
# primo(n) se verifica si n es primo. Por ejemplo,
#    primo(30)  == False
#    primo(31)  == True
def primo1(n: int) -> bool:
    return divisores1(n) == [1, n]
 
def divisoresPrimos1(x: int) -> list[int]:
    return [n for n in divisores1(x) if primo1(n)]
 
# 2ª solución
# ===========
 
# primerosDivisores(n) es la lista de los divisores del número n cuyo
# cuadrado es menor o gual que n. Por ejemplo,
#    primerosDivisores(25)  ==  [1,5]
#    primerosDivisores(30)  ==  [1,2,3,5]
def primerosDivisores2(n: int) -> list[int]:
    return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0]
 
def divisores2(n: int) -> list[int]:
    xs = primerosDivisores2(n)
    zs = list(reversed(xs))
    if zs[0]**2 == n:
        return xs + [n // a for a in zs[1:]]
    return xs + [n // a for a in zs]
 
def primo2(n: int) -> bool:
    return divisores2(n) == [1, n]
 
def divisoresPrimos2(x: int) -> list[int]:
    return [n for n in divisores2(x) if primo2(n)]
 
# 3ª solución
# ===========
 
# reducido(m, x) es el resultado de dividir repetidamente m por x,
# mientras sea divisible. Por ejemplo,
#    reducido(36, 2)  ==  9
def reducido(m: int, x: int) -> int:
    if m % x == 0:
        return reducido(m // x, x)
    return m
 
def divisoresPrimos3(n: int) -> list[int]:
    if n % 2 == 0:
        return [2] + divisoresPrimos3(reducido(n, 2))
 
    def aux(m, xs):
        if m == 1:
            return []
        if xs == []:
            return []
        if m % xs[0] == 0:
            return [xs[0]] + aux(reducido(m, xs[0]), xs[1:])
        return aux(m, xs[1:])
    return aux(n, range(3, n + 1, 2))
 
# 4ª solución
# ===========
 
def divisoresPrimos4(x: int) -> list[int]:
    return [n for n in divisors(x) if isprime(n)]
 
# 5ª solución
# ===========
 
def divisoresPrimos5(n):
    return primefactors(n)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_divisoresPrimos(n):
    assert divisoresPrimos1(n) ==\
           divisoresPrimos2(n) ==\
           divisoresPrimos3(n) ==\
           divisoresPrimos4(n) ==\
           divisoresPrimos5(n)
 
# La comprobación es
#    src> poetry run pytest -q divisores_primos.py
#    1 passed in 0.70s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
def producto(xs: list[int]) -> int:
    return reduce(mul, xs)
 
# La comparación es
#    >>> tiempo('divisoresPrimos1(producto(list(range(1, 12))))')
#    11.14 segundos
#    >>> tiempo('divisoresPrimos2(producto(list(range(1, 12))))')
#    0.03 segundos
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 12))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos4(producto(list(range(1, 12))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 12))))')
#    0.00 segundos
#
#    >>> tiempo('divisoresPrimos2(producto(list(range(1, 17))))')
#    14.21 segundos
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 17))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos4(producto(list(range(1, 17))))')
#    0.01 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 17))))')
#    0.00 segundos
#
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 32))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos4(producto(list(range(1, 32))))')
#    4.59 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 32))))')
#    0.00 segundos
#
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 10001))))')
#    3.00 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 10001))))')
#    0.24 segundos

El código se encuentra en GitHub.

Posted in PFH