Ir al contenido principal

Menor potencia de 2 comenzando un número dado

Definir las siguientes funciones

potenciasDe2  :: Integer -> [Integer]
menorPotenciaDe2 :: Integer -> Integer

tales que

  • (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,
λ> 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,
λ> 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

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