octubre 2022 – Exercitium

Número a partir de sus dígitos

PorJosé A. Alonso 31-octubre-202214-diciembre-2022

Definir la función

   listaNumero :: [Integer] -> Integer

1	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

listaNumero [5] == 5

listaNumero [1,3,4,7] == 1347

listaNumero [0,0,1] == 1

Soluciones

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

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

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.

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

100

101

102

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.

Suma de los dígitos de un número

PorJosé A. Alonso 28-octubre-202214-diciembre-2022

Definir la función

   sumaDigitos :: Integer -> Integer

1	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

sumaDigitos 3 == 3

sumaDigitos 2454 == 15

sumaDigitos 20045 == 11

Soluciones

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

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)

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.

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

100

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

Dígitos de un número

PorJosé A. Alonso 27-octubre-202214-diciembre-2022

Definir la función

   digitos :: Integer -> [Int]

1	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]

1	digitos 320274 == [3,2,0,2,7,4]

Soluciones

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

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

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.

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

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.

Algoritmo de Euclides del mcd

PorJosé A. Alonso 26-octubre-202214-diciembre-2022

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

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

Definir la función

   mcd :: Integer -> Integer -> Integer

1	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

1 2	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

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

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.

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.

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

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.

Potencia entera

PorJosé A. Alonso 25-octubre-202214-diciembre-2022

Definir la función

   potencia :: Integer -> Integer -> Integer

1	potencia :: Integer -> Integer -> Integer

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

   potencia 2 3  ==  8

1	potencia 2 3 == 8

Soluciones

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

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

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.

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

100

101

102

103

104

105

106

107

108

109

110

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.

Base de datos de actividades

PorJosé A. Alonso 24-octubre-202214-diciembre-2022

Las bases de datos sobre actividades de personas pueden representarse mediante listas de elementos de la forma (a,b,c,d), donde a es el nombre de la persona, b su actividad, c su fecha de nacimiento y d la de su fallecimiento. Un ejemplo es la siguiente que usaremos a lo largo de este ejercicio,

   personas :: [(String,String,Int,Int)]
   personas = [("Cervantes","Literatura",1547,1616),
               ("Velazquez","Pintura",1599,1660),
               ("Picasso","Pintura",1881,1973),
               ("Beethoven","Musica",1770,1823),
               ("Poincare","Ciencia",1854,1912),
               ("Quevedo","Literatura",1580,1654),
               ("Goya","Pintura",1746,1828),
               ("Einstein","Ciencia",1879,1955),
               ("Mozart","Musica",1756,1791),
               ("Botticelli","Pintura",1445,1510),
               ("Borromini","Arquitectura",1599,1667),
               ("Bach","Musica",1685,1750)]

personas :: [(String,String,Int,Int)]

personas = [("Cervantes","Literatura",1547,1616),

("Velazquez","Pintura",1599,1660),

("Picasso","Pintura",1881,1973),

("Beethoven","Musica",1770,1823),

("Poincare","Ciencia",1854,1912),

("Quevedo","Literatura",1580,1654),

("Goya","Pintura",1746,1828),

("Einstein","Ciencia",1879,1955),

("Mozart","Musica",1756,1791),

("Botticelli","Pintura",1445,1510),

("Borromini","Arquitectura",1599,1667),

("Bach","Musica",1685,1750)]

Definir las funciones

   nombres   :: [(String,String,Int,Int)] -> [String]
   musicos   :: [(String,String,Int,Int)] -> [String]
   seleccion :: [(String,String,Int,Int)] -> String -> [String]
   musicos'  :: [(String,String,Int,Int)] -> [String]
   vivas     :: [(String,String,Int,Int)] -> Int -> [String]

nombres :: [(String,String,Int,Int)] -> [String]

musicos :: [(String,String,Int,Int)] -> [String]

seleccion :: [(String,String,Int,Int)] -> String -> [String]

musicos' :: [(String,String,Int,Int)] -> [String]

vivas :: [(String,String,Int,Int)] -> Int -> [String]

tales que

nombres bd es la lista de los nombres de las personas de la base de datos bd. Por ejemplo,

     λ> nombres personas
     ["Cervantes","Velazquez","Picasso","Beethoven","Poincare",
      "Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini",
      "Bach"]

λ> nombres personas

["Cervantes","Velazquez","Picasso","Beethoven","Poincare",

"Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini",

"Bach"]

musicos bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,

     musicos personas  ==  ["Beethoven","Mozart","Bach"]

1	musicos personas == ["Beethoven","Mozart","Bach"]

seleccion bd m es la lista de los nombres de las personas de la base de datos bd cuya actividad es m. Por ejemplo,

     λ> seleccion personas "Pintura"
     ["Velazquez","Picasso","Goya","Botticelli"]
     λ> seleccion personas "Musica"
     ["Beethoven","Mozart","Bach"]

λ> seleccion personas "Pintura"

["Velazquez","Picasso","Goya","Botticelli"]

λ> seleccion personas "Musica"

["Beethoven","Mozart","Bach"]

musicos' bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,

     musicos' personas  ==  ["Beethoven","Mozart","Bach"]

1	musicos' personas == ["Beethoven","Mozart","Bach"]

vivas bd a es la lista de los nombres de las personas de la base de datos bd que estaban vivas en el año a. Por ejemplo,

     λ> vivas personas 1600
     ["Cervantes","Velazquez","Quevedo","Borromini"]

1 2	λ> vivas personas 1600 ["Cervantes","Velazquez","Quevedo","Borromini"]

Soluciones

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

Soluciones en Haskell

personas :: [(String,String,Int,Int)]
personas = [("Cervantes","Literatura",1547,1616),
            ("Velazquez","Pintura",1599,1660),
            ("Picasso","Pintura",1881,1973),
            ("Beethoven","Musica",1770,1823),
            ("Poincare","Ciencia",1854,1912),
            ("Quevedo","Literatura",1580,1654),
            ("Goya","Pintura",1746,1828),
            ("Einstein","Ciencia",1879,1955),
            ("Mozart","Musica",1756,1791),
            ("Botticelli","Pintura",1445,1510),
            ("Borromini","Arquitectura",1599,1667),
            ("Bach","Musica",1685,1750)]

nombres :: [(String,String,Int,Int)] -> [String]
nombres bd = [x | (x,_,_,_) <- bd]

musicos :: [(String,String,Int,Int)] -> [String]
musicos bd = [x | (x,"Musica",_,_) <- bd]

seleccion :: [(String,String,Int,Int)] -> String -> [String]
seleccion bd m = [ x | (x,m',_,_) <- bd, m == m' ]

musicos' :: [(String,String,Int,Int)] -> [String]
musicos' bd = seleccion bd "Musica"

vivas :: [(String,String,Int,Int)] -> Int -> [String]
vivas bd a = [x | (x,_,a1,a2) <- bd, a1 <= a, a <= a2]

personas :: [(String,String,Int,Int)]

personas = [("Cervantes","Literatura",1547,1616),

("Velazquez","Pintura",1599,1660),

("Picasso","Pintura",1881,1973),

("Beethoven","Musica",1770,1823),

("Poincare","Ciencia",1854,1912),

("Quevedo","Literatura",1580,1654),

("Goya","Pintura",1746,1828),

("Einstein","Ciencia",1879,1955),

("Mozart","Musica",1756,1791),

("Botticelli","Pintura",1445,1510),

("Borromini","Arquitectura",1599,1667),

("Bach","Musica",1685,1750)]

nombres :: [(String,String,Int,Int)] -> [String]

nombres bd = [x | (x,_,_,_) <- bd]

musicos :: [(String,String,Int,Int)] -> [String]

musicos bd = [x | (x,"Musica",_,_) <- bd]

seleccion :: [(String,String,Int,Int)] -> String -> [String]

seleccion bd m = [ x | (x,m',_,_) <- bd, m == m' ]

musicos' :: [(String,String,Int,Int)] -> [String]

musicos' bd = seleccion bd "Musica"

vivas :: [(String,String,Int,Int)] -> Int -> [String]

vivas bd a = [x | (x,_,a1,a2) <- bd, a1 <= a, a <= a2]

El código se encuentra en GitHub.

Soluciones en Python

BD = list[tuple[str, str, int, int]]

personas: BD = [
    ("Cervantes", "Literatura", 1547, 1616),
    ("Velazquez", "Pintura", 1599, 1660),
    ("Picasso", "Pintura", 1881, 1973),
    ("Beethoven", "Musica", 1770, 1823),
    ("Poincare", "Ciencia", 1854, 1912),
    ("Quevedo", "Literatura", 1580, 1654),
    ("Goya", "Pintura", 1746, 1828),
    ("Einstein", "Ciencia", 1879, 1955),
    ("Mozart", "Musica", 1756, 1791),
    ("Botticelli", "Pintura", 1445, 1510),
    ("Borromini", "Arquitectura", 1599, 1667),
    ("Bach", "Musica", 1685, 1750)]

def nombres(bd: BD) -> list[str]:
    return [p[0] for p in bd]

def musicos(bd: BD) -> list[str]:
    return [p[0] for p in bd if p[1] == "Musica"]

def seleccion(bd: BD, m: str) -> list[str]:
    return [p[0] for p in bd if p[1] == m]

def musicos2(bd: BD) -> list[str]:
    return seleccion(bd, "Musica")

def vivas(bd: BD, a: int) -> list[str]:
    return [p[0] for p in bd if p[2] <= a <= p[3]]

BD = list[tuple[str, str, int, int]]

personas: BD = [

("Cervantes", "Literatura", 1547, 1616),

("Velazquez", "Pintura", 1599, 1660),

("Picasso", "Pintura", 1881, 1973),

("Beethoven", "Musica", 1770, 1823),

("Poincare", "Ciencia", 1854, 1912),

("Quevedo", "Literatura", 1580, 1654),

("Goya", "Pintura", 1746, 1828),

("Einstein", "Ciencia", 1879, 1955),

("Mozart", "Musica", 1756, 1791),

("Botticelli", "Pintura", 1445, 1510),

("Borromini", "Arquitectura", 1599, 1667),

("Bach", "Musica", 1685, 1750)]

def nombres(bd: BD) -> list[str]:

return [p[0] for p in bd]

def musicos(bd: BD) -> list[str]:

return [p[0] for p in bd if p[1] == "Musica"]

def seleccion(bd: BD, m: str) -> list[str]:

return [p[0] for p in bd if p[1] == m]

def musicos2(bd: BD) -> list[str]:

return seleccion(bd, "Musica")

def vivas(bd: BD, a: int) -> list[str]:

return [p[0] for p in bd if p[2] <= a <= p[3]]

El código se encuentra en GitHub.

Representación densa de polinomios

PorJosé A. Alonso 21-octubre-202214-diciembre-2022

Los polinomios pueden representarse de forma dispersa o densa. Por ejemplo, el polinomio 6x^4-5x^2+4x-7 se puede representar de forma dispersa por [6,0,-5,4,-7] y de forma densa por [(4,6),(2,-5),(1,4),(0,-7)].

Definir la función

   densa :: [Int] -> [(Int,Int)]

1	densa :: [Int] -> [(Int,Int)]

tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,

   densa [6,0,-5,4,-7]  ==  [(4,6),(2,-5),(1,4),(0,-7)]
   densa [6,0,0,3,0,4]  ==  [(5,6),(2,3),(0,4)]
   densa [0]            ==  [(0,0)]

densa [6,0,-5,4,-7] == [(4,6),(2,-5),(1,4),(0,-7)]

densa [6,0,0,3,0,4] == [(5,6),(2,3),(0,4)]

densa [0] == [(0,0)]

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

densa1 :: [Int] -> [(Int,Int)]
densa1 xs =
  [(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y /= 0]
  ++ [(0, last xs)]
  where n = length xs

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

densa2 :: [Int] -> [(Int,Int)]
densa2 xs =
  filter (\ (_,y) -> y /= 0) (zip [n-1,n-2..1] xs)
  ++ [(0, last xs)]
  where n = length xs

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

densa3 :: [Int] -> [(Int,Int)]
densa3 xs = filter ((/= 0) . snd) (zip [n-1,n-2..1] xs)
  ++ [(0, last xs)]
  where n = length xs

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

densa4 :: [Int] -> [(Int,Int)]
densa4 xs = aux xs (length xs - 1)
  where aux [y] 0 = [(0, y)]
        aux (y:ys) n | y == 0    = aux ys (n-1)
                     | otherwise = (n,y) : aux ys (n-1)

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

-- La propiedad es
prop_densa :: NonEmptyList Int -> Bool
prop_densa (NonEmpty xs) =
  all (== densa1 xs)
      [densa2 xs,
       densa3 xs,
       densa4 xs]

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

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

-- La comparación es
--    λ> last (densa1 [1..2*10^6])
--    (0,2000000)
--    (0.95 secs, 880,569,400 bytes)
--    λ> last (densa2 [1..2*10^6])
--    (0,2000000)
--    (0.52 secs, 800,569,432 bytes)
--    λ> last (densa3 [1..2*10^6])
--    (0,2000000)
--    (0.53 secs, 752,569,552 bytes)
--    λ> last (densa4 [1..2*10^6])
--    (0,2000000)
--    (3.05 secs, 1,267,842,032 bytes)
--
--    λ> last (densa1 [1..10^7])
--    (0,10000000)
--    (5.43 secs, 4,400,570,128 bytes)
--    λ> last (densa2 [1..10^7])
--    (0,10000000)
--    (3.03 secs, 4,000,570,160 bytes)
--    λ> last (densa3 [1..10^7])
--    (0,10000000)
--    (2.34 secs, 3,760,570,280 bytes)

import Test.QuickCheck

-- 1ª solución

-- ===========

densa1 :: [Int] -> [(Int,Int)]

densa1 xs =

[(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y /= 0]

++ [(0, last xs)]

where n = length xs

-- 2ª solución

-- ===========

densa2 :: [Int] -> [(Int,Int)]

densa2 xs =

filter (\ (_,y) -> y /= 0) (zip [n-1,n-2..1] xs)

++ [(0, last xs)]

where n = length xs

-- 3ª solución

-- ===========

densa3 :: [Int] -> [(Int,Int)]

densa3 xs = filter ((/= 0) . snd) (zip [n-1,n-2..1] xs)

++ [(0, last xs)]

where n = length xs

-- 4ª solución

-- ===========

densa4 :: [Int] -> [(Int,Int)]

densa4 xs = aux xs (length xs - 1)

where aux [y] 0 = [(0, y)]

aux (y:ys) n | y == 0 = aux ys (n-1)

| otherwise = (n,y) : aux ys (n-1)

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_densa :: NonEmptyList Int -> Bool

prop_densa (NonEmpty xs) =

all (== densa1 xs)

[densa2 xs,

densa3 xs,

densa4 xs]

-- La comprobación es

-- λ> quickCheck prop_densa

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> last (densa1 [1..2*10^6])

-- (0,2000000)

-- (0.95 secs, 880,569,400 bytes)

-- λ> last (densa2 [1..2*10^6])

-- (0,2000000)

-- (0.52 secs, 800,569,432 bytes)

-- λ> last (densa3 [1..2*10^6])

-- (0,2000000)

-- (0.53 secs, 752,569,552 bytes)

-- λ> last (densa4 [1..2*10^6])

-- (0,2000000)

-- (3.05 secs, 1,267,842,032 bytes)

-- λ> last (densa1 [1..10^7])

-- (0,10000000)

-- (5.43 secs, 4,400,570,128 bytes)

-- λ> last (densa2 [1..10^7])

-- (0,10000000)

-- (3.03 secs, 4,000,570,160 bytes)

-- λ> last (densa3 [1..10^7])

-- (0,10000000)

-- (2.34 secs, 3,760,570,280 bytes)

El código se encuentra en GitHub.

Soluciones en Python

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 densa1(xs: list[int]) -> list[tuple[int, int]]:
    n = len(xs)
    return [(x, y)
            for (x, y) in zip(range(n-1, 0, -1), xs)
            if y != 0] + [(0, xs[-1])]

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

def densa2(xs: list[int]) -> list[tuple[int, int]]:
    n = len(xs)
    return list(filter(lambda p: p[1] != 0,
                       zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])]

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

def densa3(xs: list[int]) -> list[tuple[int, int]]:
    def aux(ys: list[int], n: int) -> list[tuple[int, int]]:
        if n == 0:
            return [(0, ys[0])]
        if ys[0] == 0:
            return aux(ys[1:], n-1)
        return [(n, ys[0])] + aux(ys[1:], n-1)

    return aux(xs, len(xs) - 1)

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

# La propiedad es
@given(st.lists(st.integers(), min_size=1))
def test_densa(xs: list[int]) -> None:
    r = densa1(xs)
    assert densa2(xs) == r
    assert densa3(xs) == r

# La comprobación es
#    src> poetry run pytest -q representacion_densa_de_polinomios.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('densa1(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('densa2(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('densa3(range(1, 10**4))')
#    0.25 segundos
#
#    >>> tiempo('densa1(range(1, 10**7))')
#    1.87 segundos
#    >>> tiempo('densa2(range(1, 10**7))')
#    2.15 segundos

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 densa1(xs: list[int]) -> list[tuple[int, int]]:

n = len(xs)

return [(x, y)

for (x, y) in zip(range(n-1, 0, -1), xs)

if y != 0] + [(0, xs[-1])]

# 2ª solución

# ===========

def densa2(xs: list[int]) -> list[tuple[int, int]]:

n = len(xs)

return list(filter(lambda p: p[1] != 0,

zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])]

# 3ª solución

# ===========

def densa3(xs: list[int]) -> list[tuple[int, int]]:

def aux(ys: list[int], n: int) -> list[tuple[int, int]]:

if n == 0:

return [(0, ys[0])]

if ys[0] == 0:

return aux(ys[1:], n-1)

return [(n, ys[0])] + aux(ys[1:], n-1)

return aux(xs, len(xs) - 1)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers(), min_size=1))

def test_densa(xs: list[int]) -> None:

r = densa1(xs)

assert densa2(xs) == r

assert densa3(xs) == r

# La comprobación es

# src> poetry run pytest -q representacion_densa_de_polinomios.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('densa1(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('densa2(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('densa3(range(1, 10**4))')

# 0.25 segundos

# >>> tiempo('densa1(range(1, 10**7))')

# 1.87 segundos

# >>> tiempo('densa2(range(1, 10**7))')

# 2.15 segundos

El código se encuentra en GitHub

Suma de elementos consecutivos

PorJosé A. Alonso 20-octubre-202214-diciembre-2022

Definir la función

   sumaConsecutivos :: [Integer] -> [Integer]

1	sumaConsecutivos :: [Integer] -> [Integer]

tal que sumaConsecutivos xs es la suma de los pares de elementos consecutivos de la lista xs. Por ejemplo,

   sumaConsecutivos [3,1,5,2]  ==  [4,6,7]
   sumaConsecutivos [3]        ==  []
   last (sumaConsecutivos [1..10^8])  ==  199999999

sumaConsecutivos [3,1,5,2] == [4,6,7]

sumaConsecutivos [3] == []

last (sumaConsecutivos [1..10^8]) == 199999999

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

sumaConsecutivos1 :: [Integer] -> [Integer]
sumaConsecutivos1 xs = [x+y | (x,y) <- zip xs (tail xs)]

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

sumaConsecutivos2 :: [Integer] -> [Integer]
sumaConsecutivos2 xs = zipWith (+) xs (tail xs)

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

sumaConsecutivos3 :: [Integer] -> [Integer]
sumaConsecutivos3 = zipWith (+) <*> tail

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

sumaConsecutivos4 :: [Integer] -> [Integer]
sumaConsecutivos4 (x:y:zs) = x+y : sumaConsecutivos4 (y:zs)
sumaConsecutivos4 _        = []

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

-- La propiedad es
prop_sumaConsecutivos :: [Integer] -> Bool
prop_sumaConsecutivos xs =
  all (== sumaConsecutivos1 xs)
      [sumaConsecutivos2 xs,
       sumaConsecutivos3 xs,
       sumaConsecutivos4 xs]

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

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

-- La comparación es
--    λ> last (sumaConsecutivos1 [1..8*10^6])
--    15999999
--    (1.98 secs, 2,176,566,784 bytes)
--    λ> last (sumaConsecutivos2 [1..8*10^6])
--    15999999
--    (0.19 secs, 1,408,566,840 bytes)
--    λ> last (sumaConsecutivos3 [1..8*10^6])
--    15999999
--    (0.19 secs, 1,408,566,936 bytes)
--    λ> last (sumaConsecutivos4 [1..8*10^6])
--    15999999
--    (2.78 secs, 2,560,566,832 bytes)

import Test.QuickCheck

-- 1ª solución

-- ===========

sumaConsecutivos1 :: [Integer] -> [Integer]

sumaConsecutivos1 xs = [x+y | (x,y) <- zip xs (tail xs)]

-- 2ª solución

-- ===========

sumaConsecutivos2 :: [Integer] -> [Integer]

sumaConsecutivos2 xs = zipWith (+) xs (tail xs)

-- 3ª solución

-- ===========

sumaConsecutivos3 :: [Integer] -> [Integer]

sumaConsecutivos3 = zipWith (+) <*> tail

-- 4ª solución

-- ===========

sumaConsecutivos4 :: [Integer] -> [Integer]

sumaConsecutivos4 (x:y:zs) = x+y : sumaConsecutivos4 (y:zs)

sumaConsecutivos4 _ = []

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_sumaConsecutivos :: [Integer] -> Bool

prop_sumaConsecutivos xs =

all (== sumaConsecutivos1 xs)

[sumaConsecutivos2 xs,

sumaConsecutivos3 xs,

sumaConsecutivos4 xs]

-- La comprobación es

-- λ> quickCheck prop_sumaConsecutivos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> last (sumaConsecutivos1 [1..8*10^6])

-- 15999999

-- (1.98 secs, 2,176,566,784 bytes)

-- λ> last (sumaConsecutivos2 [1..8*10^6])

-- 15999999

-- (0.19 secs, 1,408,566,840 bytes)

-- λ> last (sumaConsecutivos3 [1..8*10^6])

-- 15999999

-- (0.19 secs, 1,408,566,936 bytes)

-- λ> last (sumaConsecutivos4 [1..8*10^6])

-- 15999999

-- (2.78 secs, 2,560,566,832 bytes)

El código se encuentra en GitHub.

Soluciones en Python

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
# ===========

def sumaConsecutivos1(xs: list[int]) -> list[int]:
    return [x + y for (x, y) in zip(xs, xs[1:])]

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

def sumaConsecutivos2(xs: list[int]) -> list[int]:
    return list(map(add, xs, xs[1:]))

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

def sumaConsecutivos3(xs: list[int]) -> list[int]:
    if len(xs) >= 2:
        return [xs[0] + xs[1]] + sumaConsecutivos3(xs[1:])
    return []

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

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=100)))
def test_sumaConsecutivos(xs: list[int]) -> None:
    r = sumaConsecutivos1(xs)
    assert sumaConsecutivos2(xs) == r
    assert sumaConsecutivos3(xs) == r

# La comprobación es
#    src> poetry run pytest -q suma_elementos_consecutivos.py
#    1 passed in 0.26s

# 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('sumaConsecutivos1(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('sumaConsecutivos2(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('sumaConsecutivos3(range(1, 10**4))')
#    0.18 segundos
#
#    >>> tiempo('sumaConsecutivos1(range(1, 10**8))')
#    8.34 segundos
#    >>> tiempo('sumaConsecutivos2(range(1, 10**8))')
#    6.28 segundos

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

# ===========

def sumaConsecutivos1(xs: list[int]) -> list[int]:

return [x + y for (x, y) in zip(xs, xs[1:])]

# 2ª solución

# ===========

def sumaConsecutivos2(xs: list[int]) -> list[int]:

return list(map(add, xs, xs[1:]))

# 3ª solución

# ===========

def sumaConsecutivos3(xs: list[int]) -> list[int]:

if len(xs) >= 2:

return [xs[0] + xs[1]] + sumaConsecutivos3(xs[1:])

return []

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers(min_value=1, max_value=100)))

def test_sumaConsecutivos(xs: list[int]) -> None:

r = sumaConsecutivos1(xs)

assert sumaConsecutivos2(xs) == r

assert sumaConsecutivos3(xs) == r

# La comprobación es

# src> poetry run pytest -q suma_elementos_consecutivos.py

# 1 passed in 0.26s

# 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('sumaConsecutivos1(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('sumaConsecutivos2(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('sumaConsecutivos3(range(1, 10**4))')

# 0.18 segundos

# >>> tiempo('sumaConsecutivos1(range(1, 10**8))')

# 8.34 segundos

# >>> tiempo('sumaConsecutivos2(range(1, 10**8))')

# 6.28 segundos

El código se encuentra en GitHub.

Producto escalar

PorJosé A. Alonso 19-octubre-202214-diciembre-2022

El producto escalar de dos listas de enteros xs y ys de longitud n viene dado por la suma de los productos de los elementos correspondientes.

Definir la función

   productoEscalar :: [Integer] -> [Integer] -> Integer

1	productoEscalar :: [Integer] -> [Integer] -> Integer

tal que productoEscalar xs ys es el producto escalar de las listas xs e ys. Por ejemplo,

   productoEscalar [1,2,3] [4,5,6]  ==  32

1	productoEscalar [1,2,3] [4,5,6] == 32

Soluciones

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

Soluciones en Haskell

import Numeric.LinearAlgebra ((<.>), vector)
import Test.QuickCheck (quickCheck)

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

productoEscalar1 :: [Integer] -> [Integer] -> Integer
productoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys]

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

productoEscalar2 :: [Integer] -> [Integer] -> Integer
productoEscalar2 xs ys = sum (zipWith (*) xs ys)

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

productoEscalar3 :: [Integer] -> [Integer] -> Integer
productoEscalar3 = (sum .) . zipWith (*)

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

productoEscalar4 :: [Integer] -> [Integer] -> Integer
productoEscalar4 [] _          = 0
productoEscalar4 _ []          = 0
productoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys

-- 5ª solución
-- ===========

productoEscalar5 :: [Integer] -> [Integer] -> Integer
productoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys
productoEscalar5 _ _           = 0

-- 6ª solución
-- ===========

productoEscalar6 :: [Integer] -> [Integer] -> Integer
productoEscalar6 xs ys =
  round (vector xs' <.> vector ys')
  where xs' = map fromIntegral xs
        ys' = map fromIntegral ys

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

-- La propiedad es
prop_productoEscalar :: [Integer] -> [Integer] -> Bool
prop_productoEscalar xs ys =
  all (== productoEscalar1 xs ys)
      [productoEscalar2 xs ys,
       productoEscalar3 xs ys,
       productoEscalar4 xs ys,
       productoEscalar5 xs ys,
       productoEscalar6 xs' ys']
  where n = min (length xs) (length ys)
        xs' = take n xs
        ys' = take n ys

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

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

-- La comparación es
--    λ> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.37 secs, 803,827,520 bytes)
--    λ> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.69 secs, 611,008,272 bytes)
--    λ> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.69 secs, 611,008,536 bytes)
--    λ> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.64 secs, 742,290,272 bytes)
--    λ> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.63 secs, 742,290,064 bytes)
--    λ> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.32 secs, 835,679,200 bytes)
--
--    λ> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (1.90 secs, 1,831,960,336 bytes)
--    λ> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (1.87 secs, 1,831,960,600 bytes)
--    λ> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (0.78 secs, 2,573,005,952 bytes)

import Numeric.LinearAlgebra ((<.>), vector)

import Test.QuickCheck (quickCheck)

-- 1ª solución

-- ===========

productoEscalar1 :: [Integer] -> [Integer] -> Integer

productoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys]

-- 2ª solución

-- ===========

productoEscalar2 :: [Integer] -> [Integer] -> Integer

productoEscalar2 xs ys = sum (zipWith (*) xs ys)

-- 3ª solución

-- ===========

productoEscalar3 :: [Integer] -> [Integer] -> Integer

productoEscalar3 = (sum .) . zipWith (*)

-- 4ª solución

-- ===========

productoEscalar4 :: [Integer] -> [Integer] -> Integer

productoEscalar4 [] _ = 0

productoEscalar4 _ [] = 0

productoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys

-- 5ª solución

-- ===========

productoEscalar5 :: [Integer] -> [Integer] -> Integer

productoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys

productoEscalar5 _ _ = 0

-- 6ª solución

-- ===========

productoEscalar6 :: [Integer] -> [Integer] -> Integer

productoEscalar6 xs ys =

round (vector xs' <.> vector ys')

where xs' = map fromIntegral xs

ys' = map fromIntegral ys

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_productoEscalar :: [Integer] -> [Integer] -> Bool

prop_productoEscalar xs ys =

all (== productoEscalar1 xs ys)

[productoEscalar2 xs ys,

productoEscalar3 xs ys,

productoEscalar4 xs ys,

productoEscalar5 xs ys,

productoEscalar6 xs' ys']

where n = min (length xs) (length ys)

xs' = take n xs

ys' = take n ys

-- La comprobación es

-- λ> quickCheck prop_productoEscalar

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (1.37 secs, 803,827,520 bytes)

-- λ> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (0.69 secs, 611,008,272 bytes)

-- λ> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (0.69 secs, 611,008,536 bytes)

-- λ> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (1.64 secs, 742,290,272 bytes)

-- λ> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (1.63 secs, 742,290,064 bytes)

-- λ> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (0.32 secs, 835,679,200 bytes)

-- λ> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1)

-- 6000000

-- (1.90 secs, 1,831,960,336 bytes)

-- λ> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1)

-- 6000000

-- (1.87 secs, 1,831,960,600 bytes)

-- λ> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1)

-- 6000000

-- (0.78 secs, 2,573,005,952 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import mul
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from numpy import dot

setrecursionlimit(10**6)

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

def productoEscalar1(xs: list[int], ys: list[int]) -> int:
    return sum(x * y for (x, y) in zip(xs, ys))

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

def productoEscalar2(xs: list[int], ys: list[int]) -> int:
    return sum(map(mul, xs, ys))

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

def productoEscalar3(xs: list[int], ys: list[int]) -> int:
    if xs and ys:
        return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:])
    return 0

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

def productoEscalar4(xs: list[int], ys: list[int]) -> int:
    return dot(xs, ys)

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

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=100)),
       st.lists(st.integers(min_value=1, max_value=100)))
def test_productoEscalar(xs: list[int], ys: list[int]) -> None:
    r = productoEscalar1(xs, ys)
    assert productoEscalar2(xs, ys) == r
    assert productoEscalar3(xs, ys) == r
    n = min(len(xs), len(ys))
    xs1 = xs[:n]
    ys1 = ys[:n]
    assert productoEscalar4(xs1, ys1) == r

# La comprobación es
#    src> poetry run pytest -q producto_escalar.py
#    1 passed in 0.37s

# 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('productoEscalar1([1]*(10**4), [1]*(10**4))')
#    0.00 segundos
#    >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))')
#    0.55 segundos
#
#    >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))')
#    0.60 segundos
#    >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))')
#    0.26 segundos
#    >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))')
#    1.73 segundos

from operator import mul

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from numpy import dot

setrecursionlimit(10**6)

# 1ª solución

# ===========

def productoEscalar1(xs: list[int], ys: list[int]) -> int:

return sum(x * y for (x, y) in zip(xs, ys))

# 2ª solución

# ===========

def productoEscalar2(xs: list[int], ys: list[int]) -> int:

return sum(map(mul, xs, ys))

# 3ª solución

# ===========

def productoEscalar3(xs: list[int], ys: list[int]) -> int:

if xs and ys:

return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:])

return 0

# 4ª solución

# ===========

def productoEscalar4(xs: list[int], ys: list[int]) -> int:

return dot(xs, ys)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers(min_value=1, max_value=100)),

st.lists(st.integers(min_value=1, max_value=100)))

def test_productoEscalar(xs: list[int], ys: list[int]) -> None:

r = productoEscalar1(xs, ys)

assert productoEscalar2(xs, ys) == r

assert productoEscalar3(xs, ys) == r

n = min(len(xs), len(ys))

xs1 = xs[:n]

ys1 = ys[:n]

assert productoEscalar4(xs1, ys1) == r

# La comprobación es

# src> poetry run pytest -q producto_escalar.py

# 1 passed in 0.37s

# 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('productoEscalar1([1]*(10**4), [1]*(10**4))')

# 0.00 segundos

# >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))')

# 0.55 segundos

# >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))')

# 0.60 segundos

# >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))')

# 0.26 segundos

# >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))')

# 1.73 segundos

El código se encuentra en GitHub.

Ternas pitagóricas con suma dada

PorJosé A. Alonso 18-octubre-202214-diciembre-2022

Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a²+b²=c². Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

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

1	ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

tal que ternasPitagoricas x es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

   ternasPitagoricas 12     == [(3,4,5)]
   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

ternasPitagoricas 12 == [(3,4,5)]

ternasPitagoricas 60 == [(10,24,26),(15,20,25)]

ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Soluciones

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

Soluciones en Haskell

import Data.List (nub,sort)
import Test.QuickCheck

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

ternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas1 x =
  [(a,b,c) | a <- [0..x],
             b <- [a+1..x],
             c <- [b+1..x],
             a^2 + b^2 == c^2,
             a+b+c == x]

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

ternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas2 x =
  [(a,b,c) | a <- [1..x],
             b <- [a+1..x-a],
             let c = x-a-b,
             a^2+b^2 == c^2]

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

-- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse
-- por
--    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,
-- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

ternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas3 x =
  nub [(d*a,d*b,d*c) | d <- [1..x],
                       x `mod` d == 0,
                       (a,b,c) <- aux (x `div` d)]
  where
    aux y = [(a,b,c) | m <- [2..limite],
                       n <- [1..m-1],
                       let [a,b] = sort [m^2 - n^2, 2*m*n],
                       let c = m^2 + n^2,
                       a+b+c == y]
      where limite = ceiling (sqrt (fromIntegral y))

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_ternasPitagoricas :: Positive Integer -> Bool
prop_ternasPitagoricas (Positive x) =
  all (== (ternasPitagoricas1 x))
      [ternasPitagoricas2 x,
       ternasPitagoricas3 x]

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

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

-- La comparación es
--    λ> ternasPitagoricas1 200
--    [(40,75,85)]
--    (1.90 secs, 2,404,800,856 bytes)
--    λ> ternasPitagoricas2 200
--    [(40,75,85)]
--    (0.06 secs, 19,334,232 bytes)
--    λ> ternasPitagoricas3 200
--    [(40,75,85)]
--    (0.01 secs, 994,224 bytes)
--
--    λ> ternasPitagoricas2 3000
--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]
--    (4.41 secs, 4,354,148,136 bytes)
--    λ> ternasPitagoricas3 3000
--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]
--    (0.05 secs, 17,110,360 bytes)

import Data.List (nub,sort)

import Test.QuickCheck

-- 1ª solución --

-- ===========

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

ternasPitagoricas1 x =

[(a,b,c) | a <- [0..x],

b <- [a+1..x],

c <- [b+1..x],

a^2 + b^2 == c^2,

a+b+c == x]

-- 2ª solución --

-- ===========

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

ternasPitagoricas2 x =

[(a,b,c) | a <- [1..x],

b <- [a+1..x-a],

let c = x-a-b,

a^2+b^2 == c^2]

-- 3ª solución --

-- ===========

-- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse

-- por

-- a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,

-- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

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

ternasPitagoricas3 x =

nub [(d*a,d*b,d*c) | d <- [1..x],

x `mod` d == 0,

(a,b,c) <- aux (x `div` d)]

where

aux y = [(a,b,c) | m <- [2..limite],

n <- [1..m-1],

let [a,b] = sort [m^2 - n^2, 2*m*n],

let c = m^2 + n^2,

a+b+c == y]

where limite = ceiling (sqrt (fromIntegral y))

-- Equivalencia de las definiciones

-- ================================

-- La propiedad es

prop_ternasPitagoricas :: Positive Integer -> Bool

prop_ternasPitagoricas (Positive x) =

all (== (ternasPitagoricas1 x))

[ternasPitagoricas2 x,

ternasPitagoricas3 x]

-- La comprobación es

-- λ> quickCheck prop_ternasPitagoricas

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> ternasPitagoricas1 200

-- [(40,75,85)]

-- (1.90 secs, 2,404,800,856 bytes)

-- λ> ternasPitagoricas2 200

-- [(40,75,85)]

-- (0.06 secs, 19,334,232 bytes)

-- λ> ternasPitagoricas3 200

-- [(40,75,85)]

-- (0.01 secs, 994,224 bytes)

-- λ> ternasPitagoricas2 3000

-- [(500,1200,1300),(600,1125,1275),(750,1000,1250)]

-- (4.41 secs, 4,354,148,136 bytes)

-- λ> ternasPitagoricas3 3000

-- [(500,1200,1300),(600,1125,1275),(750,1000,1250)]

-- (0.05 secs, 17,110,360 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import ceil, sqrt
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

def ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]:
    return [(a, b, c)
            for a in range(0, x+1)
            for b in range(a+1, x+1)
            for c in range(b+1, x+1)
            if a**2 + b**2 == c**2 and a + b + c == x]

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

def ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]:
    return [(a, b, c)
            for a in range(1, x+1)
            for b in range(a+1, x-a+1)
            for c in [x - a - b]
            if a**2 + b**2 == c**2]

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

# Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse
# por
#    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,
# con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

def ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]:
    def aux(y: int) -> list[tuple[int, int, int]]:
        return [(a, b, c)
                for m in range(2, 1 + ceil(sqrt(y)))
                for n in range(1, m)
                for a in [min(m**2 - n**2, 2*m*n)]
                for b in [max(m**2 - n**2, 2*m*n)]
                for c in [m**2 + n**2]
                if a+b+c == y]

    return list(set(((d*a, d*b, d*c)
                     for d in range(1, x+1)
                     for (a, b, c) in aux(x // d)
                     if x % d == 0)))

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

# La propiedad es
@given(st.integers(min_value=1, max_value=50))
def test_ternasPitagoricas(n: int) -> None:
    r = set(ternasPitagoricas1(n))
    assert set(ternasPitagoricas2(n)) == r
    assert set(ternasPitagoricas3(n)) == r

# La comprobación es
#    src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.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('ternasPitagoricas1(300)')
#    2.83 segundos
#    >>> tiempo('ternasPitagoricas2(300)')
#    0.01 segundos
#    >>> tiempo('ternasPitagoricas3(300)')
#    0.00 segundos
#
#    >>> tiempo('ternasPitagoricas2(3000)')
#    1.48 segundos
#    >>> tiempo('ternasPitagoricas3(3000)')
#    0.02 segundos

from math import ceil, sqrt

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución --

# ===========

def ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]:

return [(a, b, c)

for a in range(0, x+1)

for b in range(a+1, x+1)

for c in range(b+1, x+1)

if a**2 + b**2 == c**2 and a + b + c == x]

# 2ª solución --

# ===========

def ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]:

return [(a, b, c)

for a in range(1, x+1)

for b in range(a+1, x-a+1)

for c in [x - a - b]

if a**2 + b**2 == c**2]

# 3ª solución --

# ===========

# Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse

# por

# a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,

# con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

def ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]:

def aux(y: int) -> list[tuple[int, int, int]]:

return [(a, b, c)

for m in range(2, 1 + ceil(sqrt(y)))

for n in range(1, m)

for a in [min(m**2 - n**2, 2*m*n)]

for b in [max(m**2 - n**2, 2*m*n)]

for c in [m**2 + n**2]

if a+b+c == y]

return list(set(((d*a, d*b, d*c)

for d in range(1, x+1)

for (a, b, c) in aux(x // d)

if x % d == 0)))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=50))

def test_ternasPitagoricas(n: int) -> None:

r = set(ternasPitagoricas1(n))

assert set(ternasPitagoricas2(n)) == r

assert set(ternasPitagoricas3(n)) == r

# La comprobación es

# src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.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('ternasPitagoricas1(300)')

# 2.83 segundos

# >>> tiempo('ternasPitagoricas2(300)')

# 0.01 segundos

# >>> tiempo('ternasPitagoricas3(300)')

# 0.00 segundos

# >>> tiempo('ternasPitagoricas2(3000)')

# 1.48 segundos

# >>> tiempo('ternasPitagoricas3(3000)')

# 0.02 segundos

El código se encuentra en GitHub.

Ternas pitagóricas

PorJosé A. Alonso 17-octubre-202214-diciembre-2022

Una terna (x,y,z) de enteros positivos es pitagórica si x² + y² = z² y x < y < z.

Definir la función

   pitagoricas :: Int -> [(Int,Int,Int)]

1	pitagoricas :: Int -> [(Int,Int,Int)]

tal que pitagoricas n es la lista de todas las ternas pitagóricas cuyas componentes están entre 1 y n. Por ejemplo,

   pitagoricas 10  ==  [(3,4,5),(6,8,10)]
   pitagoricas 15  ==  [(3,4,5),(5,12,13),(6,8,10),(9,12,15)]

1 2	pitagoricas 10 == [(3,4,5),(6,8,10)] pitagoricas 15 == [(3,4,5),(5,12,13),(6,8,10),(9,12,15)]

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

pitagoricas1 :: Int -> [(Int,Int,Int)]
pitagoricas1 n = [(x,y,z) | x <- [1..n]
                          , y <- [1..n]
                          , z <- [1..n]
                          , x^2 + y^2 == z^2
                          , x < y && y < z]

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

pitagoricas2 :: Int -> [(Int,Int,Int)]
pitagoricas2 n = [(x,y,z) | x <- [1..n]
                          , y <- [x+1..n]
                          , z <- [ceiling (sqrt (fromIntegral (x^2+y^2)))..n]
                          , x^2 + y^2 == z^2]

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

pitagoricas3 :: Int -> [(Int,Int,Int)]
pitagoricas3 n = [(x,y,z) | x <- [1..n]
                          , y <- [x+1..n]
                          , let z = round (sqrt (fromIntegral (x^2+y^2)))
                          , y < z
                          , z <= n
                          , x^2 + y^2 == z^2]

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

-- La propiedad es
prop_pitagoricas :: Positive Int -> Bool
prop_pitagoricas (Positive n) =
  all (== pitagoricas1 n)
      [pitagoricas2 n,
       pitagoricas3 n]

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

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

-- La comparación es
--    λ> length (pitagoricas1 200)
--    127
--    (12.25 secs, 12,680,320,400 bytes)
--    λ> length (pitagoricas2 200)
--    127
--    (1.61 secs, 1,679,376,824 bytes)
--    λ> length (pitagoricas3 200)
--    127
--    (0.06 secs, 55,837,072 bytes)

import Test.QuickCheck

-- 1ª solución

-- ===========

pitagoricas1 :: Int -> [(Int,Int,Int)]

pitagoricas1 n = [(x,y,z) | x <- [1..n]

, y <- [1..n]

, z <- [1..n]

, x^2 + y^2 == z^2

, x < y && y < z]

-- 2ª solución

-- ===========

pitagoricas2 :: Int -> [(Int,Int,Int)]

pitagoricas2 n = [(x,y,z) | x <- [1..n]

, y <- [x+1..n]

, z <- [ceiling (sqrt (fromIntegral (x^2+y^2)))..n]

, x^2 + y^2 == z^2]

-- 3ª solución

-- ===========

pitagoricas3 :: Int -> [(Int,Int,Int)]

pitagoricas3 n = [(x,y,z) | x <- [1..n]

, y <- [x+1..n]

, let z = round (sqrt (fromIntegral (x^2+y^2)))

, y < z

, z <= n

, x^2 + y^2 == z^2]

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_pitagoricas :: Positive Int -> Bool

prop_pitagoricas (Positive n) =

all (== pitagoricas1 n)

[pitagoricas2 n,

pitagoricas3 n]

-- La comprobación es

-- λ> quickCheck prop_pitagoricas

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (pitagoricas1 200)

-- 127

-- (12.25 secs, 12,680,320,400 bytes)

-- λ> length (pitagoricas2 200)

-- 127

-- (1.61 secs, 1,679,376,824 bytes)

-- λ> length (pitagoricas3 200)

-- 127

-- (0.06 secs, 55,837,072 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import ceil, sqrt
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

def pitagoricas1(n: int) -> list[tuple[int, int, int]]:
    return [(x, y, z)
            for x in range(1, n+1)
            for y in range(1, n+1)
            for z in range(1, n+1)
            if x**2 + y**2 == z**2 and x < y < z]

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

def pitagoricas2(n: int) -> list[tuple[int, int, int]]:
    return [(x, y, z)
            for x in range(1, n+1)
            for y in range(x+1, n+1)
            for z in range(ceil(sqrt(x**2+y**2)), n+1)
            if x**2 + y**2 == z**2]

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

def pitagoricas3(n: int) -> list[tuple[int, int, int]]:
    return [(x, y, z)
            for x in range(1, n+1)
            for y in range(x+1, n+1)
            for z in [ceil(sqrt(x**2+y**2))]
            if y < z <= n and x**2 + y**2 == z**2]

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

# La propiedad es
@given(st.integers(min_value=1, max_value=50))
def test_pitagoricas(n: int) -> None:
    r = pitagoricas1(n)
    assert pitagoricas2(n) == r
    assert pitagoricas3(n) == r

# La comprobación es
#    src> poetry run pytest -q ternas_pitagoricas.py
#    1 passed in 1.83s

# Comparación de eficiencia de pitagoricas
# ======================================

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('pitagoricas1(200)')
#    4.76 segundos
#    >>> tiempo('pitagoricas2(200)')
#    0.69 segundos
#    >>> tiempo('pitagoricas3(200)')
#    0.02 segundos

from math import ceil, sqrt

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución

# ===========

def pitagoricas1(n: int) -> list[tuple[int, int, int]]:

return [(x, y, z)

for x in range(1, n+1)

for y in range(1, n+1)

for z in range(1, n+1)

if x**2 + y**2 == z**2 and x < y < z]

# 2ª solución

# ===========

def pitagoricas2(n: int) -> list[tuple[int, int, int]]:

return [(x, y, z)

for x in range(1, n+1)

for y in range(x+1, n+1)

for z in range(ceil(sqrt(x**2+y**2)), n+1)

if x**2 + y**2 == z**2]

# 3ª solución

# ===========

def pitagoricas3(n: int) -> list[tuple[int, int, int]]:

return [(x, y, z)

for x in range(1, n+1)

for y in range(x+1, n+1)

for z in [ceil(sqrt(x**2+y**2))]

if y < z <= n and x**2 + y**2 == z**2]

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=50))

def test_pitagoricas(n: int) -> None:

r = pitagoricas1(n)

assert pitagoricas2(n) == r

assert pitagoricas3(n) == r

# La comprobación es

# src> poetry run pytest -q ternas_pitagoricas.py

# 1 passed in 1.83s

# Comparación de eficiencia de pitagoricas

# ======================================

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('pitagoricas1(200)')

# 4.76 segundos

# >>> tiempo('pitagoricas2(200)')

# 0.69 segundos

# >>> tiempo('pitagoricas3(200)')

# 0.02 segundos

El código se encuentra en GitHub.

Cálculo del número π mediante la fórmula de Leibniz

PorJosé A. Alonso 14-octubre-202214-diciembre-2022

El número π puede calcularse con la fórmula de Leibniz

   π/4 = 1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1) + ...

1	π/4 = 1 - 1/3 + 1/5 - 1/7 + ...+ (-1)*n/(2n+1) + ...

Definir las funciones

   calculaPi :: Int -> Double
   errorPi   :: Double -> Int

1 2	calculaPi :: Int -> Double errorPi :: Double -> Int

tales que

calculaPi n es la aproximación del número π calculada mediante la expresión

     4*(1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1))

1	4(1 - 1/3 + 1/5 - 1/7 + ...+ (-1)n/(2n+1))

Por ejemplo,

     calculaPi 3    ==  2.8952380952380956
     calculaPi 300  ==  3.1449149035588526

1 2	calculaPi 3 == 2.8952380952380956 calculaPi 300 == 3.1449149035588526

errorPi x es el menor número de términos de la serie necesarios para obtener pi con un error menor que x. Por ejemplo,

     errorPi 0.1    ==    9
     errorPi 0.01   ==   99
     errorPi 0.001  ==  999

errorPi 0.1 == 9

errorPi 0.01 == 99

errorPi 0.001 == 999

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

-- 1ª definición de calculaPi
-- ==========================

calculaPi1 :: Int -> Double
calculaPi1 k = 4 * sum [(-1)**n/(2*n+1) | n <- [0..k']]
  where k' = fromIntegral k

-- 2ª definición de calculaPi
-- ==========================

calculaPi2 :: Int -> Double
calculaPi2 0 = 4
calculaPi2 n = calculaPi2 (n-1) + 4*(-1)**n'/(2*n'+1)
  where n' = fromIntegral n

-- 3ª definición de calculaPi
-- ==========================

calculaPi3 :: Int -> Double
calculaPi3 = aux . fromIntegral
  where aux 0 = 4
        aux n = 4*(-1)**n/(2*n+1) + aux (n-1)

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

-- La propiedad es
prop_calculaPi :: Positive Int -> Bool
prop_calculaPi (Positive k) =
  all (== calculaPi1 k)
      [calculaPi2 k,
       calculaPi3 k]

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

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

-- La comparación es
--    λ> calculaPi1 (10^6)
--    3.1415936535887745
--    (1.31 secs, 609,797,408 bytes)
--    λ> calculaPi2 (10^6)
--    3.1415936535887745
--    (1.68 secs, 723,032,272 bytes)
--    λ> calculaPi3 (10^6)
--    3.1415936535887745
--    (2.22 secs, 1,099,032,608 bytes)


-- 1ª definición de errorPi
-- ========================

errorPi1 :: Double -> Int
errorPi1 x =
  head [n | n <- [1..]
          , abs (pi - calculaPi1 n) < x]

-- 2ª definición de errorPi
-- ========================

errorPi2 :: Double -> Int
errorPi2 x = aux 1
  where aux n | abs (pi - calculaPi1 n) < x = n
              | otherwise                   = aux (n+1)

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

-- La propiedad es
prop_errorPi :: Positive Double -> Bool
prop_errorPi (Positive x) =
  errorPi1 x == errorPi2 x

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

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

-- La comparación es
--    λ> errorPi1 0.0005
--    1999
--    (1.88 secs, 1,189,226,384 bytes)
--    λ> errorPi2 0.0005
--    1999
--    (1.87 secs, 1,213,341,096 bytes)

import Test.QuickCheck

-- 1ª definición de calculaPi

-- ==========================

calculaPi1 :: Int -> Double

calculaPi1 k = 4 * sum [(-1)**n/(2*n+1) | n <- [0..k']]

where k' = fromIntegral k

-- 2ª definición de calculaPi

-- ==========================

calculaPi2 :: Int -> Double

calculaPi2 0 = 4

calculaPi2 n = calculaPi2 (n-1) + 4*(-1)**n'/(2*n'+1)

where n' = fromIntegral n

-- 3ª definición de calculaPi

-- ==========================

calculaPi3 :: Int -> Double

calculaPi3 = aux . fromIntegral

where aux 0 = 4

aux n = 4*(-1)**n/(2*n+1) + aux (n-1)

-- Comprobación de equivalencia de calculaPi

-- =========================================

-- La propiedad es

prop_calculaPi :: Positive Int -> Bool

prop_calculaPi (Positive k) =

all (== calculaPi1 k)

[calculaPi2 k,

calculaPi3 k]

-- La comprobación es

-- λ> quickCheck prop_calculaPi

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de calculaPi

-- ======================================

-- La comparación es

-- λ> calculaPi1 (10^6)

-- 3.1415936535887745

-- (1.31 secs, 609,797,408 bytes)

-- λ> calculaPi2 (10^6)

-- 3.1415936535887745

-- (1.68 secs, 723,032,272 bytes)

-- λ> calculaPi3 (10^6)

-- 3.1415936535887745

-- (2.22 secs, 1,099,032,608 bytes)

-- 1ª definición de errorPi

-- ========================

errorPi1 :: Double -> Int

errorPi1 x =

head [n | n <- [1..]

, abs (pi - calculaPi1 n) < x]

-- 2ª definición de errorPi

-- ========================

errorPi2 :: Double -> Int

errorPi2 x = aux 1

where aux n | abs (pi - calculaPi1 n) < x = n

| otherwise = aux (n+1)

-- Comprobación de equivalencia de errorPi

-- ============================================

-- La propiedad es

prop_errorPi :: Positive Double -> Bool

prop_errorPi (Positive x) =

errorPi1 x == errorPi2 x

-- La comprobación es

-- λ> quickCheck prop_errorPi

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de errorPi

-- ====================================

-- La comparación es

-- λ> errorPi1 0.0005

-- 1999

-- (1.88 secs, 1,189,226,384 bytes)

-- λ> errorPi2 0.0005

-- 1999

-- (1.87 secs, 1,213,341,096 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from itertools import islice
from math import pi
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ª definición de calculaPi
# ==========================

def calculaPi1(k: int) -> float:
    return 4 * sum(((-1)**n/(2*n+1) for n in range(0, k+1)))

# 2ª definición de calculaPi
# ==========================

def calculaPi2(n: int) -> float:
    if n == 0:
        return 4
    return calculaPi2(n-1) + 4*(-1)**n/(2*n+1)

# 3ª definición de calculaPi
# ==========================

def calculaPi3(n: int) -> float:
    r = 1
    for k in range(1, n+1):
        r = r + (-1)**k/(2*k+1)
    return 4 * r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=100))
def test_calculaPi(n: int) -> None:
    r = calculaPi1(n)
    assert calculaPi2(n) == r
    assert calculaPi3(n) == r

# La comprobación es
#    src> poetry run pytest -q calculo_de_pi_mediante_la_formula_de_Leibniz.py
#    1 passed in 0.14s

# Comparación de eficiencia de calculaPi
# ======================================

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('calculaPi1(10**6)')
#    0.37 segundos
#    >>> tiempo('calculaPi2(10**6)')
#    Process Python violación de segmento (core dumped)
#    >>> tiempo('calculaPi3(10**6)')
#    0.39 segundos

# 1ª definición de errorPi
# ========================

# 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 errorPi1(x: float) -> int:
    return list(islice((n for n in naturales()
                        if abs(pi - calculaPi1(n)) < x), 1))[0]

# 2ª definición de errorPi
# ========================

def errorPi2(x: float) -> int:
    def aux(n: int) -> int:
        if abs(pi - calculaPi1(n)) < x:
            return n
        return aux(n + 1)

    return aux(1)

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

@given(st.integers(min_value=1, max_value=100))
def test_errorPi(n: int) -> None:
    assert errorPi1(n) == errorPi2(n)

# La comprobación es
#    src> poetry run pytest -q calculo_de_pi_mediante_la_formula_de_Leibniz.py
#    2 passed in 0.60s

# Comparación de eficiencia de errorPi
# ====================================

# La comparación es
#    >>> tiempo('errorPi1(0.0005)')
#    0.63 segundos
#    >>> tiempo('errorPi2(0.0005)')
#    0.58 segundos

100

101

102

103

104

105

106

107

108

109

110

111

from itertools import islice

from math import pi

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ª definición de calculaPi

# ==========================

def calculaPi1(k: int) -> float:

return 4 * sum(((-1)**n/(2*n+1) for n in range(0, k+1)))

# 2ª definición de calculaPi

# ==========================

def calculaPi2(n: int) -> float:

if n == 0:

return 4

return calculaPi2(n-1) + 4*(-1)**n/(2*n+1)

# 3ª definición de calculaPi

# ==========================

def calculaPi3(n: int) -> float:

r = 1

for k in range(1, n+1):

r = r + (-1)**k/(2*k+1)

return 4 * r

# Comprobación de equivalencia de calculaPi

# =========================================

# La propiedad es

@given(st.integers(min_value=1, max_value=100))

def test_calculaPi(n: int) -> None:

r = calculaPi1(n)

assert calculaPi2(n) == r

assert calculaPi3(n) == r

# La comprobación es

# src> poetry run pytest -q calculo_de_pi_mediante_la_formula_de_Leibniz.py

# 1 passed in 0.14s

# Comparación de eficiencia de calculaPi

# ======================================

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('calculaPi1(10**6)')

# 0.37 segundos

# >>> tiempo('calculaPi2(10**6)')

# Process Python violación de segmento (core dumped)

# >>> tiempo('calculaPi3(10**6)')

# 0.39 segundos

# 1ª definición de errorPi

# ========================

# 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 errorPi1(x: float) -> int:

return list(islice((n for n in naturales()

if abs(pi - calculaPi1(n)) < x), 1))[0]

# 2ª definición de errorPi

# ========================

def errorPi2(x: float) -> int:

def aux(n: int) -> int:

if abs(pi - calculaPi1(n)) < x:

return n

return aux(n + 1)

return aux(1)

# Comprobación de equivalencia de errorPi

# =======================================

@given(st.integers(min_value=1, max_value=100))

def test_errorPi(n: int) -> None:

assert errorPi1(n) == errorPi2(n)

# La comprobación es

# src> poetry run pytest -q calculo_de_pi_mediante_la_formula_de_Leibniz.py

# 2 passed in 0.60s

# Comparación de eficiencia de errorPi

# ====================================

# La comparación es

# >>> tiempo('errorPi1(0.0005)')

# 0.63 segundos

# >>> tiempo('errorPi2(0.0005)')

# 0.58 segundos

El código se encuentra en GitHub.

Aproximación al límite de sen(x)/x cuando x tiende a cero

PorJosé A. Alonso 13-octubre-202214-diciembre-2022

El limite de sen(x)/x, cuando x tiende a cero, se puede calcular como el límite de la sucesión sen(1/n)/(1/n), cuando n tiende a infinito.

Definir las funciones

   aproxLimSeno :: Int -> [Double]
   errorLimSeno :: Double -> Int

1 2	aproxLimSeno :: Int -> [Double] errorLimSeno :: Double -> Int

tales que

aproxLimSeno n es la lista de los n primeros términos de la sucesión sen(1/m)/(1/m). Por ejemplo,

     aproxLimSeno 1 == [0.8414709848078965]
     aproxLimSeno 2 == [0.8414709848078965,0.958851077208406]

1 2	aproxLimSeno 1 == [0.8414709848078965] aproxLimSeno 2 == [0.8414709848078965,0.958851077208406]

errorLimSeno x es el menor número de términos de la sucesión sen(1/m)/(1/m) necesarios para obtener su límite con un error menor que x. Por ejemplo,

     errorLimSeno 0.1     ==   2
     errorLimSeno 0.01    ==   5
     errorLimSeno 0.001   ==  13
     errorLimSeno 0.0001  ==  41

errorLimSeno 0.1 == 2

errorLimSeno 0.01 == 5

errorLimSeno 0.001 == 13

errorLimSeno 0.0001 == 41

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

-- 1ª definición de aproxLimSeno
-- =============================

aproxLimSeno1 :: Int -> [Double]
aproxLimSeno1 k = [sin(1/n)/(1/n) | n <- [1..k']]
  where k' = fromIntegral k

-- 2ª definición de aproxLimSeno
-- =============================

aproxLimSeno2 :: Int -> [Double]
aproxLimSeno2 0 = []
aproxLimSeno2 n = aproxLimSeno2 (n-1) ++ [sin(1/n')/(1/n')]
  where n' = fromIntegral n

-- 3ª definición de aproxLimSeno
-- =============================

aproxLimSeno3 :: Int -> [Double]
aproxLimSeno3 = reverse . aux . fromIntegral
  where aux 0 = []
        aux n = sin(1/n)/(1/n) : aux (n-1)

-- 4ª definición de aproxLimSeno
-- =============================

aproxLimSeno4 :: Int -> [Double]
aproxLimSeno4 k = aux [] (fromIntegral k)
  where aux xs 0 = xs
        aux xs n = aux (sin(1/n)/(1/n) : xs) (n-1)

-- 5ª definición de aproxLimSeno
-- =============================

aproxLimSeno5 :: Int -> [Double]
aproxLimSeno5 k =  map (\ n -> sin(1/n)/(1/n)) [1..k']
  where k' = fromIntegral k

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

-- La propiedad es
prop_aproxLimSeno :: Positive Int -> Bool
prop_aproxLimSeno (Positive k) =
  all (== aproxLimSeno1 k)
      [aproxLimSeno2 k,
       aproxLimSeno3 k,
       aproxLimSeno4 k,
       aproxLimSeno5 k]

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

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

-- La comparación es
--    λ> last (aproxLimSeno1 (2*10^4))
--    0.9999999995833334
--    (0.01 secs, 5,415,816 bytes)
--    λ> last (aproxLimSeno2 (2*10^4))
--    0.9999999995833334
--    (4.48 secs, 17,514,768,064 bytes)
--    λ> last (aproxLimSeno3 (2*10^4))
--    0.9999999995833334
--    (0.02 secs, 9,530,120 bytes)
--    λ> last (aproxLimSeno4 (2*10^4))
--    0.9999999995833334
--    (0.02 secs, 9,529,968 bytes)
--    λ> last (aproxLimSeno5 (2*10^4))
--    0.9999999995833334
--    (0.01 secs, 4,889,720 bytes)
--
--    λ> last (aproxLimSeno1 (2*10^6))
--    0.9999999999999583
--    (0.46 secs, 480,569,808 bytes)
--    λ> last (aproxLimSeno3 (2*10^6))
--    0.9999999999999583
--    (1.96 secs, 896,569,992 bytes)
--    λ> last (aproxLimSeno4 (2*10^6))
--    0.9999999999999583
--    (1.93 secs, 896,570,048 bytes)
--    λ> last (aproxLimSeno5 (2*10^6))
--    0.9999999999999583
--    (0.05 secs, 432,569,800 bytes)
--
--    λ> last (aproxLimSeno1 (10^7))
--    0.9999999999999983
--    (2.26 secs, 2,400,569,760 bytes)
--    λ> last (aproxLimSeno5 (10^7))
--    0.9999999999999983
--    (0.24 secs, 2,160,569,752 bytes)

-- 1ª definición de errorLimSeno
-- =============================

errorLimSeno1 :: Double -> Int
errorLimSeno1 x =
  round (head [m | m <- [1..], abs (1 - sin(1/m)/(1/m)) < x])

-- 2ª definición de errorLimSeno
-- =============================

errorLimSeno2 :: Double -> Int
errorLimSeno2 x = aux 1
  where aux n | abs (1 - sin(1/n)/(1/n)) < x = round n
              | otherwise                    = aux (n+1)

-- 3ª definición de errorLimSeno
-- =============================

errorLimSeno3 :: Double -> Int
errorLimSeno3 x =
  round (head (dropWhile (\ n -> abs (1 - sin(1/n)/(1/n)) >= x) [1..]))

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

-- La propiedad es
prop_errorLimSeno :: Positive Double -> Bool
prop_errorLimSeno (Positive x) =
  all (== errorLimSeno1 x)
      [errorLimSeno2 x,
       errorLimSeno3 x]

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

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

-- La comparación es
--    λ> errorLimSeno1 (10**(-12))
--    408230
--    (0.41 secs, 206,300,808 bytes)
--    λ> errorLimSeno2 (10**(-12))
--    408230
--    (0.46 secs, 225,895,672 bytes)
--    λ> errorLimSeno3 (10**(-12))
--    408230
--    (0.37 secs, 186,705,688 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

import Test.QuickCheck

-- 1ª definición de aproxLimSeno

-- =============================

aproxLimSeno1 :: Int -> [Double]

aproxLimSeno1 k = [sin(1/n)/(1/n) | n <- [1..k']]

where k' = fromIntegral k

-- 2ª definición de aproxLimSeno

-- =============================

aproxLimSeno2 :: Int -> [Double]

aproxLimSeno2 0 = []

aproxLimSeno2 n = aproxLimSeno2 (n-1) ++ [sin(1/n')/(1/n')]

where n' = fromIntegral n

-- 3ª definición de aproxLimSeno

-- =============================

aproxLimSeno3 :: Int -> [Double]

aproxLimSeno3 = reverse . aux . fromIntegral

where aux 0 = []

aux n = sin(1/n)/(1/n) : aux (n-1)

-- 4ª definición de aproxLimSeno

-- =============================

aproxLimSeno4 :: Int -> [Double]

aproxLimSeno4 k = aux [] (fromIntegral k)

where aux xs 0 = xs

aux xs n = aux (sin(1/n)/(1/n) : xs) (n-1)

-- 5ª definición de aproxLimSeno

-- =============================

aproxLimSeno5 :: Int -> [Double]

aproxLimSeno5 k = map (\ n -> sin(1/n)/(1/n)) [1..k']

where k' = fromIntegral k

-- Comprobación de equivalencia de aproxLimSeno

-- ============================================

-- La propiedad es

prop_aproxLimSeno :: Positive Int -> Bool

prop_aproxLimSeno (Positive k) =

all (== aproxLimSeno1 k)

[aproxLimSeno2 k,

aproxLimSeno3 k,

aproxLimSeno4 k,

aproxLimSeno5 k]

-- La comprobación es

-- λ> quickCheck prop_aproxLimSeno

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de aproxLimSeno

-- =========================================

-- La comparación es

-- λ> last (aproxLimSeno1 (2*10^4))

-- 0.9999999995833334

-- (0.01 secs, 5,415,816 bytes)

-- λ> last (aproxLimSeno2 (2*10^4))

-- 0.9999999995833334

-- (4.48 secs, 17,514,768,064 bytes)

-- λ> last (aproxLimSeno3 (2*10^4))

-- 0.9999999995833334

-- (0.02 secs, 9,530,120 bytes)

-- λ> last (aproxLimSeno4 (2*10^4))

-- 0.9999999995833334

-- (0.02 secs, 9,529,968 bytes)

-- λ> last (aproxLimSeno5 (2*10^4))

-- 0.9999999995833334

-- (0.01 secs, 4,889,720 bytes)

-- λ> last (aproxLimSeno1 (2*10^6))

-- 0.9999999999999583

-- (0.46 secs, 480,569,808 bytes)

-- λ> last (aproxLimSeno3 (2*10^6))

-- 0.9999999999999583

-- (1.96 secs, 896,569,992 bytes)

-- λ> last (aproxLimSeno4 (2*10^6))

-- 0.9999999999999583

-- (1.93 secs, 896,570,048 bytes)

-- λ> last (aproxLimSeno5 (2*10^6))

-- 0.9999999999999583

-- (0.05 secs, 432,569,800 bytes)

-- λ> last (aproxLimSeno1 (10^7))

-- 0.9999999999999983

-- (2.26 secs, 2,400,569,760 bytes)

-- λ> last (aproxLimSeno5 (10^7))

-- 0.9999999999999983

-- (0.24 secs, 2,160,569,752 bytes)

-- 1ª definición de errorLimSeno

-- =============================

errorLimSeno1 :: Double -> Int

errorLimSeno1 x =

round (head [m | m <- [1..], abs (1 - sin(1/m)/(1/m)) < x])

-- 2ª definición de errorLimSeno

-- =============================

errorLimSeno2 :: Double -> Int

errorLimSeno2 x = aux 1

where aux n | abs (1 - sin(1/n)/(1/n)) < x = round n

| otherwise = aux (n+1)

-- 3ª definición de errorLimSeno

-- =============================

errorLimSeno3 :: Double -> Int

errorLimSeno3 x =

round (head (dropWhile (\ n -> abs (1 - sin(1/n)/(1/n)) >= x) [1..]))

-- Comprobación de equivalencia de errorLimSeno

-- ============================================

-- La propiedad es

prop_errorLimSeno :: Positive Double -> Bool

prop_errorLimSeno (Positive x) =

all (== errorLimSeno1 x)

[errorLimSeno2 x,

errorLimSeno3 x]

-- La comprobación es

-- λ> quickCheck prop_errorLimSeno

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de errorLimSeno

-- =========================================

-- La comparación es

-- λ> errorLimSeno1 (10**(-12))

-- 408230

-- (0.41 secs, 206,300,808 bytes)

-- λ> errorLimSeno2 (10**(-12))

-- 408230

-- (0.46 secs, 225,895,672 bytes)

-- λ> errorLimSeno3 (10**(-12))

-- 408230

-- (0.37 secs, 186,705,688 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from itertools import dropwhile, islice
from math import sin
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ª definición de aproxLimSeno
# =============================

def aproxLimSeno1(k: int) -> list[float]:
    return [sin(1/n)/(1/n) for n in range(1, k + 1)]

# 2ª definición de aproxLimSeno
# =============================

def aproxLimSeno2(n: int) -> list[float]:
    if n == 0:
        return []
    return aproxLimSeno2(n - 1) + [sin(1/n)/(1/n)]

# 3ª definición de aproxLimSeno
# =============================

def aproxLimSeno3(n: int) -> list[float]:
    def aux(n: int) -> list[float]:
        if n == 0:
            return []
        return [sin(1/n)/(1/n)] + aux(n - 1)

    return list(reversed(aux(n)))

# 4ª definición de aproxLimSeno
# =============================

def aproxLimSeno4(n: int) -> list[float]:
    def aux(xs: list[float], n: int) -> list[float]:
        if n == 0:
            return xs
        return aux([sin(1/n)/(1/n)] + xs, n - 1)

    return aux([], n)

# 5ª definición de aproxLimSeno
# =============================

def aproxLimSeno5(n: int) -> list[float]:
    return list(map((lambda k: sin(1/k)/(1/k)), range(1, n+1)))

# 6ª definición de aproxLimSeno
# =============================

def aproxLimSeno6(n: int) -> list[float]:
    r = []
    for k in range(1, n+1):
        r.append(sin(1/k)/(1/k))
    return r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=100))
def test_aproxLimSeno(n: int) -> None:
    r = aproxLimSeno1(n)
    assert aproxLimSeno2(n) == r
    assert aproxLimSeno3(n) == r
    assert aproxLimSeno4(n) == r
    assert aproxLimSeno5(n) == r
    assert aproxLimSeno6(n) == r

# La comprobación es
#    src> poetry run pytest -q limite_del_seno.py
#    1 passed in 0.60s

# Comparación de eficiencia de aproxLimSeno
# =========================================

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('aproxLimSeno1(3*10**5)')
#    0.03 segundos
#    >>> tiempo('aproxLimSeno2(3*10**5)')
#    Process Python violación de segmento (core dumped)
#    >>> tiempo('aproxLimSeno3(3*10**5)')
#    Process Python violación de segmento (core dumped)
#    >>> tiempo('aproxLimSeno4(3*10**5)')
#    Process Python violación de segmento (core dumped)
#    >>> tiempo('aproxLimSeno5(3*10**5)')
#    0.04 segundos
#    >>> tiempo('aproxLimSeno6(3*10**5)')
#    0.07 segundos
#
#    >>> tiempo('aproxLimSeno1(10**7)')
#    1.29 segundos
#    >>> tiempo('aproxLimSeno5(10**7)')
#    1.40 segundos
#    >>> tiempo('aproxLimSeno6(10**7)')
#    1.45 segundos

# 1ª definición de errorLimSeno
# ============================

# 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 errorLimSeno1(x: float) -> int:
    return list(islice((n for n in naturales()
                        if abs(1 - sin(1/n)/(1/n)) < x), 1))[0]

# 2ª definición de errorLimSeno
# ============================

def errorLimSeno2(x: float) -> int:
    def aux(n: int) -> int:
        if abs(1 - sin(1/n)/(1/n)) < x:
            return n
        return aux(n + 1)

    return aux(1)

# 3ª definición de errorLimSeno
# ============================

def errorLimSeno3(x: float) -> int:
    return list(islice(dropwhile(lambda n: abs(1 - sin(1/n)/(1/n)) >= x,
                                 naturales()),
                       1))[0]


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

@given(st.integers(min_value=1, max_value=100))
def test_errorLimSeno(n: int) -> None:
    r = errorLimSeno1(n)
    assert errorLimSeno2(n) == r
    assert errorLimSeno3(n) == r

# La comprobación es
#    src> poetry run pytest -q limite_del_seno.py
#    2 passed in 0.60s

# Comparación de eficiencia de errorLimSeno
# =========================================

# La comparación es
#    >>> tiempo('errorLimSeno1(10**(-12))')
#    0.07 segundos
#    >>> tiempo('errorLimSeno2(10**(-12))')
#    Process Python violación de segmento (core dumped)
#    >>> tiempo('errorLimSeno3(10**(-12))')
#    0.10 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

from itertools import dropwhile, islice

from math import sin

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ª definición de aproxLimSeno

# =============================

def aproxLimSeno1(k: int) -> list[float]:

return [sin(1/n)/(1/n) for n in range(1, k + 1)]

# 2ª definición de aproxLimSeno

# =============================

def aproxLimSeno2(n: int) -> list[float]:

if n == 0:

return []

return aproxLimSeno2(n - 1) + [sin(1/n)/(1/n)]

# 3ª definición de aproxLimSeno

# =============================

def aproxLimSeno3(n: int) -> list[float]:

def aux(n: int) -> list[float]:

if n == 0:

return []

return [sin(1/n)/(1/n)] + aux(n - 1)

return list(reversed(aux(n)))

# 4ª definición de aproxLimSeno

# =============================

def aproxLimSeno4(n: int) -> list[float]:

def aux(xs: list[float], n: int) -> list[float]:

if n == 0:

return xs

return aux([sin(1/n)/(1/n)] + xs, n - 1)

return aux([], n)

# 5ª definición de aproxLimSeno

# =============================

def aproxLimSeno5(n: int) -> list[float]:

return list(map((lambda k: sin(1/k)/(1/k)), range(1, n+1)))

# 6ª definición de aproxLimSeno

# =============================

def aproxLimSeno6(n: int) -> list[float]:

r = []

for k in range(1, n+1):

r.append(sin(1/k)/(1/k))

return r

# Comprobación de equivalencia de aproxLimSeno

# ============================================

# La propiedad es

@given(st.integers(min_value=1, max_value=100))

def test_aproxLimSeno(n: int) -> None:

r = aproxLimSeno1(n)

assert aproxLimSeno2(n) == r

assert aproxLimSeno3(n) == r

assert aproxLimSeno4(n) == r

assert aproxLimSeno5(n) == r

assert aproxLimSeno6(n) == r

# La comprobación es

# src> poetry run pytest -q limite_del_seno.py

# 1 passed in 0.60s

# Comparación de eficiencia de aproxLimSeno

# =========================================

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('aproxLimSeno1(3*10**5)')

# 0.03 segundos

# >>> tiempo('aproxLimSeno2(3*10**5)')

# Process Python violación de segmento (core dumped)

# >>> tiempo('aproxLimSeno3(3*10**5)')

# Process Python violación de segmento (core dumped)

# >>> tiempo('aproxLimSeno4(3*10**5)')

# Process Python violación de segmento (core dumped)

# >>> tiempo('aproxLimSeno5(3*10**5)')

# 0.04 segundos

# >>> tiempo('aproxLimSeno6(3*10**5)')

# 0.07 segundos

# >>> tiempo('aproxLimSeno1(10**7)')

# 1.29 segundos

# >>> tiempo('aproxLimSeno5(10**7)')

# 1.40 segundos

# >>> tiempo('aproxLimSeno6(10**7)')

# 1.45 segundos

# 1ª definición de errorLimSeno

# ============================

# 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 errorLimSeno1(x: float) -> int:

return list(islice((n for n in naturales()

if abs(1 - sin(1/n)/(1/n)) < x), 1))[0]

# 2ª definición de errorLimSeno

# ============================

def errorLimSeno2(x: float) -> int:

def aux(n: int) -> int:

if abs(1 - sin(1/n)/(1/n)) < x:

return n

return aux(n + 1)

return aux(1)

# 3ª definición de errorLimSeno

# ============================

def errorLimSeno3(x: float) -> int:

return list(islice(dropwhile(lambda n: abs(1 - sin(1/n)/(1/n)) >= x,

naturales()),

1))[0]

# Comprobación de equivalencia de errorLimSeno

# ============================================

@given(st.integers(min_value=1, max_value=100))

def test_errorLimSeno(n: int) -> None:

r = errorLimSeno1(n)

assert errorLimSeno2(n) == r

assert errorLimSeno3(n) == r

# La comprobación es

# src> poetry run pytest -q limite_del_seno.py

# 2 passed in 0.60s

# Comparación de eficiencia de errorLimSeno

# =========================================

# La comparación es

# >>> tiempo('errorLimSeno1(10**(-12))')

# 0.07 segundos

# >>> tiempo('errorLimSeno2(10**(-12))')

# Process Python violación de segmento (core dumped)

# >>> tiempo('errorLimSeno3(10**(-12))')

# 0.10 segundos

El código se encuentra en GitHub.

Aproximación del número e

PorJosé A. Alonso 12-octubre-202214-diciembre-2022

El número e se define como el límite de la sucesión $\left(1+\dfrac{1}{n}\right)^n$ .

Definir las funciones

   aproxE      :: Int -> [Double]
   errorAproxE :: Double -> Int

1 2	aproxE :: Int -> [Double] errorAproxE :: Double -> Int

tales que

aproxE k es la lista de los k primeros términos de la sucesión. Por ejemplo,

     aproxE 4 == [2.0,2.25,2.37037037037037,2.44140625]
     last (aproxE (7*10^7))  ==  2.7182818287372563

1 2	aproxE 4 == [2.0,2.25,2.37037037037037,2.44140625] last (aproxE (7*10^7)) == 2.7182818287372563

errorE x es el menor número de términos de la sucesión necesarios para obtener su límite con un error menor que x. Por ejemplo,

     errorAproxE 0.1    ==  13
     errorAproxE 0.01   ==  135
     errorAproxE 0.001  ==  1359

errorAproxE 0.1 == 13

errorAproxE 0.01 == 135

errorAproxE 0.001 == 1359

Soluciones en Haskell

import Test.QuickCheck

-- 1ª definición de aproxE
-- =======================

aproxE1 :: Int -> [Double]
aproxE1 k = [(1+1/n)**n | n <- [1..k']]
  where k' = fromIntegral k

-- 2ª definición de aproxE
-- =======================

aproxE2 :: Int -> [Double]
aproxE2 0 = []
aproxE2 n = aproxE2 (n-1) ++ [(1+1/n')**n']
  where n' = fromIntegral n

-- 3ª definición de aproxE
-- =======================

aproxE3 :: Int -> [Double]
aproxE3 = reverse . aux . fromIntegral
  where aux 0 = []
        aux n = (1+1/n)**n : aux (n-1)

-- 4ª definición de aproxE
-- =======================

aproxE4 :: Int -> [Double]
aproxE4 k = aux [] (fromIntegral k)
  where aux xs 0 = xs
        aux xs n = aux ((1+1/n)**n : xs) (n-1)

-- 5ª definición de aproxE
-- =======================

aproxE5 :: Int -> [Double]
aproxE5 k = map (\ n -> (1+1/n)**n) [1..k']
  where k' = fromIntegral k

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

-- La propiedad es
prop_aproxE :: Positive Int -> Bool
prop_aproxE (Positive k) =
  all (== aproxE1 k)
      [aproxE2 k,
       aproxE3 k,
       aproxE4 k,
       aproxE5 k]

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

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

-- La comparación es
--    λ> last (aproxE1 (2*10^4))
--    2.718213874533619
--    (0.04 secs, 5,368,968 bytes)
--    λ> last (aproxE2 (2*10^4))
--    2.718213874533619
--    (5.93 secs, 17,514,767,104 bytes)
--    λ> last (aproxE3 (2*10^4))
--    2.718213874533619
--    (0.05 secs, 9,529,336 bytes)
--    λ> last (aproxE4 (2*10^4))
--    2.718213874533619
--    (0.05 secs, 9,529,184 bytes)
--    λ> last (aproxE5 (2*10^4))
--    2.718213874533619
--    (0.01 secs, 4,888,960 bytes)
--
--    λ> last (aproxE1 (2*10^6))
--    2.7182811492688552
--    (0.54 secs, 480,570,120 bytes)
--    λ> last (aproxE3 (2*10^6))
--    2.7182811492688552
--    (2.07 secs, 896,570,280 bytes)
--    λ> last (aproxE4 (2*10^6))
--    2.7182811492688552
--    (2.18 secs, 896,570,336 bytes)
--    λ> last (aproxE5 (2*10^6))
--    2.7182811492688552
--    (0.09 secs, 432,570,112 bytes)

-- 1ª definición de errorAproxE
-- ============================

errorAproxE1 :: Double -> Int
errorAproxE1 x =
  round (head [n | n <- [1..], abs (exp 1 - (1+1/n)**n) < x])

-- 2ª definición de errorAproxE
-- ============================

errorAproxE2 :: Double -> Int
errorAproxE2 x = aux 1
  where aux n | abs (exp 1 - (1+1/n)**n) < x = round n
              | otherwise                    = aux (n+1)

-- 3ª definición de errorAproxE
-- ============================

errorAproxE3 :: Double -> Int
errorAproxE3 x =
  round (head (dropWhile (\ n -> abs (exp 1 - (1+1/n)**n) >= x) [1..]))

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

-- La propiedad es
prop_errorAproxE :: Positive Double -> Bool
prop_errorAproxE (Positive x) =
  all (== errorAproxE1 x)
      [errorAproxE2 x,
       errorAproxE3 x]

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

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

-- La comparación es
--    λ> errorAproxE1 0.000001
--    1358611
--    (1.70 secs, 674,424,552 bytes)
--    λ> errorAproxE2 0.000001
--    1358611
--    (1.79 secs, 739,637,704 bytes)
--    λ> errorAproxE3 0.000001
--    1358611
--    (1.20 secs, 609,211,144 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

import Test.QuickCheck

-- 1ª definición de aproxE

-- =======================

aproxE1 :: Int -> [Double]

aproxE1 k = [(1+1/n)**n | n <- [1..k']]

where k' = fromIntegral k

-- 2ª definición de aproxE

-- =======================

aproxE2 :: Int -> [Double]

aproxE2 0 = []

aproxE2 n = aproxE2 (n-1) ++ [(1+1/n')**n']

where n' = fromIntegral n

-- 3ª definición de aproxE

-- =======================

aproxE3 :: Int -> [Double]

aproxE3 = reverse . aux . fromIntegral

where aux 0 = []

aux n = (1+1/n)**n : aux (n-1)

-- 4ª definición de aproxE

-- =======================

aproxE4 :: Int -> [Double]

aproxE4 k = aux [] (fromIntegral k)

where aux xs 0 = xs

aux xs n = aux ((1+1/n)**n : xs) (n-1)

-- 5ª definición de aproxE

-- =======================

aproxE5 :: Int -> [Double]

aproxE5 k = map (\ n -> (1+1/n)**n) [1..k']

where k' = fromIntegral k

-- Comprobación de equivalencia de aproxE

-- ======================================

-- La propiedad es

prop_aproxE :: Positive Int -> Bool

prop_aproxE (Positive k) =

all (== aproxE1 k)

[aproxE2 k,

aproxE3 k,

aproxE4 k,

aproxE5 k]

-- La comprobación es

-- λ> quickCheck prop_aproxE

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de aproxE

-- ===================================

-- La comparación es

-- λ> last (aproxE1 (2*10^4))

-- 2.718213874533619

-- (0.04 secs, 5,368,968 bytes)

-- λ> last (aproxE2 (2*10^4))

-- 2.718213874533619

-- (5.93 secs, 17,514,767,104 bytes)

-- λ> last (aproxE3 (2*10^4))

-- 2.718213874533619

-- (0.05 secs, 9,529,336 bytes)

-- λ> last (aproxE4 (2*10^4))

-- 2.718213874533619

-- (0.05 secs, 9,529,184 bytes)

-- λ> last (aproxE5 (2*10^4))

-- 2.718213874533619

-- (0.01 secs, 4,888,960 bytes)

-- λ> last (aproxE1 (2*10^6))

-- 2.7182811492688552

-- (0.54 secs, 480,570,120 bytes)

-- λ> last (aproxE3 (2*10^6))

-- 2.7182811492688552

-- (2.07 secs, 896,570,280 bytes)

-- λ> last (aproxE4 (2*10^6))

-- 2.7182811492688552

-- (2.18 secs, 896,570,336 bytes)

-- λ> last (aproxE5 (2*10^6))

-- 2.7182811492688552

-- (0.09 secs, 432,570,112 bytes)

-- 1ª definición de errorAproxE

-- ============================

errorAproxE1 :: Double -> Int

errorAproxE1 x =

round (head [n | n <- [1..], abs (exp 1 - (1+1/n)**n) < x])

-- 2ª definición de errorAproxE

-- ============================

errorAproxE2 :: Double -> Int

errorAproxE2 x = aux 1

where aux n | abs (exp 1 - (1+1/n)**n) < x = round n

| otherwise = aux (n+1)

-- 3ª definición de errorAproxE

-- ============================

errorAproxE3 :: Double -> Int

errorAproxE3 x =

round (head (dropWhile (\ n -> abs (exp 1 - (1+1/n)**n) >= x) [1..]))

-- Comprobación de equivalencia de errorAproxE

-- ===========================================

-- La propiedad es

prop_errorAproxE :: Positive Double -> Bool

prop_errorAproxE (Positive x) =

all (== errorAproxE1 x)

[errorAproxE2 x,

errorAproxE3 x]

-- La comprobación es

-- λ> quickCheck prop_errorAproxE

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de errorAproxE

-- ========================================

-- La comparación es

-- λ> errorAproxE1 0.000001

-- 1358611

-- (1.70 secs, 674,424,552 bytes)

-- λ> errorAproxE2 0.000001

-- 1358611

-- (1.79 secs, 739,637,704 bytes)

-- λ> errorAproxE3 0.000001

-- 1358611

-- (1.20 secs, 609,211,144 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from itertools import dropwhile, islice
from math import e
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ª definición de aproxE
# =======================

def aproxE1(k: int) -> list[float]:
    return [(1 + 1/n)**n for n in range(1, k + 1)]

# 2ª definición de aproxE
# =======================

def aproxE2(n: int) -> list[float]:
    if n == 0:
        return []
    return aproxE2(n - 1) + [(1 + 1/n)**n]

# 3ª definición de aproxE
# =======================

def aproxE3(n: int) -> list[float]:
    def aux(n: int) -> list[float]:
        if n == 0:
            return []
        return [(1 + 1/n)**n] + aux(n - 1)

    return list(reversed(aux(n)))

# 4ª definición de aproxE
# =======================

def aproxE4(n: int) -> list[float]:
    def aux(xs: list[float], n: int) -> list[float]:
        if n == 0:
            return xs
        return aux([(1 + 1/n)**n] + xs, n - 1)

    return aux([], n)

# 5ª definición de aproxE
# =======================

def aproxE5(n: int) -> list[float]:
    return list(map((lambda k: (1+1/k)**k), range(1, n+1)))

# 6ª definición de aproxE
# =======================

def aproxE6(n: int) -> list[float]:
    r = []
    for k in range(1, n+1):
        r.append((1+1/k)**k)
    return r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=100))
def test_aproxE(n: int) -> None:
    r = aproxE1(n)
    assert aproxE2(n) == r
    assert aproxE3(n) == r
    assert aproxE4(n) == r
    assert aproxE5(n) == r
    assert aproxE6(n) == r

# La comprobación es
#    src> poetry run pytest -q aproximacion_del_numero_e.py
#    1 passed in 0.60s

# Comparación de eficiencia de aproxE
# ===================================

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('aproxE1(20000)')
#    0.00 segundos
#    >>> tiempo('aproxE2(20000)')
#    0.43 segundos
#    >>> tiempo('aproxE3(20000)')
#    0.60 segundos
#    >>> tiempo('aproxE4(20000)')
#    1.23 segundos
#    >>> tiempo('aproxE5(20000)')
#    0.00 segundos
#    >>> tiempo('aproxE6(20000)')
#    0.00 segundos

#    >>> tiempo('aproxE1(10**7)')
#    1.18 segundos
#    >>> tiempo('aproxE5(10**7)')
#    1.48 segundos
#    >>> tiempo('aproxE6(10**7)')
#    1.43 segundos

# 1ª definición de errorAproxE
# ============================

# 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 errorAproxE1(x: float) -> int:
    return list(islice((n for n in naturales()
                        if abs(e - (1 + 1/n)**n) < x), 1))[0]

# # 2ª definición de errorAproxE
# # ============================

def errorAproxE2(x: float) -> int:
    def aux(n: int) -> int:
        if abs(e - (1 + 1/n)**n) < x:
            return n
        return aux(n + 1)

    return aux(1)

# 3ª definición de errorAproxE
# ============================

def errorAproxE3(x: float) -> int:
    return list(islice(dropwhile(lambda n: abs(e - (1 + 1/n)**n) >= x,
                                 naturales()),
                       1))[0]


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

@given(st.integers(min_value=1, max_value=100))
def test_errorAproxE(n: int) -> None:
    r = errorAproxE1(n)
    assert errorAproxE2(n) == r
    assert errorAproxE3(n) == r

# La comprobación es
#    src> poetry run pytest -q aproximacion_del_numero_e.py
#    2 passed in 0.60s

# Comparación de eficiencia de aproxE
# ===================================

# La comparación es
#    >>> tiempo('errorAproxE1(0.0001)')
#    0.00 segundos
#    >>> tiempo('errorAproxE2(0.0001)')
#    0.00 segundos
#    >>> tiempo('errorAproxE3(0.0001)')
#    0.00 segundos
#
#    >>> tiempo('errorAproxE1(0.0000001)')
#    2.48 segundos
#    >>> tiempo('errorAproxE3(0.0000001)')
#    2.61 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

from itertools import dropwhile, islice

from math import e

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ª definición de aproxE

# =======================

def aproxE1(k: int) -> list[float]:

return [(1 + 1/n)**n for n in range(1, k + 1)]

# 2ª definición de aproxE

# =======================

def aproxE2(n: int) -> list[float]:

if n == 0:

return []

return aproxE2(n - 1) + [(1 + 1/n)**n]

# 3ª definición de aproxE

# =======================

def aproxE3(n: int) -> list[float]:

def aux(n: int) -> list[float]:

if n == 0:

return []

return [(1 + 1/n)**n] + aux(n - 1)

return list(reversed(aux(n)))

# 4ª definición de aproxE

# =======================

def aproxE4(n: int) -> list[float]:

def aux(xs: list[float], n: int) -> list[float]:

if n == 0:

return xs

return aux([(1 + 1/n)**n] + xs, n - 1)

return aux([], n)

# 5ª definición de aproxE

# =======================

def aproxE5(n: int) -> list[float]:

return list(map((lambda k: (1+1/k)**k), range(1, n+1)))

# 6ª definición de aproxE

# =======================

def aproxE6(n: int) -> list[float]:

r = []

for k in range(1, n+1):

r.append((1+1/k)**k)

return r

# Comprobación de equivalencia de aproxE

# ======================================

# La propiedad es

@given(st.integers(min_value=1, max_value=100))

def test_aproxE(n: int) -> None:

r = aproxE1(n)

assert aproxE2(n) == r

assert aproxE3(n) == r

assert aproxE4(n) == r

assert aproxE5(n) == r

assert aproxE6(n) == r

# La comprobación es

# src> poetry run pytest -q aproximacion_del_numero_e.py

# 1 passed in 0.60s

# Comparación de eficiencia de aproxE

# ===================================

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('aproxE1(20000)')

# 0.00 segundos

# >>> tiempo('aproxE2(20000)')

# 0.43 segundos

# >>> tiempo('aproxE3(20000)')

# 0.60 segundos

# >>> tiempo('aproxE4(20000)')

# 1.23 segundos

# >>> tiempo('aproxE5(20000)')

# 0.00 segundos

# >>> tiempo('aproxE6(20000)')

# 0.00 segundos

# >>> tiempo('aproxE1(10**7)')

# 1.18 segundos

# >>> tiempo('aproxE5(10**7)')

# 1.48 segundos

# >>> tiempo('aproxE6(10**7)')

# 1.43 segundos

# 1ª definición de errorAproxE

# ============================

# 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 errorAproxE1(x: float) -> int:

return list(islice((n for n in naturales()

if abs(e - (1 + 1/n)**n) < x), 1))[0]

# # 2ª definición de errorAproxE

# # ============================

def errorAproxE2(x: float) -> int:

def aux(n: int) -> int:

if abs(e - (1 + 1/n)**n) < x:

return n

return aux(n + 1)

return aux(1)

# 3ª definición de errorAproxE

# ============================

def errorAproxE3(x: float) -> int:

return list(islice(dropwhile(lambda n: abs(e - (1 + 1/n)**n) >= x,

naturales()),

1))[0]

# Comprobación de equivalencia de errorAproxE

# ===========================================

@given(st.integers(min_value=1, max_value=100))

def test_errorAproxE(n: int) -> None:

r = errorAproxE1(n)

assert errorAproxE2(n) == r

assert errorAproxE3(n) == r

# La comprobación es

# src> poetry run pytest -q aproximacion_del_numero_e.py

# 2 passed in 0.60s

# Comparación de eficiencia de aproxE

# ===================================

# La comparación es

# >>> tiempo('errorAproxE1(0.0001)')

# 0.00 segundos

# >>> tiempo('errorAproxE2(0.0001)')

# 0.00 segundos

# >>> tiempo('errorAproxE3(0.0001)')

# 0.00 segundos

# >>> tiempo('errorAproxE1(0.0000001)')

# 2.48 segundos

# >>> tiempo('errorAproxE3(0.0000001)')

# 2.61 segundos

El código se encuentra en GitHub.

Puntos en el círculo

PorJosé A. Alonso 11-octubre-202214-diciembre-2022

En el círculo de radio 2 hay 6 puntos cuyas coordenadas son puntos naturales:

   (0,0),(0,1),(0,2),(1,0),(1,1),(2,0)

1	(0,0),(0,1),(0,2),(1,0),(1,1),(2,0)

y en de radio 3 hay 11:

   (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)

1	(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)

Definir la función

   circulo :: Int -> Int

1	circulo :: Int -> Int

tal que circulo n es el la cantidad de pares de números naturales (x,y) que se encuentran en el círculo de radio n. Por ejemplo,

   circulo 1    ==  3
   circulo 2    ==  6
   circulo 3    ==  11
   circulo 4    ==  17
   circulo 100  ==  7955

circulo 1 == 3

circulo 2 == 6

circulo 3 == 11

circulo 4 == 17

circulo 100 == 7955

Soluciones en Haskell

import Test.QuickCheck

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

circulo1 :: Int -> Int
circulo1 n = length (enCirculo1 n)

enCirculo1 :: Int -> [(Int, Int)]
enCirculo1 n = [(x,y) | x <- [0..n],
                        y <- [0..n],
                        x*x+y*y <= n*n]

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

circulo2 :: Int -> Int
circulo2 0 = 1
circulo2 n =
  2 * length (enSemiCirculo n) + ceiling(fromIntegral n / sqrt 2)

enSemiCirculo :: Int -> [(Int, Int)]
enSemiCirculo n =
  [(x,y) | x <- [0..floor (sqrt (fromIntegral (n * n)))],
           y <- [x+1..truncate (sqrt (fromIntegral (n*n - x*x)))]]

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

-- La propiedad es
prop_circulo :: Positive Int -> Bool
prop_circulo (Positive n) =
  circulo1 n == circulo2 n

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

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

-- La comparación es
--    λ> circulo1 (2*10^3)
--    3143587
--    (3.58 secs, 1,744,162,600 bytes)
--    λ> circulo2 (2*10^3)
--    3143587
--    (0.41 secs, 266,374,208 bytes)

import Test.QuickCheck

-- 1ª solución

-- ===========

circulo1 :: Int -> Int

circulo1 n = length (enCirculo1 n)

enCirculo1 :: Int -> [(Int, Int)]

enCirculo1 n = [(x,y) | x <- [0..n],

y <- [0..n],

x*x+y*y <= n*n]

-- 2ª solución

-- ===========

circulo2 :: Int -> Int

circulo2 0 = 1

circulo2 n =

2 * length (enSemiCirculo n) + ceiling(fromIntegral n / sqrt 2)

enSemiCirculo :: Int -> [(Int, Int)]

enSemiCirculo n =

[(x,y) | x <- [0..floor (sqrt (fromIntegral (n * n)))],

y <- [x+1..truncate (sqrt (fromIntegral (n*n - x*x)))]]

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_circulo :: Positive Int -> Bool

prop_circulo (Positive n) =

circulo1 n == circulo2 n

-- La comprobación es

-- λ> quickCheck prop_circulo

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> circulo1 (2*10^3)

-- 3143587

-- (3.58 secs, 1,744,162,600 bytes)

-- λ> circulo2 (2*10^3)

-- 3143587

-- (0.41 secs, 266,374,208 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import sqrt, trunc, ceil
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

def circulo1(n: int) -> int:
    return len([(x, y)
                for x in range(0, n + 1)
                for y in range(0, n + 1)
                if x * x + y * y <= n * n])

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

def enSemiCirculo(n: int) -> list[tuple[int, int]]:
    return [(x, y)
            for x in range(0, ceil(sqrt(n**2)) + 1)
            for y in range(x+1, trunc(sqrt(n**2 - x**2)) + 1)]

def circulo2(n: int) -> int:
    if n == 0:
        return 1
    return (2 * len(enSemiCirculo(n)) + ceil(n / sqrt(2)))

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

def circulo3(n: int) -> int:
    r = 0
    for x in range(0, n + 1):
        for y in range(0, n + 1):
            if x**2 + y**2 <= n**2:
                r = r + 1
    return r

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

def circulo4(n: int) -> int:
    r = 0
    for x in range(0, ceil(sqrt(n**2)) + 1):
        for y in range(x + 1, trunc(sqrt(n**2 - x**2)) + 1):
            if x**2 + y**2 <= n**2:
                r = r + 1
    return 2 * r + ceil(n / sqrt(2))

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

# La propiedad es
@given(st.integers(min_value=1, max_value=100))
def test_circulo(n: int) -> None:
    r = circulo1(n)
    assert circulo2(n) == r
    assert circulo3(n) == r
    assert circulo4(n) == r

# La comprobación es
#    src> poetry run pytest -q puntos_dentro_del_circulo.py
#    1 passed in 0.60s

# 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('circulo1(2000)')
#    0.71 segundos
#    >>> tiempo('circulo2(2000)')
#    0.76 segundos
#    >>> tiempo('circulo3(2000)')
#    2.63 segundos
#    >>> tiempo('circulo4(2000)')
#    1.06 segundos

from math import sqrt, trunc, ceil

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución

# ===========

def circulo1(n: int) -> int:

return len([(x, y)

for x in range(0, n + 1)

for y in range(0, n + 1)

if x * x + y * y <= n * n])

# 2ª solución

# ===========

def enSemiCirculo(n: int) -> list[tuple[int, int]]:

return [(x, y)

for x in range(0, ceil(sqrt(n**2)) + 1)

for y in range(x+1, trunc(sqrt(n**2 - x**2)) + 1)]

def circulo2(n: int) -> int:

if n == 0:

return 1

return (2 * len(enSemiCirculo(n)) + ceil(n / sqrt(2)))

# 3ª solución

# ===========

def circulo3(n: int) -> int:

r = 0

for x in range(0, n + 1):

for y in range(0, n + 1):

if x**2 + y**2 <= n**2:

r = r + 1

return r

# 4ª solución

# ===========

def circulo4(n: int) -> int:

r = 0

for x in range(0, ceil(sqrt(n**2)) + 1):

for y in range(x + 1, trunc(sqrt(n**2 - x**2)) + 1):

if x**2 + y**2 <= n**2:

r = r + 1

return 2 * r + ceil(n / sqrt(2))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=100))

def test_circulo(n: int) -> None:

r = circulo1(n)

assert circulo2(n) == r

assert circulo3(n) == r

assert circulo4(n) == r

# La comprobación es

# src> poetry run pytest -q puntos_dentro_del_circulo.py

# 1 passed in 0.60s

# 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('circulo1(2000)')

# 0.71 segundos

# >>> tiempo('circulo2(2000)')

# 0.76 segundos

# >>> tiempo('circulo3(2000)')

# 2.63 segundos

# >>> tiempo('circulo4(2000)')

# 1.06 segundos

El código se encuentra en GitHub.

Suma de múltiplos de 3 ó 5

PorJosé A. Alonso 10-octubre-202214-diciembre-2022

Definir la función

   euler1 :: Integer -> Integer

1	euler1 :: Integer -> Integer

tal que euler1 n es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

   euler1 10      == 23
   euler1 (10^2)  == 2318
   euler1 (10^3)  == 233168
   euler1 (10^4)  == 23331668
   euler1 (10^5)  == 2333316668
   euler1 (10^10) == 23333333331666666668
   euler1 (10^20) == 2333333333333333333316666666666666666668
   euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668

euler1 10 == 23

euler1 (10^2) == 2318

euler1 (10^3) == 233168

euler1 (10^4) == 23331668

euler1 (10^5) == 2333316668

euler1 (10^10) == 23333333331666666668

euler1 (10^20) == 2333333333333333333316666666666666666668

euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668

Nota: Este ejercicio está basado en el problema 1 del Proyecto Euler

Soluciones

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

Soluciones en Haskell

import Data.List (nub, union)
import qualified Data.Set as S (fromAscList, union)
import Test.QuickCheck

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

euler1a :: Integer -> Integer
euler1a n =
  sum [x | x <- [1..n-1],
           multiplo x 3 || multiplo x 5]

-- (multiplo x y) se verifica si x es un múltiplo de y. Por ejemplo.
--    multiplo 12 3  ==  True
--    multiplo 14 3  ==  False
multiplo :: Integer -> Integer -> Bool
multiplo x y = mod x y == 0

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

euler1b :: Integer -> Integer
euler1b n =
  sum [x | x <- [1..n-1],
           gcd x 15 > 1]

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

euler1c :: Integer -> Integer
euler1c n =
  sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]

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

euler1d :: Integer -> Integer
euler1d n =
  sum (nub ([3,6..n-1] ++ [5,10..n-1]))

-- 5ª solución                                                        --
-- ===========

euler1e :: Integer -> Integer
euler1e n =
  sum ([3,6..n-1] `union` [5,10..n-1])

-- 6ª solución                                                        --
-- ===========

euler1f :: Integer -> Integer
euler1f n =
  sum (S.fromAscList [3,6..n-1] `S.union` S.fromAscList [5,10..n-1])

-- 7ª solución                                                      --
-- ===========

euler1g :: Integer -> Integer
euler1g n =
  suma 3 n + suma 5 n - suma 15 n

-- (suma d x) es la suma de los múltiplos de d menores que x. Por
-- ejemplo,
--    suma 3 20  ==  63
suma :: Integer -> Integer -> Integer
suma d x = (a+b)*n `div` 2
    where a = d
          b = d * ((x-1) `div` d)
          n = 1 + (b-a) `div` d

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

-- La propiedad es
prop_euler1 :: Positive Integer -> Bool
prop_euler1 (Positive n) =
  all (== euler1a n)
      [euler1b n,
       euler1c n,
       euler1d n,
       euler1e n,
       euler1f n,
       euler1g n]

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

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

-- La comparación es
--    λ> euler1a (5*10^4)
--    583291668
--    (0.05 secs, 21,895,296 bytes)
--    λ> euler1b (5*10^4)
--    583291668
--    (0.05 secs, 26,055,096 bytes)
--    λ> euler1c (5*10^4)
--    583291668
--    (0.01 secs, 5,586,072 bytes)
--    λ> euler1d (5*10^4)
--    583291668
--    (2.83 secs, 7,922,304 bytes)
--    λ> euler1e (5*10^4)
--    583291668
--    (4.56 secs, 12,787,705,248 bytes)
--    λ> euler1f (5*10^4)
--    583291668
--    (0.01 secs, 8,168,584 bytes)
--    λ> euler1g (5*10^4)
--    583291668
--    (0.02 secs, 557,488 bytes)
--
--    λ> euler1a (3*10^6)
--    2099998500000
--    (2.72 secs, 1,282,255,816 bytes)
--    λ> euler1b (3*10^6)
--    2099998500000
--    (2.06 secs, 1,531,855,776 bytes)
--    λ> euler1c (3*10^6)
--    2099998500000
--    (0.38 secs, 305,127,480 bytes)
--    λ> euler1f (3*10^6)
--    2099998500000
--    (0.54 secs, 457,358,232 bytes)
--    λ> euler1g (3*10^6)
--    2099998500000
--    (0.01 secs, 560,472 bytes)
--
--    λ> euler1c (10^7)
--    23333331666668
--    (1.20 secs, 1,015,920,024 bytes)
--    λ> euler1f (10^7)
--    23333331666668
--    (2.00 secs, 1,523,225,648 bytes)
--    λ> euler1g (10^7)
--    23333331666668
--    (0.01 secs, 561,200 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

import Data.List (nub, union)

import qualified Data.Set as S (fromAscList, union)

import Test.QuickCheck

-- 1ª solución

-- ===========

euler1a :: Integer -> Integer

euler1a n =

sum [x | x <- [1..n-1],

multiplo x 3 || multiplo x 5]

-- (multiplo x y) se verifica si x es un múltiplo de y. Por ejemplo.

-- multiplo 12 3 == True

-- multiplo 14 3 == False

multiplo :: Integer -> Integer -> Bool

multiplo x y = mod x y == 0

-- 2ª solución --

-- ===========

euler1b :: Integer -> Integer

euler1b n =

sum [x | x <- [1..n-1],

gcd x 15 > 1]

-- 3ª solución --

-- ===========

euler1c :: Integer -> Integer

euler1c n =

sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]

-- 4ª solución --

-- ===========

euler1d :: Integer -> Integer

euler1d n =

sum (nub ([3,6..n-1] ++ [5,10..n-1]))

-- 5ª solución --

-- ===========

euler1e :: Integer -> Integer

euler1e n =

sum ([3,6..n-1] `union` [5,10..n-1])

-- 6ª solución --

-- ===========

euler1f :: Integer -> Integer

euler1f n =

sum (S.fromAscList [3,6..n-1] `S.union` S.fromAscList [5,10..n-1])

-- 7ª solución --

-- ===========

euler1g :: Integer -> Integer

euler1g n =

suma 3 n + suma 5 n - suma 15 n

-- (suma d x) es la suma de los múltiplos de d menores que x. Por

-- ejemplo,

-- suma 3 20 == 63

suma :: Integer -> Integer -> Integer

suma d x = (a+b)*n `div` 2

where a = d

b = d * ((x-1) `div` d)

n = 1 + (b-a) `div` d

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_euler1 :: Positive Integer -> Bool

prop_euler1 (Positive n) =

all (== euler1a n)

[euler1b n,

euler1c n,

euler1d n,

euler1e n,

euler1f n,

euler1g n]

-- La comprobación es

-- λ> quickCheck prop_euler1

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> euler1a (5*10^4)

-- 583291668

-- (0.05 secs, 21,895,296 bytes)

-- λ> euler1b (5*10^4)

-- 583291668

-- (0.05 secs, 26,055,096 bytes)

-- λ> euler1c (5*10^4)

-- 583291668

-- (0.01 secs, 5,586,072 bytes)

-- λ> euler1d (5*10^4)

-- 583291668

-- (2.83 secs, 7,922,304 bytes)

-- λ> euler1e (5*10^4)

-- 583291668

-- (4.56 secs, 12,787,705,248 bytes)

-- λ> euler1f (5*10^4)

-- 583291668

-- (0.01 secs, 8,168,584 bytes)

-- λ> euler1g (5*10^4)

-- 583291668

-- (0.02 secs, 557,488 bytes)

-- λ> euler1a (3*10^6)

-- 2099998500000

-- (2.72 secs, 1,282,255,816 bytes)

-- λ> euler1b (3*10^6)

-- 2099998500000

-- (2.06 secs, 1,531,855,776 bytes)

-- λ> euler1c (3*10^6)

-- 2099998500000

-- (0.38 secs, 305,127,480 bytes)

-- λ> euler1f (3*10^6)

-- 2099998500000

-- (0.54 secs, 457,358,232 bytes)

-- λ> euler1g (3*10^6)

-- 2099998500000

-- (0.01 secs, 560,472 bytes)

-- λ> euler1c (10^7)

-- 23333331666668

-- (1.20 secs, 1,015,920,024 bytes)

-- λ> euler1f (10^7)

-- 23333331666668

-- (2.00 secs, 1,523,225,648 bytes)

-- λ> euler1g (10^7)

-- 23333331666668

-- (0.01 secs, 561,200 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import gcd
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

# multiplo(x, y) se verifica si x es un múltiplo de y. Por ejemplo.
#    multiplo(12, 3)  ==  True
#    multiplo(14, 3)  ==  False
def multiplo(x: int, y: int) -> int:
    return x % y == 0

def euler1a(n: int) -> int:
    return sum(x for x in range(1, n)
               if (multiplo(x, 3) or multiplo(x, 5)))

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

def euler1b(n: int) -> int:
    return sum(x for x in range(1, n)
               if gcd(x, 15) > 1)

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

def euler1c(n: int) -> int:
    return sum(range(3, n, 3)) + \
           sum(range(5, n, 5)) - \
           sum(range(15, n, 15))

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

def euler1d(n: int) -> int:
    return sum(set(list(range(3, n, 3)) + list(range(5, n, 5))))

# 5ª solución                                                        --
# ===========

def euler1e(n: int) -> int:
    return sum(set(list(range(3, n, 3))) | set(list(range(5, n, 5))))

# 6ª solución                                                        --
# ===========

# suma(d, x) es la suma de los múltiplos de d menores que x. Por
# ejemplo,
#    suma(3, 20)  ==  63
def suma(d: int, x: int) -> int:
    a = d
    b = d * ((x - 1) // d)
    n = 1 + (b - a) // d
    return (a + b) * n // 2

def euler1f(n: int) -> int:
    return suma(3, n) + suma(5, n) - suma(15, n)

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_euler1(n: int) -> None:
    r = euler1a(n)
    assert euler1b(n) == r
    assert euler1c(n) == r
    assert euler1d(n) == r
    assert euler1e(n) == r

# La comprobación es
#    src> poetry run pytest -q suma_de_multiplos_de_3_o_5.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('euler1a(10**7)')
#    1.49 segundos
#    >>> tiempo('euler1b(10**7)')
#    0.93 segundos
#    >>> tiempo('euler1c(10**7)')
#    0.07 segundos
#    >>> tiempo('euler1d(10**7)')
#    0.42 segundos
#    >>> tiempo('euler1e(10**7)')
#    0.69 segundos
#    >>> tiempo('euler1f(10**7)')
#    0.00 segundos
#
#    >>> tiempo('euler1c(10**8)')
#    0.72 segundos
#    >>> tiempo('euler1f(10**8)')
#    0.00 segundos

100

101

102

103

from math import gcd

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución

# ===========

# multiplo(x, y) se verifica si x es un múltiplo de y. Por ejemplo.

# multiplo(12, 3) == True

# multiplo(14, 3) == False

def multiplo(x: int, y: int) -> int:

return x % y == 0

def euler1a(n: int) -> int:

return sum(x for x in range(1, n)

if (multiplo(x, 3) or multiplo(x, 5)))

# 2ª solución --

# ===========

def euler1b(n: int) -> int:

return sum(x for x in range(1, n)

if gcd(x, 15) > 1)

# 3ª solución --

# ===========

def euler1c(n: int) -> int:

return sum(range(3, n, 3)) + \

sum(range(5, n, 5)) - \

sum(range(15, n, 15))

# 4ª solución --

# ===========

def euler1d(n: int) -> int:

return sum(set(list(range(3, n, 3)) + list(range(5, n, 5))))

# 5ª solución --

# ===========

def euler1e(n: int) -> int:

return sum(set(list(range(3, n, 3))) | set(list(range(5, n, 5))))

# 6ª solución --

# ===========

# suma(d, x) es la suma de los múltiplos de d menores que x. Por

# ejemplo,

# suma(3, 20) == 63

def suma(d: int, x: int) -> int:

a = d

b = d * ((x - 1) // d)

n = 1 + (b - a) // d

return (a + b) * n // 2

def euler1f(n: int) -> int:

return suma(3, n) + suma(5, n) - suma(15, n)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_euler1(n: int) -> None:

r = euler1a(n)

assert euler1b(n) == r

assert euler1c(n) == r

assert euler1d(n) == r

assert euler1e(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_multiplos_de_3_o_5.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('euler1a(10**7)')

# 1.49 segundos

# >>> tiempo('euler1b(10**7)')

# 0.93 segundos

# >>> tiempo('euler1c(10**7)')

# 0.07 segundos

# >>> tiempo('euler1d(10**7)')

# 0.42 segundos

# >>> tiempo('euler1e(10**7)')

# 0.69 segundos

# >>> tiempo('euler1f(10**7)')

# 0.00 segundos

# >>> tiempo('euler1c(10**8)')

# 0.72 segundos

# >>> tiempo('euler1f(10**8)')

# 0.00 segundos

El código se encuentra en GitHub.

Números abundantes impares

PorJosé A. Alonso 7-octubre-202214-diciembre-2022

Definir la lista

  abundantesImpares :: [Integer]

1	abundantesImpares :: [Integer]

cuyos elementos son los números abundantes impares. Por ejemplo,

   λ> take 12 abundantesImpares
   [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615]

1 2	λ> take 12 abundantesImpares [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615]

Soluciones

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

Soluciones en Haskell

import Math.NumberTheory.ArithmeticFunctions (sigma)
import Test.QuickCheck


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

abundantesImpares1 :: [Integer]
abundantesImpares1 = [x | x <- [1,3..], numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo,
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
--    sumaDivisores 12                 ==  28
--    sumaDivisores 25                 ==  31
sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

abundantesImpares2 :: [Integer]
abundantesImpares2 = filter numeroAbundante1 [1,3..]

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

-- Sustituyendo la definición de numeroAbundante1 de las soluciones
-- anteriores por cada una de las del ejercicio "Números abundantes"
-- https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes
-- impares. La usada en las definiciones anteriores es la menos
-- eficiente y la que se usa en la siguiente definición es la más eficiente.

abundantesImpares3 :: [Integer]
abundantesImpares3 = filter numeroAbundante3 [1,3..]

numeroAbundante3 :: Integer -> Bool
numeroAbundante3 x =
  x < sumaDivisores3 x - x

sumaDivisores3 :: Integer -> Integer
sumaDivisores3 = sigma 1

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

-- La propiedad es
prop_abundantesImpares :: Positive Int -> Bool
prop_abundantesImpares (Positive n) =
  all (== take n abundantesImpares1)
      [take n abundantesImpares2,
       take n abundantesImpares3]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_abundantesImpares
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> abundantesImpares1 !! 5
--    4095
--    (2.07 secs, 841,525,368 bytes)
--    λ> abundantesImpares2 !! 5
--    4095
--    (2.06 secs, 841,443,112 bytes)
--    λ> abundantesImpares3 !! 5
--    4095
--    (0.01 secs, 550,776 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

abundantesImpares1 :: [Integer]

abundantesImpares1 = [x | x <- [1,3..], numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

-- sumaDivisores 12 == 28

-- sumaDivisores 25 == 31

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

abundantesImpares2 :: [Integer]

abundantesImpares2 = filter numeroAbundante1 [1,3..]

-- 3ª solución

-- ===========

-- Sustituyendo la definición de numeroAbundante1 de las soluciones

-- anteriores por cada una de las del ejercicio "Números abundantes"

-- https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes

-- impares. La usada en las definiciones anteriores es la menos

-- eficiente y la que se usa en la siguiente definición es la más eficiente.

abundantesImpares3 :: [Integer]

abundantesImpares3 = filter numeroAbundante3 [1,3..]

numeroAbundante3 :: Integer -> Bool

numeroAbundante3 x =

x < sumaDivisores3 x - x

sumaDivisores3 :: Integer -> Integer

sumaDivisores3 = sigma 1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_abundantesImpares :: Positive Int -> Bool

prop_abundantesImpares (Positive n) =

all (== take n abundantesImpares1)

[take n abundantesImpares2,

take n abundantesImpares3]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_abundantesImpares

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> abundantesImpares1 !! 5

-- 4095

-- (2.07 secs, 841,525,368 bytes)

-- λ> abundantesImpares2 !! 5

-- 4095

-- (2.06 secs, 841,443,112 bytes)

-- λ> abundantesImpares3 !! 5

-- 4095

-- (0.01 secs, 550,776 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisor_sigma

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

def abundantesImpares1(n: int) -> list[int]:
    return [x for x in range(1, n, 2) if numeroAbundante1(x)]

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,
#    sumaDivisores(12)                ==  28
#    sumaDivisores(25)                ==  31
def sumaDivisores1(n: int) -> int:
    return sum(divisores1(n))

# numeroAbundante(n) se verifica si n es un número abundante. Por
# ejemplo,
#    numeroAbundante(5)  == False
#    numeroAbundante(12) == True
#    numeroAbundante(28) == False
#    numeroAbundante(30) == True
def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

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

def abundantesImpares2(n: int) -> list[int]:
    return list(filter(numeroAbundante1, range(1, n, 2)))

# 3ª solución
# ===========
#
# Sustituyendo la definición de numeroAbundante1 de las soluciones
# anteriores por cada una de las del ejercicio "Números abundantes"
# https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes
# impares. La usada en las definiciones anteriores es la menos
# eficiente y la que se usa en la siguiente definición es la más eficiente.

def abundantesImpares3(n: int) -> list[int]:
    return list(filter(numeroAbundante3, range(1, n, 2)))

def sumaDivisores3(n: int) -> int:
    return divisor_sigma(n, 1)

def numeroAbundante3(x: int) -> bool:
    return x < sumaDivisores3(x) - x

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_abundantesImpares(n: int) -> None:
    r = abundantesImpares1(n)
    assert abundantesImpares2(n) == r
    assert abundantesImpares3(n) == r

# La comprobación es
#    src> poetry run pytest -q numeros_abundantes_impares.py
#    1 passed in 1.42s

# 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('abundantesImpares1(10000)[5]')
#    1.25 segundos
#    >>> tiempo('abundantesImpares2(10000)[5]')
#    1.22 segundos
#    >>> tiempo('abundantesImpares3(10000)[5]')
#    0.33 segundos

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy import divisor_sigma

# 1ª solución

# ===========

def abundantesImpares1(n: int) -> list[int]:

return [x for x in range(1, n, 2) if numeroAbundante1(x)]

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,

# sumaDivisores(12) == 28

# sumaDivisores(25) == 31

def sumaDivisores1(n: int) -> int:

return sum(divisores1(n))

# numeroAbundante(n) se verifica si n es un número abundante. Por

# ejemplo,

# numeroAbundante(5) == False

# numeroAbundante(12) == True

# numeroAbundante(28) == False

# numeroAbundante(30) == True

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

# 2ª solución

# ===========

def abundantesImpares2(n: int) -> list[int]:

return list(filter(numeroAbundante1, range(1, n, 2)))

# 3ª solución

# ===========

# Sustituyendo la definición de numeroAbundante1 de las soluciones

# anteriores por cada una de las del ejercicio "Números abundantes"

# https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes

# impares. La usada en las definiciones anteriores es la menos

# eficiente y la que se usa en la siguiente definición es la más eficiente.

def abundantesImpares3(n: int) -> list[int]:

return list(filter(numeroAbundante3, range(1, n, 2)))

def sumaDivisores3(n: int) -> int:

return divisor_sigma(n, 1)

def numeroAbundante3(x: int) -> bool:

return x < sumaDivisores3(x) - x

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_abundantesImpares(n: int) -> None:

r = abundantesImpares1(n)

assert abundantesImpares2(n) == r

assert abundantesImpares3(n) == r

# La comprobación es

# src> poetry run pytest -q numeros_abundantes_impares.py

# 1 passed in 1.42s

# 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('abundantesImpares1(10000)[5]')

# 1.25 segundos

# >>> tiempo('abundantesImpares2(10000)[5]')

# 1.22 segundos

# >>> tiempo('abundantesImpares3(10000)[5]')

# 0.33 segundos

El código se encuentra en GitHub.

Todos los abundantes hasta n son pares

PorJosé A. Alonso 6-octubre-202225-septiembre-2022

Definir la función

   todosPares :: Integer -> Bool

1	todosPares :: Integer -> Bool

tal que todosPares n se verifica si todos los números abundantes menores o iguales que n son pares. Por ejemplo,

   todosPares 10    ==  True
   todosPares 100   ==  True
   todosPares 1000  ==  False

todosPares 10 == True

todosPares 100 == True

todosPares 1000 == False

Soluciones en Haskell

module Todos_los_abundantes_hasta_n_son_pares where

import Math.NumberTheory.ArithmeticFunctions (sigma)
import Test.QuickCheck

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

todosPares1 :: Integer -> Bool
todosPares1 n = and [even x | x <- numerosAbundantesMenores1 n]

-- (numerosAbundantesMenores n) es la lista de números abundantes
-- menores o iguales que n. Por ejemplo,
--    numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
--    numerosAbundantesMenores 48  ==  [12,18,20,24,30,36,40,42,48]
numerosAbundantesMenores1 :: Integer -> [Integer]
numerosAbundantesMenores1 n =
  [x | x <- [1..n],
      numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo,
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
--    sumaDivisores 12                 ==  28
--    sumaDivisores 25                 ==  31
sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

-- Sustituyendo la definición de numerosAbundantesMenores de la solución
-- anterior por cada una de las del ejercicio anterior se obtiene una
-- nueva definición de todosPares. La usada en la definición anterior es
-- la menos eficiente y la que se usa en la siguiente definición es la
-- más eficiente.

todosPares2 :: Integer -> Bool
todosPares2 n = and [even x | x <- numerosAbundantesMenores2 n]

numerosAbundantesMenores2 :: Integer -> [Integer]
numerosAbundantesMenores2 n =
  [x | x <- [1..n],
      numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool
numeroAbundante2 x =
  x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

todosPares3 :: Integer -> Bool
todosPares3 1 = True
todosPares3 n | numeroAbundante1 n = even n && todosPares3 (n-1)
              | otherwise          = todosPares3 (n-1)

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

todosPares4 :: Integer -> Bool
todosPares4 n = all even (numerosAbundantesMenores1 n)

-- 5ª solución
-- ===========

todosPares5 :: Integer -> Bool
todosPares5 = all even . numerosAbundantesMenores1

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

-- La propiedad es
prop_todosPares :: Positive Integer -> Bool
prop_todosPares (Positive n) =
  all (== todosPares1 n)
      [todosPares2 n,
       todosPares3 n,
       todosPares4 n,
       todosPares5 n]

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

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

-- La comparación es
--    λ> todosPares1 (10^3)
--    False
--    (0.22 secs, 91,257,744 bytes)
--    λ> todosPares2 (10^3)
--    False
--    (0.01 secs, 2,535,656 bytes)
--    λ> todosPares3 (10^3)
--    False
--    (0.03 secs, 11,530,528 bytes)
--    λ> todosPares4 (10^3)
--    False
--    (0.24 secs, 91,231,144 bytes)
--    λ> todosPares5 (10^3)
--    False
--    (0.22 secs, 91,231,208 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

module Todos_los_abundantes_hasta_n_son_pares where

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

todosPares1 :: Integer -> Bool

todosPares1 n = and [even x | x <- numerosAbundantesMenores1 n]

-- (numerosAbundantesMenores n) es la lista de números abundantes

-- menores o iguales que n. Por ejemplo,

-- numerosAbundantesMenores 50 == [12,18,20,24,30,36,40,42,48]

-- numerosAbundantesMenores 48 == [12,18,20,24,30,36,40,42,48]

numerosAbundantesMenores1 :: Integer -> [Integer]

numerosAbundantesMenores1 n =

[x | x <- [1..n],

numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

-- sumaDivisores 12 == 28

-- sumaDivisores 25 == 31

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

-- Sustituyendo la definición de numerosAbundantesMenores de la solución

-- anterior por cada una de las del ejercicio anterior se obtiene una

-- nueva definición de todosPares. La usada en la definición anterior es

-- la menos eficiente y la que se usa en la siguiente definición es la

-- más eficiente.

todosPares2 :: Integer -> Bool

todosPares2 n = and [even x | x <- numerosAbundantesMenores2 n]

numerosAbundantesMenores2 :: Integer -> [Integer]

numerosAbundantesMenores2 n =

[x | x <- [1..n],

numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool

numeroAbundante2 x =

x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- 3ª solución

-- ===========

todosPares3 :: Integer -> Bool

todosPares3 1 = True

todosPares3 n | numeroAbundante1 n = even n && todosPares3 (n-1)

| otherwise = todosPares3 (n-1)

-- 4ª solución

-- ===========

todosPares4 :: Integer -> Bool

todosPares4 n = all even (numerosAbundantesMenores1 n)

-- 5ª solución

-- ===========

todosPares5 :: Integer -> Bool

todosPares5 = all even . numerosAbundantesMenores1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_todosPares :: Positive Integer -> Bool

prop_todosPares (Positive n) =

all (== todosPares1 n)

[todosPares2 n,

todosPares3 n,

todosPares4 n,

todosPares5 n]

-- La comprobación es

-- λ> quickCheck prop_todosPares

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> todosPares1 (10^3)

-- False

-- (0.22 secs, 91,257,744 bytes)

-- λ> todosPares2 (10^3)

-- False

-- (0.01 secs, 2,535,656 bytes)

-- λ> todosPares3 (10^3)

-- False

-- (0.03 secs, 11,530,528 bytes)

-- λ> todosPares4 (10^3)

-- False

-- (0.24 secs, 91,231,144 bytes)

-- λ> todosPares5 (10^3)

-- False

-- (0.22 secs, 91,231,208 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,
#    sumaDivisores(12)                ==  28
#    sumaDivisores(25)                ==  31
def sumaDivisores1(n: int) -> int:
    return sum(divisores1(n))

# numeroAbundante(n) se verifica si n es un número abundante. Por
# ejemplo,
#    numeroAbundante(5)  == False
#    numeroAbundante(12) == True
#    numeroAbundante(28) == False
#    numeroAbundante(30) == True
def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

# numerosAbundantesMenores(n) es la lista de números abundantes menores
# o iguales que n. Por ejemplo,
#    numerosAbundantesMenores(50)  ==  [12,18,20,24,30,36,40,42,48]
#    numerosAbundantesMenores(48)  ==  [12,18,20,24,30,36,40,42,48]
def numerosAbundantesMenores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if numeroAbundante1(x)]

def todosPares1(n: int) -> bool:
    return False not in [x % 2 == 0 for x in numerosAbundantesMenores1(n)]

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

# Sustituyendo la definición de numerosAbundantesMenores de la solución
# anterior por cada una de las del ejercicio anterior se obtiene una
# nueva definición de todosPares. La usada en la definición anterior es
# la menos eficiente y la que se usa en la siguiente definición es la
# más eficiente.

def sumaDivisores2(n: int) -> int:
    return divisor_sigma(n, 1)

def numeroAbundante2(x: int) -> bool:
    return x < sumaDivisores2(x) - x

def numerosAbundantesMenores2(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if numeroAbundante2(x)]

def todosPares2(n: int) -> bool:
    return False not in [x % 2 == 0 for x in numerosAbundantesMenores2(n)]

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

def todosPares3(n: int) -> bool:
    return all(x % 2 == 0 for x in numerosAbundantesMenores1(n))

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_todosPares(n: int) -> None:
    assert todosPares1(n) == todosPares2(n) == todosPares3(n)

# La comprobación es
#    src> poetry run pytest -q todos_los_abundantes_hasta_n_son_pares.py
#    1 passed in 2.63s

# 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('todosPares1(1000)')
#    0.03 segundos
#    >>> tiempo('todosPares2(1000)')
#    0.05 segundos
#    >>> tiempo('todosPares3(1000)')
#    0.02 segundos
#
#    >>> tiempo('todosPares1(10000)')
#    2.07 segundos
#    >>> tiempo('todosPares2(10000)')
#    0.47 segundos
#    >>> tiempo('todosPares3(10000)')
#    2.42 segundos

100

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,

# sumaDivisores(12) == 28

# sumaDivisores(25) == 31

def sumaDivisores1(n: int) -> int:

return sum(divisores1(n))

# numeroAbundante(n) se verifica si n es un número abundante. Por

# ejemplo,

# numeroAbundante(5) == False

# numeroAbundante(12) == True

# numeroAbundante(28) == False

# numeroAbundante(30) == True

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

# numerosAbundantesMenores(n) es la lista de números abundantes menores

# o iguales que n. Por ejemplo,

# numerosAbundantesMenores(50) == [12,18,20,24,30,36,40,42,48]

# numerosAbundantesMenores(48) == [12,18,20,24,30,36,40,42,48]

def numerosAbundantesMenores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if numeroAbundante1(x)]

def todosPares1(n: int) -> bool:

return False not in [x % 2 == 0 for x in numerosAbundantesMenores1(n)]

# 2ª solución

# ===========

# Sustituyendo la definición de numerosAbundantesMenores de la solución

# anterior por cada una de las del ejercicio anterior se obtiene una

# nueva definición de todosPares. La usada en la definición anterior es

# la menos eficiente y la que se usa en la siguiente definición es la

# más eficiente.

def sumaDivisores2(n: int) -> int:

return divisor_sigma(n, 1)

def numeroAbundante2(x: int) -> bool:

return x < sumaDivisores2(x) - x

def numerosAbundantesMenores2(n: int) -> list[int]:

return [x for x in range(1, n + 1) if numeroAbundante2(x)]

def todosPares2(n: int) -> bool:

return False not in [x % 2 == 0 for x in numerosAbundantesMenores2(n)]

# 3ª solución

# ===========

def todosPares3(n: int) -> bool:

return all(x % 2 == 0 for x in numerosAbundantesMenores1(n))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_todosPares(n: int) -> None:

assert todosPares1(n) == todosPares2(n) == todosPares3(n)

# La comprobación es

# src> poetry run pytest -q todos_los_abundantes_hasta_n_son_pares.py

# 1 passed in 2.63s

# 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('todosPares1(1000)')

# 0.03 segundos

# >>> tiempo('todosPares2(1000)')

# 0.05 segundos

# >>> tiempo('todosPares3(1000)')

# 0.02 segundos

# >>> tiempo('todosPares1(10000)')

# 2.07 segundos

# >>> tiempo('todosPares2(10000)')

# 0.47 segundos

# >>> tiempo('todosPares3(10000)')

# 2.42 segundos

El código se encuentra en GitHub.

Números abundantes menores o iguales que n

PorJosé A. Alonso 5-octubre-202225-septiembre-2022

Un número natural n se denomina abundante si es menor que la suma de sus divisores propios. Por ejemplo, 12 es abundante ya que la suma de sus divisores propios es 16 (= 1 + 2 + 3 + 4 + 6), pero 5 y 28 no lo son.

Definir la función

   numerosAbundantesMenores :: Integer -> [Integer]

1	numerosAbundantesMenores :: Integer -> [Integer]

tal que numerosAbundantesMenores n es la lista de números abundantes menores o iguales que n. Por ejemplo,

   numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
   numerosAbundantesMenores 48  ==  [12,18,20,24,30,36,40,42,48]
   length (numerosAbundantesMenores (10^6)) ==  247545

numerosAbundantesMenores 50 == [12,18,20,24,30,36,40,42,48]

numerosAbundantesMenores 48 == [12,18,20,24,30,36,40,42,48]

length (numerosAbundantesMenores (10^6)) == 247545

Soluciones en Haskell

import Math.NumberTheory.ArithmeticFunctions (sigma)
import Test.QuickCheck

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

numerosAbundantesMenores1 :: Integer -> [Integer]
numerosAbundantesMenores1 n =
  [x | x <- [1..n],
      numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo,
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
--    sumaDivisores 12                 ==  28
--    sumaDivisores 25                 ==  31
sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

-- Sustituyendo la definición de numeroAbundante de la solución anterior por
-- cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)
-- se obtiene una nueva definición de numerosAbundantesMenores. La usada en la
-- definición anterior es la menos eficiente y la que se usa en la
-- siguiente definición es la más eficiente.

numerosAbundantesMenores2 :: Integer -> [Integer]
numerosAbundantesMenores2 n =
  [x | x <- [1..n],
      numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool
numeroAbundante2 x =
  x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

numerosAbundantesMenores3 :: Integer -> [Integer]
numerosAbundantesMenores3 n =
  filter numeroAbundante2 [1..n]

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

numerosAbundantesMenores4 :: Integer -> [Integer]
numerosAbundantesMenores4 =
  filter numeroAbundante2 . enumFromTo 1

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

-- La propiedad es
prop_numerosAbundantesMenores :: Positive Integer -> Bool
prop_numerosAbundantesMenores (Positive n) =
  all (== numerosAbundantesMenores1 n)
      [numerosAbundantesMenores2 n,
       numerosAbundantesMenores3 n,
       numerosAbundantesMenores4 n]

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

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

-- La comparación es
--    λ> length (numerosAbundantesMenores1 (5*10^3))
--    1239
--    (5.49 secs, 2,508,692,808 bytes)
--    λ> length (numerosAbundantesMenores2 (5*10^3))
--    1239
--    (0.01 secs, 11,501,944 bytes)

--    λ> length (numerosAbundantesMenores2 (10^6))
--    247545
--    (1.48 secs, 2,543,048,024 bytes)
--    λ> length (numerosAbundantesMenores3 (10^6))
--    247545
--    (1.30 secs, 2,499,087,272 bytes)
--    λ> length (numerosAbundantesMenores4 (10^6))
--    247545
--    (1.30 secs, 2,499,087,248 bytes)

100

101

102

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

numerosAbundantesMenores1 :: Integer -> [Integer]

numerosAbundantesMenores1 n =

[x | x <- [1..n],

numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

-- sumaDivisores 12 == 28

-- sumaDivisores 25 == 31

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

-- Sustituyendo la definición de numeroAbundante de la solución anterior por

-- cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)

-- se obtiene una nueva definición de numerosAbundantesMenores. La usada en la

-- definición anterior es la menos eficiente y la que se usa en la

-- siguiente definición es la más eficiente.

numerosAbundantesMenores2 :: Integer -> [Integer]

numerosAbundantesMenores2 n =

[x | x <- [1..n],

numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool

numeroAbundante2 x =

x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- 3ª solución

-- ===========

numerosAbundantesMenores3 :: Integer -> [Integer]

numerosAbundantesMenores3 n =

filter numeroAbundante2 [1..n]

-- 4ª solución

-- ===========

numerosAbundantesMenores4 :: Integer -> [Integer]

numerosAbundantesMenores4 =

filter numeroAbundante2 . enumFromTo 1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_numerosAbundantesMenores :: Positive Integer -> Bool

prop_numerosAbundantesMenores (Positive n) =

all (== numerosAbundantesMenores1 n)

[numerosAbundantesMenores2 n,

numerosAbundantesMenores3 n,

numerosAbundantesMenores4 n]

-- La comprobación es

-- λ> quickCheck prop_numerosAbundantesMenores

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (numerosAbundantesMenores1 (5*10^3))

-- 1239

-- (5.49 secs, 2,508,692,808 bytes)

-- λ> length (numerosAbundantesMenores2 (5*10^3))

-- 1239

-- (0.01 secs, 11,501,944 bytes)

-- λ> length (numerosAbundantesMenores2 (10^6))

-- 247545

-- (1.48 secs, 2,543,048,024 bytes)

-- λ> length (numerosAbundantesMenores3 (10^6))

-- 247545

-- (1.30 secs, 2,499,087,272 bytes)

-- λ> length (numerosAbundantesMenores4 (10^6))

-- 247545

-- (1.30 secs, 2,499,087,248 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,
#    sumaDivisores(12)                ==  28
#    sumaDivisores(25)                ==  31
def sumaDivisores1(n: int) -> int:
    return sum(divisores1(n))

# numeroAbundante(n) se verifica si n es un número abundante. Por
# ejemplo,
#    numeroAbundante(5)  == False
#    numeroAbundante(12) == True
#    numeroAbundante(28) == False
#    numeroAbundante(30) == True
def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

def numerosAbundantesMenores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if numeroAbundante1(x)]

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

# Sustituyendo la definición de numeroAbundante de la solución anterior por
# cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)
# se obtiene una nueva definición de numerosAbundantesMenores. La usada en la
# definición anterior es la menos eficiente y la que se usa en la
# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:
    return divisor_sigma(n, 1)

def numeroAbundante2(x: int) -> bool:
    return x < sumaDivisores2(x) - x

def numerosAbundantesMenores2(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if numeroAbundante2(x)]

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_numerosAbundantesMenores(n: int) -> None:
    assert numerosAbundantesMenores1(n) == numerosAbundantesMenores2(n)

# La comprobación es
#    src> poetry run pytest -q numeros_abundantes_menores_o_iguales_que_n.py
#    1 passed in 1.54s

# 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(numerosAbundantesMenores1(10**4))')
#    2.21 segundos
#    >>> tiempo('len(numerosAbundantesMenores2(10**4))')
#    0.55 segundos
#
#    >>> tiempo('len(numerosAbundantesMenores2(10**5))')
#    5.96 segundos

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,

# sumaDivisores(12) == 28

# sumaDivisores(25) == 31

def sumaDivisores1(n: int) -> int:

return sum(divisores1(n))

# numeroAbundante(n) se verifica si n es un número abundante. Por

# ejemplo,

# numeroAbundante(5) == False

# numeroAbundante(12) == True

# numeroAbundante(28) == False

# numeroAbundante(30) == True

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

def numerosAbundantesMenores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if numeroAbundante1(x)]

# 2ª solución

# ===========

# Sustituyendo la definición de numeroAbundante de la solución anterior por

# cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)

# se obtiene una nueva definición de numerosAbundantesMenores. La usada en la

# definición anterior es la menos eficiente y la que se usa en la

# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:

return divisor_sigma(n, 1)

def numeroAbundante2(x: int) -> bool:

return x < sumaDivisores2(x) - x

def numerosAbundantesMenores2(n: int) -> list[int]:

return [x for x in range(1, n + 1) if numeroAbundante2(x)]

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_numerosAbundantesMenores(n: int) -> None:

assert numerosAbundantesMenores1(n) == numerosAbundantesMenores2(n)

# La comprobación es

# src> poetry run pytest -q numeros_abundantes_menores_o_iguales_que_n.py

# 1 passed in 1.54s

# 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(numerosAbundantesMenores1(10**4))')

# 2.21 segundos

# >>> tiempo('len(numerosAbundantesMenores2(10**4))')

# 0.55 segundos

# >>> tiempo('len(numerosAbundantesMenores2(10**5))')

# 5.96 segundos

El código se encuentra en GitHub

Números abundantes

PorJosé A. Alonso 4-octubre-202214-diciembre-2022

Definir la función

   numeroAbundante :: Int -> Bool

1	numeroAbundante :: Int -> Bool

tal que numeroAbundante n se verifica si n es un número abundante. Por ejemplo,

   numeroAbundante 5  == False
   numeroAbundante 12 == True
   numeroAbundante 28 == False
   numeroAbundante 30 == True
   numeroAbundante 100000000  ==  True
   numeroAbundante 100000001  ==  False

numeroAbundante 5 == False

numeroAbundante 12 == True

numeroAbundante 28 == False

numeroAbundante 30 == True

numeroAbundante 100000000 == True

numeroAbundante 100000001 == False

Soluciones

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

Soluciones en Haskell

import Math.NumberTheory.ArithmeticFunctions (sigma)
import Test.QuickCheck

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

numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
--    sumaDivisores 12                 ==  28
--    sumaDivisores 25                 ==  31
sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

-- Sustituyendo la definición de sumaDivisores de la solución anterior por
-- cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)
-- se obtiene una nueva definición de numeroAbundante. La usada en la
-- definición anterior es la menos eficiente y la que se usa en la
-- siguiente definición es la más eficiente.

numeroAbundante2 :: Integer -> Bool
numeroAbundante2 x =
  x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

-- La propiedad es
prop_numeroAbundante :: Positive Integer -> Bool
prop_numeroAbundante (Positive n) =
  numeroAbundante1 n == numeroAbundante2 n

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

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

-- La comparación es
--    λ> numeroAbundante1 (5*10^6)
--    True
--    (2.55 secs, 1,000,558,840 bytes)
--    λ> numeroAbundante2 (5*10^6)
--    True
--    (0.00 secs, 555,408 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 x - x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

-- sumaDivisores 12 == 28

-- sumaDivisores 25 == 31

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

-- Sustituyendo la definición de sumaDivisores de la solución anterior por

-- cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)

-- se obtiene una nueva definición de numeroAbundante. La usada en la

-- definición anterior es la menos eficiente y la que se usa en la

-- siguiente definición es la más eficiente.

numeroAbundante2 :: Integer -> Bool

numeroAbundante2 x =

x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_numeroAbundante :: Positive Integer -> Bool

prop_numeroAbundante (Positive n) =

numeroAbundante1 n == numeroAbundante2 n

-- La comprobación es

-- λ> quickCheck prop_numeroAbundante

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> numeroAbundante1 (5*10^6)

-- True

-- (2.55 secs, 1,000,558,840 bytes)

-- λ> numeroAbundante2 (5*10^6)

-- True

-- (0.00 secs, 555,408 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,
#    sumaDivisores(12)                ==  28
#    sumaDivisores(25)                ==  31
def sumaDivisores1(n: int) -> int:
    return sum(divisores1(n))

def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

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

# Sustituyendo la definición de sumaDivisores de la solución anterior por
# cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)
# se obtiene una nueva definición de numeroAbundante. La usada en la
# definición anterior es la menos eficiente y la que se usa en la
# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:
    return divisor_sigma(n, 1)

def numeroAbundante2(x: int) -> bool:
    return x < sumaDivisores2(x) - x

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_numeroAbundante(n):
    assert numeroAbundante1(n) == numeroAbundante2(n)

# La comprobación es
#    src> poetry run pytest -q numeros_abundantes.py
#    1 passed in 0.38s

# 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('numeroAbundante1(4 * 10**7)')
#    2.02 segundos
#    >>> tiempo('numeroAbundante2(4 * 10**7)')
#    0.00 segundos

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,

# sumaDivisores(12) == 28

# sumaDivisores(25) == 31

def sumaDivisores1(n: int) -> int:

return sum(divisores1(n))

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

# 2ª solución

# ===========

# Sustituyendo la definición de sumaDivisores de la solución anterior por

# cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)

# se obtiene una nueva definición de numeroAbundante. La usada en la

# definición anterior es la menos eficiente y la que se usa en la

# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:

return divisor_sigma(n, 1)

def numeroAbundante2(x: int) -> bool:

return x < sumaDivisores2(x) - x

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_numeroAbundante(n):

assert numeroAbundante1(n) == numeroAbundante2(n)

# La comprobación es

# src> poetry run pytest -q numeros_abundantes.py

# 1 passed in 0.38s

# 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('numeroAbundante1(4 * 10**7)')

# 2.02 segundos

# >>> tiempo('numeroAbundante2(4 * 10**7)')

# 0.00 segundos

El código se encuentra en GitHub.

Números perfectos

PorJosé A. Alonso 3-octubre-202214-diciembre-2022

Un números entero positivo es perfecto es igual a la suma de sus divisores, excluyendo el propio número. Por ejemplo, 6 es un número perfecto porque sus divisores propios son 1, 2 y 3; y 6 = 1 + 2 + 3.

Definir la función

   perfectos :: Integer -> [Integer]

1	perfectos :: Integer -> [Integer]

tal que perfectos n es la lista de todos los números perfectos menores o iguales que n. Por ejemplo,

   perfectos 500     ==  [6,28,496]
   perfectos (10^5)  ==  [6,28,496,8128]

1 2	perfectos 500 == [6,28,496] perfectos (10^5) == [6,28,496,8128]

Soluciones

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

Soluciones en Haskell

import Math.NumberTheory.ArithmeticFunctions (sigma)
import Test.QuickCheck

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

perfectos1 :: Integer -> [Integer]
perfectos1 n =
  [x | x <- [1..n],
       esPerfecto1 x]

-- (esPerfecto x) se verifica si x es un número perfecto. Por ejemplo,
--    esPerfecto 6  ==  True
--    esPerfecto 8  ==  False
esPerfecto1 :: Integer -> Bool
esPerfecto1 x =
  sumaDivisores1 x - x == x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
--    sumaDivisores 12                 ==  28
--    sumaDivisores 25                 ==  31
sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

-- Sustituyendo la definición de sumaDivisores de la solución anterior por
-- cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)
-- se obtiene una nueva definición deperfectos. La usada en la
-- definición anterior es la menos eficiente y la que se usa en la
-- siguiente definición es la más eficiente.

perfectos2 :: Integer -> [Integer]
perfectos2 n =
  [x | x <- [1..n],
       esPerfecto2 x]

esPerfecto2 :: Integer -> Bool
esPerfecto2 x =
  sumaDivisores2 x - x == x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

perfectos3 :: Integer -> [Integer]
perfectos3 n = filter esPerfecto2 [1..n]

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

perfectos4 :: Integer -> [Integer]
perfectos4 = filter esPerfecto2 . enumFromTo 1

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

-- La propiedad es
prop_perfectos :: Positive Integer -> Bool
prop_perfectos (Positive n) =
  all (== perfectos1 n)
      [perfectos2 n,
       perfectos3 n,
       perfectos4 n]

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

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

-- La comparación es
--    λ> perfectos1 (4*10^3)
--    [6,28,496]
--    (4.64 secs, 1,606,883,384 bytes)
--    λ> perfectos2 (4*10^3)
--    [6,28,496]
--    (0.02 secs, 9,167,208 bytes)
--
--    λ> perfectos2 (2*10^6)
--    [6,28,496,8128]
--    (3.32 secs, 5,120,880,728 bytes)
--    λ> perfectos3 (2*10^6)
--    [6,28,496,8128]
--    (2.97 secs, 5,040,880,632 bytes)
--    λ> perfectos4 (2*10^6)
--    [6,28,496,8128]
--    (2.80 secs, 5,040,880,608 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

perfectos1 :: Integer -> [Integer]

perfectos1 n =

[x | x <- [1..n],

esPerfecto1 x]

-- (esPerfecto x) se verifica si x es un número perfecto. Por ejemplo,

-- esPerfecto 6 == True

-- esPerfecto 8 == False

esPerfecto1 :: Integer -> Bool

esPerfecto1 x =

sumaDivisores1 x - x == x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

-- sumaDivisores 12 == 28

-- sumaDivisores 25 == 31

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

-- Sustituyendo la definición de sumaDivisores de la solución anterior por

-- cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)

-- se obtiene una nueva definición deperfectos. La usada en la

-- definición anterior es la menos eficiente y la que se usa en la

-- siguiente definición es la más eficiente.

perfectos2 :: Integer -> [Integer]

perfectos2 n =

[x | x <- [1..n],

esPerfecto2 x]

esPerfecto2 :: Integer -> Bool

esPerfecto2 x =

sumaDivisores2 x - x == x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- 3ª solución

-- ===========

perfectos3 :: Integer -> [Integer]

perfectos3 n = filter esPerfecto2 [1..n]

-- 4ª solución

-- ===========

perfectos4 :: Integer -> [Integer]

perfectos4 = filter esPerfecto2 . enumFromTo 1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_perfectos :: Positive Integer -> Bool

prop_perfectos (Positive n) =

all (== perfectos1 n)

[perfectos2 n,

perfectos3 n,

perfectos4 n]

-- La comprobación es

-- λ> quickCheck prop_perfectos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> perfectos1 (4*10^3)

-- [6,28,496]

-- (4.64 secs, 1,606,883,384 bytes)

-- λ> perfectos2 (4*10^3)

-- [6,28,496]

-- (0.02 secs, 9,167,208 bytes)

-- λ> perfectos2 (2*10^6)

-- [6,28,496,8128]

-- (3.32 secs, 5,120,880,728 bytes)

-- λ> perfectos3 (2*10^6)

-- [6,28,496,8128]

-- (2.97 secs, 5,040,880,632 bytes)

-- λ> perfectos4 (2*10^6)

-- [6,28,496,8128]

-- (2.80 secs, 5,040,880,608 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,
#    sumaDivisores(12)                ==  28
#    sumaDivisores(25)                ==  31
def sumaDivisores1(n: int) -> int:
    return sum(divisores1(n))

# esPerfecto(x) se verifica si x es un número perfecto. Por ejemplo,
#    esPerfecto(6)  ==  True
#    esPerfecto(8)  ==  False
def esPerfecto1(x: int) -> bool:
    return sumaDivisores1(x) - x == x

def perfectos1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if esPerfecto1(x)]

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

# Sustituyendo la definición de sumaDivisores de la solución anterior por
# cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)
# se obtiene una nueva definición deperfectos. La usada en la
# definición anterior es la menos eficiente y la que se usa en la
# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:
    return divisor_sigma(n, 1)

def esPerfecto2(x: int) -> bool:
    return sumaDivisores2(x) - x == x

def perfectos2(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if esPerfecto2(x)]

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_perfectos(n):
    assert perfectos1(n) == perfectos2(n)

# La comprobación es
#    src> poetry run pytest -q numeros_perfectos.py
#    1 passed in 1.43s

# 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('perfectos1(10**4)')
#    2.97 segundos
#    >>> tiempo('perfectos2(10**4)')
#    0.57 segundos

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy import divisor_sigma

# 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]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,

# sumaDivisores(12) == 28

# sumaDivisores(25) == 31

def sumaDivisores1(n: int) -> int:

return sum(divisores1(n))

# esPerfecto(x) se verifica si x es un número perfecto. Por ejemplo,

# esPerfecto(6) == True

# esPerfecto(8) == False

def esPerfecto1(x: int) -> bool:

return sumaDivisores1(x) - x == x

def perfectos1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if esPerfecto1(x)]

# 2ª solución

# ===========

# Sustituyendo la definición de sumaDivisores de la solución anterior por

# cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)

# se obtiene una nueva definición deperfectos. La usada en la

# definición anterior es la menos eficiente y la que se usa en la

# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:

return divisor_sigma(n, 1)

def esPerfecto2(x: int) -> bool:

return sumaDivisores2(x) - x == x

def perfectos2(n: int) -> list[int]:

return [x for x in range(1, n + 1) if esPerfecto2(x)]

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_perfectos(n):

assert perfectos1(n) == perfectos2(n)

# La comprobación es

# src> poetry run pytest -q numeros_perfectos.py

# 1 passed in 1.43s

# 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('perfectos1(10**4)')

# 2.97 segundos

# >>> tiempo('perfectos2(10**4)')

# 0.57 segundos

El código se encuentra en GitHub.

Suma de divisores

PorJosé A. Alonso 1-octubre-202214-diciembre-2022

Definir la función

   sumaDivisores :: Integer -> Integer

1	sumaDivisores :: Integer -> Integer

tal que sumaDivisores x es la suma de los divisores de x. Por ejemplo,

   sumaDivisores 12                 ==  28
   sumaDivisores 25                 ==  31
   sumaDivisores (product [1..25])  ==  93383273455325195473152000
   length (show (sumaDivisores (product [1..30000])))  ==  121289
   maximum (map sumaDivisores [1..2*10^6])             ==  8851392

sumaDivisores 12 == 28

sumaDivisores 25 == 31

sumaDivisores (product [1..25]) == 93383273455325195473152000

length (show (sumaDivisores (product [1..30000]))) == 121289

maximum (map sumaDivisores [1..2*10^6]) == 8851392

Soluciones

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

Soluciones en Haskell

import Data.List (foldl', genericLength, group, inits)
import Data.Set (toList)
import Data.Numbers.Primes (primeFactors)
import Math.NumberTheory.ArithmeticFunctions (divisors, sigma)
import Test.QuickCheck

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

sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

-- Sustituyendo la definición de divisores de la solución anterior por
-- cada una de las del ejercicio [Divisores de un número](https://bit.ly/3S1HYwi)
-- Se obtiene una nueva definición de sumaDivisores. La usada en la
-- definición anterior es la menos eficiente y la que se usa en la
-- siguiente definición es la más eficiente.

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sum . divisores2

divisores2 :: Integer -> [Integer]
divisores2 = toList . divisors

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

-- La solución anterior se puede simplificar

sumaDivisores3 :: Integer -> Integer
sumaDivisores3 = sum . divisors

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

sumaDivisores4 :: Integer -> Integer
sumaDivisores4 = foldl' (+) 0 . divisores2

-- 5ª solución
-- ===========

sumaDivisores5 :: Integer -> Integer
sumaDivisores5 n = aux [1..n]
  where aux [] = 0
        aux (x:xs) | n `rem` x == 0 = x + aux xs
                   | otherwise      = aux xs

-- 6ª solución
-- ===========

sumaDivisores6 :: Integer -> Integer
sumaDivisores6 = sum
               . map (product . concat)
               . mapM inits
               . group
               . primeFactors

-- 7ª solución
-- ===========

-- Si la descomposición de x en factores primos es
--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
-- entonces la suma de los divisores de x es
--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
--   ------------------- . ------------------- ... -------------------
--        p(1)-1                p(2)-1                  p(n)-1
-- Ver la demostración en http://bit.ly/2zUXZPc

sumaDivisores7 :: Integer -> Integer
sumaDivisores7 x =
  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de la
-- descomposición prima de x. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) =
  (x, 1 + genericLength xs)

-- 8ª solución
-- ===========

sumaDivisores8 :: Integer -> Integer
sumaDivisores8 = sigma 1

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

-- La propiedad es
prop_sumaDivisores :: Positive Integer -> Bool
prop_sumaDivisores (Positive x) =
  all (== sumaDivisores1 x)
      [ sumaDivisores2 x
      , sumaDivisores3 x
      , sumaDivisores4 x
      , sumaDivisores5 x
      , sumaDivisores6 x
      , sumaDivisores7 x
      , sumaDivisores8 x
      ]

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

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

-- La comparación es
--    λ> sumaDivisores1 5336100
--    21386001
--    (2.25 secs, 1,067,805,248 bytes)
--    λ> sumaDivisores2 5336100
--    21386001
--    (0.01 secs, 659,112 bytes)
--    λ> sumaDivisores3 5336100
--    21386001
--    (0.01 secs, 635,688 bytes)
--    λ> sumaDivisores4 5336100
--    21386001
--    (0.01 secs, 648,992 bytes)
--    λ> sumaDivisores5 5336100
--    21386001
--    (2.44 secs, 1,323,924,176 bytes)
--    λ> sumaDivisores6 5336100
--    21386001
--    (0.01 secs, 832,104 bytes)
--    λ> sumaDivisores7 5336100
--    21386001
--    (0.01 secs, 571,040 bytes)
--    λ> sumaDivisores8 5336100
--    21386001
--    (0.00 secs, 558,296 bytes)
--
--    λ> sumaDivisores2 251888923423315469521109880000000
--    1471072204661054993275791673480320
--    (2.30 secs, 1,130,862,080 bytes)
--    λ> sumaDivisores3 251888923423315469521109880000000
--    1471072204661054993275791673480320
--    (1.83 secs, 896,386,232 bytes)
--    λ> sumaDivisores4 251888923423315469521109880000000
--    1471072204661054993275791673480320
--    (1.52 secs, 997,992,328 bytes)
--    λ> sumaDivisores6 251888923423315469521109880000000
--    1471072204661054993275791673480320
--    (2.35 secs, 5,719,848,600 bytes)
--    λ> sumaDivisores7 251888923423315469521109880000000
--    1471072204661054993275791673480320
--    (0.00 secs, 628,136 bytes)
--    λ> sumaDivisores8 251888923423315469521109880000000
--    1471072204661054993275791673480320
--    (0.00 secs, 591,352 bytes)
--
--    λ> length (show (sumaDivisores7 (product [1..30000])))
--    121289
--    (2.76 secs, 4,864,576,304 bytes)
--    λ> length (show (sumaDivisores8 (product [1..30000])))
--    121289
--    (1.65 secs, 3,173,319,312 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

import Data.List (foldl', genericLength, group, inits)

import Data.Set (toList)

import Data.Numbers.Primes (primeFactors)

import Math.NumberTheory.ArithmeticFunctions (divisors, sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

-- Sustituyendo la definición de divisores de la solución anterior por

-- cada una de las del ejercicio [Divisores de un número](https://bit.ly/3S1HYwi)

-- Se obtiene una nueva definición de sumaDivisores. La usada en la

-- definición anterior es la menos eficiente y la que se usa en la

-- siguiente definición es la más eficiente.

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sum . divisores2

divisores2 :: Integer -> [Integer]

divisores2 = toList . divisors

-- 3ª solución

-- ===========

-- La solución anterior se puede simplificar

sumaDivisores3 :: Integer -> Integer

sumaDivisores3 = sum . divisors

-- 4ª solución

-- ===========

sumaDivisores4 :: Integer -> Integer

sumaDivisores4 = foldl' (+) 0 . divisores2

-- 5ª solución

-- ===========

sumaDivisores5 :: Integer -> Integer

sumaDivisores5 n = aux [1..n]

where aux [] = 0

aux (x:xs) | n `rem` x == 0 = x + aux xs

| otherwise = aux xs

-- 6ª solución

-- ===========

sumaDivisores6 :: Integer -> Integer

sumaDivisores6 = sum

. map (product . concat)

. mapM inits

. group

. primeFactors

-- 7ª solución

-- ===========

-- Si la descomposición de x en factores primos es

-- x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)

-- entonces la suma de los divisores de x es

-- p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1

-- ------------------- . ------------------- ... -------------------

-- p(1)-1 p(2)-1 p(n)-1

-- Ver la demostración en http://bit.ly/2zUXZPc

sumaDivisores7 :: Integer -> Integer

sumaDivisores7 x =

product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de la

-- descomposición prima de x. Por ejemplo,

-- factorizacion 600 == [(2,3),(3,1),(5,2)]

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

factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs

-- y la longitud de xs. Por ejemplo,

-- primeroYlongitud [3,2,5,7] == (3,4)

primeroYlongitud :: [a] -> (a,Integer)

primeroYlongitud (x:xs) =

(x, 1 + genericLength xs)

-- 8ª solución

-- ===========

sumaDivisores8 :: Integer -> Integer

sumaDivisores8 = sigma 1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_sumaDivisores :: Positive Integer -> Bool

prop_sumaDivisores (Positive x) =

all (== sumaDivisores1 x)

[ sumaDivisores2 x

, sumaDivisores3 x

, sumaDivisores4 x

, sumaDivisores5 x

, sumaDivisores6 x

, sumaDivisores7 x

, sumaDivisores8 x

]

-- La comprobación es

-- λ> quickCheck prop_sumaDivisores

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> sumaDivisores1 5336100

-- 21386001

-- (2.25 secs, 1,067,805,248 bytes)

-- λ> sumaDivisores2 5336100

-- 21386001

-- (0.01 secs, 659,112 bytes)

-- λ> sumaDivisores3 5336100

-- 21386001

-- (0.01 secs, 635,688 bytes)

-- λ> sumaDivisores4 5336100

-- 21386001

-- (0.01 secs, 648,992 bytes)

-- λ> sumaDivisores5 5336100

-- 21386001

-- (2.44 secs, 1,323,924,176 bytes)

-- λ> sumaDivisores6 5336100

-- 21386001

-- (0.01 secs, 832,104 bytes)

-- λ> sumaDivisores7 5336100

-- 21386001

-- (0.01 secs, 571,040 bytes)

-- λ> sumaDivisores8 5336100

-- 21386001

-- (0.00 secs, 558,296 bytes)

-- λ> sumaDivisores2 251888923423315469521109880000000

-- 1471072204661054993275791673480320

-- (2.30 secs, 1,130,862,080 bytes)

-- λ> sumaDivisores3 251888923423315469521109880000000

-- 1471072204661054993275791673480320

-- (1.83 secs, 896,386,232 bytes)

-- λ> sumaDivisores4 251888923423315469521109880000000

-- 1471072204661054993275791673480320

-- (1.52 secs, 997,992,328 bytes)

-- λ> sumaDivisores6 251888923423315469521109880000000

-- 1471072204661054993275791673480320

-- (2.35 secs, 5,719,848,600 bytes)

-- λ> sumaDivisores7 251888923423315469521109880000000

-- 1471072204661054993275791673480320

-- (0.00 secs, 628,136 bytes)

-- λ> sumaDivisores8 251888923423315469521109880000000

-- 1471072204661054993275791673480320

-- (0.00 secs, 591,352 bytes)

-- λ> length (show (sumaDivisores7 (product [1..30000])))

-- 121289

-- (2.76 secs, 4,864,576,304 bytes)

-- λ> length (show (sumaDivisores8 (product [1..30000])))

-- 121289

-- (1.65 secs, 3,173,319,312 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import mul
from functools import reduce
from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import divisors, divisor_sigma, factorint
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

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

# divisores(x) es la lista de los divisores de x. Por ejemplo,
#    divisores(60)  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
def divisores(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

def sumaDivisores1(n: int) -> int:
    return sum(divisores(n))

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

# Sustituyendo la definición de divisores de la solución anterior por
# cada una de las del ejercicio Divisores de un número https://bit.ly/3S1HYwi)
# Se obtiene una nueva definición de sumaDivisores. La usada en la
# definición anterior es la menos eficiente y la que se usa en la
# siguiente definición es la más eficiente.
def sumaDivisores2(n: int) -> int:
    return sum(divisors(n))

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

def sumaDivisores3(n: int) -> int:
    def aux(xs: list[int]) -> int:
        if xs:
            if n % xs[0] == 0:
                return xs[0] + aux(xs[1:])
            return aux(xs[1:])
        return 0

    return aux(list(range(1, n + 1)))

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

# Si la descomposición de x en factores primos es
#    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
# entonces la suma de los divisores de x es
#    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
#   ------------------- . ------------------- ... -------------------
#        p(1)-1                p(2)-1                  p(n)-1
# Ver la demostración en http://bit.ly/2zUXZPc

def sumaDivisores4(n: int) -> int:
    return reduce(mul, [(p ** (e + 1) - 1) // (p - 1)
                        for (p, e) in factorint(n).items()])

# 5ª solución
# ===========

def sumaDivisores5(n: int) -> int:
    x = 1
    r1 = 0
    r2 = 0
    while x * x < n:
        if n % x == 0:
            r1 += x
            r2 += n // x
        x += 1
    if x * x == n:
        r1 += x
    return r1 + r2

# 6ª solución
# ===========

def sumaDivisores6(n: int) -> int:
    return divisor_sigma(n, 1)

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_sumaDivisores(n):
    r = sumaDivisores1(n)
    assert sumaDivisores2(n) == r
    assert sumaDivisores3(n) == r
    assert sumaDivisores4(n) == r
    assert sumaDivisores5(n) == r
    assert sumaDivisores6(n) == r

# La comprobación es
#    src> poetry run pytest -q suma_de_divisores.py
#    1 passed in 0.90s

# 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('sumaDivisores1(5336100)')
#    0.29 segundos
#    >>> tiempo('sumaDivisores2(5336100)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores3(5336100)')
#    Process Python terminado (killed)
#    >>> tiempo('sumaDivisores4(5336100)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores5(5336100)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores6(5336100)')
#    0.00 segundos
#
#    >>> tiempo('sumaDivisores1(2**9 * 3**8 * 5**2)')
#    4.52 segundos
#    >>> tiempo('sumaDivisores2(2**9 * 3**8 * 5**2)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores4(2**9 * 3**8 * 5**2)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores5(2**9 * 3**8 * 5**2)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores6(2**9 * 3**8 * 5**2)')
#    0.00 segundos
#
#    >>> tiempo('sumaDivisores2(2**9 * 3**8 * 5**7 * 7**4)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores4(2**9 * 3**8 * 5**7 * 7**4)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores5(2**9 * 3**8 * 5**7 * 7**4)')
#    3.24 segundos
#    >>> tiempo('sumaDivisores6(2**9 * 3**8 * 5**7 * 7**4)')
#    0.00 segundos
#
#    >>> tiempo('sumaDivisores2(251888923423315469521109880000000)')
#    1.13 segundos
#    >>> tiempo('sumaDivisores4(251888923423315469521109880000000)')
#    0.00 segundos
#    >>> tiempo('sumaDivisores6(251888923423315469521109880000000)')
#    0.00 segundos
#
#    >>> tiempo('sumaDivisores4(reduce(mul, list(range(1, 30000))))')
#    1.89 segundos
#    >>> tiempo('sumaDivisores6(reduce(mul, list(range(1, 30000))))')
#    1.88 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

from operator import mul

from functools import reduce

from timeit import Timer, default_timer

from sys import setrecursionlimit

from sympy import divisors, divisor_sigma, factorint

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

# divisores(x) es la lista de los divisores de x. Por ejemplo,

# divisores(60) == [1,5,3,15,2,10,6,30,4,20,12,60]

def divisores(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

def sumaDivisores1(n: int) -> int:

return sum(divisores(n))

# 2ª solución

# ===========

# Sustituyendo la definición de divisores de la solución anterior por

# cada una de las del ejercicio Divisores de un número https://bit.ly/3S1HYwi)

# Se obtiene una nueva definición de sumaDivisores. La usada en la

# definición anterior es la menos eficiente y la que se usa en la

# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:

return sum(divisors(n))

# 3ª solución

# ===========

def sumaDivisores3(n: int) -> int:

def aux(xs: list[int]) -> int:

if xs:

if n % xs[0] == 0:

return xs[0] + aux(xs[1:])

return aux(xs[1:])

return 0

return aux(list(range(1, n + 1)))

# 4ª solución

# ===========

# Si la descomposición de x en factores primos es

# x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)

# entonces la suma de los divisores de x es

# p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1

# ------------------- . ------------------- ... -------------------

# p(1)-1 p(2)-1 p(n)-1

# Ver la demostración en http://bit.ly/2zUXZPc

def sumaDivisores4(n: int) -> int:

return reduce(mul, [(p ** (e + 1) - 1) // (p - 1)

for (p, e) in factorint(n).items()])

# 5ª solución

# ===========

def sumaDivisores5(n: int) -> int:

x = 1

r1 = 0

r2 = 0

while x * x < n:

if n % x == 0:

r1 += x

r2 += n // x

x += 1

if x * x == n:

r1 += x

return r1 + r2

# 6ª solución

# ===========

def sumaDivisores6(n: int) -> int:

return divisor_sigma(n, 1)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_sumaDivisores(n):

r = sumaDivisores1(n)

assert sumaDivisores2(n) == r

assert sumaDivisores3(n) == r

assert sumaDivisores4(n) == r

assert sumaDivisores5(n) == r

assert sumaDivisores6(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_divisores.py

# 1 passed in 0.90s

# 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('sumaDivisores1(5336100)')

# 0.29 segundos

# >>> tiempo('sumaDivisores2(5336100)')

# 0.00 segundos

# >>> tiempo('sumaDivisores3(5336100)')

# Process Python terminado (killed)

# >>> tiempo('sumaDivisores4(5336100)')

# 0.00 segundos

# >>> tiempo('sumaDivisores5(5336100)')

# 0.00 segundos

# >>> tiempo('sumaDivisores6(5336100)')

# 0.00 segundos

# >>> tiempo('sumaDivisores1(2**9 * 3**8 * 5**2)')

# 4.52 segundos

# >>> tiempo('sumaDivisores2(2**9 * 3**8 * 5**2)')

# 0.00 segundos

# >>> tiempo('sumaDivisores4(2**9 * 3**8 * 5**2)')

# 0.00 segundos

# >>> tiempo('sumaDivisores5(2**9 * 3**8 * 5**2)')

# 0.00 segundos

# >>> tiempo('sumaDivisores6(2**9 * 3**8 * 5**2)')

# 0.00 segundos

# >>> tiempo('sumaDivisores2(2**9 * 3**8 * 5**7 * 7**4)')

# 0.00 segundos

# >>> tiempo('sumaDivisores4(2**9 * 3**8 * 5**7 * 7**4)')

# 0.00 segundos

# >>> tiempo('sumaDivisores5(2**9 * 3**8 * 5**7 * 7**4)')

# 3.24 segundos

# >>> tiempo('sumaDivisores6(2**9 * 3**8 * 5**7 * 7**4)')

# 0.00 segundos

# >>> tiempo('sumaDivisores2(251888923423315469521109880000000)')

# 1.13 segundos

# >>> tiempo('sumaDivisores4(251888923423315469521109880000000)')

# 0.00 segundos

# >>> tiempo('sumaDivisores6(251888923423315469521109880000000)')

# 0.00 segundos

# >>> tiempo('sumaDivisores4(reduce(mul, list(range(1, 30000))))')

# 1.89 segundos

# >>> tiempo('sumaDivisores6(reduce(mul, list(range(1, 30000))))')

# 1.88 segundos

El código se encuentra en GitHub.

Meses: octubre 2022

Número a partir de sus dígitos

Suma de los dígitos de un número

Dígitos de un número

Algoritmo de Euclides del mcd

Potencia entera

Base de datos de actividades

Representación densa de polinomios

Suma de elementos consecutivos

Producto escalar

Ternas pitagóricas con suma dada

Ternas pitagóricas

Cálculo del número π mediante la fórmula de Leibniz

Aproximación al límite de sen(x)/x cuando x tiende a cero

Aproximación del número e

Puntos en el círculo

Suma de múltiplos de 3 ó 5

Números abundantes impares

Todos los abundantes hasta n son pares

Números abundantes menores o iguales que n

Números abundantes

Números perfectos

Suma de divisores

Entradas recientes

Buscar

Correo electrónico