Conjetura de Grimm
La conjetura de Grimm establece que a cada elemento de un conjunto de números compuestos se puede asignar número primo que lo divide, de forma que cada uno de los números primos elegidos es distinto de todos los demás. Más formalmente, si n+1, n+2, ..., n+k son números compuestos, entonces existen números primos p(i), distintos entre sí, tales que p(i) divide a n+i para 1 ≤ i ≤ k.
Diremos que la lista ps = [p(1),...,p(k)] es una sucesión de Grim para la lista xs = [x(1),...,x(k)] si p(i) son números primos distintos y p(i) divide a x(i), para 1 ≤ i ≤ k. Por ejemplo, 2, 5, 13, 3, 7 es una sucesión de Grim de 24, 25, 26, 27, 28.
Definir las funciones
compuestos :: Integer -> [Integer] sucesionesDeGrim :: [Integer] -> [[Integer]]
tales que
- (compuestos n) es la mayor lista de números enteros consecutivos empezando en n. Por ejemplo,
compuestos 24 == [24,25,26,27,28] compuestos 8 == [8,9,10] compuestos 15 == [15,16] compuestos 16 == [16] compuestos 17 == []
- (sucesionesDeGrim xs) es la lista de las sucesiones de Grim de xs. Por ejemplo,
sucesionesDeGrim [15,16] == [[3,2],[5,2]] sucesionesDeGrim [8,9,10] == [[2,3,5]] sucesionesDeGrim [9,10] == [[3,2],[3,5]] sucesionesDeGrim [24,25,26,27,28] == [[2,5,13,3,7]] sucesionesDeGrim [25,26,27,28] == [[5,2,3,7],[5,13,3,2],[5,13,3,7]]
Comprobar con QuickCheck la conjetura de Grim; es decir, para todo número n > 1, (sucesionesDeGrim (compuestos n)) es una lista no vacía.
Soluciones
import Data.List (nub) import Data.Numbers.Primes (isPrime, primeFactors) import Test.QuickCheck compuestos :: Integer -> [Integer] compuestos n = takeWhile (not . isPrime) [n..] sucesionesDeGrim :: [Integer] -> [[Integer]] sucesionesDeGrim [] = [[]] sucesionesDeGrim (x:xs) = [y:ys | y <- divisoresPrimos x , ys <- sucesionesDeGrim xs , y `notElem` ys] -- (divisoresPrimos n) es la lista de los divisores primos de n. Por -- ejemplo, -- divisoresPrimos 60 == [2,3,5] divisoresPrimos :: Integer -> [Integer] divisoresPrimos = nub . primeFactors -- La propiedad es conjeturaDeGrim :: Integer -> Property conjeturaDeGrim n = n > 1 ==> not (null (sucesionesDeGrim (compuestos n))) -- La comprobación es -- λ> quickCheck conjeturaDeGrim -- +++ OK, passed 100 tests.