Números en potencias de dos
Las potencias de dos son
1 |
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
1 |
potenciasContenedoras :: Integer -> [Integer] |
tal que (potenciasContenedoras x) es la lista de las potencias de 2 que contienen a x. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
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. |