El teorema de existencia de divisores afirma que
En cualquier subconjunto de {1, 2, …, 2m} con al menos m+1 elementos existen números distintos a, b tales que a divide a b.
Un conjunto de números naturales xs es mayoritario si existe un m tal que la lista de xs es un subconjunto de {1,2,…,2m} con al menos m+1 elementos. Por ejemplo, {2,3,5,6} porque es un subconjunto de {1,2,…,6} con más de 3 elementos.
Definir las funciones
divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
esMayoritario :: [Integer] -> Bool |
divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
esMayoritario :: [Integer] -> Bool
tales que
- (divisores xs) es la lista de pares de elementos distintos de (a,b) tales que a divide a b. Por ejemplo,
divisoresMultiplos [2,3,5,6] == [(2,6),(3,6)]
divisoresMultiplos [2,3,5] == []
divisoresMultiplos [4..8] == [(4,8)] |
divisoresMultiplos [2,3,5,6] == [(2,6),(3,6)]
divisoresMultiplos [2,3,5] == []
divisoresMultiplos [4..8] == [(4,8)]
- (esMayoritario xs) se verifica xs es mayoritario. Por ejemplo,
esMayoritario [2,3,5,6] == True
esMayoritario [2,3,5] == False |
esMayoritario [2,3,5,6] == True
esMayoritario [2,3,5] == False
Comprobar con QuickCheck el teorema de existencia de divisores; es decir, en cualquier conjunto mayoritario existen números distintos a, b tales que a divide a b. Para la comprobación se puede usar el siguiente generador de conjuntos mayoritarios
mayoritario :: Gen [Integer]
mayoritario = do
m' <- arbitrary
let m = 1 + abs m'
xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
return xs' |
mayoritario :: Gen [Integer]
mayoritario = do
m' <- arbitrary
let m = 1 + abs m'
xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
return xs'
con lo que la propiedad que hay que comprobar con QuickCheck es
teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
forAll mayoritario (not . null . divisoresMultiplos) |
teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
forAll mayoritario (not . null . divisoresMultiplos)
Soluciones
import Data.List (genericLength)
import Test.QuickCheck
divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
divisoresMultiplos xs =
[(x,y) | x <- xs
, y <- xs
, y /= x
, y `mod` x == 0]
esMayoritario :: [Integer] -> Bool
esMayoritario xs =
not (null xs) && length xs > ceiling (n / 2)
where n = fromIntegral (maximum xs)
-- Comprobación del teorema
-- ========================
-- La propiedad es
teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
forAll mayoritario (not . null . divisoresMultiplos)
-- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo,
-- λ> sample mayoritario
-- [1,2]
-- [2,5,7,8]
-- [1,2,8,10,14]
-- [3,8,11,12,13,15,18,19,22,23,25,26]
-- [1,3,4,6]
-- [3,6,9,11,12,14,17,19]
mayoritario :: Gen [Integer]
mayoritario = do
m' <- arbitrary
let m = 1 + abs m'
xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
return xs'
-- La comprobación es
-- λ> quickCheck teorema_de_existencia_de_divisores
-- +++ OK, passed 100 tests. |
import Data.List (genericLength)
import Test.QuickCheck
divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
divisoresMultiplos xs =
[(x,y) | x <- xs
, y <- xs
, y /= x
, y `mod` x == 0]
esMayoritario :: [Integer] -> Bool
esMayoritario xs =
not (null xs) && length xs > ceiling (n / 2)
where n = fromIntegral (maximum xs)
-- Comprobación del teorema
-- ========================
-- La propiedad es
teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
forAll mayoritario (not . null . divisoresMultiplos)
-- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo,
-- λ> sample mayoritario
-- [1,2]
-- [2,5,7,8]
-- [1,2,8,10,14]
-- [3,8,11,12,13,15,18,19,22,23,25,26]
-- [1,3,4,6]
-- [3,6,9,11,12,14,17,19]
mayoritario :: Gen [Integer]
mayoritario = do
m' <- arbitrary
let m = 1 + abs m'
xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
return xs'
-- La comprobación es
-- λ> quickCheck teorema_de_existencia_de_divisores
-- +++ OK, passed 100 tests.
Pensamiento
Guiomar, Guiomar,
mírame en ti castigado:
reo de haberte creado,
ya no te puedo olvidar.
Antonio Machado