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:

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

45 = 7^2 - 2^2

= 9^2 - 6^2

= 23^2 - 22^2

Definir la función

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

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,

   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)

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)

-- 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)

5 Comentarios

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]

1 2	diferencias ::Integer -> Integer -> [(Integer,Integer)] diferencias x n = [(a,b) \| a<-[0..x], b<-[0..a], a^n-b^n==x]

Responder

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))

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))

Responder

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

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

Responder

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))

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))

Responder

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)

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)

Responder

Números como diferencias de potencias

Soluciones

5 Comentarios

Leave a Reply to carriomon1Cancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Leave a Reply to carriomon1Cancel reply

Entradas recientes

Buscar

Correo electrónico