Menu Close

La conjetura de Collatz

La conjetura de Collatz, conocida también como conjetura 3n+1, fue enunciada por Lothar Collatz en 1937 y, hasta la fecha, no se ha resuelto.

La conjetura hace referencia a una propiedad de las sucesiones de Siracusa. La sucesión de Siracusa de un número entero positivo x es la sucesión cuyo primer término es x y el siguiente de un término se obtiene dividiéndolo entre 2, si es par o multiplicándolo por 3 y sumándole 1, si es impar. Por ejemplo, la sucesión de Siracusa de 12 es

   12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

La conjetura de Collatz afirma que para todo número entero positivo x, el 1 pertenece a la sucesión de Siracusa de x.

Definir las funciones

   siracusa        :: Integer -> [Integer]
   graficaSiracusa :: Int -> [Integer] -> IO ()

tales que

  • (siracusa x) es la sucesión de Siracusa de x. Por ejemplo,
     λ> take 20 (siracusa 12)
     [12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]
     λ> take 20 (siracusa 22)
     [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]
  • (graficaSiracusa n xs) dibuja los n primeros términos de las sucesiones de Siracusas de los elementos de xs. Por ejemplo, (graficaSiracusa 100 [27]) dibuja

y (graficaSiracusa 150 [1..1000]) dibuja

Comprobar con QuickCheck la conjetura de Collatz.

Soluciones

import Test.QuickCheck
import Graphics.Gnuplot.Simple
 
-- 1ª definición de siracusa
-- =========================
 
siracusa :: Integer -> [Integer]
siracusa n | even n    = n : siracusa (n `div` 2)
           | otherwise = n : siracusa (3*n+1)
 
-- 2ª definición de siracusa
-- =========================
 
siracusa2 :: Integer -> [Integer]
siracusa2 = iterate siguiente 
  where siguiente x | even x    = x `div` 2
                    | otherwise = 3*x+1
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> siracusa 12 !! (10^6)
--    4
--    (0.55 secs, 362,791,008 bytes)
--    λ> siracusa 12 !! (2*10^6)
--    2
--    (1.05 secs, 725,456,376 bytes)
--    λ> siracusa2 12 !! (10^6)
--    4
--    (1.66 secs, 647,189,664 bytes)
--    λ> siracusa2 12 !! (2*10^6)
--    2
--    (3.11 secs, 1,294,286,792 bytes)
 
-- Definición de graficaSiracusa
-- =============================
 
graficaSiracusa :: Int -> [Integer] -> IO ()
graficaSiracusa n xs =
  plotLists [ Key Nothing
            , PNG "La_conjetura_de_Collatz.png"
            ]
            [take n (siracusa x) | x <- xs]
 
-- Comprobación de la conjetura
-- ============================
 
-- La conjetura es
conjeturaCollatz :: Positive Integer -> Bool
conjeturaCollatz (Positive n) =
  1 `elem` siracusa n
 
-- La comprobación es
--    λ> quickCheck conjeturaCollatz
--    +++ OK, passed 100 tests.

Pensamiento

Que el caminante es suma del camino …

Antonio Machado

6 soluciones de “La conjetura de Collatz

  1. frahidzam
    siracusa :: Integer -> [Integer]
    siracusa n = n : siracusa (sigSiracusa n)
     
    sigSiracusa :: Integer -> Integer
    sigSiracusa n | even n = div n 2
                  | otherwise = 3*n+1
     
    graficaSiracusa :: Int -> [Integer] -> IO ()
    graficaSiracusa n xs = plotLists [Key Nothing] [take n (siracusa a) | a <- xs]
     
    conjeturaCollatz :: Integer -> Property
    conjeturaCollatz n = n > 0 ==> p (siracusa n)
      where  p (x:xs) | x == 1 = True
                      | otherwise = p xs
     
    λ> quickCheck conjeturaCollatz
    +++ OK, passed 100 tests.
  2. adogargon
    import Graphics.Gnuplot.Simple
     
    siracusa :: Integer -> [Integer]
    siracusa n = iterate f n
      where f n | even n = n `div` 2
                | otherwise = 3*n +1
     
    graficaSiracusa :: Int -> [Integer] -> IO ()
    graficaSiracusa n xs = plotLists [Key Nothing] (map (take n . siracusa) xs)
  3. danmorper2
    siracusa :: Integer -> [Integer]
    siracusa n | even n= [n]++(siracusa m)
               | otherwise=[n]++(siracusa q)
       where
         m=div n 2
         q=3*n+1
    graficaSiracusa :: Int -> [Integer] -> IO ()
    graficaSiracusa n xs = plotLists [Key Nothing] (map (take n)(map (siracusa) xs))
  4. rafasidia

     
    import Graphics.Gnuplot.Simple
    import Test.QuickCheck
    
    siracusa :: Integer -> [Integer]
    siracusa x | even x = x:(siracusa (div x 2))
               |otherwise = x:(siracusa (3*x+1))
                             
    graficaSiracusa :: Int -> [Integer] -> IO ()
    graficaSiracusa n xs = plotLists [Key Nothing] (map (take n . siracusa) xs)
    
    collatz :: Integer -> Property
    collatz n = n>0 ==> elem 1 (siracusa n)
     

  5. luipromor
    siracusa        :: Integer -> [Integer]
    siracusa n | even n =  n : siracusa ( div n 2)
               | otherwise = n : siracusa ( 3*n +1)
    graficaSiracusa :: Int -> [Integer] -> IO ()
    graficaSiracusa n xs = plotLists [Key Nothing] $ map (take n.siracusa) xs
    conjetura_collar :: Integer -> Bool
    conjetura_collar x = elem 1 $ siracusa $ abs x +1
  6. javmarcha1
    import Graphics.Gnuplot.Simple
     
    siracusa :: Integer -> [Integer]
    siracusa x | odd x = x:siracusa (3*x+1)
               | otherwise = x:siracusa(div x 2)
     
    graficaSiracusa :: Int -> [Integer] -> IO ()
    graficaSiracusa n xs = plotLists [Key Nothing] [take n (siracusa x) | x <- xs]

Escribe tu solución

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