sumas  :: Integer -> Integer -> [[Integer]]
esSuma :: Integer -> Integer -> Bool

sumas 16 3  ==  [[2,4,10],[2,6,8]]
sumas 18 4  ==  []

esSuma 16 3  ==  True
esSuma 18 4  ==  False
esSuma (10^5000) (10^7)  ==  True
esSuma (11^5000) (10^7)  ==  False

import Test.QuickCheck

sumas :: Integer -> Integer -> [[Integer]]
sumas n k = sumasLista n k [2,4..n]

-- (sumasLista n k xs) es la lista de las descomposiciones de n como k
-- elementos de xs (cada uno una vez como máximo). Por ejemplo,
--    sumasLista 16 3 [2,4..15]  ==  [[2,4,10],[2,6,8]]
--    sumasLista 18 4 [2,4..15]  ==  []
sumasLista :: Integer -> Integer -> [Integer] -> [[Integer]]
sumasLista _ _ [] = []
sumasLista n 1 xs
  | n `elem` xs = [[n]]
  | otherwise   = []
sumasLista n k (x:xs)
  | x > n     = []
  | otherwise = [x:ys | ys <- sumasLista (n-x) (k-1) xs] ++
                sumasLista n k xs

-- 1ª definición de esSuma
-- =======================

esSuma :: Integer -> Integer -> Bool
esSuma n k = not (null (sumas n k))

-- 2ª definición de esSuma
-- =======================

-- Se observan las siguientes propiedades:
-- 1. Si n es impar, no se puede escribir como suma de pares.
-- 2. El menor número que se puede escribir como suma de k sumandos
--    impares distintos es 2 * sum [1..k] y su descomposición es
--    [2,4..2*k] (es decir, map (*2) [1..k]).
-- 3. Si n es un número par mayor o igual que (2 * sum [1..k])
--    entonces se puede escribir como suma de k sumandos pares distintos;
--    en efecto,
--       x = 2 + 4 + ··· + 2*(k-1) + (x - (2 + 4 + ··· + 2*(k-1))

esSuma2 :: Integer -> Integer -> Bool
esSuma2 n k
  | odd n               = False
  | 2 * sum [1..k] <= n = True
  | otherwise           = False

-- 3ª definición de esSuma
-- =======================

esSuma3 :: Integer -> Integer -> Bool
esSuma3 n k
  | odd n            = False
  | k * (k + 1) <= n = True
  | otherwise        = False

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_equiv_esSuma :: Integer -> Integer -> Property
prop_equiv_esSuma n k =
  n > 0 && k > 0 ==>
  all (== (esSuma3 n k)) [esSuma n k, esSuma2 n k]

-- La comprobación es
--    λ> quickCheck prop_equiv_esSuma
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> esSuma 200 20
--    False
--    (6.12 secs, 3,079,059,560 bytes)
--    λ> esSuma2 200 20
--    False
--    (0.00 secs, 102,800 bytes)
--    λ> esSuma3 200 20
--    False
--    (0.01 secs, 102,760 bytes)
--
--    λ> esSuma2 (10^5000) (10^7)
--    True
--    (2.55 secs, 1,612,412,664 bytes)
--    λ> esSuma3 (10^5000) (10^7)
--    True
--    (0.03 secs, 109,200 bytes)