Menu Close

Etiqueta: odd

Separación por posición

Definir la función

   particion :: [a] -> ([a],[a])

tal que (particion xs) es el par cuya primera componente son los elementos de xs en posiciones pares y su segunda componente son los restantes elementos. Por ejemplo,

   particion [3,5,6,2]    ==  ([3,6],[5,2])
   particion [3,5,6,2,7]  ==  ([3,6,7],[5,2])
   particion "particion"  ==  ("priin","atco")

Código de las alergias

Para la determinación de las alergia se utiliza los siguientes códigos para los alérgenos:

   Huevos ........   1
   Cacahuetes ....   2
   Mariscos ......   4
   Fresas ........   8
   Tomates .......  16
   Chocolate .....  32
   Polen .........  64
   Gatos ......... 128

Así, si Juan es alérgico a los cacahuetes y al chocolate, su puntuación es 34 (es decir, 2+32).

Los alérgenos se representan mediante el siguiente tipo de dato

  data Alergeno = Huevos
                | Cacahuetes
                | Mariscos
                | Fresas
                | Tomates
                | Chocolate
                | Polen
                | Gatos
    deriving (Enum, Eq, Show, Bounded)

Definir la función

   alergias :: Int -> [Alergeno]

tal que (alergias n) es la lista de alergias correspondiente a una puntuación n. Por ejemplo,

   λ> alergias 1
   [Huevos]
   λ> alergias 2
   [Cacahuetes]
   λ> alergias 3
   [Huevos,Cacahuetes]
   λ> alergias 5
   [Huevos,Mariscos]
   λ> alergias 255
   [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos]

Soluciones

Máximos locales en los números de descomposiciones de Goldbach

La conjetura de Goldbach afirma que todo número entero mayor que 2 se puede expresar como suma de dos primos.

Las descomposiciones de Goldbach son las maneras de expresar un número como suma de dos primos. Por ejemplo, el número 10 tiene dos descomposiciones de Goldbach ya que se puede expresar como la suma de 3 y 7 y la suma de 5 y 5.

Definir las funciones

   descomposicionesGoldbach :: Integer -> [(Integer,Integer)]
   numeroGoldbach :: Integer -> Integer
   tieneMaximoLocalGoldbach :: Integer -> Bool

tales que

  • (descomposicionesGoldbach n) es la lista de las descomposiciones de Goldbach del número n. Por ejemplo,
     descomposicionesGoldbach 5   ==  [(2,3)]
     descomposicionesGoldbach 10  ==  [(3,7),(5,5)]
     descomposicionesGoldbach 22  ==  [(3,19),(5,17),(11,11)]
     descomposicionesGoldbach 34  ==  [(3,31),(5,29),(11,23),(17,17)]
     descomposicionesGoldbach 35  ==  []
     descomposicionesGoldbach (9+10^9)  ==  [(2,1000000007)]
  • (numeroGolbach n) es el número de descomposiciones de Goldbach del número n. Por ejemplo,
     numeroGoldbach 5         ==  1
     numeroGoldbach 10        ==  2
     numeroGoldbach 22        ==  3
     numeroGoldbach 34        ==  4
     numeroGoldbach 35        ==  0
     numeroGoldbach (9+10^9)  ==  1
     maximum [numeroGoldbach n | n <- [2..3000]]  ==  128
  • (tieneMaximoLocalGoldbach n) se verifica si en n se alcanza un máximo local en el número de descomposiciones de Goldbach; es decir, los números n tales que el número de descomposiciones de Goldbach de n es mayor o igual que las de n-1 y las de n+1. Por ejemplo,
     λ> filter tieneMaximoLocalGoldbach [1..45]
     [1,2,4,5,6,7,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44]

En el ejemplo anterior se comprueba que en los múltiplos de 6 (es decir, en 6, 12, 18, 24, 30, 36 y 42), el número de descomposiciones de Goldbach alcanza un máximo local. Comprobar con QuickCheck que esta propiedad se cumple en general; es decir, para todo entero positivo n, el número de descomposiciones de Goldbach en 6n es un máximo local.

Soluciones

import Data.List (genericLength)
import Data.Numbers.Primes (primes, isPrime)
import Test.QuickCheck
 
-- Definiciones de descomposicionesGoldbach
-- ========================================
 
-- 1ª definición
descomposicionesGoldbach1 :: Integer -> [(Integer,Integer)]
descomposicionesGoldbach1 n =
  [(p,n-p) | p <- takeWhile (<= n `div` 2) primes
           , isPrime (n-p)]
 
-- 2ª definición
descomposicionesGoldbach2 :: Integer -> [(Integer,Integer)]
descomposicionesGoldbach2 n
  | odd n     = [(2,n-2) | isPrime (n-2)]
  | otherwise = [(p,n-p) | p <- takeWhile (<= n `div` 2) primes
                         , isPrime (n-p)]                               
 
-- Comparación de eficiencia 
--    λ> descomposicionesGoldbach1 (9+10^8)
--    [(2,100000007)]
--    (10.75 secs, 32,177,389,480 bytes)
--    λ> descomposicionesGoldbach2 (9+10^8)
--    [(2,100000007)]
--    (0.01 secs, 3,228,912 bytes)
 
-- En lo que sigue, usaremos la 2ª definición
descomposicionesGoldbach :: Integer -> [(Integer,Integer)]
descomposicionesGoldbach = descomposicionesGoldbach2
 
-- Definición de numeroGolbach
-- ===========================
 
numeroGoldbach :: Integer -> Integer
numeroGoldbach = genericLength . descomposicionesGoldbach
 
-- Definición de tieneMaximoLocalGoldbach
-- ======================================
 
tieneMaximoLocalGoldbach :: Integer -> Bool
tieneMaximoLocalGoldbach n =
  numeroGoldbach (n-1) <= x && x >= numeroGoldbach (n+1)
  where x = numeroGoldbach n
 
-- La propiedad es
prop_Goldbach :: Integer -> Property
prop_Goldbach n =
  n > 0 ==> tieneMaximoLocalGoldbach (6*n)
 
-- La comprobación es
--    λ> quickCheck prop_Goldbach
--    +++ OK, passed 100 tests.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Referencia

Pensamiento

Te abanicaras
con un madrigal que diga:
en amor el olvido pone la sal.

Antonio Machado

Números cíclopes

Un número cíclope es un número natural cuya representación binaria sólo tiene un cero en el centro. Por ejemplo,

     0      es ciclope porque su representación binaria es 0       
     1   no es ciclope porque su representación binaria es 1       
     5      es ciclope porque su representación binaria es 101     
     9   no es ciclope porque su representación binaria es 1001    
    10   no es ciclope porque su representación binaria es 1010    
    27      es ciclope porque su representación binaria es 11011   
    85   no es ciclope porque su representación binaria es 1010101 
   101   no es ciclope porque su representación binaria es 1100101 
   111   no es ciclope porque su representación binaria es 1101111 
   119      es ciclope porque su representación binaria es 1110111

Definir las funciones

   esCiclope       :: Integer -> Bool
   ciclopes        :: [Integer]
   graficaCiclopes :: Int -> IO ()

tales que

  • (esCiclope n) se verifica si el número natual n es cíclope. Por ejemplo,
      esCiclope 0    ==  True
      esCiclope 1    ==  False
      esCiclope 5    ==  True
      esCiclope 9    ==  False
      esCiclope 10   ==  False
      esCiclope 27   ==  True
      esCiclope 85   ==  False
      esCiclope 101  ==  False
      esCiclope 111  ==  False
      esCiclope 119  ==  True
  • ciclopes es la lista de los número cíclopes. Por ejemplo,
     λ> take 12 ciclopes
     [0,5,27,119,495,2015,8127,32639,130815,523775,2096127,8386559]
     λ> length (show (ciclopes !! (10^5)))
     60207
  • (graficaCiclopes n) dibuja la gráfica del último dígito de los n primeros números cíclopes. Por ejemplo, (graficaCiclopes n) dibuja

Soluciones

import Graphics.Gnuplot.Simple
 
-- 1ª solución
-- ===========
 
--    esCiclope 5  ==  True
--    esCiclope 6  ==  False
esCiclope :: Integer -> Bool
esCiclope n =
  esCiclopeBinario (decimalAbinario n)
 
--    decimalAbinario 4  ==  [0,0,1]
--    decimalAbinario 5  ==  [1,0,1]
--    decimalAbinario 6  ==  [0,1,1]
decimalAbinario :: Integer -> [Integer]
decimalAbinario 0 = [0]
decimalAbinario 1 = [1]
decimalAbinario n = r : decimalAbinario q
  where (q,r) = quotRem n 2
 
--    esCiclopeBinario [1,1,0,1,1]  ==  True
--    esCiclopeBinario [1,1,0,1]  ==  False
--    esCiclopeBinario [1,1,2,1,1]  ==  False
--    esCiclopeBinario [2,2,0,2,2]  ==  False
esCiclopeBinario :: [Integer] -> Bool
esCiclopeBinario xs =
  odd n && xs == ys ++ 0 : ys
  where n  = length xs
        m  = n `div` 2
        ys = replicate m 1
 
--    take 8 ciclopes  ==  [0,5,27,119,495,2015,8127,32639]
ciclopes :: [Integer]
ciclopes = filter esCiclope [0..]
 
-- 2ª solución
-- ===========
 
--    take 8 ciclopes2  ==  [0,5,27,119,495,2015,8127,32639]
ciclopes2 :: [Integer]
ciclopes2 =
  [binarioAdecimal (replicate n 1 ++ 0 : replicate n 1) | n <- [0..]]
 
--    binarioAdecimal [0,1,1]  ==  6
binarioAdecimal :: [Integer] -> Integer
binarioAdecimal [x]    = x
binarioAdecimal (x:xs) = x + 2 * binarioAdecimal xs
 
esCiclope2 :: Integer -> Bool
esCiclope2 n =
  n `pertenece` ciclopes2
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- 3ª solución
-- ===========
 
--    take 8 ciclopes3  ==  [0,5,27,119,495,2015,8127,32639]
ciclopes3 :: [Integer]
ciclopes3 =
  [sum [2^k | k <- [0..n-1]] + sum [2^k | k <- [n+1..n+n]] | n <- [0..]]
 
esCiclope3 :: Integer -> Bool
esCiclope3 n =
  n `pertenece` ciclopes3
 
-- 4ª solución
-- ===========
 
--    take 8 ciclopes3  ==  [0,5,27,119,495,2015,8127,32639]
ciclopes4 :: [Integer]
ciclopes4 =
  [2^(2*n+1) - 1 - 2^n | n <- [0..]]
 
esCiclope4 :: Integer -> Bool
esCiclope4 n =
  n `pertenece` ciclopes4
 
 
-- 5ª solución
-- ===========
 
--    take 8 ciclopes5  ==  [0,5,27,119,495,2015,8127,32639]
ciclopes5 :: [Integer]
ciclopes5 =
  [2*4^n - 1 - 2^n | n <- [0..]]
 
esCiclope5 :: Integer -> Bool
esCiclope5 n =
  n `pertenece` ciclopes5
 
-- 6ª solución
-- ===========
 
--    take 8 ciclopes6  ==  [0,5,27,119,495,2015,8127,32639]
ciclopes6 :: [Integer]
ciclopes6 =
  [2*x*x - 1 - x | x <- iterate (*2) 1]
 
esCiclope6 :: Integer -> Bool
esCiclope6 n =
  n `pertenece` ciclopes6
 
 
 
-- Comparación de eficiencia
-- =========================
 
--    λ> ciclopes !! 9
--    523775
--    (6.68 secs, 4,696,734,960 bytes)
--    λ> ciclopes2 !! 9
--    523775
--    (0.00 secs, 134,664 bytes)
--    λ> ciclopes3 !! 9
--    523775
--    (0.00 secs, 150,920 bytes)
--    λ> ciclopes4 !! 9
--    523775
--    (0.01 secs, 131,936 bytes)
--    λ> ciclopes5 !! 9
--    523775
--    (0.00 secs, 132,064 bytes)
--
--    λ> length (show (ciclopes2 !! (3*10^4)))
--    18063
--    (0.65 secs, 486,437,480 bytes)
--    λ> length (show (ciclopes3 !! (3*10^4)))
--    18063
--    (2.94 secs, 1,188,645,584 bytes)
--    λ> length (show (ciclopes4 !! (3*10^4)))
--    18063
--    (0.02 secs, 6,769,592 bytes)
--    λ> length (show (ciclopes5 !! (3*10^4)))
--    18063
--    (0.02 secs, 6,773,552 bytes)
--
--    λ> length (show (ciclopes2 !! (10^5)))
--    60207
--    (6.42 secs, 5,148,671,368 bytes)
--    λ> length (show (ciclopes4 !! (10^5)))
--    60207
--    (0.07 secs, 22,291,480 bytes)
--    λ> length (show (ciclopes5 !! (10^5)))
--    60207
--    (0.04 secs, 22,316,216 bytes)
--    
--    λ> length (show (ciclopes4 !! (5*10^6)))
--    3010301
--    (2.34 secs, 1,116,327,832 bytes)
--    λ> length (show (ciclopes5 !! (5*10^6)))
--    3010301
--    (2.39 secs, 1,099,177,056 bytes)
 
-- Definición de graficaCiclopes
-- =============================
 
graficaCiclopes :: Int -> IO ()
graficaCiclopes n =
  plotList [ Key Nothing
           -- , PNG "Numeros_ciclopes.png"
           ]
           [x `mod` 10 | x <- take n ciclopes5]

Pensamiento

¿Sabes cuando el agua suena,
si es agua de cumbre o valle,
de plaza, jardín o huerta?
Cantores, dejad
palmas y jaleo
para los demás.

Antonio Machado

Impares en filas del triángulo de Pascal

El triángulo de Pascal es un triángulo de números

         1
        1 1
       1 2 1
     1  3 3  1
    1 4  6  4 1
   1 5 10 10 5 1
  ...............

construido de la siguiente forma

  • la primera fila está formada por el número 1;
  • las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

Definir las funciones

   imparesPascal          :: [[Integer]]
   nImparesPascal         :: [Int]
   grafica_nImparesPascal :: Int -> IO ()

tales que

  • imparesPascal es la lista de los elementos impares en cada una de las filas del triángulo de Pascal. Por ejemplo,
     λ> take 8 imparesPascal
     [[1],[1,1],[1,1],[1,3,3,1],[1,1],[1,5,5,1],[1,15,15,1],[1,7,21,35,35,21,7,1]]
  • nImparesPascal es la lista del número de elementos impares en cada una de las filas del triángulo de Pascal. Por ejemplo,
     λ> take 32 nImparesPascal
     [1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32]
     λ> maximum (take (10^6) nImparesPascal3)
     524288
  • (grafica_nImparesPascal n) dibuja la gráfica de los n primeros términos de nImparesPascal. Por ejemplo, (grafica_nImparesPascal 50) dibuja

y (grafica_nImparesPascal 100) dibuja

Comprobar con QuickCheck que todos los elementos de nImparesPascal son potencias de dos.

Soluciones

import Data.List (transpose)
import Test.QuickCheck
import Graphics.Gnuplot.Simple
 
-- 1ª definición de imparesPascal
-- ==============================
 
imparesPascal :: [[Integer]]
imparesPascal =
  map (filter odd) pascal
 
-- pascal es la lista de las filas del triángulo de Pascal. Por ejemplo,
--    λ> take 7 pascal
--    [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]]
pascal :: [[Integer]]
pascal = [1] : map f pascal
  where f xs = zipWith (+) (0:xs) (xs++[0])
 
-- 2ª definición de imparesPascal
-- ==============================
 
imparesPascal2 :: [[Integer]]
imparesPascal2 =
  map (filter odd) pascal
 
pascal2 :: [[Integer]]
pascal2 = iterate f [1]
  where f xs = zipWith (+) (0:xs) (xs++[0])
 
-- 1ª definición de nImparesPascal
-- ===============================
 
nImparesPascal :: [Int]
nImparesPascal =
  map length imparesPascal
 
-- 2ª definición de nImparesPascal
-- ===============================
 
nImparesPascal2 :: [Int]
nImparesPascal2 =
  map (length . filter odd) imparesPascal
 
-- 3ª definición de nImparesPascal
-- ===============================
 
--    λ> take 32 nImparesPascal2
--    [1,2,
--     2,4,
--     2,4,4,8,
--     2,4,4,8,4,8,8,16,
--     2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32]
nImparesPascal3 :: [Int]
nImparesPascal3 = 1 : zs
  where zs = 2 : concat (transpose [zs, map (*2) zs])
 
-- Definición de grafica_nImparesPascal
-- =========================================
 
grafica_nImparesPascal :: Int -> IO ()
grafica_nImparesPascal n =
  plotListStyle
    [ Key Nothing
    , PNG ("Impares_en_filas_del_triangulo_de_Pascal_" ++ show n ++ ".png")
    ]
    (defaultStyle {plotType = LinesPoints})
    (take n nImparesPascal3)
 
-- Propiedad de nImparesPascal
-- ===========================
 
-- La propiedad es
prop_nImparesPascal :: Positive Int -> Bool
prop_nImparesPascal (Positive n) =
  esPotenciaDeDos (nImparesPascal3 !! n)
 
-- (esPotenciaDeDos n) se verifica si n es una potencia de dos. Por
-- ejemplo,
--    esPotenciaDeDos 16  ==  True
--    esPotenciaDeDos 18  ==  False
esPotenciaDeDos :: Int -> Bool
esPotenciaDeDos 1 = True
esPotenciaDeDos n = even n && esPotenciaDeDos (n `div` 2)
 
-- La comprobación es
--    λ> quickCheck prop_nImparesPascal
--    +++ OK, passed 100 tests.

Pensamiento

De lo que llaman los hombres
virtud, justicia y bondad,
una mitad es envidia,
y la otra no es caridad.

Antonio Machado

Tablas de operaciones binarias

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

   0 1 2    0 2 1
   1 2 0    1 0 2
   2 0 1    2 1 0
   Suma     Resta

Definir las funciones

   tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
   tablaSuma      :: Int -> [[Int]]
   tablaResta     :: Int -> [[Int]]
   tablaProducto  :: Int -> [[Int]]

tales que

  • (tablaOperacion f n) es la tabla de la operación f módulo n en [0..n-1]. Por ejemplo,
     tablaOperacion (+) 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
     tablaOperacion (-) 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
     tablaOperacion (-) 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
     tablaOperacion (\x y -> abs (x-y)) 3  ==  [[0,1,2],[1,0,1],[2,1,0]]
  • (tablaSuma n) es la tabla de la suma módulo n en [0..n-1]. Por ejemplo,
     tablaSuma 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
     tablaSuma 4  ==  [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
  • (tablaResta n) es la tabla de la resta módulo n en [0..n-1]. Por ejemplo,
     tablaResta 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
     tablaResta 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
  • (tablaProducto n) es la tabla del producto módulo n en [0..n-1]. Por ejemplo,
     tablaProducto 3  ==  [[0,0,0],[0,1,2],[0,2,1]]
     tablaProducto 4  ==  [[0,0,0,0],[0,1,2,3],[0,2,0,2],[0,3,2,1]]

Comprobar con QuickCheck, si parato entero positivo n de verificar las siguientes propiedades:

  • La suma, módulo n, de todos los números de (tablaSuma n) es 0.
  • La suma, módulo n, de todos los números de (tablaResta n) es 0.
  • La suma, módulo n, de todos los números de (tablaProducto n) es n/2 si n es el doble de un número impar y es 0, en caso contrario.

Soluciones

import Test.QuickCheck
 
tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
tablaOperacion f n =
  [[f i j `mod` n | j <- [0..n-1]] | i <- [0..n-1]]
 
tablaSuma :: Int -> [[Int]]
tablaSuma = tablaOperacion (+)
 
tablaResta :: Int -> [[Int]]
tablaResta = tablaOperacion (-)
 
tablaProducto :: Int -> [[Int]]
tablaProducto = tablaOperacion (*)
 
-- (sumaTabla xss) es la suma, módulo n, de los elementos de la tabla de
-- operación xss (donde n es el número de elementos de xss). Por
-- ejemplo, 
--    sumaTabla [[0,2,1],[1,1,2],[2,1,0]]  ==  1
sumaTabla :: [[Int]] -> Int
sumaTabla = sum . concat
 
-- La propiedad de la tabla de la suma es
prop_tablaSuma :: (Positive Int) -> Bool
prop_tablaSuma (Positive n) =
  sumaTabla (tablaSuma n) == 0
 
-- La comprobación es
--    λ> quickCheck prop_tablaSuma
--    +++ OK, passed 100 tests.
 
-- La propiedad de la tabla de la resta es
prop_tablaResta :: (Positive Int) -> Bool
prop_tablaResta (Positive n) =
  sumaTabla (tablaResta n) == 0
 
-- La comprobación es
--    λ> quickCheck prop_tablaResta
--    +++ OK, passed 100 tests.
 
-- La propiedad de la tabla del producto es
prop_tablaProducto :: (Positive Int) -> Bool
prop_tablaProducto (Positive n)
  | even n && odd (n `div` 2) = suma == n `div` 2
  | otherwise                 = suma == 0
  where suma = sumaTabla (tablaProducto n)

Pensamiento

¿Tu verdad? No, la Verdad,
y ven conmigo a buscarla.
La tuya guárdatela.

Antonio Machado

División equitativa

Definir la función

   divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

   divisionEquitativa [1,2,3,4,5,15]  ==  Just ([1,2,3,4,5],[15])
   divisionEquitativa [15,1,2,3,4,5]  ==  Just ([15],[1,2,3,4,5])
   divisionEquitativa [1,2,3,4,7,15]  ==  Nothing
   divisionEquitativa [1,2,3,4,15,5]  ==  Nothing

Soluciones

import Data.Maybe (isNothing, fromJust, listToMaybe)
import Data.List  (elemIndex, inits, tails)
 
-- 1ª solución
divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa1 xs = aux (particiones xs)
 where aux []                              = Nothing
       aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)
                        | otherwise        = aux ys                   
       particiones xs = [splitAt i xs | i <- [1..length xs-1]]
 
-- 2ª solución
divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa2 xs
  | 2 * b == suma = Just $ splitAt (length as + 1) xs
  | otherwise     = Nothing
  where suma        = sum xs
        (as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs
 
-- 3ª solución
divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa3 xs
  | odd n       = Nothing
  | isNothing p = Nothing
  | otherwise   = Just (splitAt (1 + fromJust p) xs)
  where n  = sum xs
        ys = scanl1 (+) xs
        p  = elemIndex (n `div` 2) ys
 
-- 4ª solución
divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa4 xs
  | odd (sum xs) = Nothing
  | otherwise    = aux [] xs
  where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs)
                          | sum as > sum bs  = Nothing
                          | otherwise        = aux (b:as) (bs')
 
-- 5ª solución
divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa5 xs =
  listToMaybe
    [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)
              , sum ys == sum zs ]

Listas alternadas

Una lista de números enteros se llama alternada si sus elementos son alternativamente par/impar o impar/par.

Definir la función

   alternada :: [Int] -> Bool

tal que (alternada xs) se verifica si xs es una lista alternada. Por ejemplo,

   alternada [1,2,3]     == True
   alternada [1,4,6,5]   == False
   alternada [1,4,3,5]   == False
   alternada [8,1,2,3,4] == True
   alternada [8,1,2,3]   == True
   alternada [8]         == True
   alternada [7]         == True

Soluciones

-- 1ª solución:
alternada1 :: [Int] -> Bool
alternada1 (x:y:xs)
  | even x    = odd y  && alternada1 (y:xs)
  | otherwise = even y && alternada1 (y:xs)
alternada1 _ = True
 
-- 2ª solución
alternada2 :: [Int] -> Bool
alternada2 xs = all odd (zipWith (+) xs (tail xs))

Sumas de posiciones pares e impares

Definir la función

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

tal que (sumasParesImpares) xs es el par formado por la suma de los elementos de xs en posiciones pares y por la suma de los elementos de xs en posiciones impares. Por ejemplo,

   sumasParesImpares []         ==  (0,0)
   sumasParesImpares [3]        ==  (3,0)
   sumasParesImpares [3,2]      ==  (3,2)
   sumasParesImpares [3,2,1]    ==  (4,2)
   sumasParesImpares [3,2,1,5]  ==  (4,7)
   sumasParesImpares [1..10^7]  ==  (25000000000000,25000005000000)

Soluciones

-- 1ª solución
sumasParesImpares1 :: [Integer] -> (Integer,Integer)
sumasParesImpares1 xs =
  (sum [x | (x,n) <- xns, even n],
   sum [x | (x,n) <- xns, odd n])
  where xns = zip xs [0..]
 
-- 2ª solución
sumasParesImpares2 :: [Integer] -> (Integer,Integer)
sumasParesImpares2 xs = aux xs (0,0)
  where aux (x1:x2:xs) (a,b) = aux xs (x1+a,x2+b)
        aux [x]        (a,b) = (x+a,b)
        aux []         (a,b) = (a,b)
 
-- Comparación de eficiencia
--    λ> sumasParesImpares1 [1..10^6]
--    (250000000000,250000500000)
--    (4.48 secs, 731,994,904 bytes)
--    λ> sumasParesImpares2 [1..10^6]
--    (250000000000,250000500000)
--    (1.78 secs, 235,663,400 bytes)

Paridad del número de divisores

Definir la función

   nDivisoresPar :: Integer -> Bool

tal que (nDivisoresPar n) se verifica si n tiene un número par de divisores. Por ejemplo,

   nDivisoresPar 12                     ==  True
   nDivisoresPar 16                     ==  False
   nDivisoresPar (product [1..2*10^4])  ==  True

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primeFactors)
 
-- 1ª definición
-- =============
 
nDivisoresPar1 :: Integer -> Bool
nDivisoresPar1 = even . length . divisores
 
-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 12  ==  [1,2,3,4,6,12]
--    divisores 16  ==  [1,2,4,8,16]
divisores :: Integer -> [Integer]
divisores n =
    [x | x <- [1..n], n `mod` x == 0]
 
-- 2ª definición
-- =============
 
nDivisoresPar2 :: Integer -> Bool
nDivisoresPar2 n =
    any odd (map length (group (primeFactors n)))
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nDivisoresPar1 (10^7)
--    True
--    (14.18 secs, 2,078,736,992 bytes)
--    λ> nDivisoresPar2 (10^7)
--    True
--    (0.01 secs, 0 bytes)
--
--    λ> nDivisoresPar2 (product [1..2*10^4])
--    True
--    (2.30 secs, 1,003,013,112 bytes)

Solución en Maxima

/* concat(xs) es la lista obtenida concatenado los elementos de xss. Por
   ejemplo,
      concat([[1,3],[2,4],[5,7]])  ==  [1, 3, 2, 4, 5, 7]             */
concat (xs) := block ([r:[]],
  for x in reverse (xs) do r : append (x,r),
  r)$
 
nDivisoresPares (n) := block(
  [xs : concat (map (rest, ifactors (n))), p : false],
  for x in xs do p: oddp (x) or p,
  p)$