Representaciones de un número como suma de dos cuadrados
Definir la función
|
1 |
representaciones :: Integer -> [(Integer,Integer)] |
tal que (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.
|
1 2 3 4 |
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] length (representaciones (10^14)) == 8 |
Comprobar con QuickCheck que un número natural n se puede como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.
Soluciones
|
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 |
import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== representaciones1 :: Integer -> [(Integer,Integer)] representaciones1 n = [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y] -- 2ª solución -- =========== representaciones2 :: Integer -> [(Integer,Integer)] representaciones2 n = [(x,raiz z) | x <- [0..raiz (n `div` 2)], let z = n - x*x, esCuadrado z] -- (raiz x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz 25 == 5 -- raiz 24 == 4 -- raiz 26 == 5 raiz :: Integer -> Integer raiz = floor . sqrt . fromIntegral -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado 25 == True -- esCuadrado 26 == False esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raiz x -- 3ª solución -- =========== representaciones3 :: Integer -> [(Integer, Integer)] representaciones3 n = aux 0 (raiz n) where aux x y | x > y = [] | otherwise = case compare (x*x + y*y) n of LT -> aux (x + 1) y EQ -> (x, y) : aux (x + 1) (y - 1) GT -> aux x (y - 1) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_representaciones :: Positive Integer -> Bool prop_representaciones (Positive n) = all (== representaciones1 n) [representaciones2 n, representaciones3 n] -- La comprobación es -- λ> quickCheck prop_representaciones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> representaciones1 4000 -- [(20,60),(36,52)] -- (4.95 secs, 2,434,929,624 bytes) -- λ> representaciones2 4000 -- [(20,60),(36,52)] -- (0.00 secs, 599,800 bytes) -- λ> representaciones3 4000 -- [(20,60),(36,52)] -- (0.01 secs, 591,184 bytes) -- -- λ> length (representaciones2 (10^14)) -- 8 -- (6.64 secs, 5,600,837,088 bytes) -- λ> length (representaciones3 (10^14)) -- 8 -- (9.37 secs, 4,720,548,264 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_representacion :: Positive Integer -> Bool prop_representacion (Positive n) = not (null (representaciones2 n)) == all (\(p,e) -> p `mod` 4 /= 3 || even e) (factorizacion n) -- (factorizacion n) es la factorización prima de n. Por ejemplo, -- factorizacion 600 == [(2,3),(3,1),(5,2)] factorizacion :: Integer -> [(Integer,Integer)] factorizacion n = map (\xs -> (head xs, genericLength xs)) (group (primeFactors n)) -- La comprobación es -- λ> quickCheck prop_representacion -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.