Se considera la siguiente operaci\u00f3n, aplicable a cualquier n\u00famero entero positivo:<\/p>\n
Dado un n\u00famero cualquiera, podemos calcular su \u00f3rbita; es decir, las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita de 13 es<\/p>\n
\n 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...\n<\/pre>\nSi observamos este ejemplo, la \u00f3rbita de 13 es peri\u00f3dica, es decir, se repite indefinidamente a partir de un momento dado). La conjetura de Collatz dice que siempre alcanzaremos el 1 para cualquier n\u00famero con el que comencemos. Por ejemplo,<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n mayoresGeneradores :: Integer -> [Integer]\n<\/pre>\ntal que (mayoresGeneradores n) es la lista de los n\u00fameros menores o iguales que n cuyas \u00f3rbitas de Collatz son las de mayor longitud. Por ejemplo,<\/p>\n
\n mayoresGeneradores 20 == [18,19]\n mayoresGeneradores (10^6) == [837799]\n<\/pre>\nSoluciones<\/h4>\n\nimport qualified Data.MemoCombinators as Memo (integral)\nimport Data.List (genericLength, genericTake, maximumBy)\nimport Test.QuickCheck (Positive(..), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores :: Integer -> [Integer]\nmayoresGeneradores n =\n [x | (x,y) <- ps, y == m]\n where ps = genericTake n longitudesOrbitas\n m = maximum (map snd ps)\n\n-- longitudesOrbita es la lista de los n\u00fameros junto a las longitudes de\n-- las \u00f3rbitas de Collatz que generan. Por ejemplo,\n-- \u03bb> take 10 longitudesOrbitas\n-- [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]\nlongitudesOrbitas :: [(Integer, Integer)]\nlongitudesOrbitas =\n [(n, genericLength (collatz n)) | n <- [1..]]\n\n-- (siguiente n) es el siguiente de n en la sucesi\u00f3n de Collatz. Por\n-- ejemplo,\n-- siguiente 13 == 40\n-- siguiente 40 == 20\nsiguiente :: Integer -> Integer\nsiguiente n | even n = n `div` 2\n | otherwise = 3*n+1\n\n-- (collatz1 n) es la \u00f3rbita de Collatz de n hasta alcanzar el\n-- 1. Por ejemplo,\n-- collatz 13 == [13,40,20,10,5,16,8,4,2,1]\n\n-- 1\u00aa definici\u00f3n de collatz\ncollatz1 :: Integer -> [Integer]\ncollatz1 1 = [1]\ncollatz1 n = n : collatz1 (siguiente n)\n\n-- 2\u00aa definici\u00f3n de collatz\ncollatz2 :: Integer -> [Integer]\ncollatz2 n = takeWhile (\/=1) (iterate siguiente n) ++ [1]\n\n-- Usaremos la 2\u00aa definici\u00f3n de collatz\ncollatz :: Integer -> [Integer]\ncollatz = collatz2\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores2 :: Integer -> [Integer]\nmayoresGeneradores2 n =\n [x | (x,y) <- ps, y == m]\n where ps = [(x, longitudOrbita x) | x <- [1..n]]\n m = maximum (map snd ps)\n\n-- (longitudOrbita x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n-- longitudOrbita 13 == 10\nlongitudOrbita :: Integer -> Integer\nlongitudOrbita 1 = 1\nlongitudOrbita x = 1 + longitudOrbita (siguiente x)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores3 :: Integer -> [Integer]\nmayoresGeneradores3 n =\n [x | (x,y) <- ps, y == m]\n where ps = [(x, longitudOrbita2 x) | x <- [1..n]]\n m = maximum (map snd ps)\n\nlongitudOrbita2 :: Integer -> Integer\nlongitudOrbita2 = Memo.integral longitudOrbita2'\n where\n longitudOrbita2' 1 = 1\n longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)\n\n\n-- Equivalencia de definiciones\n-- ============================\n\n-- La propiedad es\nprop_mayoresGeneradores :: (Positive Integer) -> Bool\nprop_mayoresGeneradores (Positive n) =\n all (== (mayoresGeneradores n))\n [mayoresGeneradores2 n,\n mayoresGeneradores3 n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_mayoresGeneradores\n-- +++ OK, passed 100 tests.\n\n-- Comprobaci\u00f3n de eficiencia\n-- ==========================\n\n-- La comprobaci\u00f3n es\n-- \u03bb> mayoresGeneradores (10^5)\n-- [77031]\n-- (5.43 secs, 6,232,320,064 bytes)\n-- \u03bb> mayoresGeneradores2 (10^5)\n-- [77031]\n-- (7.68 secs, 5,238,991,616 bytes)\n-- \u03bb> mayoresGeneradores3 (10^5)\n-- [77031]\n-- (0.88 secs, 571,788,736 bytes)\n<\/pre>\n