Menu Close

Etiqueta: span

Eliminación de las ocurrencias aisladas.

Definir la función

   eliminaAisladas :: Eq a => a -> [a] -> [a]

tal que (eliminaAisladas x ys) es la lista obtenida eliminando en ys las ocurrencias aisladas de x (es decir, aquellas ocurrencias de x tales que su elemento anterior y posterior son distintos de x). Por ejemplo,

   eliminaAisladas 'X' ""                  == ""
   eliminaAisladas 'X' "X"                 == ""
   eliminaAisladas 'X' "XX"                == "XX"
   eliminaAisladas 'X' "XXX"               == "XXX"
   eliminaAisladas 'X' "abcd"              == "abcd"
   eliminaAisladas 'X' "Xabcd"             == "abcd"
   eliminaAisladas 'X' "XXabcd"            == "XXabcd"
   eliminaAisladas 'X' "XXXabcd"           == "XXXabcd"
   eliminaAisladas 'X' "abcdX"             == "abcd"
   eliminaAisladas 'X' "abcdXX"            == "abcdXX"
   eliminaAisladas 'X' "abcdXXX"           == "abcdXXX"
   eliminaAisladas 'X' "abXcd"             == "abcd"
   eliminaAisladas 'X' "abXXcd"            == "abXXcd"
   eliminaAisladas 'X' "abXXXcd"           == "abXXXcd"
   eliminaAisladas 'X' "XabXcdX"           == "abcd"
   eliminaAisladas 'X' "XXabXXcdXX"        == "XXabXXcdXX"
   eliminaAisladas 'X' "XXXabXXXcdXXX"     == "XXXabXXXcdXXX"
   eliminaAisladas 'X' "XabXXcdXeXXXfXx"   == "abXXcdeXXXfx"

Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

  • Inicialmente todas las puertas están cerradas.
  • El primer camarero cambia de estado las puertas de todas las habitaciones.
  • El segundo cambia de estado de las puertas de las habitaciones pares.
  • El tercero cambia de estado todas las puertas que son múltiplos de 3.
  • El cuarto cambia de estado todas las puertas que son múltiplos de 4
  • Así hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

   Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
   Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
   Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
   Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
   Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
   Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
   Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

Los estados de las puertas se representan por el siguiente tipo de datos

   data Estado = Abierta | Cerrada deriving Show

Definir la función

   final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

   ghci> final 5
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
   ghci> final 7
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Soluciones

 
-- 1ª solución
-- ===========
 
data Estado = Abierta | Cerrada 
  deriving (Eq, Show)
 
cambia Abierta = Cerrada
cambia Cerrada = Abierta
 
-- (inicial n) es el estado inicial para el problema de las n
-- habitaciones. Por ejemplo,
--    inicial 5  ==  [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]
inicial :: Int -> [Estado]
inicial n = replicate n Cerrada
 
-- (pase k es) es la lista de los estados de las puertas después de pasar el
-- camarero k que las encuentra en los estados es. Por ejemplo,
--    ghci> pase 1 (inicial 5)
--    [Abierta,Abierta,Abierta,Abierta,Abierta]
--    ghci> pase 2 it
--    [Abierta,Cerrada,Abierta,Cerrada,Abierta]
--    ghci> pase 3 it
--    [Abierta,Cerrada,Cerrada,Cerrada,Abierta]
--    ghci> pase 4 it
--    [Abierta,Cerrada,Cerrada,Abierta,Abierta]
--    ghci> pase 5 it
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
pase :: [Estado] -> Int -> [Estado] 
pase es k = zipWith cambiaK  es [1..] 
  where cambiaK e n | n `mod` k == 0 = cambia e
                    | otherwise      = e
 
final :: Int -> [Estado]
final n = aux [1..n] (inicial n) 
  where aux []     es = es  
        aux (k:ks) es = aux ks (pase es k)
 
-- 2ª solución
-- ===========
 
final2 :: Int -> [Estado]
final2 n = foldl pase (inicial n) [1..n] 
 
-- 3ª solución
-- =============
 
final3 :: Int -> [Estado]
final3 n = map f [1..n]
  where f x | even (length (divisores x)) = Cerrada
            | otherwise                   = Abierta
 
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `mod` x == 0]
 
-- 4ª solución
-- ===========
 
-- En primer lugar, vamos a determinar la lista de las posiciones
-- (comenzando a contar en 1) de las puertas que quedan abierta en el
-- problema de las n puertas. 
posicionesAbiertas :: Int -> [Int]
posicionesAbiertas n = 
  [x | (x,y) <- zip [1..] (final n), y == Abierta]
 
-- Al calcularlas,
--    ghci> posicionesAbiertas 200
--    [1,4,9,16,25,36,49,64,81,100,121,144,169,196]
-- Se observa las que quedan abiertas son las que sus posiciones son
-- cuadrados perfectos. Usando esta observación se construye la
-- siguiente definición
 
final4 :: Int -> [Estado]
final4 n = aux [1..n] [k*k | k <- [1..]] 
  where aux (x:xs) (y:ys) | x == y  =  Abierta : aux xs ys
        aux (x:xs) ys               =  Cerrada : aux xs ys
        aux []     _                =  []
 
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------
 
--    ghci> last (final 1000)
--    Cerrada
--    (0.23 secs, 218727400 bytes)
--    ghci> last (final 2000)
--    Cerrada
--    (1.78 secs, 868883080 bytes)
--    ghci> last (final2 1000)
--    Cerrada
--    (0.08 secs, 218729392 bytes)
--    ghci> last (final2 2000)
--    Cerrada
--    (1.77 secs, 868948600 bytes)
--    ghci> last (final3 1000)
--    Cerrada
--    (0.01 secs, 1029256 bytes)
--    ghci> last (final3 2000)
--    Cerrada
--    (0.01 secs, 2121984 bytes)
--    ghci> last (final4 1000)
--    Cerrada
--    (0.01 secs, 1029328 bytes)
--    ghci> last (final4 2000)
--    Cerrada
--    (0.01 secs, 1578504 bytes)
--    ghci> last (final3 10000)
--    Abierta
--    (0.01 secs, 4670104 bytes)
--    ghci> last (final3 100000)
--    Cerrada
--    (0.09 secs, 38717032 bytes)
--    ghci> last (final3 1000000)
--    Abierta
--    (1.27 secs, 377100832 bytes)
--    ghci> last (final4 1000000)
--    Abierta
--    (1.41 secs, 273292448 bytes)

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>

Números como sumas de primos consecutivos

En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas

   41 =  2 +  3 +  5 + 7 + 11 + 13
   41 = 11 + 13 + 17

el 240 se puede escribir de tres formas

   240 =  17 +  19 + 23 + 29 + 31 + 37 + 41 + 43
   240 =  53 +  59 + 61 + 67
   240 = 113 + 127

y el 311 se puede escribir de 4 formas

   311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
   311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
   311 =  53 +  59 +  61 + 67 + 71
   311 = 101 + 103 + 107

Definir la función

   sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,

   ghci> sumas 41
   [[2,3,5,7,11,13],[11,13,17]]
   ghci> sumas 240
   [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]
   ghci> sumas 311
   [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
    [53,59,61,67,71],[101,103,107]]
   ghci> maximum [length (sumas n) | n <- [1..600]]
   4

Soluciones

import Data.Numbers.Primes (primes)
 
sumas :: Integer -> [[Integer]]
sumas x = [ys | n <- takeWhile (< x) primes, 
                let ys = sumaDesde x n,
                not (null ys)]
 
-- (sumaDesde x n) es la lista de al menos dos números primos
-- consecutivos a partir del número primo n cuya suma es x, si existen y
-- la lista vacía en caso contrario. Por ejemplo,
--    sumaDesde 15 3  ==  [3,5,7]
--    sumaDesde  7 3  ==  []
sumaDesde :: Integer -> Integer -> [Integer]
sumaDesde x n | x == y    = take (1 + length us) ys
              | otherwise = []
    where ys       = dropWhile (<n) primes
          (us,y:_) = span (<x) (scanl1 (+) ys)

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>

Pensamiento

“El desarrollo de las matemáticas hacia una mayor precisión ha llevado, como es bien sabido, a la formalización de grandes partes de las mismas, de modo que se puede probar cualquier teorema usando nada más que unas pocas reglas mecánicas.”

Kurt Gödel.

Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

  • Inicialmente todas las puertas están cerradas.
  • El primer camarero cambia de estado las puertas de todas las habitaciones.
  • El segundo cambia de estado de las puertas de las habitaciones pares.
  • El tercero cambia de estado todas las puertas que son múltiplos de 3.
  • El cuarto cambia de estado todas las puertas que son múltiplos de 4
  • Así hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

   Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
   Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
   Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
   Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
   Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
   Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
   Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

Los estados de las puertas se representan por el siguiente tipo de datos

   data Estado = Abierta | Cerrada deriving Show

Definir la función

   final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

   ghci> final 5
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
   ghci> final 7
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Soluciones

-- 1ª solución
-- ===========
 
data Estado = Abierta | Cerrada 
              deriving (Eq, Show)
 
cambia Abierta = Cerrada
cambia Cerrada = Abierta
 
-- (inicial n) es el estado inicial para el problema de las n
-- habitaciones. Por ejemplo,
--    inicial 5  ==  [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]
inicial :: Int -> [Estado]
inicial n = replicate n Cerrada
 
-- (pase k es) es la lista de los estados de las puertas después de pasar el
-- camarero k que las encuentra en los estados es. Por ejemplo,
--    ghci> pase 1 (inicial 5)
--    [Abierta,Abierta,Abierta,Abierta,Abierta]
--    ghci> pase 2 it
--    [Abierta,Cerrada,Abierta,Cerrada,Abierta]
--    ghci> pase 3 it
--    [Abierta,Cerrada,Cerrada,Cerrada,Abierta]
--    ghci> pase 4 it
--    [Abierta,Cerrada,Cerrada,Abierta,Abierta]
--    ghci> pase 5 it
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
pase :: [Estado] -> Int -> [Estado] 
pase es k = zipWith cambiaK  es[1..] 
  where cambiaK e n | n `mod` k == 0 = cambia e
                    | otherwise      = e
 
final :: Int -> [Estado]
final n = aux [1..n] (inicial n) 
  where aux []     es = es  
        aux (k:ks) es = aux ks (pase es k)
 
-- 2ª solución
-- ===========
 
final2 :: Int -> [Estado]
final2 n = foldl pase (inicial n) [1..n] 
 
-- 3ª solución
-- =============
 
final3 :: Int -> [Estado]
final3 n = map f [1..n]
  where f x | even (length (divisores x)) = Cerrada
            | otherwise                   = Abierta
 
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `mod` x == 0]
 
-- 4ª solución
-- ===========
 
-- En primer lugar, vamos a determinar la lista de las posiciones
-- (comenzando a contar en 1) de las puertas que quedan abierta en el
-- problema de las n puertas. 
posicionesAbiertas :: Int -> [Int]
posicionesAbiertas n = 
  [x | (x,y) <- zip [1..] (final n), y == Abierta]
 
-- Al calcularlas,
--    ghci> posicionesAbiertas 200
--    [1,4,9,16,25,36,49,64,81,100,121,144,169,196]
-- Se observa las que quedan abiertas son las que sus posiciones son
-- cuadrados perfectos. Usando esta observación se construye la
-- siguiente definición
 
final4 :: Int -> [Estado]
final4 n = aux [1..n] [k*k | k <- [1..]] 
  where aux (x:xs) (y:ys) | x == y  =  Abierta : aux xs ys
        aux (x:xs) ys               =  Cerrada : aux xs ys
        aux []     _                =  []
 
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------
 
--    ghci> last (final 1000)
--    Cerrada
--    (0.23 secs, 218727400 bytes)
--    ghci> last (final 2000)
--    Cerrada
--    (1.78 secs, 868883080 bytes)
--    ghci> last (final2 1000)
--    Cerrada
--    (0.08 secs, 218729392 bytes)
--    ghci> last (final2 2000)
--    Cerrada
--    (1.77 secs, 868948600 bytes)
--    ghci> last (final3 1000)
--    Cerrada
--    (0.01 secs, 1029256 bytes)
--    ghci> last (final3 2000)
--    Cerrada
--    (0.01 secs, 2121984 bytes)
--    ghci> last (final4 1000)
--    Cerrada
--    (0.01 secs, 1029328 bytes)
--    ghci> last (final4 2000)
--    Cerrada
--    (0.01 secs, 1578504 bytes)
--    ghci> last (final3 10000)
--    Abierta
--    (0.01 secs, 4670104 bytes)
--    ghci> last (final3 100000)
--    Cerrada
--    (0.09 secs, 38717032 bytes)
--    ghci> last (final3 1000000)
--    Abierta
--    (1.27 secs, 377100832 bytes)
--    ghci> last (final4 1000000)
--    Abierta
--    (1.41 secs, 273292448 bytes)

Pensamiento

… cuánto exilio en la presencia cabe.

Antonio Machado

El 2019 es apocalíptico

Un número natural n es apocalíptico si 2^n contiene la secuencia 666. Por ejemplo, 157 es apocalíptico porque 2^157 es 182687704666362864775460604089535377456991567872 que contiene la secuencia 666.

Definir las funciones

   esApocaliptico       :: Integer -> Bool
   apocalipticos        :: [Integer]
   posicionApocaliptica :: Integer -> Maybe Int

tales que

  • (esApocaliptico n) se verifica si n es un número apocalíptico. Por ejemplo,
     esApocaliptico 157   ==  True
     esApocaliptico 2019  ==  True
     esApocaliptico 2018  ==  False
  • apocalipticos es la lista de los números apocalípticos. Por ejemplo,
     take 9 apocalipticos  ==  [157,192,218,220,222,224,226,243,245]
     apocalipticos !! 450  ==  2019
  • (posicionApocalitica n) es justo la posición de n en la sucesión de números apocalípticos, si n es apocalíptico o Nothing, en caso contrario. Por ejemplo,
     posicionApocaliptica 157   ==  Just 0
     posicionApocaliptica 2019  ==  Just 450
     posicionApocaliptica 2018  ==  Nothing

Soluciones

import Data.List (isInfixOf, elemIndex)
 
-- 1ª definición de esApocaliptico
esApocaliptico :: Integer -> Bool
esApocaliptico n = "666" `isInfixOf` show (2^n)
 
-- 2ª definición de esApocaliptico
esApocaliptico2 :: Integer -> Bool
esApocaliptico2 = isInfixOf "666" . show . (2^)
 
-- 1ª definición de apocalipticos
apocalipticos :: [Integer]
apocalipticos = [n | n <- [1..], esApocaliptico n]
 
-- 2ª definición de apocalipticos
apocalipticos2 :: [Integer]
apocalipticos2 = filter esApocaliptico [1..]
 
-- 1ª definición de posicionApocaliptica
posicionApocaliptica :: Integer -> Maybe Int
posicionApocaliptica n
  | y == n    = Just (length xs)
  | otherwise = Nothing
  where (xs,y:_) = span (<n) apocalipticos
 
-- 2ª definición de posicionApocaliptica
posicionApocaliptica2 :: Integer -> Maybe Int
posicionApocaliptica2 n
  | esApocaliptico n = elemIndex n apocalipticos
  | otherwise        = Nothing

Pensamiento

A vosotros no os importe pensar lo que habéis leído ochenta veces y oído
quinientas, porque no es lo mismo pensar que haber leído.

Antonio Machado

Notas de evaluación acumulada

La evaluación acumulada, las notas se calculan recursivamente con la siguiente función

   N(1) = E(1)
   N(k) = máximo(E(k), 0.4*N(k-1)+0.6*E(k))

donde E(k) es la nota del examen k. Por ejemplo, si las notas de los exámenes son [3,7,6,3] entonces las acumuladas son [3.0,7.0,6.4,4.4]

Las notas e los exámenes se encuentran en ficheros CSV con los valores separados por comas. Cada línea representa la nota de un alumno, el primer valor es el identificador del alumno y los restantes son sus notas. Por ejemplo, el contenido de examenes.csv es

   juaruigar,3,7,9,3
   evadialop,3,6,7,4
   carrodmes,0,9,8,7

Definir las funciones

   acumuladas      :: [Double] -> [Double]
   notasAcumuladas :: FilePath -> FilePath -> IO ()

tales que

  • (acumuladas xs) es la lista de las notas acumuladas (redondeadas con un decimal) de los notas de los exámenes xs. Por ejemplo,
     acumuladas [2,5]      ==  [2.0,5.0]
     acumuladas [5,2]      ==  [5.0,3.2]
     acumuladas [3,7,6,3]  ==  [3.0,7.0,6.4,4.4]
     acumuladas [3,6,7,3]  ==  [3.0,6.0,7.0,4.6]
  • (notasAcumuladas f1 f2) que escriba en el fichero f2 las notas acumuladas correspondientes a las notas de los exámenes del fichero f1. Por ejemplo, al evaluar
     notasAcumuladas "examenes.csv" "acumuladas.csv"

escribe en el fichero acumuladas.csv

     juaruigar,3.0,7.0,9.0,5.4
     evadialop,3.0,6.0,7.0,5.2
     carrodmes,0.0,9.0,8.4,7.6

Soluciones

import Text.CSV
import Data.Either
 
-- Definicioń de acumuladas
-- ========================
 
acumuladas :: [Double] -> [Double]
acumuladas = reverse . aux . reverse
  where aux []     = []
        aux [x]    = [x]
        aux (x:xs) = conUnDecimal (max x (0.6*x+0.4*y)) : y : ys 
          where (y:ys) = aux xs
 
--    conUnDecimal 7.26  ==  7.3
--    conUnDecimal 7.24  ==  7.2
conUnDecimal :: Double -> Double
conUnDecimal x = fromIntegral (round (10*x)) / 10
 
-- 1ª definición de notasAcumuladas
-- ================================
 
notasAcumuladas :: FilePath -> FilePath -> IO ()
notasAcumuladas f1 f2 = do
  cs <- readFile f1
  writeFile f2 (unlines (map ( acumuladaACadena
                             . notaAAcumuladas
                             . listaANota
                             . cadenaALista
                             )
                             (contenidoALineasDeNotas cs)))
 
--   λ> contenidoALineasDeNotas "juaruigar,3,7,6,3\nevadialop,3,6,7,3\n\n  \n"
--   ["juaruigar,3,7,6,3","evadialop,3,6,7,3"]
contenidoALineasDeNotas :: String -> [String]
contenidoALineasDeNotas = filter esLineaDeNotas . lines
  where esLineaDeNotas = elem ','
 
--    cadenaALista "a,b c,d"            ==  ["a","b c","d"]
--    cadenaALista "juaruigar,3,7,6,3"  ==  ["juaruigar","3","7","6","3"]
cadenaALista :: String -> [String]
cadenaALista cs
  | tieneComas cs = d : cadenaALista ds
  | otherwise     = [cs]
  where (d,_:ds)   = span (/=',') cs
        tieneComas = elem ','
 
--    λ> listaANota ["juaruigar","3","7","6","3"]
--    ("juaruigar",[3.0,7.0,6.0,3.0])
listaANota :: [String] -> (String,[Double])
listaANota (x:xs) = (x,map read xs)
 
--   λ> notaAAcumuladas ("juaruigar",[3.0,7.0,6.0,3.0])
--   ("juaruigar",[3.0,7.0,6.4,4.4])
notaAAcumuladas :: (String,[Double]) -> (String,[Double])
notaAAcumuladas (x,xs) = (x, acumuladas xs)
 
--    λ> acumuladaACadena ("juaruigar",[3.0,7.0,6.4,4.4])
--    "juaruigar,3.0,7.0,6.4,4.4"
acumuladaACadena :: (String,[Double]) -> String
acumuladaACadena (x,xs) =
  x ++ "," ++ tail (init (show xs))
 
-- 2ª definición de notasAcumuladas
-- ================================
 
notasAcumuladas2 :: FilePath -> FilePath -> IO ()
notasAcumuladas2 f1 f2 = do
  cs <- readFile f1
  let (Right csv) = parseCSV f1 cs
  let notas = [xs | xs <- csv, length xs > 1]
  writeFile f2 (unlines (map ( acumuladaACadena
                             . notaAAcumuladas
                             . listaANota
                             )
                             notas))

Números que no son cuadrados

Definir las funciones

   noCuadrados :: [Integer]
   graficaNoCuadrados :: Integer -> IO ()

tales que

  • noCuadrados es la lista de los números naturales que no son cuadrados. Por ejemplo,
     λ> take 25 noCuadrados
     [2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30]
  • (graficaNoCuadrados n) dibuja las diferencias entre los n primeros elementos de noCuadrados y sus posiciones. Por ejemplo, (graficaNoCuadrados 300) dibuja
    Numeros_que_no_son_cuadrados_300
    (graficaNoCuadrados 3000) dibuja
    Numeros_que_no_son_cuadrados_3000
    (graficaNoCuadrados 30000) dibuja
    Numeros_que_no_son_cuadrados_30000

Comprobar con QuickCheck que el término de noCuadrados en la posición n-1 es (n + floor(1/2 + sqrt(n))).

Soluciones

import Data.List (genericIndex)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
noCuadrados :: [Integer]
noCuadrados = aux [0..] cuadrados
  where aux xs (y:ys) = as ++ aux bs ys
          where (as,_:bs) = span (<y) xs
 
cuadrados :: [Integer]
cuadrados = [x^2 | x <- [0..]]
 
-- 2ª definición
-- =============
 
noCuadrados2 :: [Integer]
noCuadrados2 = aux 2 [1..]
  where aux n (_:xs) = ys ++ aux (n+2) zs
          where (ys,zs) = splitAt n xs
 
-- Definición de graficaNoCuadrados
-- ================================
 
graficaNoCuadrados :: Integer -> IO ()
graficaNoCuadrados n =
  plotList [ Key Nothing
           , PNG ("Numeros_que_no_son_cuadrados_" ++ show n ++ ".png")
           ]
           (zipWith (-) noCuadrados [0..n-1])
 
-- La propiedad es
prop_noCuadrados :: Positive Integer -> Bool
prop_noCuadrados (Positive n) =
  noCuadrados `genericIndex` (n-1) ==
  n + floor (1/2 + sqrt (fromIntegral n))
 
-- La comprobación es
--    λ> quickCheck prop_noCuadrados
--    +++ OK, passed 100 tests.

Exponentes de Hamming

Los números de Hamming forman una sucesión estrictamente creciente de números que cumplen las siguientes condiciones:

  • El número 1 está en la sucesión.
  • Si x está en la sucesión, entonces 2x, 3x y 5x también están.
  • Ningún otro número está en la sucesión.

Los primeros números de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, …

Los exponentes de un número de Hamming n es una terna (x,y,z) tal que n = 2^x*3^y*5^z. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z.

Definir la sucesión

   sucExponentesHamming :: [(Int,Int,Int)]

cuyos elementos son los exponentes de los números de Hamming. Por ejemplo,

   λ> take 21 sucExponentesHamming
   [(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),
    (0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),
    (3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]
   λ> sucExponentesHamming !! (5*10^5)
   (74,82,7)

Soluciones

import Data.Numbers.Primes (primeFactors)
 
-- 1ª solución
-- ===========
 
sucExponentesHamming :: [(Int,Int,Int)]
sucExponentesHamming = map exponentes hamming
 
-- (exponentes n) es la terna de exponentes del número de Hamming n. Por
-- ejemplo, 
--    exponentes 600  ==  (3,1,2)
exponentes :: Integer -> (Int,Int,Int)
exponentes x = (length as, length cs, length ds)
  where xs = primeFactors x
        (as,bs) = span (==2) xs
        (cs,ds) = span (==3) bs
 
-- hamming es la sucesión de los números de Hamming. Por ejemplo,
--    λ> take 21 hamming
--    [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40]
hamming :: [Integer]
hamming = 1 : mezcla3 [2*i | i <- hamming]  
                      [3*i | i <- hamming]  
                      [5*i | i <- hamming]  
 
-- mezcla3 xs ys zs es la lista obtenida mezclando las listas ordenadas
-- xs, ys y zs y eliminando los elementos duplicados. Por ejemplo, 
--    mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]  ==  [2,3,4,5,6,8,9,10,12]
mezcla3 :: Ord a => [a] -> [a] -> [a] -> [a]
mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)  
 
-- mezcla2 xs ys zs es la lista obtenida mezclando las listas ordenadas
-- xs e ys y eliminando los elementos duplicados. Por ejemplo, 
--    mezcla2 [2,4,6,8,10,12] [3,6,9,12]  ==  [2,3,4,6,8,9,10,12]
mezcla2 :: Ord a => [a] -> [a] -> [a] 
mezcla2 p@(x:xs) q@(y:ys) | x < y     = x:mezcla2 xs q
                          | x > y     = y:mezcla2 p  ys  
                          | otherwise = x:mezcla2 xs ys
mezcla2 []       ys                   = ys
mezcla2 xs       []                   = xs
 
-- 2ª solución
-- ===========
 
sucExponentesHamming2 :: [(Int,Int,Int)]
sucExponentesHamming2 = map exponentes2 hamming
 
exponentes2 :: Integer -> (Int,Int,Int)
exponentes2 = aux (0,0,0)
  where aux (a,b,c) 1 = (a,b,c)
        aux (a,b,c) x | mod x 2 == 0 = aux (a+1,b,c) (div x 2)
                      | mod x 3 == 0 = aux (a,b+1,c) (div x 3)
                      | otherwise    = aux (a,b,c+1) (div x 5)
 
-- 3ª solución
-- ===========
 
sucExponentesHamming3 :: [(Int,Int,Int)]
sucExponentesHamming3 = map exponentes3 hamming
 
exponentes3 :: Integer -> (Int,Int,Int)
exponentes3 1 = (0,0,0)
exponentes3 x
  | x `mod` 2 == 0 = suma (1,0,0) (descomposicion (x `div` 2))
  | x `mod` 3 == 0 = suma (0,1,0) (descomposicion (x `div` 3))
  | otherwise      = suma (0,0,1) (descomposicion (x `div` 5))
  where suma (x,y,z) (a,b,c) = (x+a,y+b,z+c)
 
-- 4ª solución
-- ===========
 
type Terna = (Int,Int,Int)
 
sucExponentesHamming4 :: [Terna]
sucExponentesHamming4 =
  (0,0,0) : mezclaT3 [(x+1,y,z) | (x,y,z) <- sucExponentesHamming4]
                     [(x,y+1,z) | (x,y,z) <- sucExponentesHamming4]
                     [(x,y,z+1) | (x,y,z) <- sucExponentesHamming4]
 
mezclaT3 :: [Terna] -> [Terna] -> [Terna] -> [Terna]
mezclaT3 t1 t2 t3 = mezclaT2 t1 (mezclaT2 t2 t3)
 
mezclaT2 :: [Terna] -> [Terna] -> [Terna]
mezclaT2 ts1@((i,j,k):xs) ts2@((a,b,c):ys)
  | x < y     = (i,j,k) : mezclaT2 xs ts2
  | x > y     = (a,b,c) : mezclaT2 ts1 ys
  | otherwise = (i,j,k) : mezclaT2 xs ys
  where x = 2^i*3^j*5^k
        y = 2^a*3^b*5^c

Sucesión de raíces enteras de los números primos

Definir las siguientes funciones

   raicesEnterasPrimos :: [Integer]
   posiciones :: Integer -> (Int,Int)
   frecuencia :: Integer -> Int
   grafica_raicesEnterasPrimos :: Int -> IO ()
   grafica_posicionesIniciales :: Integer -> IO ()
   grafica_frecuencias :: Integer -> IO ()

tales que

  • raicesEnterasPrimos es la sucesión de las raíces enteras (por defecto) de los números primos. Por ejemplo,
     λ> take 20 raicesEnterasPrimos
     [1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8]
     λ> raicesEnterasPrimos !! 2500000
     6415
  • (posiciones x) es el par formado por la menor y la mayor posición de x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
      posiciones 2     ==  (2,3)
      posiciones 4     ==  (6,8)
      posiciones 2017  ==  (287671,287931)
      posiciones 2018  ==  (287932,288208)
  • (frecuencia x) es el número de veces que aparece x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
      frecuencia 2     ==  2
      frecuencia 4     ==  3
      frecuencia 2017  ==  261
      frecuencia 2018  ==  277
  • (grafica_raicesEnterasPrimos n) dibuja la gráfica de los n primeros términos de la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_raicesEnterasPrimos 200) dibuja
    Sucesion_de_raices_enteras_de_primos_1
  • (grafica_posicionesIniciales n) dibuja la gráfica de las menores posiciones de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_posicionesIniciales 200) dibuja
    Sucesion_de_raices_enteras_de_primos_2
  • (grafica_frecuencia n) dibuja la gráfica de las frecuencia de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_frecuencia 200) dibuja
    Sucesion_de_raices_enteras_de_primos_3

Soluciones

import Data.Numbers.Primes (primes)
import Graphics.Gnuplot.Simple
 
raicesEnterasPrimos :: [Integer]
raicesEnterasPrimos = map raizEntera primes                       
 
raizEntera :: Integer -> Integer
raizEntera = floor . sqrt . fromIntegral
 
posiciones :: Integer -> (Int,Int)
posiciones x = (n,n+m-1)
  where (as,bs) = span (<x) raicesEnterasPrimos
        cs      = takeWhile (==x) bs 
        n       = length as
        m       = length cs
 
frecuencia :: Integer -> Int
frecuencia x =
  ( length
  . takeWhile (==x)
  . dropWhile (<x)
  ) raicesEnterasPrimos
 
grafica_raicesEnterasPrimos :: Int -> IO ()
grafica_raicesEnterasPrimos n = 
  plotList [ Title "Raices enteras de primos"
           , XLabel "Posiciones de numeros primos"
           , YLabel "Raiz entera del n-esimo primo"
           , Key Nothing
           , PNG "Sucesion_de_raices_enteras_de_primos_1.png"
           ]
           (take n raicesEnterasPrimos)
 
grafica_posicionesIniciales :: Integer -> IO ()
grafica_posicionesIniciales n = 
  plotList [ Title "Posiciones iniciales en raices enteras de primos"
           , XLabel "Numeros enteros"
           , YLabel "Posicion del numero n en las raices enteras de primos"
           , Key Nothing
           , PNG "Sucesion_de_raices_enteras_de_primos_2.png"
           ]
           (map (fst . posiciones) [1..n])
 
grafica_frecuencias :: Integer -> IO ()
grafica_frecuencias n = 
  plotList [ Title "Frecuencias en raices enteras de primos"
           , XLabel "Numeros enteros n"
           , YLabel "Frecuencia del numero n en las raices enteras de primos"
           , Key Nothing
           , PNG "Sucesion_de_raices_enteras_de_primos_3.png"
           ]
           (map frecuencia [1..n])

Números como sumas de primos consecutivos

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

   311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
   311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
   311 =  53 +  59 +  61 + 67 + 71
   311 = 101 + 103 + 107
   311 = 311

el número 41 se puede escribir de 4 formas

   41 =  2 +  3 +  5 + 7 + 11 + 13
   41 = 11 + 13 + 17
   41 = 41

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

   sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,

   λ> sumas 311
   [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
    [53,59,61,67,71],[101,103,107],[311]]
   λ> sumas 41
   [[2,3,5,7,11,13],[11,13,17],[41]]
   λ> sumas 14
   []
   λ> [length (sumas n) | n <- [0..20]]
   [0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0]
   λ> maximum [length (sumas n) | n <- [1..600]]
   5

Soluciones

import Data.Numbers.Primes (primes)
import Data.List (span)
 
sumas :: Integer -> [[Integer]]
sumas x = [ys | n <- takeWhile (<= x) primes, 
                let ys = sumaDesde x n,
                not (null ys)]
 
-- (sumaDesde x n) es la lista de al menos dos números primos
-- consecutivos a partir del número primo n cuya suma es x, si existen y
-- la lista vacía en caso contrario. Por ejemplo,
--    sumaDesde 15 3  ==  [3,5,7]
--    sumaDesde  7 3  ==  []
sumaDesde :: Integer -> Integer -> [Integer]
sumaDesde x n | x == y    = take (1 + length us) ys
              | otherwise = []
    where ys       = dropWhile (<n) primes
          (us,y:_) = span (<x) (scanl1 (+) ys)