Menu Close

La conjetura de Collatz

José A. Alonso,

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

Inicial
, , , , , , , , , ,

6 soluciones de “La conjetura de Collatz”

  1. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.