Menu Close

Ecuación diofántica con primos (OME1995 P4)

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 1995 es

Siendo p un número primo, halla las soluciones enteras de la ecuación:

p.(x + y) = x.y

Definir la función

   soluciones :: Integer -> [(Integer, Integer)]

tal que (soluciones p) es la lista de los pares de enteros (x,y) tales que p.(x + y) = x.y. Por ejemplo,

   λ> take 3 (soluciones 7)
   [(0,0),(14,14),(-42,6)]
   λ> sum [x+y | (x,y) <- take 6 (soluciones (primes !! (10^6)))]
   185830404

Soluciones

import Data.List (sort)
import Data.Numbers.Primes (primes)
 
-- 1ª solución
-- ===========
 
soluciones :: Integer -> [(Integer, Integer)]
soluciones p =
  [(x,y) | (x,y) <- pares,
           p * (x + y) == x * y]
 
-- pares es la lista de los pares de números enteros ordenados por la
-- suma de los valores absolutos de sus componentes. Por ejemplo,
--    λ> take 38 pares
--    [(0,0),(-1,0),(0,-1),(0,1),(1,0),(-2,0),(-1,-1),(-1,1),(0,-2),
--     (0,2),(1,-1),(1,1),(2,0),(-3,0),(-2,-1),(-2,1),(-1,-2),(-1,2),
--     (0,-3),(0,3),(1,-2),(1,2),(2,-1),(2,1),(3,0),(-4,0),(-3,-1),
--     (-3,1),(-2,-2),(-2,2),(-1,-3),(-1,3),(0,-4),(0,4),(1,-3),(1,3),
--     (2,-2),(2,2)]
pares :: [(Integer,Integer)]
pares = concatMap paresEnterosSuma [0..]
 
-- (paresEnterosSuma n) es la lista de pares de enteros (x,y) tales que la suma
-- de los valores absolutos de x e y es igual a n. Por ejemplo,
--    λ> paresEnterosSuma 3
--    [(-3,0),(-2,-1),(-2,1),(-1,-2),(-1,2),(0,-3),(0,3),(1,-2),(1,2),
--     (2,-1),(2,1),(3,0)]
paresEnterosSuma :: Integer -> [(Integer,Integer)]
paresEnterosSuma n = concatMap aux [-n..n]
  where aux k | m == 0    = [(k,0)]
              | otherwise = [(k,-m),(k,m)]
          where m = n - abs k
 
-- 2ª solución
-- ===========
 
-- Observando los siguientes cálculos:
--    take 6 (soluciones 2)  == [(0,0),(-2,1),(1,-2),(4,4),(3,6),(6,3)]
--    take 6 (soluciones 3)  == [(0,0),(-6,2),(2,-6),(6,6),(4,12),(12,4)]
--    take 6 (soluciones 5)  == [(0,0),(10,10),(-20,4),(4,-20),(6,30),(30,6)]
--    take 6 (soluciones 7)  == [(0,0),(14,14),(-42,6),(6,-42),(8,56),(56,8)]
--    take 6 (soluciones 11) == [(0,0),(22,22),(-110,10),(10,-110),(12,132),(132,12)]
 
soluciones2 :: Integer -> [(Integer, Integer)]
soluciones2 2 = [(0,0),(-2,1),(1,-2),(4,4),(3,6),(6,3)]
soluciones2 3 = [(0,0),(-6,2),(2,-6),(6,6),(4,12),(12,4)]
soluciones2 p =
  [(0,0), (2*p,2*p), (p*(1-p),p-1), (p-1,p*(1-p)), (p+1,p*(p+1)), (p*(p+1),p+1)]
 
-- Comparación de equivalencia
-- ===========================
 
-- La propiedad es
prop_equivalencia :: Bool
prop_equivalencia =
  and [ take 6 (soluciones p) == soluciones2 p
      | p <- takeWhile (<= 37) primes]
 
-- La comprobación es
--    λ> prop_equivalencia
--    True
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> take 6 (soluciones 37)
--    [(0,0),(74,74),(-1332,36),(36,-1332),(38,1406),(1406,38)]
--    (3.88 secs, 2,521,196,352 bytes)
--    λ> take 6 (soluciones2 37)
--    [(0,0),(74,74),(-1332,36),(36,-1332),(38,1406),(1406,38)]
--    (0.01 secs, 144,192 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

2 soluciones de “Ecuación diofántica con primos (OME1995 P4)

  1. Rubén Muñoz Mkrtchian
    -- 1ª Definición:
    -- =============
     
    -- A partir de la expresión p(x+y) = xy, vamos a tratar de encontrar los
    -- posibles valores de y en función de x y p. Para asegurarnos de poder
    -- dividir entre x-p comprobamos que x = p jamás puede ser solución.
    --    x == p ==> p(p+y) = p^2 + py = py ==> p^2 = 0 ==> p = 0
    --    x /= p ==> p(x+y) = px + py = xy ==> px = (x-p)y ==> y = px / (x-p)
    --
    -- Ahora bien, teniendo en cuenta que y debe ser un número entero, la primera
    -- definición es la siguiente:
     
    soluciones :: Integer -> [(Integer, Integer)]
    soluciones p = [(x,y) | x <- enteros, let (y,r) = divMod (p*x) (x-p), x /= p, r == 0]
       where enteros = 0 : concat [[-x,x] | x <- [1..]]
     
    -- Si para n > 6 escribimos take n (soluciones p), con p un primo cualquiera,
    -- observamos que el cálculo de la lista solución nunca termina. Resulta lógico
    -- por lo tanto pensar que hay un número finito de soluciones enteras de la
    -- ecuación planteada, en concreto seis soluciones.
     
    solucionesTotales :: Integer -> [(Integer, Integer)]
    solucionesTotales = take 6 . soluciones
     
    -- 2ª Definición:
    -- =============
     
    -- Vamos a calcular ahora las soluciones de la ecuación para distintos primos
    -- para así encontrar algún patrón en las soluciones.
    --    λ> solucionesTotales 5
    --    [(0,0),(4,-20),(6,30),(10,10),(-20,4),(30,6)]
    --    λ> solucionesTotales 7
    --    [(0,0),(6,-42),(8,56),(14,14),(-42,6),(56,8)]
    --    λ> solucionesTotales 11
    --    [(0,0),(10,-110),(12,132),(22,22),(-110,10),(132,12)]
     
    solucionesTotales2 :: Integer -> [(Integer, Integer)]
    solucionesTotales2 p = [(0,0), (a,d), (b,e), (c,c), (d,a), (e,b)]
       where a = p-1
             b = p+1
             c = 2*p
             d = -a*p
             e = b*p
     
    -- Equivalencia de las definiciones:
    -- ================================
     
    -- Para p = 2 y p = 3 las listas son iguales pero el orden de los elementos es
    -- distinto. Vamos a comprobar la equivalencia para p > 3.
     
    prop :: Integer -> Bool
    prop 2 = True
    prop 3 = True
    prop p = not (isPrime p) || solucionesTotales p == solucionesTotales2 p
     
    -- La comprobación es:
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
     
    -- Comparación de eficiencia:
    -- =========================
     
    -- λ> solucionesTotales (primes !! 100)
    -- [(0,0),(546,-298662),(548,299756),(1094,1094),(-298662,546),(299756,548)]
    -- (0.82 secs, 343,234,280 bytes)
    -- λ> solucionesTotales2 (primes !! 100)
    -- [(0,0),(546,-298662),(548,299756),(1094,1094),(-298662,546),(299756,548)]
    -- (0.00 secs, 296,272 bytes)
     
    -- λ> sum [x+y | (x,y) <- solucionesTotales2 (primes !! (10^6))]
    -- 185830404
    -- (2.34 secs, 6,708,404,024 bytes)
  2. j0sejuan
    {-
     
      Como
     
        p (x + y) = x y
     
      o bien `x` o bien `y` tiene como factor a `p`, sea
     
        x = z p
     
      queda pues
     
        p (z p + y) = z p y
     
      es decir
     
              z p
        y = ------
             z - 1
     
      como `y` ha de ser entero y `z` es coprimo con `z - 1`
      entonces `z - 1` debe dividir a `p` que al ser primo
      únicamente es divisible por
     
        -p, -1, 1, p
     
      de cada caso sacamos las `z` posibles
     
        z - 1 = -p => z = 1 - p
        z - 1 = -1 => z = 0
        z - 1 =  1 => z = 2
        z - 1 =  p => z = 1 + p
     
      teniendo en cuenta que la primera y última son asimétricas
      y como `x` e `y` han quedado fijadas por `z` queda
     
    -}
     
    soluciones :: Integer -> [(Integer, Integer)]
    soluciones p = swap a: swap b: xs
      where xs@(a:b:_) = [(z * p, (z * p) `div` (z - 1)) | z <- [1 - p, 1 + p, 0, 2]]

Leave a Reply

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