Números sin 2 en base 3

Definir la sucesión

   numerosSin2EnBase3 :: [Integer]

1	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]

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

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.

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 Comentarios

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)

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)

Responder

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.

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.

Responder

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.

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.

Responder

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)]

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)]

Responder

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]

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]

Responder

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)

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)

Responder

Números sin 2 en base 3

Soluciones

Otras soluciones

Pensamiento

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Otras soluciones

Pensamiento

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico