Números libres de cuadrados
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
1 |
libreDeCuadrados :: Integer -> Bool |
tal que libreDeCuadrados x
se verifica si x
es libre de cuadrados. Por ejemplo,
1 2 3 |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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.