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
1 |
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
1 2 |
siracusa :: Integer -> [Integer] graficaSiracusa :: Int -> [Integer] -> IO () |
tales que
- (siracusa x) es la sucesión de Siracusa de x. Por ejemplo,
1 2 3 4 |
λ> 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
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 Comentarios