El teorema de Navidad de Fermat
El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el Teorema de Navidad de Fermat.
Definir las funciones
1 2 3 |
representaciones :: Integer -> [(Integer,Integer)] primosImparesConRepresentacionUnica :: [Integer] primos4nM1 :: [Integer] |
tales que
- (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo,
1 2 3 4 5 6 |
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] representaciones 100000147984 == [(0,316228)] length (representaciones (10^10)) == 6 length (representaciones (4*10^12)) == 7 |
- primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,
1 2 |
λ> take 20 primosImparesConRepresentacionUnica [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
- primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,
1 2 |
λ> take 20 primos4nM1 [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y^2 (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).
Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.
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 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 |
import Data.Numbers.Primes (primes) import Test.QuickCheck -- 1ª definición de representaciones -- ================================= representaciones :: Integer -> [(Integer,Integer)] representaciones n = [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y] -- 2ª definición de representaciones -- ================================= representaciones2 :: Integer -> [(Integer,Integer)] representaciones2 n = [(x,raiz z) | x <- [0..raiz (n `div` 2)] , let z = n - x*x , esCuadrado z] -- (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 -- (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 0 = 0 raiz 1 = 1 raiz x = aux (0,x) where aux (a,b) | d == x = c | c == a = a | d < x = aux (c,b) | otherwise = aux (a,c) where c = (a+b) `div` 2 d = c^2 -- 3ª definición de representaciones -- ================================= representaciones3 :: Integer -> [(Integer,Integer)] representaciones3 n = [(x,raiz3 z) | x <- [0..raiz3 (n `div` 2)] , let z = n - x*x , esCuadrado3 z] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado3 25 == True -- esCuadrado3 26 == False esCuadrado3 :: Integer -> Bool esCuadrado3 x = x == y * y where y = raiz3 x -- (raiz3 x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz3 25 == 5 -- raiz3 24 == 4 -- raiz3 26 == 5 raiz3 :: Integer -> Integer raiz3 x = floor (sqrt (fromIntegral x)) -- 4ª definición de representaciones -- ================================= representaciones4 :: Integer -> [(Integer, Integer)] representaciones4 n = aux 0 (floor (sqrt (fromIntegral 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) -- Equivalencia de las definiciones de representaciones -- ==================================================== -- La propiedad es prop_representaciones_equiv :: (Positive Integer) -> Bool prop_representaciones_equiv (Positive n) = representaciones n == representaciones2 n && representaciones2 n == representaciones3 n && representaciones3 n == representaciones4 n -- La comprobación es -- λ> quickCheck prop_representaciones_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia de las definiciones de representaciones -- ================================================================= -- λ> representaciones 3025 -- [(0,55),(33,44)] -- (2.86 secs, 1,393,133,528 bytes) -- λ> representaciones2 3025 -- [(0,55),(33,44)] -- (0.00 secs, 867,944 bytes) -- λ> representaciones3 3025 -- [(0,55),(33,44)] -- (0.00 secs, 173,512 bytes) -- λ> representaciones4 3025 -- [(0,55),(33,44)] -- (0.00 secs, 423,424 bytes) -- -- λ> length (representaciones2 (10^10)) -- 6 -- (3.38 secs, 2,188,903,544 bytes) -- λ> length (representaciones3 (10^10)) -- 6 -- (0.10 secs, 62,349,048 bytes) -- λ> length (representaciones4 (10^10)) -- 6 -- (0.11 secs, 48,052,360 bytes) -- -- λ> length (representaciones3 (4*10^12)) -- 7 -- (1.85 secs, 1,222,007,176 bytes) -- λ> length (representaciones4 (4*10^12)) -- 7 -- (1.79 secs, 953,497,480 bytes) -- Definición de primosImparesConRepresentacionUnica -- ================================================= primosImparesConRepresentacionUnica :: [Integer] primosImparesConRepresentacionUnica = [x | x <- tail primes , length (representaciones4 x) == 1] -- Definición de primos4nM1 -- ======================== primos4nM1 :: [Integer] primos4nM1 = [x | x <- primes , x `mod` 4 == 1] -- Teorema de Navidad de Fermat -- ============================ -- La propiedad es prop_teoremaDeNavidadDeFermat :: Positive Int -> Bool prop_teoremaDeNavidadDeFermat (Positive n) = primosImparesConRepresentacionUnica !! n == primos4nM1 !! n -- La comprobación es -- λ> quickCheck prop_teoremaDeNavidadDeFermat -- +++ OK, passed 100 tests. |
Pensamiento
Dijo Dios: brote la nada
Y alzó su mano derecha,
hasta ocultar su mirada.
Y quedó la nada hecha.Antonio Machado