Menu Close

Números como diferencias de potencias

José A. Alonso,

El número 45 se puede escribir de tres formas como diferencia de los cuadrados de dos números naturales:

   45 =  7^2 -  2^2 
      =  9^2 -  6^2
      = 23^2 - 22^2

Definir la función

   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,

   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ª 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)
Inicial
, , ,

5 soluciones de “Números como diferencias de potencias”

  1. Responder
    alerodrod5

    Aquí una definición pero que no es suficientemente eficiente para el último caso

     
diferencias ::Integer -> Integer -> [(Integer,Integer)]
diferencias x n = [(a,b) | a<-[0..x], b<-[0..a], a^n-b^n==x]
    • Responder
      carriomon1

      Esta es otra definición más eficiente que la tuya, pero sigue sin poder calcular el último ejemplo.

       
diferencias :: Integer -> Integer -> [(Integer,Integer)]
diferencias x n = [(a,b) | a <- [(raizN x n)..x] ,let b = raizN (a^n-x) n, a^n-b^n== x ]
 
raizN :: Integer -> Integer -> Integer
raizN x n = floor $ (fromIntegral x) ** (1 / (fromIntegral n))
  2. Responder
    jaibengue 
    diferencias :: Integer -> Integer -> [(Integer,Integer)]
diferencias a b = aux 0
  where aux n | condicion1 = []
              | condicion2 = (roundT, n) : aux (n+1)
              | otherwise  = aux (n+1)
                where condicion1 = (n+1)^b - n^b > a
                      condicion2 = roundT^b - n^b == a
                      t = (fromIntegral (a + n^b)) ** (1/(fromIntegral b))
                      roundT = round t
  3. Responder
    carbremor 
    diferencias :: Integer -> Integer -> [(Integer, Integer)]
diferencias n x = [(a,b) | a <- [(raizEnesima n x)..(div n 2)+1], b <- [0..(div n 2)+1], a^x-b^x == n]
 
raizEnesima :: Integer -> Integer -> Integer
raizEnesima n x = round $ (fromIntegral n**(1/fromIntegral x))
  4. Responder
    Chema Cortés 
    raizEnesima :: Integer -> Integer -> Integer
raizEnesima x n = round (fromIntegral x ** (1/fromIntegral n))
 
diferencias :: Integer -> Integer -> [(Integer,Integer)]
diferencias x n = [(a,b) | a <- [aMin..aMax+1]
                         , let c = a^n - x
                         , let b = raizEnesima c n
                         , b^n == c ]
  where
    aMin = raizEnesima x n
    aMax = raizEnesima (x `div` 2) (n-1)

Escribe tu solución

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