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
|
1 2 3 |
3 * 5 - 7 = 8 = 2^3 5 * 7 - 3 = 32 = 2^5 7 * 3 - 5 = 16 = 2^4 |
Definir las funciones
|
1 2 |
esEspecial :: (Integer,Integer,Integer) -> Bool ternasEspeciales :: [(Integer,Integer,Integer)] |
tales que
- (esEspecial t) se verifica si t es una terna especial. Por ejemplo,
|
1 2 |
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,
|
1 2 3 4 5 |
λ> 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
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
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. |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
3 Comentarios