Menu Close

Sucesión de Recamán

La sucesión de Recamán está definida como sigue:

   a(0) = 0
   a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
   a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

   sucRecaman :: [Int]
   invRecaman :: Int -> Int
   graficaSucRecaman :: Int -> IO ()
   graficaInvRecaman :: Int -> IO ()

tales que

  • sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,
      λ> take 25 sucRecaman3
      [0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
      λ> sucRecaman !! 1000
      3686
      λ> sucRecaman !! 1000001
      1057163
  • (invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,
      invRecaman 10       ==  12
      invRecaman 3686     ==  1000
      invRecaman 1057163  ==  1000001
  • (graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja
    Sucesion_de_Recaman_1
  • (graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja
    Sucesion_de_Recaman_2
    y (graficaInvRecaman 100) dibuja
    Sucesion_de_Recaman_3

Soluciones

import qualified Data.Set as S
 
-- 1ª solución
-- ===========
 
sucRecaman1 :: [Int]
sucRecaman1 = map suc1 [0..]
 
suc1 :: Int -> Int
suc1 0 = 0
suc1 n | y > n && y - n `notElem` ys = y - n
       | otherwise                   = y + n
  where y  = suc1 (n - 1)
        ys = [suc1 k | k <- [0..n - 1]]
 
-- 2ª solución
-- ===========
 
sucRecaman2 :: [Int]
sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)
  where f y n ys | y > n && y - n `notElem` take n ys = y - n
                 | otherwise                          = y + n
 
-- 3ª solución
-- ===========
 
sucRecaman3 :: [Int]
sucRecaman3 = 0 : recaman (S.singleton 0) 1 0
 
recaman :: S.Set Int -> Int -> Int -> [Int]
recaman s n x
  | x > n && (x-n) `S.notMember` s =
    (x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)
  | otherwise =
    (x+n):recaman (S.insert (x+n) s) (n+1) (x+n) 
 
-- Comparación de eficiencia:
--    λ> sucRecaman1 !! 25
--    17
--    (3.76 secs, 2,394,593,952 bytes)
--    λ> sucRecaman2 !! 25
--    17
--    (0.00 secs, 0 bytes)
--    λ> sucRecaman3 !! 25
--    17
--    (0.00 secs, 0 bytes)
--
--    λ> sucRecaman2 !! (2*10^4)
--    14358
--    (2.69 secs, 6,927,559,784 bytes)
--    λ> sucRecaman3 !! (2*10^4)
--    14358
--    (0.04 secs, 0 bytes)
 
-- Definición de invRecaman
invRecaman :: Int -> Int
invRecaman n =
  length (takeWhile (/=n) sucRecaman3)
 
graficaSucRecaman :: Int -> IO ()
graficaSucRecaman n =
  plotList [Key Nothing]
           (take n sucRecaman3)
 
graficaInvRecaman :: Int -> IO ()
graficaInvRecaman n =
  plotList [Key Nothing]
           [invRecaman k | k <- [0..n]]

6 soluciones de “Sucesión de Recamán

  1. albcercid
    import Graphics.Gnuplot.Simple
    import qualified Data.Set as S
     
    sucRecaman :: [Int]
    sucRecaman = 0:aux 0 1 (S.fromList [0])
      where aux a b xs
              | a > b && not (S.member t1 xs) = t1 : aux t1 (b + 1) (S.insert t1 xs)
              | otherwise                     = t2 : aux t2 (b + 1) (S.insert t2 xs)
              where t1 = a - b
                    t2 = a + b
     
    invRecaman :: Int -> Int
    invRecaman x = snd $ head $ dropWhile f $ zip sucRecaman [0..]
        where f (a,b) = x /= a
     
    graficaSucRecaman :: Int -> IO ()
    graficaSucRecaman n = plotList [Key Nothing] (take n sucRecaman)
     
    graficaInvRecaman :: Int -> IO ()
    graficaInvRecaman n = plotList [Key Nothing] (map invRecaman [0..n])
  2. glovizcas
    sucRecaman :: [Int]
    sucRecaman =  [a(n) | n <- [0..]]
     
    a 0 = 0
    a n | a (n-1) > n &&
          ((a (n-1) - n) `notElem` (take (n-1) (sucRecaman))) = a (n-1) - n
        | otherwise   = a (n-1) + n
     
     
    invRecaman :: Int -> Int
    invRecaman n = head [ a | (a,b) <- zip [0..] sucRecaman, n == b]
     
    graficaSucRecaman :: Int -> IO ()
    graficaSucRecaman n = plotList [Key Nothing] (take n sucRecaman)
     
    graficaInvRecaman :: Int -> IO ()
    graficaInvRecaman k = plotList [Key Nothing] [invRecaman x | x <- [0..k]]
  3. artmorfer
    import Graphics.Gnuplot.Simple
     
    sucRecaman :: [Int]
    sucRecaman = [sucesion x | x <- [0..]]
      where
        sucesion 0 = 0
        sucesion n = if (sucesion (n-1) > n &&
                          (sucesion (n-1) - n) `notElem` (take (n-1) sucRecaman))
                     then ((sucesion (n-1)) - n)
                     else ((sucesion (n -1)) + n)
     
    invRecaman :: Int -> Int
    invRecaman n = head [ x | (x,b) <- zip [0..] sucRecaman, b == n]
     
    graficaSucRecaman :: Int -> IO ()
    graficaSucRecaman n = plotList [Key Nothing] (take n sucRecaman)
     
    graficaInvRecaman :: Int -> IO ()
    graficaInvRecaman n = plotList [Key Nothing] (map invRecaman [0..n])
  4. enrnarbej
    import qualified Data.Set as S
    import Graphics.Gnuplot.Simple
     
    sucRecaman :: [Int]
    sucRecaman = sucRecamanS S.empty 0 0
     
    sucRecamanS :: S.Set Int -> Int -> Int -> [Int]
    sucRecamanS xs 0 0 = 0 : sucRecamanS (S.insert 0 xs) 0 1
    sucRecamanS xs n c
      | n > c && c1 `S.notMember` xs = c1 : sucRecamanS (S.insert c1 xs) c1 (c+1)
      | otherwise                    = c2 : sucRecamanS (S.insert c2 xs) c2 (c+1)
      where
        c1 = n - c
        c2 = n + c
     
    invRecaman :: Int -> Int
    invRecaman n = (length . takeWhile (/=n)) sucRecaman
     
    graficaSucRecaman :: Int -> IO ()
    graficaSucRecaman n = (plotList [Key Nothing] . take n) sucRecaman
     
    graficaInvRecaman :: Int -> IO ()
    graficaInvRecaman n = (plotList [Key Nothing] . map invRecaman) [1..n]
  5. fragarcor3
    import Graphics.Gnuplot.Simple
    import Data.List (elemIndex)
    import Data.Maybe (fromJust)
     
    sucRecaman :: [Int]
    sucRecaman =  0 : aux 1
        where   aux :: Int -> [Int]
            aux m   | x - m > 0 && elemIndex (x-m) (take m sucRecaman)== Nothing = (x-m) : aux (m+1)
                | otherwise = (x+m) : aux (m+1)
                where   x = sucRecaman !! (m-1)
     
    invRecaman :: Int -> Int
    invRecaman n = (fromJust . elemIndex n) sucRecaman
     
    graficaSucRecaman :: Int -> IO ()
    graficaSucRecaman n = plotList [Key Nothing] (take n sucRecaman)
     
    graficaInvRecaman :: Int -> IO ()
    graficaInvRecaman n = plotList [Key Nothing] (map invRecaman [0..n])
  6. Juanjo Ortega (juaorture)
    import Graphics.Gnuplot.Simple
    import Data.Set as S
     
    sucRecaman :: [Int]
    sucRecaman = 0 : aux (singleton 0) 1 0
               where aux :: Set Int -> Int -> Int -> [Int]
                     aux xs n a | y > 0 && notMember y xs = y : aux (insert y xs) (n+1) y
                                | otherwise               = z : aux (insert z xs) (n+1) z
                                      where y = a - n
                                            z = a + n
     
    invRecaman :: Int -> Int
    invRecaman = aux sucRecaman 0
               where aux (x:xs) n a | a == x = n
                                    | otherwise = aux xs (n+1) a
     
    graficaSucRecaman :: Int -> IO ()
    graficaSucRecaman n = plotList [Key Nothing] (take n sucRecaman)
     
     
    graficaInvRecaman :: Int -> IO ()
    graficaInvRecaman n = plotList [Key Nothing] [invRecaman x | x <- [0..n]]

Escribe tu solución

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