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]]

1 2	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  ==  []

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]]

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.

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 Comentarios

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) /= []

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) /= []

Responder

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

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

Responder

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)))

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)))

Responder

Conjetura de Grimm

Soluciones

Pensamiento

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico