Menu Close

Descomposiciones en sumas de cuatro cuadrados

José A. Alonso,

Definir la función

   descomposiciones :: Int -> [[Int]]

tal que (descomposiciones x) es la lista de las listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.

   λ> descomposiciones 4
   [[1,1,1,1]]
   λ> descomposiciones 5
   []
   λ> descomposiciones 7
   [[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]]
   λ> descomposiciones 10
   [[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]]
   λ> descomposiciones 15
   [[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1],
    [4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]]
   λ> length (descomposiciones 50000)
   5682

Soluciones

import Data.Array
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
descomposiciones :: Int -> [[Int]]
descomposiciones x = aux x 4
  where 
    aux 0 1 = []
    aux 1 1 = [[1]]
    aux 2 1 = []
    aux 3 1 = []
    aux y 1 | esCuadrado y = [[y]]
            | otherwise    = []
    aux y n = [x^2 : zs | x <- [1..raizEntera y]
                        , zs <- aux (y - x^2) (n-1)]
 
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Int -> Bool
esCuadrado x = (raizEntera x)^2 == x
 
-- (raizEntera n) es el mayor entero cuya raíz cuadrada es menor o igual
-- que n. Por ejemplo,
--    raizEntera 15  ==  3
--    raizEntera 16  ==  4
--    raizEntera 17  ==  4
raizEntera :: Int -> Int
raizEntera = floor . sqrt . fromIntegral 
 
-- 2ª definición
-- =============
 
descomposiciones2 :: Int -> [[Int]]
descomposiciones2 x = a ! (x,4)
  where
    a = array ((0,1),(x,4)) [((i,j), f i j) | i <- [0..x], j <- [1..4]]
    f 0 1 = []
    f 1 1 = [[1]]
    f 2 1 = []
    f 3 1 = []
    f i 1 | esCuadrado i = [[i]]
          | otherwise    = []
    f i j = [x^2 : zs | x <- [1..raizEntera i]
                      , zs <- a ! (i - x^2,j-1)]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_descomposiciones :: Positive Int -> Bool
prop_descomposiciones (Positive x) =
  descomposiciones x == descomposiciones2 x
 
-- La comprobación es
--    λ> quickCheck prop_descomposiciones
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (descomposiciones (2*10^4))
--    1068
--    (3.70 secs, 3,307,251,704 bytes)
--    λ> length (descomposiciones2 (2*10^4))
--    1068
--    (0.72 secs, 678,416,144 bytes)

Pensamiento

No extrañéis, dulces amigos,
que esté mi frente arrugada;
yo vivo en paz con los hombres
y en guerra con mis entrañas.

Antonio Machado

Avanzado
, , , , , ,

3 soluciones de “Descomposiciones en sumas de cuatro cuadrados”

  1. Responder
    frahidzam 
    import Data.List (nub, permutations)
import Data.Array (listArray, (!))
 
descomposiciones :: Int -> [[Int]]
descomposiciones n =
  concat (map nub (map permutations (aux n)))
  where
    aux  n = [ [v ! a,v ! b,v ! c,v ! d]
             | a <- [1..u]
             , b <- [a..u]
             , c <- [b..u]
             , d <- [c..u]
             , sum [v ! a,v ! b,v ! c,v ! d] == n]
    u = floor (sqrt (fromIntegral n))
    v = listArray (1,u) [a^2 | a <- [1..u]]
  2. Responder
    adogargon 
    descomposiciones :: Int -> [[Int]]
descomposiciones n = aux (raizenteramenor n) n
  where lista k = [[a^2,b^2,c^2,d^2] | a <-[1..k]
                                     , b <-[1..k]
                                     , c <-[1..k]
                                     , d <-[1..k]]
        pares k = zip (lista k) (map sum (lista k))
        aux k n = [ xs | (xs,p) <- pares k, p == n]
 
raizenteramenor :: Int -> Int
raizenteramenor n = aux n 1
  where aux n k | k^2 > n   = k-1
                | otherwise = aux n (k+1)
  3. Responder
    javmarcha1 
    descomposiciones :: Int -> [[Int]]
descomposiciones x
  | x < 4     = []
  | otherwise = [[a,b,c,d] | a <- [1..x-3]
                           , b <- [1..x-3]
                           , c <- [1..x-3]
                           , d <- [1..x-3]
                           , a+b+c+d ==x
                           , and (map esCuadrado [a,b,c,d])]
 
 
esCuadrado :: Int -> Bool
esCuadrado x = (raizEntera x)^2 == x
 
raizEntera :: Int -> Int
raizEntera = floor . sqrt . fromIntegral

Escribe tu solución

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