La mayor potencia de dos no es divisor
Para cada número entero positivo n, se define el conjunto
|
1 |
S(n) = {1, 2, 3, ..., n} |
de los números desde el 1 hasta n.
Definir la función
|
1 |
mayorPotenciaDeDosEnS :: Integer -> Integer |
tal que (mayorPotenciaDeDosEnS n) es la mayor potencia de 2 en S(n). Por ejemplo,
|
1 2 |
mayorPotenciaDeDosEnS 3 == 2 mayorPotenciaDeDosEnS 4 == 4 |
Comprobar con QuickCheck que la mayor potencia de 2 en S(n) no divide a ningún otro elemento de S(n).
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import Data.List (delete) import Test.QuickCheck mayorPotenciaDeDosEnS :: Integer -> Integer mayorPotenciaDeDosEnS n = last (takeWhile (<=n) potenciasDeDos) -- potenciasDeDos es la lista de las potencias de 2. Por ejemplo, -- take 5 potenciasDeDos == [1,2,4,8,16] potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- La propiedad es prop_mayorPotenciaDeDosEnS :: Integer -> Property prop_mayorPotenciaDeDosEnS n = n > 0 ==> all (x `noDivide`) (delete x [1..n]) where x = mayorPotenciaDeDosEnS n x `noDivide` y = y `mod` x /= 0 -- La comprobación es -- λ> quickCheck prop_mayorPotenciaDeDosEnS -- +++ OK, passed 100 tests. |
Referencia
- Basado en Greatest power of two not divisor de ProofWiki.
Pensamiento
¡Sólo tu figura,
como una centella blanca,
en mi noche oscura.Antonio Machado