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