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.