Menu Close

El 2019 es malvado

Un número malvado es un número natural cuya expresión en base 2 contiene un número par de unos. Por ejemplo, 6 es malvado porque su expresión en base 2 es 110 que tiene dos unos.

Definir las funciones

   esMalvado       :: Integer -> Bool
   malvados        :: [Integer]
   posicionMalvada :: Integer -> Maybe Int

tales que

  • (esMalvado n) se verifica si n es un número malvado. Por ejemplo,
     esMalvado 6              ==  True
     esMalvado 7              ==  False
     esMalvado 2019           ==  True
     esMalvado (10^70000)     ==  True
     esMalvado (10^(3*10^7))  ==  True
  • malvados es la sucesión de los números malvados. Por ejemplo,
     λ> take 20 malvados
     [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39]
     malvados !! 1009    ==  2019
     malvados !! 10      ==  20
     malvados !! (10^2)  ==  201
     malvados !! (10^3)  ==  2000
     malvados !! (10^4)  ==  20001
     malvados !! (10^5)  ==  200000
     malvados !! (10^6)  ==  2000001
  • (posicionMalvada n) es justo la posición de n en la sucesión de números malvados, si n es malvado o Nothing, en caso contrario. Por ejemplo,
     posicionMalvada 6        ==  Just 3
     posicionMalvada 2019     ==  Just 1009
     posicionMalvada 2018     ==  Nothing
     posicionMalvada 2000001  ==  Just 1000000
     posicionMalvada (10^7)   ==  Just 5000000

Soluciones

import Data.List (genericLength, elemIndex)
import Data.Bits (popCount)
 
-- 1ª definición de esMalvado
-- ==========================
 
esMalvado :: Integer -> Bool
esMalvado n = even (numeroUnosBin n)
 
-- Sin argumentos
esMalvado' :: Integer -> Bool
esMalvado' = even . numeroUnosBin
 
-- (numeroUnosBin n) es el número de unos de la representación binaria
-- del número decimal n. Por ejemplo,
--   numeroUnosBin 11  ==  3
--   numeroUnosBin 12  ==  2
numeroUnosBin :: Integer -> Integer
numeroUnosBin n  = genericLength (filter (== 1) (binario n))
 
-- Sin argumentos
numeroUnosBin' :: Integer -> Integer
numeroUnosBin' = genericLength . filter (== 1) . binario
 
-- (binario n) es el número binario correspondiente al número decimal n.
-- Por ejemplo, 
--   binario 11  ==  [1,1,0,1]
--   binario 12  ==  [0,0,1,1]
binario :: Integer -> [Integer]
binario n | n < 2     = [n]
          | otherwise = n `mod` 2 : binario (n `div` 2)
 
-- 2ª definición de esMalvado
-- ==========================
 
esMalvado2 :: Integer -> Bool
esMalvado2 n = even (numeroUnosBin n)
 
-- (numeroIntBin n) es el número de unos que contiene la representación
-- binaria del número decimal n. Por ejemplo,
--   numeroIntBin 11  ==  3
--   numeroIntBin 12  ==  2
numeroIntBin :: Integer -> Integer
numeroIntBin n | n < 2     = n
               | otherwise = n `mod` 2 + numeroIntBin (n `div` 2)
 
-- 3ª definición de esMalvado
-- ==========================
 
esMalvado3 :: Integer -> Bool
esMalvado3 n = even (popCount n)
 
-- Sin argumentos
esMalvado3' :: Integer -> Bool
esMalvado3' = even . popCount 
 
-- Comparación de eficiencia
-- =========================
 
--    λ> esMalvado (10^30000)
--    True
--    (1.79 secs, 664,627,936 bytes)
--    λ> esMalvado2 (10^30000)
--    True
--    (1.79 secs, 664,626,992 bytes)
--    λ> esMalvado3 (10^30000)
--    True
--    (0.03 secs, 141,432 bytes)
--    
--    λ> esMalvado (10^40000)
--    False
--    (2.95 secs, 1,162,091,464 bytes)
--    λ> esMalvado2 (10^40000)
--    False
--    (2.96 secs, 1,162,091,096 bytes)
--    λ> esMalvado3 (10^40000)
--    False
--    (0.04 secs, 155,248 bytes)
 
-- 1ª definición de malvados
-- =========================
 
malvados :: [Integer]
malvados = [n | n <- [0..], esMalvado3 n]
 
-- 2ª definición de malvados
-- =========================
 
malvados2 :: [Integer]
malvados2 = filter esMalvado3 [0..]
 
-- 1ª definición de posicionMalvada
-- ================================
 
posicionMalvada :: Integer -> Maybe Int
posicionMalvada n
  | y == n    = Just (length xs)
  | otherwise = Nothing
  where (xs,(y:_)) = span (<n) malvados
 
-- 2ª definición de posicionMalvada
posicionMalvada2 :: Integer -> Maybe Int
posicionMalvada2 n
  | esMalvado n = elemIndex n malvados
  | otherwise        = Nothing

Pensamiento

… Yo os enseño, o pretendo enseñaros a que dudéis de todo: de lo
humano y de lo divino, sin excluir vuestra propia existencia.

Antonio Machado

Inicial

4 soluciones de “El 2019 es malvado

  1. frahidzam
    import Data.List (genericLength, group, sort)
     
    esMalvado :: Integer -> Bool
    esMalvado n =
      even (last (map genericLength (group (sort (intGToBin n)))))
     
    intGToBin :: Integer -> [Integer]
    intGToBin n | n < 2     = [n]
                | otherwise = mod n 2 : intGToBin (div n 2)
     
    malvados :: [Integer]
    malvados = 0 : [a | a <- [3..], esMalvado a]
     
    posicionMalvada :: Integer -> Maybe Int
    posicionMalvada n
      | elem n (takeWhile (<=n) malvados) = Just (posAuxM n)
      | otherwise                         = Nothing
     
    posAuxM :: Integer -> Int
    posAuxM n = head [b | (a,b) <- zip malvados [0..], n == a]
  2. lucsanand
    import Data.Bits (popCount)
     
    esMalvado :: Integer -> Bool
    esMalvado n = even (popCount n)
     
    malvados :: [Integer]
    malvados = [n | n <- [0..], esMalvado n]
     
    posicionMalvada :: Integer -> Maybe Int
    posicionMalvada n
      | esMalvado n = Just (aux n)
      | otherwise     = Nothing
      where aux :: Integer -> Int
            aux n = length (takeWhile (/= n) malvados)
  3. luipromor
    esMalvado :: Integer -> Bool
    esMalvado = even . genericLength . filter (==1) . toBin
      where toBin x | x < 2     = [x]
                    | otherwise = mod x 2 : toBin (div x 2)
     
    malvados :: [Integer]
    malvados = [x | x <- [0..], esMalvado x]
     
    posicionMalvada :: Integer -> Maybe Int
    posicionMalvada x
      | esMalvado x = Just (aux x 0)
      | otherwise     = Nothing
      where aux x n | x == malvados !! n = n
                    | otherwise            = aux x (n+1)
  4. javmarcha1
    import Data.Bits (popCount)
     
    esMalvado :: Integer -> Bool
    esMalvado n = even (popCount n)
     
    malvados :: [Integer]
    malvados = [n | n <- [0..], esMalvado n]
     
    posicionMalvada :: Integer -> Maybe Int
    posicionMalvada x
      | esMalvado x = Just (length (takeWhile (< x) malvados))
      | otherwise   = Nothing

Escribe tu solución

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