Menor potencia de 2 comenzando un número dado
Definir las siguientes funciones
1 2 |
potenciasDe2 :: Integer -> [Integer] menorPotenciaDe2 :: Integer -> Integer |
tales que
- (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,
1 2 3 4 |
λ> take 5 (potenciasDe2 3) [32,32768,33554432,34359738368,35184372088832] λ> take 2 (potenciasDe2 102) [1024,102844034832575377634685573909834406561420991602098741459288064] |
- (menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 |
λ> menorPotenciaDe2 10 1024 λ> menorPotenciaDe2 25 256 λ> menorPotenciaDe2 62 6277101735386680763835789423207666416102355444464034512896 λ> menorPotenciaDe2 425 42535295865117307932921825928971026432 λ> menorPotenciaDe2 967140655691 9671406556917033397649408 λ> [menorPotenciaDe2 a | a <- [1..10]] [1,2,32,4,512,64,70368744177664,8,9007199254740992,1024] |
Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
import Data.List (isPrefixOf) import Test.QuickCheck -- 1ª definición de potenciasDe2 -- ============================= potenciasDe2A :: Integer -> [Integer] potenciasDe2A a = [x | x <- potenciasA , a `esPrefijo` x] potenciasA :: [Integer] potenciasA = [2^n | n <- [0..]] esPrefijo :: Integer -> Integer -> Bool esPrefijo x y = show x `isPrefixOf` show y -- 2ª definición de potenciasDe2 -- ============================= potenciasDe2B :: Integer -> [Integer] potenciasDe2B a = filter (a `esPrefijo`) potenciasA -- 3ª definición de potenciasDe2 -- ============================= potenciasDe2C :: Integer -> [Integer] potenciasDe2C a = filter (a `esPrefijo`) potenciasC potenciasC :: [Integer] potenciasC = iterate (*2) 1 -- Comparación de eficiencia -- ========================= -- λ> length (show (head (potenciasDe2A 123456))) -- 19054 -- (7.17 secs, 1,591,992,792 bytes) -- λ> length (show (head (potenciasDe2B 123456))) -- 19054 -- (5.96 secs, 1,273,295,272 bytes) -- λ> length (show (head (potenciasDe2C 123456))) -- 19054 -- (6.24 secs, 1,542,698,392 bytes) -- Definición de menorPotenciaDe2 menorPotenciaDe2 :: Integer -> Integer menorPotenciaDe2 = head . potenciasDe2B -- Propiedad prop_potenciasDe2 :: Integer -> Property prop_potenciasDe2 a = a > 0 ==> not (null (potenciasDe2B a)) -- Comprobación -- λ> quickCheck prop_potenciasDe2 -- +++ OK, passed 100 tests. |
Referencias
- Potencias de 2 por Philippe Chevanne en «Mad Maths».
- Sucesión A018802 de la OEIS
Que siempre existe
k
«parece» fácil de ver, pero no consigo concretar nada.Otra solución inspirada por la identidad anterior (que no permite encontrar soluciones para
k
arbitrarios y que itera sobre todos los bits) sería:Eficiencia mejorada: