Menu Close

Números sin 2 en base 3

Definir la sucesión

   numerosSin2EnBase3 :: [Integer]

cuyos términos son los números cuya representación en base 3 no contiene el dígito 2. Por ejemplo,

   λ> 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

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

6 soluciones de “Números sin 2 en base 3

  1. PEDRO PORRAS DEL RIO
    numerosSin2EnBase3 :: [Integer]
    numerosSin2EnBase3 = [x | x <- [0..], not (elem 2 (enBase3 x))]
     
    enBase3 :: Integer -> [Integer]
    enBase3 n | n < 3     = [n]
              | otherwise = mod n 3 : enBase3 (div n 3)
  2. juabaerui
    import Test.QuickCheck
     
    numerosSin2EnBase3 :: [Integer]
    numerosSin2EnBase3 =
      filter (x -> 2 `notElem` (base3 x)) [0,1..]
     
    base3 :: Integer -> [Integer]
    base3 n
      | n < 3     = [n]
      | otherwise = mod n 3 : base3 (div n 3)
     
    prop_base3 :: Int -> Property
    prop_base3 n = 
      n >= 0 ==>
      numerosSin2EnBase3 !! n == sucesionSin3enPA !! n
     
    -- λ> quickCheck prop_base3
    -- +++ OK, passed 100 tests.
  3. rebgongor
    import Test.QuickCheck
     
    numerosSin2EnBase3 :: [Integer]
    numerosSin2EnBase3 = map aDecimal (filter (2 `notElem`) ternarios)
     
    ternarios :: [[Integer]]
    ternarios = map enBase3 [0..] 
     
    enBase3 :: Integer -> [Integer]
    enBase3 n | n < 3 = [n]
                | otherwise = mod n 3 : enBase3 (div n 3)
     
    aDecimal :: [Integer] -> Integer
    aDecimal []     = 0
    aDecimal (x:xs) = x + 3*(aDecimal xs)
     
    propiedad :: Int -> Property
    propiedad n =
      n >= 0 ==> numerosSin2EnBase3 !! n == sucesionSin3enPA !! n
     
    -- λ> quickCheck propiedad
    -- +++ OK, passed 100 tests.
  4. José Conde Suso
    enBase3 :: Integer -> [Integer]
    enBase3 n = reverse (magia n)
      where magia c | c < 3     = [c]
                    | otherwise = [rem c 3] ++ (magia (div c 3))
     
    numerosSin2EnBase3 :: [Integer]
    numerosSin2EnBase3 = [x | x <- [0..], notElem 2 (enBase3 x)]
  5. ignarrrod
    numerosSin2EnBase3 :: [Integer]
    numerosSin2EnBase3 = [x | x <- [0..], x `mod` 3 /= 2 && no2 x]
     
    no2 :: Integer -> Bool
    no2 n = notElem 2 (desco n)
     
    desco :: Integer -> [Integer]
    desco n | n >= 3    = [n `mod` 3] ++ desco (n `div` 3)
            | otherwise = [n]
  6. fernando sanchez
    numerosSin2EnBase3 :: [Integer]
    numerosSin2EnBase3 = map base2a3 listabase2
     
    base2a3 :: [Integer] -> Integer
    base2a3 xs = aux1 0 (reverse xs)
      where aux1 n (x:xs) = 3^n*x + aux1 (n+1) xs
            aux1 n []     = 0  
     
    listabase2 :: [[Integer]]
    listabase2 = [reverse $ intAbase2 x | x <- [0..]]
     
    intAbase2 :: Integer -> [Integer]
    intAbase2 n | n < 2     = [n]
                | otherwise = mod n 2 : intAbase2 (div n 2)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.