septiembre 2022 – Exercitium

Triángulo aritmético

PorJosé A. Alonso 30-septiembre-202214-diciembre-2022

Los triángulos aritméticos se forman como sigue

    1
    2  3
    4  5  6
    7  8  9 10
   11 12 13 14 15
   16 17 18 19 20 21

2 3

4 5 6

7 8 9 10

11 12 13 14 15

16 17 18 19 20 21

Definir las funciones

   linea     :: Integer -> [Integer]
   triangulo :: Integer -> [[Integer]]

1 2	linea :: Integer -> [Integer] triangulo :: Integer -> [[Integer]]

tales que

linea n es la línea n-ésima de los triángulos aritméticos. Por ejemplo,

     linea 4  ==  [7,8,9,10]
     linea 5  ==  [11,12,13,14,15]
     head (linea (10^20)) == 4999999999999999999950000000000000000001

linea 4 == [7,8,9,10]

linea 5 == [11,12,13,14,15]

head (linea (10^20)) == 4999999999999999999950000000000000000001

triangulo n es el triángulo aritmético de altura n. Por ejemplo,

     triangulo 3  ==  [[1],[2,3],[4,5,6]]
     triangulo 4  ==  [[1],[2,3],[4,5,6],[7,8,9,10]]

1 2	triangulo 3 == [[1],[2,3],[4,5,6]] triangulo 4 == [[1],[2,3],[4,5,6],[7,8,9,10]]

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 línea
-- ======================

linea1 :: Integer -> [Integer]
linea1 n = [suma1 (n-1)+1..suma1 n]

-- (suma n) es la suma de los n primeros números. Por ejemplo,
--    suma 3  ==  6
suma1 :: Integer -> Integer
suma1 n = sum [1..n]

-- 2ª definición de línea
-- ======================

linea2 :: Integer -> [Integer]
linea2 n = [s+1..s+n]
  where s = suma1 (n-1)

-- 3ª definición de línea
-- ======================

linea3 :: Integer -> [Integer]
linea3 n = [s+1..s+n]
  where s = suma2 (n-1)

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

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

-- La propiedad es
prop_linea :: Positive Integer -> Bool
prop_linea (Positive n) =
  all (== linea1 n)
      [linea2 n,
       linea3 n]

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

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

-- La comparación es
--    λ> last (linea1 (10^7))
--    50000005000000
--    (5.10 secs, 3,945,159,856 bytes)
--    λ> last (linea2 (10^7))
--    50000005000000
--    (3.11 secs, 2,332,859,512 bytes)
--    λ> last (linea3 (10^7))
--    50000005000000
--    (0.16 secs, 720,559,384 bytes)

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

triangulo1 :: Integer -> [[Integer]]
triangulo1 n = [linea1 m | m <- [1..n]]

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

triangulo2 :: Integer -> [[Integer]]
triangulo2 n = [linea2 m | m <- [1..n]]

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

triangulo3 :: Integer -> [[Integer]]
triangulo3 n = [linea3 m | m <- [1..n]]

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

-- La propiedad es
prop_triangulo :: Positive Integer -> Bool
prop_triangulo (Positive n) =
  all (== triangulo1 n)
      [triangulo2 n,
       triangulo3 n]

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

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

-- La comparación es
--    λ> last (last (triangulo1 (3*10^6)))
--    4500001500000
--    (2.25 secs, 1,735,919,184 bytes)
--    λ> last (last (triangulo2 (3*10^6)))
--    4500001500000
--    (1.62 secs, 1,252,238,872 bytes)
--    λ> last (last (triangulo3 (3*10^6)))
--    4500001500000
--    (0.79 secs, 768,558,776 bytes)

100

101

102

103

import Test.QuickCheck

-- 1ª definición de línea

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

linea1 :: Integer -> [Integer]

linea1 n = [suma1 (n-1)+1..suma1 n]

-- (suma n) es la suma de los n primeros números. Por ejemplo,

-- suma 3 == 6

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- 2ª definición de línea

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

linea2 :: Integer -> [Integer]

linea2 n = [s+1..s+n]

where s = suma1 (n-1)

-- 3ª definición de línea

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

linea3 :: Integer -> [Integer]

linea3 n = [s+1..s+n]

where s = suma2 (n-1)

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

-- Comprobación de equivalencia de linea

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

-- La propiedad es

prop_linea :: Positive Integer -> Bool

prop_linea (Positive n) =

all (== linea1 n)

[linea2 n,

linea3 n]

-- La comprobación es

-- λ> quickCheck prop_linea

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de linea

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

-- La comparación es

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

-- 50000005000000

-- (5.10 secs, 3,945,159,856 bytes)

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

-- 50000005000000

-- (3.11 secs, 2,332,859,512 bytes)

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

-- 50000005000000

-- (0.16 secs, 720,559,384 bytes)

-- 1ª definición de triangulo

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

triangulo1 :: Integer -> [[Integer]]

triangulo1 n = [linea1 m | m <- [1..n]]

-- 2ª definición de triangulo

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

triangulo2 :: Integer -> [[Integer]]

triangulo2 n = [linea2 m | m <- [1..n]]

-- 3ª definición de triangulo

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

triangulo3 :: Integer -> [[Integer]]

triangulo3 n = [linea3 m | m <- [1..n]]

-- Comprobación de equivalencia de triangulo

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

-- La propiedad es

prop_triangulo :: Positive Integer -> Bool

prop_triangulo (Positive n) =

all (== triangulo1 n)

[triangulo2 n,

triangulo3 n]

-- La comprobación es

-- λ> quickCheck prop_triangulo

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de triangulo

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

-- La comparación es

-- λ> last (last (triangulo1 (3*10^6)))

-- 4500001500000

-- (2.25 secs, 1,735,919,184 bytes)

-- λ> last (last (triangulo2 (3*10^6)))

-- 4500001500000

-- (1.62 secs, 1,252,238,872 bytes)

-- λ> last (last (triangulo3 (3*10^6)))

-- 4500001500000

-- (0.79 secs, 768,558,776 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer
from hypothesis import given, strategies as st

# 1ª definición de línea
# ======================

# suma(n) es la suma de los n primeros números. Por ejemplo,
#    suma(3)  ==  6
def suma1(n: int) -> int:
    return sum(range(1, n + 1))

def linea1(n: int) -> list[int]:
    return list(range(suma1(n - 1) + 1, suma1(n) + 1))

# 2ª definición de línea
# ======================

def linea2(n: int) -> list[int]:
    s = suma1(n-1)
    return list(range(s + 1, s + n + 1))

# 3ª definición de línea
# ======================

def suma2(n: int) -> int:
    return (1 + n) * n // 2

def linea3(n: int) -> list[int]:
    s = suma2(n-1)
    return list(range(s + 1, s + n + 1))

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

@given(st.integers(min_value=1, max_value=1000))
def test_suma(n):
    r = linea1(n)
    assert linea2(n) == r
    assert linea3(n) == r

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

# 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('linea1(10**7)')
#    0.53 segundos
#    >>> tiempo('linea2(10**7)')
#    0.40 segundos
#    >>> tiempo('linea3(10**7)')
#    0.29 segundos

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

def triangulo1(n: int) -> list[list[int]]:
    return [linea1(m) for m in range(1, n + 1)]

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

def triangulo2(n: int) -> list[list[int]]:
    return [linea2(m) for m in range(1, n + 1)]

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

def triangulo3(n: int) -> list[list[int]]:
    return [linea3(m) for m in range(1, n + 1)]

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

@given(st.integers(min_value=1, max_value=1000))
def test_triangulo(n):
    r = triangulo1(n)
    assert triangulo2(n) == r
    assert triangulo3(n) == r

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

# Comparación de eficiencia de triangulo
# ======================================
#
# La comparación es
#    >>> tiempo('triangulo1(10**4)')
#    2.58 segundos
#    >>> tiempo('triangulo2(10**4)')
#    1.91 segundos
#    >>> tiempo('triangulo3(10**4)')
#    1.26 segundos

100

101

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

# 1ª definición de línea

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

# suma(n) es la suma de los n primeros números. Por ejemplo,

# suma(3) == 6

def suma1(n: int) -> int:

return sum(range(1, n + 1))

def linea1(n: int) -> list[int]:

return list(range(suma1(n - 1) + 1, suma1(n) + 1))

# 2ª definición de línea

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

def linea2(n: int) -> list[int]:

s = suma1(n-1)

return list(range(s + 1, s + n + 1))

# 3ª definición de línea

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

def suma2(n: int) -> int:

return (1 + n) * n // 2

def linea3(n: int) -> list[int]:

s = suma2(n-1)

return list(range(s + 1, s + n + 1))

# Comprobación de equivalencia de linea

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

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

def test_suma(n):

r = linea1(n)

assert linea2(n) == r

assert linea3(n) == r

# La comprobación es

# src> poetry run pytest -q triangulo_aritmetico.py

# 1 passed in 0.15s

# 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('linea1(10**7)')

# 0.53 segundos

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

# 0.40 segundos

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

# 0.29 segundos

# 1ª definición de triangulo

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

def triangulo1(n: int) -> list[list[int]]:

return [linea1(m) for m in range(1, n + 1)]

# 2ª definición de triangulo

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

def triangulo2(n: int) -> list[list[int]]:

return [linea2(m) for m in range(1, n + 1)]

# 3ª definición de triangulo

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

def triangulo3(n: int) -> list[list[int]]:

return [linea3(m) for m in range(1, n + 1)]

# Comprobación de equivalencia de triangulo

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

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

def test_triangulo(n):

r = triangulo1(n)

assert triangulo2(n) == r

assert triangulo3(n) == r

# La comprobación es

# src> poetry run pytest -q triangulo_aritmetico.py

# 1 passed in 3.44s

# Comparación de eficiencia de triangulo

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

# La comparación es

# >>> tiempo('triangulo1(10**4)')

# 2.58 segundos

# >>> tiempo('triangulo2(10**4)')

# 1.91 segundos

# >>> tiempo('triangulo3(10**4)')

# 1.26 segundos

El código se encuentra en GitHub.

Suma de cuadrados menos cuadrado de la suma

PorJosé A. Alonso 29-septiembre-202214-diciembre-2022

Definir la función

   euler6 :: Integer -> Integer

1	euler6 :: Integer -> Integer

tal que euler6 n es la diferencia entre el cuadrado de la suma de los n primeros números y la suma de los cuadrados de los nprimeros números. Por ejemplo,

   euler6 10       ==  2640
   euler6 (10^10)  ==  2500000000166666666641666666665000000000

1 2	euler6 10 == 2640 euler6 (10^10) == 2500000000166666666641666666665000000000

Nota: Este ejercicio está basado en el problema 6 del proyecto Euler.

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

euler6a :: Integer -> Integer
euler6a n = (suma1 n)^2 - sumaDeCuadrados1 n

-- (suma n) es la suma de los n primeros números. Por ejemplo,
--    suma 3  ==  6
suma1 :: Integer -> Integer
suma1 n = sum [1..n]

-- (sumaDeCuadrados n) es la suma de los cuadrados de los
-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
--    sumaDeCuadrados 3    ==  14
--    sumaDeCuadrados 100  ==  338350

sumaDeCuadrados1 :: Integer -> Integer
sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

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

euler6b :: Integer -> Integer
euler6b n = (suma2 n)^ 2 - sumaDeCuadrados2 n

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

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

euler6c :: Integer -> Integer
euler6c n = (suma3 n)^ 2 - sumaDeCuadrados3 n

suma3 :: Integer -> Integer
suma3 1 = 1
suma3 n = n + suma3 (n-1)

sumaDeCuadrados3 :: Integer -> Integer
sumaDeCuadrados3 1 = 1
sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

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

euler6d :: Integer -> Integer
euler6d n = (suma4 n)^ 2 - sumaDeCuadrados4 n

suma4 :: Integer -> Integer
suma4 n = foldl (+) 0 [0..n]

sumaDeCuadrados4 :: Integer -> Integer
sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

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

euler6e :: Integer -> Integer
euler6e n = (suma5 n)^ 2 - sumaDeCuadrados5 n

suma5 :: Integer -> Integer
suma5 n = foldl' (+) 0 [0..n]

sumaDeCuadrados5 :: Integer -> Integer
sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

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

-- La propiedad es
prop_euler6 :: Positive Integer -> Bool
prop_euler6 (Positive n) =
  all (== euler6a n)
      [euler6b n,
       euler6c n,
       euler6d n,
       euler6e n]

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

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

-- La comparación es
--    λ> euler6a (3*10^6)
--    20250004499997749999500000
--    (3.32 secs, 2,577,174,640 bytes)
--    λ> euler6b (3*10^6)
--    20250004499997749999500000
--    (0.01 secs, 569,288 bytes)
--    λ> euler6c (3*10^6)
--    20250004499997749999500000
--    (5.60 secs, 2,849,479,288 bytes)
--    λ> euler6d (3*10^6)
--    20250004499997749999500000
--    (2.52 secs, 2,457,175,248 bytes)
--    λ> euler6e (3*10^6)
--    20250004499997749999500000
--    (1.08 secs, 2,016,569,472 bytes)
--
--    λ> euler6a (10^7)
--    2500000166666641666665000000
--    (11.14 secs, 8,917,796,648 bytes)
--    λ> euler6b (10^7)
--    2500000166666641666665000000
--    (0.01 secs, 570,752 bytes)
--    λ> euler6c (10^7)
--    *** Exception: stack overflow
--    λ> euler6d (10^7)
--    2500000166666641666665000000
--    (9.47 secs, 8,517,796,760 bytes)
--    λ> euler6e (10^7)
--    2500000166666641666665000000
--    (3.78 secs, 7,049,100,104 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

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

euler6a :: Integer -> Integer

euler6a n = (suma1 n)^2 - sumaDeCuadrados1 n

-- (suma n) es la suma de los n primeros números. Por ejemplo,

-- suma 3 == 6

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- (sumaDeCuadrados n) es la suma de los cuadrados de los

-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,

-- sumaDeCuadrados 3 == 14

-- sumaDeCuadrados 100 == 338350

sumaDeCuadrados1 :: Integer -> Integer

sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución

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

euler6b :: Integer -> Integer

euler6b n = (suma2 n)^ 2 - sumaDeCuadrados2 n

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

sumaDeCuadrados2 :: Integer -> Integer

sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución

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

euler6c :: Integer -> Integer

euler6c n = (suma3 n)^ 2 - sumaDeCuadrados3 n

suma3 :: Integer -> Integer

suma3 1 = 1

suma3 n = n + suma3 (n-1)

sumaDeCuadrados3 :: Integer -> Integer

sumaDeCuadrados3 1 = 1

sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución

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

euler6d :: Integer -> Integer

euler6d n = (suma4 n)^ 2 - sumaDeCuadrados4 n

suma4 :: Integer -> Integer

suma4 n = foldl (+) 0 [0..n]

sumaDeCuadrados4 :: Integer -> Integer

sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución

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

euler6e :: Integer -> Integer

euler6e n = (suma5 n)^ 2 - sumaDeCuadrados5 n

suma5 :: Integer -> Integer

suma5 n = foldl' (+) 0 [0..n]

sumaDeCuadrados5 :: Integer -> Integer

sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia

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

-- La propiedad es

prop_euler6 :: Positive Integer -> Bool

prop_euler6 (Positive n) =

all (== euler6a n)

[euler6b n,

euler6c n,

euler6d n,

euler6e n]

-- La comprobación es

-- λ> quickCheck prop_euler6

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> euler6a (3*10^6)

-- 20250004499997749999500000

-- (3.32 secs, 2,577,174,640 bytes)

-- λ> euler6b (3*10^6)

-- 20250004499997749999500000

-- (0.01 secs, 569,288 bytes)

-- λ> euler6c (3*10^6)

-- 20250004499997749999500000

-- (5.60 secs, 2,849,479,288 bytes)

-- λ> euler6d (3*10^6)

-- 20250004499997749999500000

-- (2.52 secs, 2,457,175,248 bytes)

-- λ> euler6e (3*10^6)

-- 20250004499997749999500000

-- (1.08 secs, 2,016,569,472 bytes)

-- λ> euler6a (10^7)

-- 2500000166666641666665000000

-- (11.14 secs, 8,917,796,648 bytes)

-- λ> euler6b (10^7)

-- 2500000166666641666665000000

-- (0.01 secs, 570,752 bytes)

-- λ> euler6c (10^7)

-- *** Exception: stack overflow

-- λ> euler6d (10^7)

-- 2500000166666641666665000000

-- (9.47 secs, 8,517,796,760 bytes)

-- λ> euler6e (10^7)

-- 2500000166666641666665000000

-- (3.78 secs, 7,049,100,104 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
from operator import add
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**6)

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

def euler6a(n: int) -> int:
    return suma1(n)**2 - sumaDeCuadrados1(n)

# suma(n) es la suma de los n primeros números. Por ejemplo,
#    suma(3)  ==  6
def suma1(n: int) -> int:
    return sum(range(1, n + 1))

# sumaDeCuadrados(n) es la suma de los cuadrados de los
# primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
#    sumaDeCuadrados(3)    ==  14
#    sumaDeCuadrados(100)  ==  338350
def sumaDeCuadrados1(n: int) -> int:
    return sum(x**2 for x in range(1, n + 1))

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

def euler6b(n: int) -> int:
    return suma2(n)**2 - sumaDeCuadrados2(n)

def suma2(n: int) -> int:
    return (1 + n) * n // 2

def sumaDeCuadrados2(n: int) -> int:
    return n * (n + 1) * (2 * n + 1) // 6

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

def euler6c(n: int) -> int:
    return suma3(n)**2 - sumaDeCuadrados3(n)

def suma3(n: int) -> int:
    if n == 1:
        return 1
    return n + suma3(n - 1)

def sumaDeCuadrados3(n: int) -> int:
    if n == 1:
        return 1
    return n**2 + sumaDeCuadrados3(n - 1)

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

def euler6d(n: int) -> int:
    return suma4(n)**2 - sumaDeCuadrados4(n)

def suma4(n: int) -> int:
    return reduce(add, range(1, n + 1))

def sumaDeCuadrados4(n: int) -> int:
    return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución
# ===========

def euler6e(n: int) -> int:
    return suma5(n)**2 - sumaDeCuadrados5(n)

def suma5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x
        x = x + 1
    return r

def sumaDeCuadrados5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x**2
        x = x + 1
    return r

# 6ª solución
# ===========

def euler6f(n: int) -> int:
    return suma6(n)**2 - sumaDeCuadrados6(n)

def suma6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x
    return r

def sumaDeCuadrados6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x**2
    return r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_euler6(n):
    r = euler6a(n)
    assert euler6b(n) == r
    assert euler6c(n) == r
    assert euler6d(n) == r
    assert euler6e(n) == r
    assert euler6f(n) == r

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

# 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('euler6a(20000)')
#    0.02 segundos
#    >>> tiempo('euler6b(20000)')
#    0.00 segundos
#    >>> tiempo('euler6c(20000)')
#    0.02 segundos
#    >>> tiempo('euler6d(20000)')
#    0.01 segundos
#    >>> tiempo('euler6e(20000)')
#    0.01 segundos
#    >>> tiempo('euler6f(20000)')
#    0.01 segundos
#
#    >>> tiempo('euler6a(10**7)')
#    2.26 segundos
#    >>> tiempo('euler6b(10**7)')
#    0.00 segundos
#    >>> tiempo('euler6d(10**7)')
#    2.58 segundos
#    >>> tiempo('euler6e(10**7)')
#    2.89 segundos
#    >>> tiempo('euler6f(10**7)')
#    2.45 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

from functools import reduce

from operator import add

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

def euler6a(n: int) -> int:

return suma1(n)**2 - sumaDeCuadrados1(n)

# suma(n) es la suma de los n primeros números. Por ejemplo,

# suma(3) == 6

def suma1(n: int) -> int:

return sum(range(1, n + 1))

# sumaDeCuadrados(n) es la suma de los cuadrados de los

# primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,

# sumaDeCuadrados(3) == 14

# sumaDeCuadrados(100) == 338350

def sumaDeCuadrados1(n: int) -> int:

return sum(x**2 for x in range(1, n + 1))

# 2ª solución

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

def euler6b(n: int) -> int:

return suma2(n)**2 - sumaDeCuadrados2(n)

def suma2(n: int) -> int:

return (1 + n) * n // 2

def sumaDeCuadrados2(n: int) -> int:

return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución

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

def euler6c(n: int) -> int:

return suma3(n)**2 - sumaDeCuadrados3(n)

def suma3(n: int) -> int:

if n == 1:

return 1

return n + suma3(n - 1)

def sumaDeCuadrados3(n: int) -> int:

if n == 1:

return 1

return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución

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

def euler6d(n: int) -> int:

return suma4(n)**2 - sumaDeCuadrados4(n)

def suma4(n: int) -> int:

return reduce(add, range(1, n + 1))

def sumaDeCuadrados4(n: int) -> int:

return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución

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

def euler6e(n: int) -> int:

return suma5(n)**2 - sumaDeCuadrados5(n)

def suma5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x

x = x + 1

return r

def sumaDeCuadrados5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x**2

x = x + 1

return r

# 6ª solución

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

def euler6f(n: int) -> int:

return suma6(n)**2 - sumaDeCuadrados6(n)

def suma6(n: int) -> int:

r = 0

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

r = r + x

return r

def sumaDeCuadrados6(n: int) -> int:

r = 0

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

r = r + x**2

return r

# Comprobación de equivalencia

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

# La propiedad es

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

def test_euler6(n):

r = euler6a(n)

assert euler6b(n) == r

assert euler6c(n) == r

assert euler6d(n) == r

assert euler6e(n) == r

assert euler6f(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_cuadrados_menos_cuadrado_de_la_suma.py

# 1 passed in 0.21s

# 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('euler6a(20000)')

# 0.02 segundos

# >>> tiempo('euler6b(20000)')

# 0.00 segundos

# >>> tiempo('euler6c(20000)')

# 0.02 segundos

# >>> tiempo('euler6d(20000)')

# 0.01 segundos

# >>> tiempo('euler6e(20000)')

# 0.01 segundos

# >>> tiempo('euler6f(20000)')

# 0.01 segundos

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

# 2.26 segundos

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

# 0.00 segundos

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

# 2.58 segundos

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

# 2.89 segundos

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

# 2.45 segundos

El código se encuentra en GitHub.

Suma de los cuadrados de los primeros números naturales

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

Definir la función

   sumaDeCuadrados :: Integer -> Integer

1	sumaDeCuadrados :: Integer -> Integer

tal que sumaDeCuadrados n es la suma de los cuadrados de los primeros n números; es decir, 1² + 2² + … + n². Por ejemplo,

   sumaDeCuadrados 3    ==  14
   sumaDeCuadrados 100  ==  338350
   length (show (sumaDeCuadrados (10^100)))  ==  300

sumaDeCuadrados 3 == 14

sumaDeCuadrados 100 == 338350

length (show (sumaDeCuadrados (10^100))) == 300

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

sumaDeCuadrados1 :: Integer -> Integer
sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

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

sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

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

sumaDeCuadrados3 :: Integer -> Integer
sumaDeCuadrados3 1 = 1
sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

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

sumaDeCuadrados4 :: Integer -> Integer
sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

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

sumaDeCuadrados5 :: Integer -> Integer
sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

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

-- La propiedad es
prop_sumaDeCuadrados :: Positive Integer -> Bool
prop_sumaDeCuadrados (Positive n) =
  all (== sumaDeCuadrados1 n)
      [sumaDeCuadrados2 n,
       sumaDeCuadrados3 n,
       sumaDeCuadrados4 n,
       sumaDeCuadrados5 n]

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

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

-- La comparación es
--    λ> sumaDeCuadrados1 (2*10^6)
--    2666668666667000000
--    (1.90 secs, 1,395,835,576 bytes)
--    λ> sumaDeCuadrados2 (2*10^6)
--    2666668666667000000
--    (0.01 secs, 563,168 bytes)
--    λ> sumaDeCuadrados3 (2*10^6)
--    2666668666667000000
--    (2.37 secs, 1,414,199,400 bytes)
--    λ> sumaDeCuadrados4 (2*10^6)
--    2666668666667000000
--    (1.33 secs, 1,315,836,128 bytes)
--    λ> sumaDeCuadrados5 (2*10^6)
--    2666668666667000000
--    (0.71 secs, 1,168,563,384 bytes)

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

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

sumaDeCuadrados1 :: Integer -> Integer

sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución

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

sumaDeCuadrados2 :: Integer -> Integer

sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución

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

sumaDeCuadrados3 :: Integer -> Integer

sumaDeCuadrados3 1 = 1

sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución

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

sumaDeCuadrados4 :: Integer -> Integer

sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución

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

sumaDeCuadrados5 :: Integer -> Integer

sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia

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

-- La propiedad es

prop_sumaDeCuadrados :: Positive Integer -> Bool

prop_sumaDeCuadrados (Positive n) =

all (== sumaDeCuadrados1 n)

[sumaDeCuadrados2 n,

sumaDeCuadrados3 n,

sumaDeCuadrados4 n,

sumaDeCuadrados5 n]

-- La comprobación es

-- λ> quickCheck prop_sumaDeCuadrados

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> sumaDeCuadrados1 (2*10^6)

-- 2666668666667000000

-- (1.90 secs, 1,395,835,576 bytes)

-- λ> sumaDeCuadrados2 (2*10^6)

-- 2666668666667000000

-- (0.01 secs, 563,168 bytes)

-- λ> sumaDeCuadrados3 (2*10^6)

-- 2666668666667000000

-- (2.37 secs, 1,414,199,400 bytes)

-- λ> sumaDeCuadrados4 (2*10^6)

-- 2666668666667000000

-- (1.33 secs, 1,315,836,128 bytes)

-- λ> sumaDeCuadrados5 (2*10^6)

-- 2666668666667000000

-- (0.71 secs, 1,168,563,384 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import add
from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**6)

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

def sumaDeCuadrados1(n: int) -> int:
    return sum(x**2 for x in range(1, n + 1))

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

def sumaDeCuadrados2(n: int) -> int:
    return n * (n + 1) * (2 * n + 1) // 6

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

def sumaDeCuadrados3(n: int) -> int:
    if n == 1:
        return 1
    return n**2 + sumaDeCuadrados3(n - 1)

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

def sumaDeCuadrados4(n: int) -> int:
    return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución
# ===========

def sumaDeCuadrados5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x**2
        x = x + 1
    return r

# 6ª solución
# ===========

def sumaDeCuadrados6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x**2
    return r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_sumaDeCuadrados(n):
    r = sumaDeCuadrados1(n)
    assert sumaDeCuadrados2(n) == r
    assert sumaDeCuadrados3(n) == r
    assert sumaDeCuadrados4(n) == r
    assert sumaDeCuadrados5(n) == r
    assert sumaDeCuadrados6(n) == r

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

# 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('sumaDeCuadrados1(20000)')
#    0.01 segundos
#    >>> tiempo('sumaDeCuadrados2(20000)')
#    0.00 segundos
#    >>> tiempo('sumaDeCuadrados3(20000)')
#    0.02 segundos
#    >>> tiempo('sumaDeCuadrados4(20000)')
#    0.02 segundos
#    >>> tiempo('sumaDeCuadrados5(20000)')
#    0.02 segundos
#    >>> tiempo('sumaDeCuadrados6(20000)')
#    0.02 segundos
#
#    >>> tiempo('sumaDeCuadrados1(10**7)')
#    2.19 segundos
#    >>> tiempo('sumaDeCuadrados2(10**7)')
#    0.00 segundos
#    >>> tiempo('sumaDeCuadrados4(10**7)')
#    2.48 segundos
#    >>> tiempo('sumaDeCuadrados5(10**7)')
#    2.53 segundos
#    >>> tiempo('sumaDeCuadrados6(10**7)')
#    2.22 segundos

100

101

from operator import add

from functools import reduce

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

def sumaDeCuadrados1(n: int) -> int:

return sum(x**2 for x in range(1, n + 1))

# 2ª solución

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

def sumaDeCuadrados2(n: int) -> int:

return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución

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

def sumaDeCuadrados3(n: int) -> int:

if n == 1:

return 1

return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución

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

def sumaDeCuadrados4(n: int) -> int:

return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución

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

def sumaDeCuadrados5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x**2

x = x + 1

return r

# 6ª solución

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

def sumaDeCuadrados6(n: int) -> int:

r = 0

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

r = r + x**2

return r

# Comprobación de equivalencia

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

# La propiedad es

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

def test_sumaDeCuadrados(n):

r = sumaDeCuadrados1(n)

assert sumaDeCuadrados2(n) == r

assert sumaDeCuadrados3(n) == r

assert sumaDeCuadrados4(n) == r

assert sumaDeCuadrados5(n) == r

assert sumaDeCuadrados6(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_los_cuadrados_de_los_primeros_numeros_naturales.py

# 1 passed in 0.19s

# 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('sumaDeCuadrados1(20000)')

# 0.01 segundos

# >>> tiempo('sumaDeCuadrados2(20000)')

# 0.00 segundos

# >>> tiempo('sumaDeCuadrados3(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados4(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados5(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados6(20000)')

# 0.02 segundos

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

# 2.19 segundos

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

# 0.00 segundos

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

# 2.48 segundos

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

# 2.53 segundos

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

# 2.22 segundos

El código se encuentra en GitHub.

Suma de los primeros números naturales

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

Definir la función

   suma :: Integer -> Integer

1	suma :: Integer -> Integer

tal suma n es la suma de los n primeros números. Por ejemplo,

   suma 3  ==  6
   length (show (suma (10^100)))  ==  200

1 2	suma 3 == 6 length (show (suma (10^100))) == 200

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

suma1 :: Integer -> Integer
suma1 n = sum [1..n]

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

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

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

suma3 :: Integer -> Integer
suma3 1 = 1
suma3 n = n + suma3 (n-1)

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

suma4 :: Integer -> Integer
suma4 n = foldl (+) 0 [0..n]

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

suma5 :: Integer -> Integer
suma5 n = foldl' (+) 0 [0..n]

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

-- La propiedad es
prop_suma :: Positive Integer -> Bool
prop_suma (Positive n) =
  all (== suma1 n)
      [suma2 n,
       suma3 n,
       suma4 n,
       suma5 n]

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

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

-- La comparación es
--    λ> suma1 (5*10^6)
--    12500002500000
--    (1.23 secs, 806,692,792 bytes)
--    λ> suma2 (5*10^6)
--    12500002500000
--    (0.02 secs, 559,064 bytes)
--    λ> suma3 (5*10^6)
--    12500002500000
--    (3.06 secs, 1,214,684,352 bytes)
--    λ> suma4 (5*10^6)
--    12500002500000
--    (1.25 secs, 806,692,848 bytes)
--    λ> suma5 (5*10^6)
--    12500002500000
--    (0.26 secs, 440,559,048 bytes)

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

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

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- 2ª solución

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

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

-- 3ª solución

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

suma3 :: Integer -> Integer

suma3 1 = 1

suma3 n = n + suma3 (n-1)

-- 4ª solución

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

suma4 :: Integer -> Integer

suma4 n = foldl (+) 0 [0..n]

-- 5ª solución

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

suma5 :: Integer -> Integer

suma5 n = foldl' (+) 0 [0..n]

-- Comprobación de equivalencia

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

-- La propiedad es

prop_suma :: Positive Integer -> Bool

prop_suma (Positive n) =

all (== suma1 n)

[suma2 n,

suma3 n,

suma4 n,

suma5 n]

-- La comprobación es

-- λ> quickCheck prop_suma

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> suma1 (5*10^6)

-- 12500002500000

-- (1.23 secs, 806,692,792 bytes)

-- λ> suma2 (5*10^6)

-- 12500002500000

-- (0.02 secs, 559,064 bytes)

-- λ> suma3 (5*10^6)

-- 12500002500000

-- (3.06 secs, 1,214,684,352 bytes)

-- λ> suma4 (5*10^6)

-- 12500002500000

-- (1.25 secs, 806,692,848 bytes)

-- λ> suma5 (5*10^6)

-- 12500002500000

-- (0.26 secs, 440,559,048 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import add
from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**8)

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

def suma1(n: int) -> int:
    return sum(range(1, n + 1))

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

def suma2(n: int) -> int:
    return (1 + n) * n // 2

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

def suma3(n: int) -> int:
    if n == 1:
        return 1
    return n + suma3(n - 1)

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

def suma4(n: int) -> int:
    return reduce(add, range(1, n + 1))

# 5ª solución
# ===========

def suma5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x
        x = x + 1
    return r

# 6ª solución
# ===========

def suma6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x
    return r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_suma(n):
    r = suma1(n)
    assert suma2(n) == r
    assert suma3(n) == r
    assert suma4(n) == r
    assert suma5(n) == r
    assert suma6(n) == r

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

# 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('suma3(20000)')
#    0.04 segundos
#    >>> tiempo('suma1(20000)')
#    0.00 segundos
#    >>> tiempo('suma2(20000)')
#    0.00 segundos
#    >>> tiempo('suma3(20000)')
#    0.02 segundos
#    >>> tiempo('suma4(20000)')
#    0.00 segundos
#    >>> tiempo('suma5(20000)')
#    0.01 segundos
#    >>> tiempo('suma6(20000)')
#    0.00 segundos
#
#    >>> tiempo('suma1(10**8)')
#    1.55 segundos
#    >>> tiempo('suma2(10**8)')
#    0.00 segundos
#    >>> tiempo('suma4(10**8)')
#    3.69 segundos
#    >>> tiempo('suma5(10**8)')
#    7.04 segundos
#    >>> tiempo('suma6(10**8)')
#    4.23 segundos

100

101

102

103

from operator import add

from functools import reduce

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**8)

# 1ª solución

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

def suma1(n: int) -> int:

return sum(range(1, n + 1))

# 2ª solución

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

def suma2(n: int) -> int:

return (1 + n) * n // 2

# 3ª solución

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

def suma3(n: int) -> int:

if n == 1:

return 1

return n + suma3(n - 1)

# 4ª solución

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

def suma4(n: int) -> int:

return reduce(add, range(1, n + 1))

# 5ª solución

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

def suma5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x

x = x + 1

return r

# 6ª solución

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

def suma6(n: int) -> int:

r = 0

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

r = r + x

return r

# Comprobación de equivalencia

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

# La propiedad es

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

def test_suma(n):

r = suma1(n)

assert suma2(n) == r

assert suma3(n) == r

assert suma4(n) == r

assert suma5(n) == r

assert suma6(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_los_primeros_numeros_naturales.py

# 1 passed in 0.16s

# 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('suma3(20000)')

# 0.04 segundos

# >>> tiempo('suma1(20000)')

# 0.00 segundos

# >>> tiempo('suma2(20000)')

# 0.00 segundos

# >>> tiempo('suma3(20000)')

# 0.02 segundos

# >>> tiempo('suma4(20000)')

# 0.00 segundos

# >>> tiempo('suma5(20000)')

# 0.01 segundos

# >>> tiempo('suma6(20000)')

# 0.00 segundos

# >>> tiempo('suma1(10**8)')

# 1.55 segundos

# >>> tiempo('suma2(10**8)')

# 0.00 segundos

# >>> tiempo('suma4(10**8)')

# 3.69 segundos

# >>> tiempo('suma5(10**8)')

# 7.04 segundos

# >>> tiempo('suma6(10**8)')

# 4.23 segundos

El código se encuentra en GitHub

Números libres de cuadrados

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

Un número es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

   libreDeCuadrados :: Integer -> Bool

1	libreDeCuadrados :: Integer -> Bool

tal que libreDeCuadrados x se verifica si x es libre de cuadrados. Por ejemplo,

   libreDeCuadrados 70  ==  True
   libreDeCuadrados 40  ==  False
   libreDeCuadrados (product (take 30000 primes))  ==  True

libreDeCuadrados 70 == True

libreDeCuadrados 40 == False

libreDeCuadrados (product (take 30000 primes)) == True

Soluciones

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

Soluciones en Haskell

import Data.List (nub)
import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck

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

libreDeCuadrados1 :: Integer -> Bool
libreDeCuadrados1 n =
  null [x | x <- [2..n], rem n (x^2) == 0]

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

libreDeCuadrados2 :: Integer -> Bool
libreDeCuadrados2 x =
  x == product (divisoresPrimos2 x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por
-- ejemplo,
--    divisoresPrimos 40 == [2,5]
--    divisoresPrimos 70 == [2,5,7]
divisoresPrimos2 :: Integer -> [Integer]
divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 25  ==  [1,5,25]
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores2 :: Integer -> [Integer]
divisores2 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True
primo2 :: Integer -> Bool
primo2 n = divisores2 n == [1, n]

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

libreDeCuadrados3 :: Integer -> Bool
libreDeCuadrados3 n
  | even n = n `mod` 4 /= 0 && libreDeCuadrados3 (n `div` 2)
  | otherwise = aux n [3,5..n]
  where aux 1 _  = True
        aux _ [] = True
        aux m (x:xs)
          | m `mod` x == 0 = m `mod` (x^2) /= 0 && aux (m `div` x) xs
          | otherwise      = aux m xs

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

libreDeCuadrados4 :: Integer -> Bool
libreDeCuadrados4 x =
  x == product (divisoresPrimos4 x)

divisoresPrimos4 :: Integer -> [Integer]
divisoresPrimos4 = nub . primeFactors

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

libreDeCuadrados5 :: Integer -> Bool
libreDeCuadrados5 =
  sinRepetidos . primeFactors

-- (sinRepetidos xs) se verifica si xs no tiene elementos repetidos. Por
-- ejemplo,
--    sinRepetidos [3,2,5]  ==  True
--    sinRepetidos [3,2,5,2]  ==  False
sinRepetidos :: [Integer] -> Bool
sinRepetidos xs =
  nub xs == xs

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

-- La propiedad es
prop_libreDeCuadrados :: Integer -> Property
prop_libreDeCuadrados x =
  x > 1 ==>
  all (== libreDeCuadrados1 x)
      [libreDeCuadrados2 x,
       libreDeCuadrados3 x,
       libreDeCuadrados4 x,
       libreDeCuadrados5 x]

-- La comprobación es
--    λ> quickCheck prop_libreDeCuadrados
--    +++ OK, passed 100 tests; 165 discarded.

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

-- La comparación es
--    λ> libreDeCuadrados1 9699690
--    True
--    (8.54 secs, 6,441,144,248 bytes)
--    λ> libreDeCuadrados2 9699690
--    True
--    (4.78 secs, 1,940,781,632 bytes)
--    λ> libreDeCuadrados3 9699690
--    True
--    (0.01 secs, 561,400 bytes)
--    λ> libreDeCuadrados4 9699690
--    True
--    (0.01 secs, 568,160 bytes)
--    λ> libreDeCuadrados5 9699690
--    True
--    (0.01 secs, 567,536 bytes)
--
--    λ> libreDeCuadrados3 (product (take 30000 primes))
--    True
--    (2.30 secs, 2,369,316,208 bytes)
--    λ> libreDeCuadrados4 (product (take 30000 primes))
--    True
--    (6.68 secs, 4,565,617,408 bytes)
--    λ> libreDeCuadrados5 (product (take 30000 primes))
--    True
--    (5.54 secs, 3,411,701,752 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

import Data.List (nub)

import Data.Numbers.Primes (primeFactors, primes)

import Test.QuickCheck

-- 1ª solución

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

libreDeCuadrados1 :: Integer -> Bool

libreDeCuadrados1 n =

null [x | x <- [2..n], rem n (x^2) == 0]

-- 2ª solución

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

libreDeCuadrados2 :: Integer -> Bool

libreDeCuadrados2 x =

x == product (divisoresPrimos2 x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por

-- ejemplo,

-- divisoresPrimos 40 == [2,5]

-- divisoresPrimos 70 == [2,5,7]

divisoresPrimos2 :: Integer -> [Integer]

divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,

-- divisores 25 == [1,5,25]

-- divisores 30 == [1,2,3,5,6,10,15,30]

divisores2 :: Integer -> [Integer]

divisores2 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,

-- primo 30 == False

-- primo 31 == True

primo2 :: Integer -> Bool

primo2 n = divisores2 n == [1, n]

-- 3ª solución

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

libreDeCuadrados3 :: Integer -> Bool

libreDeCuadrados3 n

| even n = n `mod` 4 /= 0 && libreDeCuadrados3 (n `div` 2)

| otherwise = aux n [3,5..n]

where aux 1 _ = True

aux _ [] = True

aux m (x:xs)

| m `mod` x == 0 = m `mod` (x^2) /= 0 && aux (m `div` x) xs

| otherwise = aux m xs

-- 4ª solución

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

libreDeCuadrados4 :: Integer -> Bool

libreDeCuadrados4 x =

x == product (divisoresPrimos4 x)

divisoresPrimos4 :: Integer -> [Integer]

divisoresPrimos4 = nub . primeFactors

-- 5ª solución

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

libreDeCuadrados5 :: Integer -> Bool

libreDeCuadrados5 =

sinRepetidos . primeFactors

-- (sinRepetidos xs) se verifica si xs no tiene elementos repetidos. Por

-- ejemplo,

-- sinRepetidos [3,2,5] == True

-- sinRepetidos [3,2,5,2] == False

sinRepetidos :: [Integer] -> Bool

sinRepetidos xs =

nub xs == xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_libreDeCuadrados :: Integer -> Property

prop_libreDeCuadrados x =

x > 1 ==>

all (== libreDeCuadrados1 x)

[libreDeCuadrados2 x,

libreDeCuadrados3 x,

libreDeCuadrados4 x,

libreDeCuadrados5 x]

-- La comprobación es

-- λ> quickCheck prop_libreDeCuadrados

-- +++ OK, passed 100 tests; 165 discarded.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> libreDeCuadrados1 9699690

-- True

-- (8.54 secs, 6,441,144,248 bytes)

-- λ> libreDeCuadrados2 9699690

-- True

-- (4.78 secs, 1,940,781,632 bytes)

-- λ> libreDeCuadrados3 9699690

-- True

-- (0.01 secs, 561,400 bytes)

-- λ> libreDeCuadrados4 9699690

-- True

-- (0.01 secs, 568,160 bytes)

-- λ> libreDeCuadrados5 9699690

-- True

-- (0.01 secs, 567,536 bytes)

-- λ> libreDeCuadrados3 (product (take 30000 primes))

-- True

-- (2.30 secs, 2,369,316,208 bytes)

-- λ> libreDeCuadrados4 (product (take 30000 primes))

-- True

-- (6.68 secs, 4,565,617,408 bytes)

-- λ> libreDeCuadrados5 (product (take 30000 primes))

-- True

-- (5.54 secs, 3,411,701,752 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import primefactors, primerange
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

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

def libreDeCuadrados1(n: int) -> bool:
    return [x for x in range(2, n + 2) if n % (x**2) == 0] == []

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

# divisores(n) es la lista de los divisores del número n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,
#    primo(30)  == False
#    primo(31)  == True
def primo1(n: int) -> bool:
    return divisores1(n) == [1, n]

# divisoresPrimos(x) es la lista de los divisores primos de x. Por
# ejemplo,
#    divisoresPrimos(40) == [2, 5]
#    divisoresPrimos(70) == [2, 5, 7]
def divisoresPrimos1(x: int) -> list[int]:
    return [n for n in divisores1(x) if primo1(n)]

# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([3, 2, 5])  ==  30
def producto(xs):
    if xs:
        return xs[0] * producto(xs[1:])
    return 1

def libreDeCuadrados2(x):
    return x == producto(divisoresPrimos1(x))

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

def libreDeCuadrados3(n: int) -> bool:
    if n % 2 == 0:
        return n % 4 != 0 and libreDeCuadrados3(n // 2)

    def aux(m, xs):
        if m == 1:
            return True
        if xs == []:
            return True
        if m % xs[0] == 0:
            return m % (xs[0]**2) != 0 and aux(m // xs[0], xs[1:])
        return aux(m, xs[1:])
    return aux(n, range(3, n + 1, 2))

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

def libreDeCuadrados4(x):
    return x == producto(primefactors(x))

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_libreDeCuadrados(n):
    assert libreDeCuadrados1(n) ==\
           libreDeCuadrados2(n) ==\
           libreDeCuadrados3(n) ==\
           libreDeCuadrados4(n)

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

# 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('libreDeCuadrados1(9699690)')
#    2.66 segundos
#    >>> tiempo('libreDeCuadrados2(9699690)')
#    2.58 segundos
#    >>> tiempo('libreDeCuadrados3(9699690)')
#    0.00 segundos
#    >>> tiempo('libreDeCuadrados4(9699690)')
#    0.00 segundos
#
#    >>> n = producto(list(primerange(1, 25000)))
#    >>> tiempo('libreDeCuadrados3(n)')
#    0.42 segundos
#    >>> tiempo('libreDeCuadrados4(n)')
#    0.14 segundos

100

101

102

103

104

105

from timeit import Timer, default_timer

from sys import setrecursionlimit

from sympy import primefactors, primerange

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

def libreDeCuadrados1(n: int) -> bool:

return [x for x in range(2, n + 2) if n % (x**2) == 0] == []

# 2ª solución

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

# divisores(n) es la lista de los divisores del número n. Por ejemplo,

# divisores(30) == [1,2,3,5,6,10,15,30]

def divisores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,

# primo(30) == False

# primo(31) == True

def primo1(n: int) -> bool:

return divisores1(n) == [1, n]

# divisoresPrimos(x) es la lista de los divisores primos de x. Por

# ejemplo,

# divisoresPrimos(40) == [2, 5]

# divisoresPrimos(70) == [2, 5, 7]

def divisoresPrimos1(x: int) -> list[int]:

return [n for n in divisores1(x) if primo1(n)]

# producto(xs) es el producto de los elementos de xs. Por ejemplo,

# producto([3, 2, 5]) == 30

def producto(xs):

if xs:

return xs[0] * producto(xs[1:])

return 1

def libreDeCuadrados2(x):

return x == producto(divisoresPrimos1(x))

# 3ª solución

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

def libreDeCuadrados3(n: int) -> bool:

if n % 2 == 0:

return n % 4 != 0 and libreDeCuadrados3(n // 2)

def aux(m, xs):

if m == 1:

return True

if xs == []:

return True

if m % xs[0] == 0:

return m % (xs[0]**2) != 0 and aux(m // xs[0], xs[1:])

return aux(m, xs[1:])

return aux(n, range(3, n + 1, 2))

# 4ª solución

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

def libreDeCuadrados4(x):

return x == producto(primefactors(x))

# Comprobación de equivalencia

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

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_libreDeCuadrados(n):

assert libreDeCuadrados1(n) ==\

libreDeCuadrados2(n) ==\

libreDeCuadrados3(n) ==\

libreDeCuadrados4(n)

# La comprobación es

# src> poetry run pytest -q numeros_libres_de_cuadrados.py

# 1 passed in 0.59s

# 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('libreDeCuadrados1(9699690)')

# 2.66 segundos

# >>> tiempo('libreDeCuadrados2(9699690)')

# 2.58 segundos

# >>> tiempo('libreDeCuadrados3(9699690)')

# 0.00 segundos

# >>> tiempo('libreDeCuadrados4(9699690)')

# 0.00 segundos

# >>> n = producto(list(primerange(1, 25000)))

# >>> tiempo('libreDeCuadrados3(n)')

# 0.42 segundos

# >>> tiempo('libreDeCuadrados4(n)')

# 0.14 segundos

El código se encuentra en GitHub.

Meses: septiembre 2022

Triángulo aritmético

Suma de cuadrados menos cuadrado de la suma

Suma de los cuadrados de los primeros números naturales

Suma de los primeros números naturales

Números libres de cuadrados

Entradas recientes

Buscar

Correo electrónico