Números como diferencias de potencias
El número 45 se puede escribir de tres formas como diferencia de los cuadrados de dos números naturales:
|
1 2 3 |
45 = 7^2 - 2^2 = 9^2 - 6^2 = 23^2 - 22^2 |
Definir la función
|
1 |
diferencias :: Integer -> Integer -> [(Integer,Integer)] |
tal que (diferencias x n) es la lista de pares tales que la diferencia de sus potencias n-ésima es x. Por ejemplo,
|
1 2 3 4 5 6 7 |
diferencias 45 2 == [(7,2),(9,6),(23,22)] diferencias 50 2 == [] diferencias 19 3 == [(3,2)] diferencias 8 3 == [(2,0)] diferencias 15 4 == [(2,1)] diferencias 4035 2 == [(142,127),(406,401),(674,671),(2018,2017)] head (diferencias 1161480105172255454401 5) == (123456,123455) |
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 |
-- 1ª definición diferencias :: Integer -> Integer -> [(Integer,Integer)] diferencias x n = [(a,b) | b <- [0..x] , a <- [b..x] , x == a^n - b^n] -- 2ª definición diferencias2 :: Integer -> Integer -> [(Integer,Integer)] diferencias2 x n = [(a,b) | a <- [1..x] , a^n >= x , let b = round ((fromIntegral (a^n - x)) ** (1/fromIntegral n)) , x == a^n - b^n] -- 3ª definición diferencias3 :: Integer -> Integer -> [(Integer,Integer)] diferencias3 x n = [(a,b) | a <- [0..x] , a^n >= x , b <- raizEntera n (a^n - x)] raizEntera :: Integer -> Integer -> [Integer] raizEntera n x | y^n == x = [y] | otherwise = [] where y = head [k | k <- [0..], k^n >= x] -- 4ª definición diferencias4 :: Integer -> Integer -> [(Integer,Integer)] diferencias4 x n = [(a,b) | a <- [0..x] , a^n >= x , b <- raizEntera n (a^n - x)] where potencias = [(k,k^n) | k <- [0..]] raizEntera n x | yn == x = [y] | otherwise = [] where (y,yn) = head [(k,kn) | (k,kn) <- potencias, kn >= x] -- Comparación de eficiencia -- λ> head (diferencias 7351 3) -- (50,49) -- (2.16 secs, 533,868,368 bytes) -- λ> head (diferencias2 7351 3) -- (50,49) -- (0.01 secs, 270,040 bytes) -- λ> head (diferencias3 7351 3) -- (50,49) -- (0.01 secs, 1,021,720 bytes) -- λ> head (diferencias4 7351 3) -- (50,49) -- (0.01 secs, 316,536 bytes) |