Menu Close

El teorema de Navidad de Fermat

José A. Alonso,

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

   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. 
     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,
     λ> 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,
     λ> take 20 primos4nM1
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

Comprobar con QuickCheck el torema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Soluciones

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

– ¡Cuándo llegará otro día!
– Hoy es siempre todavía.

Antonio Machado

Medio
, , , , , , , , , , ,

4 soluciones de “El teorema de Navidad de Fermat”

  1. Responder
    frahidzam 
    import Data.Numbers.Primes (primes)
import Data.List (delete)
 
representaciones :: Integer -> [(Integer,Integer)]
representaciones n = [(a,b) | a <- [0..n], b <- [a..n], n == a^2 + b^2]
 
primosImparesConRepresentacionUnica :: [Integer]
primosImparesConRepresentacionUnica =
  delete 2 [a | a <- primes
              , not (null (representaciones a))
              , head (representaciones a) == last (representaciones a)]
 
primos4nM1 :: [Integer]
primos4nM1 = [a | a <- primes, mod (a-1) 4 == 0]
 
prop_teoremaDeNavidadDeFermat :: Int -> Property
prop_teoremaDeNavidadDeFermat n =
  n > 0 ==>
  take n primosImparesConRepresentacionUnica == take n primos4nM1
 
-- La comprobacion es
-- λ> quickCheck prop_teoremaDeNavidadDeFermat
-- +++ OK, passed 100 tests.
  2. Responder
    lucsanand 
    import Data.List ((), nub)
import Test.QuickCheck
import Data.Numbers.Primes (primes)
 
representaciones :: Integer -> [(Integer, Integer)]
representaciones n =
  nub [(a,b) | a <- [0..n], b <- [0..n], a <= b, a^2+b^2 == n]
 
primosImparesConRepresentacionUnica :: [Integer]
primosImparesConRepresentacionUnica =
  [x | x <- primes  [2], length (representaciones x) == 1]
 
primos4nM1 :: [Integer]
primos4nM1 = [x | x <- primes, congruente4 x]
 
congruente4 :: Integer -> Bool
congruente4 x = elem x [4*n + 1 | n <- [0..div x 4]]
 
comp_teoremaNavidad :: Int -> Property
comp_teoremaNavidad n = n > 0 ==> 
  take n primosImparesConRepresentacionUnica == take n primos4nM1
 
-- La comprobación es:
--    λ> quickCheck comp_teoremaNavidad
--    +++ OK, passed 100 tests.
  3. Responder
    adogargon 
    import Data.Numbers.Primes (primes, isPrime)
import Test.QuickCheck
 
representaciones :: Integer -> [(Integer,Integer)]
representaciones x =
  reverse [(a,b) | b <- [0..x], a <- [0..b-1], a^2 + b^2 == x]
 
primosImparesConRepresentacionUnica :: [Integer]
primosImparesConRepresentacionUnica =
  [x | x <- primes, length (representaciones x) == 1 ]
 
primos4nM1 :: [Integer]
primos4nM1 = [4*n+1 | n <- [1..] , isPrime (4*n+1)]
 
prop_primos :: Int -> Property
prop_primos n =
  n > 0 ==>
  primosImparesConRepresentacionUnica !! n == primos4nM1 !! n
 
-- La comprobación es :
--    λ> quickCheck prop_primos
--    +++ OK, passed 100 tests.
  4. Responder
    luipromor 
    import Test.QuickCheck
import Data.Numbers.Primes (isPrime)
 
representaciones :: Integer -> [(Integer,Integer)]
representaciones n =
  [(x,y) | x <-[0..n], y <- [x..n], x^2 + y ^2 == n]
 
primosImparesConRepresentacionUnica :: [Integer]
primosImparesConRepresentacionUnica =
  [x | x <- [5..], (not . null) (representaciones x), isPrime x]
 
primos4nM1 :: [Integer]
primos4nM1 = [x | x <- [5..], mod (x-1) 4 == 0, isPrime x]
 
prop_navidad :: Int -> Property
prop_navidad n =
  n >= 0 ==>
  take  n  primosImparesConRepresentacionUnica  == take n  primos4nM1

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.