Órbita con raíz entera (OME1997 P4)
El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 1997 es
Sea p un número primo. Determinar todos los enteros k tales que sqrt(k² – k*p) es natural.
Definir las funciones
1 2 |
orbita :: Integer -> [Integer] orbitaDePrimo :: Integer -> [Integer] |
tales que
- (orbita n) es la lista de todos los enteros k tales que sqrt(k² – k*n) es natural. Por ejemplo,
1 2 3 4 5 |
take 4 (orbita 6) == [0,-2,6,8] take 5 (orbita 36) == [0,-12,36,48,-64] take 6 (orbita 9) == [0,-3,9,12,-16,25] take 8 (orbita 27) == [0,-9,27,36,-48,75,-169,196] take 10 (orbita 111) == [0,-37,111,148,-289,400,-972,1083,-3025,3136] |
- (orbitaDePrimo p) es la lista de todos los enteros k tales que sqrt(k² – k*p) es natural, suponiendo que p es un número primo. Por ejemplo,
1 2 |
orbitaDePrimo 5 == [0,-4,5,9] orbitaDePrimo (primes !! (10^6)) == [0,15485867,-59953011442489,59953026928356] |
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 |
import Data.Numbers.Primes (primes) orbita :: Integer -> [Integer] orbita n = [k | k <- enteros, k^2 - k*n >= 0, esCuadrado (k^2 - k*n)] -- entero es la lista de los números enteros. Por ejemplo, -- λ> take 20 enteros -- [0,-1,1,-2,2,-3,3,-4,4,-5,5,-6,6,-7,7,-8,8,-9,9,-10] enteros :: [Integer] enteros = 0 : concat [[-n,n] | n <- [1..]] -- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por -- ejemplo, -- esCuadrado 16 == True -- esCuadrado 27 == False esCuadrado :: Integer -> Bool esCuadrado x = (raizEntera x)^2 == x -- (raizEntera x) es el mayor entero cuyo cuadrado es menor o igual que -- x. Por ejemplo, -- raizEntera 16 == 4 -- raizEntera 27 == 5 raizEntera :: Integer -> Integer raizEntera x = aux (1,x) where aux (a,b) | d == x = c | c == a = c | d < x = aux (c,b) | otherwise = aux (a,c) where c = (a+b) `div` 2 d = c^2 -- 1ª definición de orbitaDePrimo -- ============================== orbitaDePrimo1 :: Integer -> [Integer] orbitaDePrimo1 2 = take 2 (orbita 2) orbitaDePrimo1 p = take 4 (orbita p) -- 2ª definición de orbitaDePrimo -- ============================== -- Basada en los siguientes cálculos -- orbitaDePrimo1 2 == [0,2] -- orbitaDePrimo1 3 == [0,-1,3,4] -- orbitaDePrimo1 5 == [0,-4,5,9] -- orbitaDePrimo1 7 == [0, 7, -9, 16] -- orbitaDePrimo1 11 == [0,11, -25, 36] -- orbitaDePrimo1 13 == [0,13, -36, 49] -- orbitaDePrimo1 17 == [0,17, -64, 81] -- orbitaDePrimo1 19 == [0,19, -81,100] -- orbitaDePrimo1 23 == [0,23,-121,144] orbitaDePrimo2 :: Integer -> [Integer] orbitaDePrimo2 p | p == 2 = [0,2] | p <= 5 = [0, -((p-1) `div` 2)^2, p, ((p+1) `div` 2)^2] | otherwise = [0, p, -((p-1) `div` 2)^2, ((p+1) `div` 2)^2] -- Comprobación de equivalencia -- ============================ -- La comprobación es -- λ> and [orbitaDePrimo1 n == orbitaDePrimo2 n | n <- take 30 primes] -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> orbitaDePrimo1 (primes !! 100) -- [0,547,-74529,75076] -- (4.94 secs, 4,471,368,256 bytes) -- λ> orbitaDePrimo2 (primes !! 100) -- [0,547,-74529,75076] -- (0.01 secs, 302,096 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>
(Por comodidad se usa aritmética real exacta, buscar directamente las raíces enteras sería mucho más raṕido)