Ternas potencias de dos
Una terna (a,b,c) de números enteros positivos es especial si se verifica que ab-c, bc-a y ca-b son potencias de 2. Por ejemplo, (3,5,7) es especial ya que
3 * 5 - 7 = 8 = 2^3 5 * 7 - 3 = 32 = 2^5 7 * 3 - 5 = 16 = 2^4
Definir las funciones
esEspecial :: (Integer,Integer,Integer) -> Bool ternasEspeciales :: [(Integer,Integer,Integer)]
tales que
- (esEspecial t) se verifica si t es una terna especial. Por ejemplo,
esEspecial (3,5,7) == True esEspecial (5,7,9) == False
- ternasEspeciales es la lista de las ternasEspeciales ordenadas según su suma y las de la misma suma por orden lexicográfico. Por ejemplo,
λ> take 16 ternasEspeciales [(2,2,2), (2,2,3),(2,3,2),(3,2,2), (3,5,7),(3,7,5),(5,3,7),(5,7,3),(7,3,5),(7,5,3), (2,6,11),(2,11,6),(6,2,11),(6,11,2),(11,2,6),(11,6,2)]
Comprobar con QuickCheck que sólo hay 16 ternas especiales; es decir, para toda terna t de enteros positivos, t pertenece a la lista de los 16 primeros elementos de ternasEspeciales o no es una terna especial.
Nota: Este ejercicio está basado en el problema N5 de la Olimpíada Internacional de Matemáticas (IMO) del 2015.
Soluciones
import Data.List (nub, permutations, sort) import Data.Numbers.Primes (primeFactors) import Data.Bits ((.&.)) import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª definición de esEspecial -- =========================== esEspecial1 :: (Integer,Integer,Integer) -> Bool esEspecial1 (a,b,c) = all esPotenciaDeDos1 [a * b - c, b * c - a, c * a - b] -- (esPotenciaDeDos n) se verifica si n es una potencia de dos. Por -- ejemplo. -- esPotenciaDeDos 8 == True -- esPotenciaDeDos 32 == True -- esPotenciaDeDos 0 == False -- esPotenciaDeDos 1 == True -- esPotenciaDeDos 2 == True -- esPotenciaDeDos 6 == False esPotenciaDeDos1 :: Integer -> Bool esPotenciaDeDos1 n | n <= 0 = False | n <= 2 = True | even n = esPotenciaDeDos1 (n `div` 2) | otherwise = False -- 2ª definición de esEspecial -- =========================== esEspecial2 :: (Integer,Integer,Integer) -> Bool esEspecial2 (a,b,c) = all esPotenciaDeDos2 [a * b - c, b * c - a, c * a - b] esPotenciaDeDos2 :: Integer -> Bool esPotenciaDeDos2 n = n == head (dropWhile (<n) potenciasDeDos) -- potenciasDeDos es la lista de las potencias de dos. Por ejemplo, potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- 3ª definición de esEspecial -- =========================== esEspecial3 :: (Integer,Integer,Integer) -> Bool esEspecial3 (a,b,c) = all esPotenciaDeDos3 [a * b - c, b * c - a, c * a - b] esPotenciaDeDos3 :: Integer -> Bool esPotenciaDeDos3 x = all (==2) (primeFactors x) -- 4ª definición de esEspecial -- =========================== esEspecial4 :: (Integer,Integer,Integer) -> Bool esEspecial4 (a,b,c) = all esPotenciaDeDos4 [a * b - c, b * c - a, c * a - b] -- La siguiente definición de esPotenciaDeDos usa la función (.&.) de la -- librería Data.Bits. Dicha función calcula el número correspondiente a -- la conjunción de las representaciones binarias de sus argumentos. Por -- ejemplo, -- 6 .&. 3 == 2 -- ya que -- la representación binaria de 6 es [1,1,0] -- la representación binaria de 3 es [1,1] -- la conjunción es [1,0] -- la representación decimal de [1,0] es 2 -- -- Otros ejemplos: -- 4 .&. 3 == [1,0,0] .&. [1,1] == 0 -- 8 .&. 7 == [1,0,0,0] .&. [1,1,1] = 0 esPotenciaDeDos4 :: Integer -> Bool esPotenciaDeDos4 n = n .&. (n-1) == 0 -- Comparación de eficiencia de las definiciones de esEspecial -- =========================================================== -- La comparación es -- λ> esEspecial1 (2^300000,2,0) -- False -- (3.05 secs, 5,765,728,296 bytes) -- λ> esEspecial2 (2^300000,2,0) -- False -- (2.68 secs, 5,755,293,608 bytes) -- λ> esEspecial3 (2^300000,2,0) -- False -- (2.45 secs, 5,758,527,232 bytes) -- λ> esEspecial4 (2^300000,2,0) -- False -- (0.01 secs, 516,512 bytes) -- Definición de esEspecial -- ======================== -- En lo sucesivo usaremos la 4ª definición. esEspecial :: (Integer,Integer,Integer) -> Bool esEspecial = esEspecial4 -- Definición de ternasEspeciales -- ============================== -- λ> take 16 ternasEspeciales -- [(2,2,2),(2,2,3),(2,3,2),(3,2,2),(3,5,7),(3,7,5),(5,3,7),(5,7,3), -- (7,3,5),(7,5,3),(2,6,11),(2,11,6),(6,2,11),(6,11,2),(11,2,6),(11,6,2)] ternasEspeciales :: [(Integer,Integer,Integer)] ternasEspeciales = filter esEspecial1 ternas -- ternas es la lista de ternas de enteros positivos con el orden -- descrito anteriormente. Por ejemplo, -- λ> take 20 ternas -- [(1,1,1), -- (1,1,2),(1,2,1),(2,1,1), -- (1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1), -- (1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)] ternas :: [(Integer,Integer,Integer)] ternas = concatMap ternasSuma [3..] -- (ternasSuma n) es la lista de las ternas de enteros positivos cuya -- suma es n ordenadas lexicográficamte. Por ejemplo, -- λ> ternasSuma 3 -- [(1,1,1)] -- λ> ternasSuma 4 -- [(1,1,2),(1,2,1),(2,1,1)] -- λ> ternasSuma 5 -- [(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)] -- λ> ternasSuma 6 -- [(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)] ternasSuma :: Integer -> [(Integer,Integer,Integer)] ternasSuma n = sort (concatMap permutaciones [(a,b,c) | a <- [1..n] , b <- [a..n] , let c = n-a-b , b <= c]) -- (permutaciones t) es la lista de las permutaciones de la terna t. Por ejemplo, -- λ> permutaciones (1,2,3) -- [(1,2,3),(2,1,3),(3,2,1),(2,3,1),(3,1,2),(1,3,2)] -- λ> permutaciones (1,1,2) -- [(1,1,2),(2,1,1),(1,2,1)] -- λ> permutaciones (1,1,1) -- [(1,1,1)] permutaciones :: (Integer,Integer,Integer) -> [(Integer,Integer,Integer)] permutaciones (a,b,c) = nub [(x,y,z) | [x,y,z] <- permutations [a,b,c]] -- Propiedad -- ========= -- La propiedad es prop_ternasEspeciales :: (Integer,Integer,Integer) -> Property prop_ternasEspeciales (a,b,c) = a > 0 && b > 0 && c > 0 ==> (a,b,c) `elem` xs || not (esEspecial (a,b,c)) where xs = take 16 ternasEspeciales -- La comprobación es -- λ> quickCheck prop_ternasEspeciales -- +++ OK, passed 100 tests.