Menu Close

Conjetura de Grimm

La conjetura de Grimm establece que a cada elemento de un conjunto de números compuestos consecutivos se puede asignar un 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.

Pensamiento

De encinar en encinar
se va fatigando el día.

Antonio Machado

3 soluciones de “Conjetura de Grimm

  1. anthormol
    import Data.Numbers.Primes
    import Data.List
    import Test.QuickCheck
     
    compuestos :: Integer -> [Integer]
    compuestos n
      | isPrime n = []
      | otherwise = [n..siguientePrimo n - 1]
     
    siguientePrimo :: Integer -> Integer
    siguientePrimo n = head (dropWhile (<= n) primes)               
     
    sucesionesDeGrim :: [Integer] -> [[Integer]]
    sucesionesDeGrim xs =
      [ys | ys <- map nub (nub (sequence [primeFactors x | x <- xs])),
            length ys == length xs]
     
    prop_Grim :: Integer -> Property
    prop_Grim n =
      n > 1 ==>  sucesionesDeGrim (compuestos n) /= []
  2. fercarnav
    import Data.Numbers.Primes
    import Data.List
    import Test.QuickCheck
     
    compuestos :: Integer -> [Integer]
    compuestos n
      | isPrime n = []
      | otherwise = [n..siguientePrimo n - 1]
     
    siguientePrimo :: Integer -> Integer
    siguientePrimo n = head (dropWhile (<= n) primes)    
     
    sucesionesDeGrim :: [Integer] -> [[Integer]]
    sucesionesDeGrim xs = nub (filter sinrepes (sequence (map (primeFactors) xs)))
     
    sinrepes :: [Integer] -> Bool
    sinrepes [] = True
    sinrepes (x:xs) = not (elem x xs) && sinrepes xs
  3. noeherbar
    import Data.Numbers.Primes
    import Data.List
    import Test.QuickCheck
     
    compuestos :: Integer -> [Integer]
    compuestos n = [n..head (dropWhile (<n) primes) - 1]
     
    sucesionesDeGrim :: [Integer] -> [[Integer]]
    sucesionesDeGrim xs =
      [ys | ys <- nub (sequence (map primeFactors xs))
          , nub ys == ys]
     
    prop4 :: Integer -> Property
    prop4 n = n > 1 ==> not (null (sucesionesDeGrim (compuestos n)))

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.