Mes: septiembre 2022

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

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

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

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

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)

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

   libreDeCuadrados :: Integer -> Bool

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

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)

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