Descomposiciones en sumas de cuatro cuadrados

Definir la función

   descomposiciones :: Int -> [[Int]]

1	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

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

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 Comentarios

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

import Data.List (nub, permutations)

import Data.Array (listArray, (!))

descomposiciones n =

concat (map nub (map permutations (aux n)))

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

Responder

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)

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)

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

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

Descomposiciones en sumas de cuatro cuadrados

Soluciones

Pensamiento

3 Comentarios

Leave a Reply to adogargonCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to adogargonCancel reply

Entradas recientes

Buscar

Correo electrónico