Números sin 2 en base 3
Definir la sucesión
1 |
numerosSin2EnBase3 :: [Integer] |
cuyos términos son los números cuya representación en base 3 no contiene el dígito 2. Por ejemplo,
1 2 |
λ> take 20 numerosSin2EnBase3 [0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85] |
Se observa que
- 12 está en la sucesión ya que su representación en base 3 es 110 (porque 1·3² + 1·3¹ + 0.3⁰ = 12) y no contiene a 2.
- 14 no está en la sucesión ya que su representación en base 3 es 112 (porque 1·3² + 1·3¹ + 2.3⁰ = 14) y contiene a 2.
Comprobar con QuickCheck que las sucesiones numerosSin2EnBase3 y sucesionSin3enPA (del ejercicio anterior) son iguales; es decir, para todo número natural n, el n-ésimo término de numerosSin2EnBase3 es igual al n-ésimo término de sucesionSin3enPA.
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 |
import Data.List ((\\)) import Test.QuickCheck -- 1ª solución -- =========== numerosSin2EnBase3a :: [Integer] numerosSin2EnBase3a = [n | n <- [0..] , 2 `notElem` (enBase3 n)] -- (enBase3 n) es la representación de n en base 3. Por ejemplo, -- enBase3 7 == [1,2] -- enBase3 9 == [0,0,1] -- enBase3 10 == [1,0,1] -- enBase3 11 == [2,0,1] enBase3 :: Integer -> [Integer] enBase3 n | n < 3 = [n] | otherwise = r : enBase3 q where (q,r) = quotRem n 3 -- 2ª definición -- ============= -- Se puede construir como un triángulo: -- 0 -- 1 -- 3 4 -- 9 10 12 13 -- 27 28 30 31 36 37 39 40 -- .... numerosSin2EnBase3b :: [Integer] numerosSin2EnBase3b = 0 : concat (iterate siguientes [1]) where siguientes xs = concatMap (\x -> [3*x,3*x+1]) xs -- Comparación de eficiencia -- ========================= -- La compración es -- λ> numerosSin2EnBase3a !! (10^4) -- 1679697 -- (4.06 secs, 2,245,415,808 bytes) -- λ> numerosSin2EnBase3b !! (10^4) -- 1679697 -- (0.03 secs, 2,109,912 bytes) -- Definición -- ========== -- En lo que sigue usaremos la 2ª definición. numerosSin2EnBase3 :: [Integer] numerosSin2EnBase3 = numerosSin2EnBase3b -- Propiedad -- ========= -- La propiedad es prop_equivalencia :: Int -> Property prop_equivalencia n = n > 0 ==> sucesionSin3enPA !! n == numerosSin2EnBase3 !! n -- sucesionSin3enPA donde cada uno de sus términos es el menor número -- natural tal que no está en PA con cualesquiera dos términos -- anteriores de la sucesión. sucesionSin3enPA :: [Integer] sucesionSin3enPA = aux [] [0..] where aux xs (y:ys) = y : aux (y:xs) (ys \\ [2 * y - x | x <- xs]) -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
O que yo pueda asesinar un día
en mi alma, al despertar, esa persona
que me hizo el mundo mientras yo dormía.Antonio Machado