Conjetura de Collatz generalizada
Sea p un número primo. Toma un número natural positivo, si divisible entre un número primo menor que p divídelo entre el menor de dicho divisores, y en otro caso multiplícalo por p y súmale uno; si el resultado no es igual a uno, repite el proceso. Por ejemplo, para p = 7 y empezando en 42 el proceso es
42 -> 21 [= 42/2] -> 7 [= 21/3] -> 50 [= 7*7+1] -> 25 [= 50/5] -> 5 [= 25/5] -> 1 [= 5/5]
La conjetura de Collatz generalizada afirma que este proceso siempre acaba en un número finito de pasos.
Definir la función
collatzGeneral :: Integer -> Integer -> [Integer]
tal que (collatzGeneral p x) es la sucesión de los elementos obtenidos en el proceso anterior para el primo p enpezando en x. Por ejemplo,
take 15 (collatzGeneral 7 42) == [42,21,7,50,25,5,1,8,4,2,1,8,4,2,1] take 15 (collatzGeneral 3 6) == [6,3,10,5,16,8,4,2,1,4,2,1,4,2,1] take 15 (collatzGeneral 5 6) == [6,3,1,6,3,1,6,3,1,6,3,1,6,3,1] take 15 (collatzGeneral 7 6) == [6,3,1,8,4,2,1,8,4,2,1,8,4,2,1] take 15 (collatzGeneral 9 6) == [6,3,1,10,5,1,10,5,1,10,5,1,10,5,1]
Comprobar con QuickCheck que se verifica la conjetura de Collatz generalizada; es decir, para todos enteros positivos n, x si p es el primo n-ésimo entonces 1 pertenece a (collatzGeneral p x).
Nota: El ejercicio etá basado en el artículo Los primos de la conjetura de Collatz publicado la semana pasada por Francisco R. Villatoro en su blog La Ciencia de la Mula Francis.
Soluciones
import Data.Numbers.Primes (primeFactors, primes) import Test.QuickCheck collatzGeneral :: Integer -> Integer -> [Integer] collatzGeneral p x = iterate (siguiente p) x siguiente :: Integer -> Integer -> Integer siguiente p x | null xs = p * x + 1 | otherwise = x `div` head xs where xs = takeWhile (<p) (primeFactors x) prop_collatzGeneral :: Int -> Integer -> Property prop_collatzGeneral n x = n > 0 && x > 0 ==> 1 `elem` collatzGeneral p x where p = primes !! n -- La comprobación es -- λ> quickCheck prop_collatzGeneral -- +++ OK, passed 100 tests.