Menu Close

Números en potencias de dos

 

Las potencias de dos son

   1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,...

Se observa que la primera potencia de dos que contiene al 638 es la 14 ya que 2^14 = 16384.

Definir la función

   potenciasContenedoras :: Integer -> [Integer]

tal que (potenciasContenedoras x) es la lista de las potencias de 2 que contienen a x. Por ejemplo,

   λ> head (potenciasContenedoras 638)
   14
   λ> head (potenciasContenedoras 2021)
   452
   λ> take 20 (potenciasContenedoras 4)
   [2,6,10,11,12,14,18,19,20,22,25,26,27,28,30,31,32,33,34,35]
   λ> [head (potenciasContenedoras n) | n <- [0..20]]
   [10,4,1,5,2,8,4,15,3,12,10,40,7,17,18,21,4,27,30,13,11]

Comprobar con QuickCheck si todos los números naturales están contenenidos en alguna potencia de 2.

Soluciones

import Data.List (isInfixOf)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
potenciasContenedoras :: Integer -> [Integer]
potenciasContenedoras x =
  [n | n <- [1..], x `estaContenidoEn` (2^n)]
 
-- (estaContenidoEn x y) se verifica si el número x está contenido en
-- y. Por ejemplo,
--    estaContenidoEn 23 42357  ==  True
--    estaContenidoEn 23 42537  ==  False
estaContenidoEn :: Integer -> Integer -> Bool
estaContenidoEn x y = show x `isInfixOf` show y
 
-- 2ª solución
-- ===========
 
potenciasContenedoras2 :: Integer -> [Integer]
potenciasContenedoras2 x =
  [n | (n,y) <- zip [0..] potenciasDeDos, x `estaContenidoEn` y]
 
-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,
--    λ> take 12 potenciasDeDos
--    [1,2,4,8,16,32,64,128,256,512,1024,2048]
potenciasDeDos :: [Integer]
potenciasDeDos = iterate (*2) 1
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_potenciasContenedoras :: Integer -> Property
prop_potenciasContenedoras n =
  n > 0 ==> not (null (potenciasContenedoras n))
 
-- La comprobación es
--    λ> quickCheck prop_potenciasContenedoras
--    +++ OK, passed 100 tests.
Inicial

5 soluciones de “Números en potencias de dos

  1. Rubén Muñoz Mkrtchian
    import Data.List (isPrefixOf, tails)
    import Test.QuickCheck (Property, (==>), quickCheck)
     
    potenciasContenedoras :: Integer -> [Integer]
    potenciasContenedoras n = [x | x <- [0..], contiene (2^x) n]
     
    -- contiene n m se verifica si m está contenido en el número n.
     
    contiene :: Integer -> Integer -> Bool
    contiene n m = any (isPrefixOf (show m)) (tails (show n))
     
    propNaturales :: Integer -> Property
    propNaturales n = n >= 1 ==> not (null (potenciasContenedoras n))
     
    -- La comprobación es:
    -- λ> quickCheck propNaturales
    -- +++ OK, passed 100 tests.
  2. Alejandro García Alcaide
    -- NÚMEROS EN POTENCIAS DE DOS
    import Data.Numbers.Primes
    import Data.List
    import Test.QuickCheck
    -- La función que buscamos podría definirse de la siguiente forma con la ayuda
    -- de dos parámetros. 
    potenciasContenedoras :: Integer -> [Integer]
    potenciasContenedoras n =
      [x | x <- [0..], contiene (pasarALista(n))(pasarALista (2^x))]
     
    -- Definimos la función auxiliar contiene, con isInfixOf que indica si una
    -- lista xs es contenida por otra ys. 
    contiene :: [Integer] -> [Integer] -> Bool
    contiene xs ys = isInfixOf xs ys
     
    -- Por su parte, la funcion pasarALista toma un número y lo transforma en una
    -- lista.
    pasarALista :: Integer -> [Integer]
    pasarALista n = [read [x]::Integer | x <- show n]
     
    -- Por último, comprobamos la propiedad propuesta:
    propiedad2 :: Integer -> Property
    propiedad2 n = n >= 1 ==> not (null (potenciasContenedoras n))
    -- Se verifica la propiedad.
  3. Inés Mora Caro
     
    import Test.QuickCheck
    import Data.List
    import Data.Char
    import Data.Numbers.Primes
     
     
    -- Definir la función
    potenciasContenedoras :: Int -> [Int]
    potenciasContenedoras n = filter (/= 0) [if x == True then y else 0
                                             | (x,y) <- zip (listaBooleana n) [1..]]
     
    -- tal que (potenciasContenedoras x) es la lista de las potencias de 2 que
    -- contienen a x.
     
     
    -- Me he dado cuenta que no hace falta crear una función para pasar de dígitos
    -- a lista de números porque es lo que hace show (aunque los muestra como
    -- lista de caracteres)
     
    digitosPotencias2 :: [[Char]]
    digitosPotencias2 = map show [2^x | x <- [1..]]
     
    listaBooleana :: Int -> [Bool]
    listaBooleana n = map (isInfixOf (show n)) digitosPotencias2
     
     
    -- listaDigitos'' :: Int -> [Int]
    -- listaDigitos'' n | n < 10  = [n]
    --                  | n >= 10 = listaDigitos' (n `div` 10) ++ [n `mod` 10]
     
    -- digitosPotencias2' :: [[Int]]
    -- digitosPotencias2' = map listaDigitos'' [2^x | x <- [1..]]
     
    -- listaBooleana' :: Int -> [Bool]
    -- listaBooleana' n = map (isInfixOf (listaDigitos'' n)) digitosPotencias2
     
     
    -- Comprobar con QuickCheck si todos los números naturales están contenenidos
    -- en alguna potencia de 2.
     
    prop_contenidos :: Int -> Property
    prop_contenidos n = n > 0 ==> potenciasContenedoras n /= []
     
    -- λ> quickCheck prop_contenidos
    -- +++ OK, passed 100 tests.
  4. Ángel Ruiz
    import Data.List       (isInfixOf)
    import Test.QuickCheck (quickCheck,Positive(..))
     
    potenciasContenedoras :: Integer -> [Integer]
    potenciasContenedoras n =
      filter (isInfixOf (show n) . show . (2^)) [1..]
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_potenciasContenedoras :: Positive Integer -> Bool
    prop_potenciasContenedoras (Positive n) =
      not (null (potenciasContenedoras n))
     
    -- La comprobación es
    --    λ> quickCheck prop_potenciasContenedoras
    --    +++ OK, passed 100 tests.

Leave a Reply

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