Menu Close

Ternas euclídeas

Uno de los problemas planteados por Euclides en los Elementos consiste en encontrar tres números tales que cada uno de sus productos, dos a dos, aumentados en la unidad sea un cuadrado perfecto.

Diremos que (x,y,z) es una terna euclídea si es una solución del problema; es decir, si x <= y <= z y xy+1, yz+1 y zx+1 son cuadrados. Por ejemplo, (4,6,20) es una terna euclídea ya que

   4x6+1 = 5^2, 6x20+1 = 11^2 y 20*4+1 = 9^2

Definir la funciones

   ternasEuclideas        :: [(Integer,Integer,Integer)]
   esMayorDeTernaEuclidea :: Integer -> Bool

tales que

  • ternasEuclideas es la lista de las ternas euclídeas. Por ejemplo,
     λ> take 7 ternasEuclideas
     [(1,3,8),(2,4,12),(1,8,15),(3,5,16),(4,6,20),(3,8,21),(5,7,24)]
  • (esMayorDeTernaEuclidea z) se verifica si existen x, y tales que (x,y,z) es una terna euclídea. Por ejemplo,
     esMayorDeTernaEuclidea 20  ==  True
     esMayorDeTernaEuclidea 22  ==  False

Comprobar con QuickCheck que z es el mayor de una terna euclídea si, y sólo si, existe un número natural x tal que 1 < x < z – 1 y x^2 es congruente con 1 módulo z.

Soluciones

import Test.QuickCheck
 
ternasEuclideas :: [(Integer,Integer,Integer)]
ternasEuclideas =
  [(x,y,z) | z <- [1..]
           , y <- [1..z]
           , esCuadrado (y * z + 1)
           , x <- [1..y]
           , esCuadrado (x * y + 1)
           , esCuadrado (z * x + 1)]
 
-- (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 = (raizEntera x)^2 == x
  where raizEntera :: Integer -> Integer
        raizEntera = floor . sqrt . fromIntegral 
 
esMayorDeTernaEuclidea :: Integer -> Bool
esMayorDeTernaEuclidea z =
  not (null [(x,y) | y <- [1..z]
                   , esCuadrado (y * z + 1)
                   , x <- [1..y]
                   , esCuadrado (x * y + 1)
                   , esCuadrado (z * x + 1)])
 
 
-- La propiedad es
prop_esMayorDeTernaEuclidea :: Positive Integer -> Bool
prop_esMayorDeTernaEuclidea (Positive z) =
  esMayorDeTernaEuclidea z == any (\x -> (x^2) `mod` z == 1) [2..z-2]
 
-- La comprobación es
--    λ> quickCheck prop_esMayorDeTernaEuclidea
--    +++ OK, passed 100 tests.

Pensamiento

Todo pasa y todo queda,
pero lo nuestro es pasar,
pasar haciendo caminos,
caminos sobre la mar.

Antonio Machado

4 soluciones de “Ternas euclídeas

  1. frahidzam
    ternasEuclideas :: [(Integer, Integer, Integer)]
    ternasEuclideas = [(x,y,z) | z <- [1..], y <- [1..z], x <- [1..z], esCuadrado (x*y+1),esCuadrado (y*z+1), esCuadrado (z*x+1), x <= y ]
     
    esCuadrado :: Integer -> Bool
    esCuadrado n = elem n (takeWhile (<= n) [a^2 | a <- [1..]])
     
    esMayorDeTernaEuclidea :: Integer -> Bool
    esMayorDeTernaEuclidea n = elemento n (unzip3 (take (fromIntegral n) ternasEuclideas))
     
    mayorTerna :: [Integer]
    mayorTerna = [a | a <- [1..], esMayorDeTernaEuclidea a]
     
    elemento :: Integer -> ([Integer], [Integer], [Integer]) -> Bool
    elemento n (xs, ys, zs) = elem n zs
     
    prop_ternaEuclidea :: Int -> Property
    prop_ternaEuclidea n = n >= 0 ==> mayorTerna !! n == mayorTerna2 !! n
     
    esMayorDeTernaEuclidea2 :: Integer -> Bool
    esMayorDeTernaEuclidea2 z = not ( null [x | x <- [2..(z-2)], mod ((x^2)-1) z == 0])
     
    mayorTerna2 :: [Integer]
    mayorTerna2 = [a | a <- [1..], esMayorDeTernaEuclidea2 a]
  2. adogargon
    import Test.QuickCheck
     
    ternasEuclideas :: [(Integer,Integer,Integer)]
    ternasEuclideas = [ (x,y,z) | z <-[1..] , y <- [1..z] , x <- [1..y] ,
                        cuadradoperfecto (x*y+1) && cuadradoperfecto (y*z+1) &&
                        cuadradoperfecto (z*x+1) ]
     
    cuadradoperfecto :: Integer -> Bool
    cuadradoperfecto x = aux x 1
      where aux x n | n^2 < x = aux x (n+1)
                    | n^2 == x = True
                    | otherwise = False
     
    esMayorDeTernaEuclidea :: Integer -> Bool
    esMayorDeTernaEuclidea x =
      x`elem`(takeWhile (<=x) [z | (_,_,z) <- ternasEuclideas])
     
    comprobacion :: Integer -> Property
    comprobacion z =
      z > 0 && esMayorDeTernaEuclidea z ==> or[x^2`mod`z == 1 | x <-[2..(z-2)]] 
     
    comprobacion2 :: Integer -> Property
    comprobacion2 z =
      z > 0 && (not.null) [ x | x <- [2..(z-2)], x^2`mod`z == 1] ==> esMayorDeTernaEuclidea z
     
    --He preferido separar las dos implicaciones para no sobrecargar la definicion , que ya es poco eficiente de por si.
    --λ> quickCheck comprobacion
    --+++ OK, passed 100 tests.
    --λ> quickCheck comprobacion2
    --+++ OK, passed 100 tests.
  3. luipromor
    ternasEuclideas        :: [(Integer,Integer,Integer)]
    ternasEuclideas = [ (x,y,z) | z <- [1..] , y <- [1..z] , x <- [1..y] , aux (x*y +1) , aux (z*y +1) , aux (x*z +1)]
      where aux a = any (==a) [ x^2 | x <- [1..div a 2]]
    esMayorDeTernaEuclidea :: Integer -> Bool
    esMayorDeTernaEuclidea z = aux z ternasEuclideas
      where aux z ((_,_,c):xs) | z == c = True
                               | c >= z = False
                               | otherwise = aux z xs
    prop_ternasEuclideas :: Integer -> Property
    prop_ternasEuclideas z = z > 0 ==> if b then a else True && if a then b  else True
      where a = not (null [ x |x <- [2..z-2] , mod (x^2) z ==1])
            b =  esMayorDeTernaEuclidea z
  4. javmarcha1
    import Data.List
     
    ternasEuclideas :: [(Integer,Integer,Integer)]
    ternasEuclideas = [(x,y,z) | (x,y,z) <- (listaTernas 3) , esTerna x y z]
     
    listaTernas :: Integer -> [(Integer,Integer,Integer)]
    listaTernas n = listaTernasSuman n ++ listaTernas (n+1)
     
    listaTernasSuman :: Integer -> [(Integer,Integer,Integer)]
    listaTernasSuman n = [(a,b,c)| [a,b,c] <- nub [ sort [x,y,z] |
                        x <- [1..n] ,y <- [1..n] ,z <- [1..n], x+y+z == n]] 
     
    esTerna :: Integer -> Integer -> Integer -> Bool
    esTerna x y z = (((esDupla x y) && (esDupla y z)) && (esDupla z x))
     
    esDupla :: Integer -> Integer -> Bool
    esDupla x y = elem x (takeWhile (<= x) (cuadradosDivididos y))
     
    cuadradosDivididos :: Integer -> [Integer]
    cuadradosDivididos n = [ quot x n | x <- cuadradosConDivisor n]
     
    cuadradosConDivisor :: Integer -> [Integer]
    cuadradosConDivisor n = [ x | x <- cuadradosmenos1 , elem n (divisores x)]
     
    divisores :: Integer -> [Integer]
    divisores n = [m | m <- [1..n], n `mod` m == 0]
     
    cuadradosmenos1 :: [Integer]
    cuadradosmenos1 = [ x^2-1 | x <- [1..]]
     
    esMayorDeTernaEuclidea :: Integer -> Bool
    esMayorDeTernaEuclidea z = or [esTerna x y z | x <- [1..z],y <- [1..z]]
     
    prop_ternasEuclideas :: Integer -> Property
    prop_ternasEuclideas z = z > 0 ==> if m then n else True && if n then m  else True
      where n = not (null [ x |x <- [2..z-2] , mod (x^2) z ==1])
            m =  esMayorDeTernaEuclidea z

Leave a Reply

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