Menu Close

Descomposiciones en sumas de cuatro cuadrados

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

3 soluciones de “Descomposiciones en sumas de cuatro cuadrados

  1. 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. 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. 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

Leave a Reply

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