fromList

Conjetura de las familias estables por uniones

PorJosé A. Alonso 24-abril-20201-mayo-2020

La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.

Una familia de conjuntos es estable por uniones si la unión de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {∅, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.

La conjetura afirma que toda familia no vacía estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.

Definir las funciones

   esEstable :: Ord a => Set (Set a) -> Bool
   familiasEstables :: Ord a => Set a -> Set (Set (Set a))
   mayoritarios :: Ord a => Set (Set a) -> [a]
   conjeturaFrankl :: Int -> Bool

esEstable :: Ord a => Set (Set a) -> Bool

familiasEstables :: Ord a => Set a -> Set (Set (Set a))

mayoritarios :: Ord a => Set (Set a) -> [a]

conjeturaFrankl :: Int -> Bool

tales que

(esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,

     λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])
     True
     λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])
     False
     λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])
     True

λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])

True

λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])

False

λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])

True

(familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,

     λ> familiasEstables (fromList [1..2])
     fromList
       [ fromList []
       , fromList [fromList []]
       , fromList [fromList [],fromList [1]]
       , fromList [fromList [],fromList [1],fromList [1,2]],
         fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
       , fromList [fromList [],fromList [1,2]]
       , fromList [fromList [],fromList [1,2],fromList [2]]
       , fromList [fromList [],fromList [2]]
       , fromList [fromList [1]]
       , fromList [fromList [1],fromList [1,2]]
       , fromList [fromList [1],fromList [1,2],fromList [2]]
       , fromList [fromList [1,2]]
       , fromList [fromList [1,2],fromList [2]]
       , fromList [fromList [2]]]
     λ> size (familiasEstables (fromList [1,2]))
     14
     λ> size (familiasEstables (fromList [1..3]))
     122
     λ> size (familiasEstables (fromList [1..4]))
     4960

λ> familiasEstables (fromList [1..2])

fromList

[ fromList []

, fromList [fromList []]

, fromList [fromList [],fromList [1]]

, fromList [fromList [],fromList [1],fromList [1,2]],

fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]

, fromList [fromList [],fromList [1,2]]

, fromList [fromList [],fromList [1,2],fromList [2]]

, fromList [fromList [],fromList [2]]

, fromList [fromList [1]]

, fromList [fromList [1],fromList [1,2]]

, fromList [fromList [1],fromList [1,2],fromList [2]]

, fromList [fromList [1,2]]

, fromList [fromList [1,2],fromList [2]]

, fromList [fromList [2]]]

λ> size (familiasEstables (fromList [1,2]))

λ> size (familiasEstables (fromList [1..3]))

122

λ> size (familiasEstables (fromList [1..4]))

4960

(mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,

     mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]
     mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []

1 2	mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3] mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []

(conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,…,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.

     conjeturaFrankl 2  ==  True
     conjeturaFrankl 3  ==  True
     conjeturaFrankl 4  ==  True

conjeturaFrankl 2 == True

conjeturaFrankl 3 == True

conjeturaFrankl 4 == True

Soluciones

import Data.Set  as S ( Set
                      , delete
                      , deleteFindMin
                      , empty
                      , filter
                      , fromList
                      , insert
                      , map
                      , member
                      , null
                      , singleton
                      , size
                      , toList
                      , union
                      , unions
                      )
import Data.List as L ( filter
                      , null
                      )

esEstable :: Ord a => Set (Set a) -> Bool
esEstable xss =
  and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss
                                    , zs <- toList yss]

-- (seleccciones xs) es la lista de los pares formada por un elemento de
-- xs y los restantes elementos. Por ejemplo,
--    λ> selecciones (fromList [3,2,5])
--    [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])]
selecciones :: Ord a => Set a -> [(a,Set a)]
selecciones xs =
  [(x,delete x xs) | x <- toList xs] 

familiasEstables :: Ord a => Set a -> Set (Set (Set a))
familiasEstables xss =
  S.filter esEstable (familias xss)

-- (familias c) es la familia formadas con elementos de c. Por ejemplo,
--    λ> mapM_ print (familias (fromList [1,2]))
--    fromList []
--    fromList [fromList []]
--    fromList [fromList [],fromList [1]]
--    fromList [fromList [],fromList [1],fromList [1,2]]
--    fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
--    fromList [fromList [],fromList [1],fromList [2]]
--    fromList [fromList [],fromList [1,2]]
--    fromList [fromList [],fromList [1,2],fromList [2]]
--    fromList [fromList [],fromList [2]]
--    fromList [fromList [1]]
--    fromList [fromList [1],fromList [1,2]]
--    fromList [fromList [1],fromList [1,2],fromList [2]]
--    fromList [fromList [1],fromList [2]]
--    fromList [fromList [1,2]]
--    fromList [fromList [1,2],fromList [2]]
--    fromList [fromList [2]]
--    λ> size (familias (fromList [1,2]))
--    16
--    λ> size (familias (fromList [1,2,3]))
--    256
--    λ> size (familias (fromList [1,2,3,4]))
--    65536
familias :: Ord a => Set a -> Set (Set (Set a))
familias c =
  subconjuntos (subconjuntos c)

-- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo,
--    λ> mapM_ print (subconjuntos (fromList [1,2,3]))
--    fromList []
--    fromList [1]
--    fromList [1,2]
--    fromList [1,2,3]
--    fromList [1,3]
--    fromList [2]
--    fromList [2,3]
--    fromList [3]
subconjuntos :: Ord a => Set a -> Set (Set a)
subconjuntos c
  | S.null c  = singleton empty
  | otherwise = S.map (insert x) sr `union` sr
  where (x,rc) = deleteFindMin c
        sr     = subconjuntos rc

-- (elementosFamilia f) es el conjunto de los elementos de los elementos
-- de la familia f. Por ejemplo, 
--    λ> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]])
--    fromList [1,2,5]
elementosFamilia :: Ord a => Set (Set a) -> Set a
elementosFamilia = unions . toList

-- (nOcurrencias f x) es el número de conjuntos de la familia f a los
-- que pertenece el elemento x. Por ejemplo,
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1
nOcurrencias :: Ord a => Set (Set a) -> a -> Int
nOcurrencias f x =
  length (L.filter (x `member`) (toList f))

mayoritarios :: Ord a => Set (Set a) -> [a]
mayoritarios f =
  [x | x <- toList (elementosFamilia f)
     , nOcurrencias f x >= n]
  where n = (1 + size f) `div` 2

conjeturaFrankl :: Int -> Bool
conjeturaFrankl n =
  and [ not (L.null (mayoritarios f))
      | f <- fs
      , f /= fromList []
      , f /= fromList [empty]]
  where fs = toList (familiasEstables (fromList [1..n]))


-- conjeturaFrankl' :: Int -> Bool
conjeturaFrankl' n =
  [f | f <- fs
     , L.null (mayoritarios f)
     , f /= fromList []
     , f /= fromList [empty]]
  where fs = toList (familiasEstables (fromList [1..n]))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

import Data.Set as S ( Set

, delete

, deleteFindMin

, empty

, filter

, fromList

, insert

, map

, member

, null

, singleton

, size

, toList

, union

, unions

)

import Data.List as L ( filter

, null

)

esEstable :: Ord a => Set (Set a) -> Bool

esEstable xss =

and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss

, zs <- toList yss]

-- (seleccciones xs) es la lista de los pares formada por un elemento de

-- xs y los restantes elementos. Por ejemplo,

-- λ> selecciones (fromList [3,2,5])

-- [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])]

selecciones :: Ord a => Set a -> [(a,Set a)]

selecciones xs =

[(x,delete x xs) | x <- toList xs]

familiasEstables :: Ord a => Set a -> Set (Set (Set a))

familiasEstables xss =

S.filter esEstable (familias xss)

-- (familias c) es la familia formadas con elementos de c. Por ejemplo,

-- λ> mapM_ print (familias (fromList [1,2]))

-- fromList []

-- fromList [fromList []]

-- fromList [fromList [],fromList [1]]

-- fromList [fromList [],fromList [1],fromList [1,2]]

-- fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]

-- fromList [fromList [],fromList [1],fromList [2]]

-- fromList [fromList [],fromList [1,2]]

-- fromList [fromList [],fromList [1,2],fromList [2]]

-- fromList [fromList [],fromList [2]]

-- fromList [fromList [1]]

-- fromList [fromList [1],fromList [1,2]]

-- fromList [fromList [1],fromList [1,2],fromList [2]]

-- fromList [fromList [1],fromList [2]]

-- fromList [fromList [1,2]]

-- fromList [fromList [1,2],fromList [2]]

-- fromList [fromList [2]]

-- λ> size (familias (fromList [1,2]))

-- 16

-- λ> size (familias (fromList [1,2,3]))

-- 256

-- λ> size (familias (fromList [1,2,3,4]))

-- 65536

familias :: Ord a => Set a -> Set (Set (Set a))

familias c =

subconjuntos (subconjuntos c)

-- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo,

-- λ> mapM_ print (subconjuntos (fromList [1,2,3]))

-- fromList []

-- fromList [1]

-- fromList [1,2]

-- fromList [1,2,3]

-- fromList [1,3]

-- fromList [2]

-- fromList [2,3]

-- fromList [3]

subconjuntos :: Ord a => Set a -> Set (Set a)

subconjuntos c

| S.null c = singleton empty

| otherwise = S.map (insert x) sr `union` sr

where (x,rc) = deleteFindMin c

sr = subconjuntos rc

-- (elementosFamilia f) es el conjunto de los elementos de los elementos

-- de la familia f. Por ejemplo,

-- λ> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]])

-- fromList [1,2,5]

elementosFamilia :: Ord a => Set (Set a) -> Set a

elementosFamilia = unions . toList

-- (nOcurrencias f x) es el número de conjuntos de la familia f a los

-- que pertenece el elemento x. Por ejemplo,

-- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2

-- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0

-- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1

nOcurrencias :: Ord a => Set (Set a) -> a -> Int

nOcurrencias f x =

length (L.filter (x `member`) (toList f))

mayoritarios :: Ord a => Set (Set a) -> [a]

mayoritarios f =

[x | x <- toList (elementosFamilia f)

, nOcurrencias f x >= n]

where n = (1 + size f) `div` 2

conjeturaFrankl :: Int -> Bool

conjeturaFrankl n =

and [ not (L.null (mayoritarios f))

| f <- fs

, f /= fromList []

, f /= fromList [empty]]

where fs = toList (familiasEstables (fromList [1..n]))

-- conjeturaFrankl' :: Int -> Bool

conjeturaFrankl' n =

[f | f <- fs

, L.null (mayoritarios f)

, f /= fromList []

, f /= fromList [empty]]

where fs = toList (familiasEstables (fromList [1..n]))

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Conjetura de las familias estables por uniones

PorJosé A. Alonso 5-abril-201925-abril-2021

La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.

La conjetura afirma que toda familia no vacía estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.

Definir las funciones

   esEstable :: Ord a => Set (Set a) -> Bool
   familiasEstables :: Ord a => Set a -> Set (Set (Set a))
   mayoritarios :: Ord a => Set (Set a) -> [a]
   conjeturaFrankl :: Int -> Bool

esEstable :: Ord a => Set (Set a) -> Bool

familiasEstables :: Ord a => Set a -> Set (Set (Set a))

mayoritarios :: Ord a => Set (Set a) -> [a]

conjeturaFrankl :: Int -> Bool

tales que

(esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,

     λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])
     True
     λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])
     False
     λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])
     True

λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])

True

λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])

False

λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])

True

(familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,

     λ> familiasEstables (fromList [1..2])
     fromList
       [ fromList []
       , fromList [fromList []]
       , fromList [fromList [],fromList [1]]
       , fromList [fromList [],fromList [1],fromList [1,2]],
         fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
       , fromList [fromList [],fromList [1,2]]
       , fromList [fromList [],fromList [1,2],fromList [2]]
       , fromList [fromList [],fromList [2]]
       , fromList [fromList [1]]
       , fromList [fromList [1],fromList [1,2]]
       , fromList [fromList [1],fromList [1,2],fromList [2]]
       , fromList [fromList [1,2]]
       , fromList [fromList [1,2],fromList [2]]
       , fromList [fromList [2]]]
     λ> size (familiasEstables (fromList [1,2]))
     14
     λ> size (familiasEstables (fromList [1..3]))
     122
     λ> size (familiasEstables (fromList [1..4]))
     4960

λ> familiasEstables (fromList [1..2])

fromList

[ fromList []

, fromList [fromList []]

, fromList [fromList [],fromList [1]]

, fromList [fromList [],fromList [1],fromList [1,2]],

fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]

, fromList [fromList [],fromList [1,2]]

, fromList [fromList [],fromList [1,2],fromList [2]]

, fromList [fromList [],fromList [2]]

, fromList [fromList [1]]

, fromList [fromList [1],fromList [1,2]]

, fromList [fromList [1],fromList [1,2],fromList [2]]

, fromList [fromList [1,2]]

, fromList [fromList [1,2],fromList [2]]

, fromList [fromList [2]]]

λ> size (familiasEstables (fromList [1,2]))

λ> size (familiasEstables (fromList [1..3]))

122

λ> size (familiasEstables (fromList [1..4]))

4960

(mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,

     mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]
     mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []

1 2	mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3] mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []

(conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,…,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.

     conjeturaFrankl 2  ==  True
     conjeturaFrankl 3  ==  True
     conjeturaFrankl 4  ==  True

conjeturaFrankl 2 == True

conjeturaFrankl 3 == True

conjeturaFrankl 4 == True

Soluciones

import Data.Set  as S ( Set
                      , delete
                      , deleteFindMin
                      , empty
                      , filter
                      , fromList
                      , insert
                      , map
                      , member
                      , null
                      , singleton
                      , size
                      , toList
                      , union
                      , unions
                      )
import Data.List as L ( filter
                      , null
                      )

esEstable :: Ord a => Set (Set a) -> Bool
esEstable xss =
  and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss
                                    , zs <- toList yss]

-- (seleccciones xs) es la lista de los pares formada por un elemento de
-- xs y los restantes elementos. Por ejemplo,
--    λ> selecciones (fromList [3,2,5])
--    [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])]
selecciones :: Ord a => Set a -> [(a,Set a)]
selecciones xs =
  [(x,delete x xs) | x <- toList xs] 

familiasEstables :: Ord a => Set a -> Set (Set (Set a))
familiasEstables xss =
  S.filter esEstable (familias xss)

-- (familias c) es la familia formadas con elementos de c. Por ejemplo,
--    λ> mapM_ print (familias (fromList [1,2]))
--    fromList []
--    fromList [fromList []]
--    fromList [fromList [],fromList [1]]
--    fromList [fromList [],fromList [1],fromList [1,2]]
--    fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
--    fromList [fromList [],fromList [1],fromList [2]]
--    fromList [fromList [],fromList [1,2]]
--    fromList [fromList [],fromList [1,2],fromList [2]]
--    fromList [fromList [],fromList [2]]
--    fromList [fromList [1]]
--    fromList [fromList [1],fromList [1,2]]
--    fromList [fromList [1],fromList [1,2],fromList [2]]
--    fromList [fromList [1],fromList [2]]
--    fromList [fromList [1,2]]
--    fromList [fromList [1,2],fromList [2]]
--    fromList [fromList [2]]
--    λ> size (familias (fromList [1,2]))
--    16
--    λ> size (familias (fromList [1,2,3]))
--    256
--    λ> size (familias (fromList [1,2,3,4]))
--    65536
familias :: Ord a => Set a -> Set (Set (Set a))
familias c =
  subconjuntos (subconjuntos c)

-- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo,
--    λ> mapM_ print (subconjuntos (fromList [1,2,3]))
--    fromList []
--    fromList [1]
--    fromList [1,2]
--    fromList [1,2,3]
--    fromList [1,3]
--    fromList [2]
--    fromList [2,3]
--    fromList [3]
subconjuntos :: Ord a => Set a -> Set (Set a)
subconjuntos c
  | S.null c  = singleton empty
  | otherwise = S.map (insert x) sr `union` sr
  where (x,rc) = deleteFindMin c
        sr     = subconjuntos rc

-- (elementosFamilia f) es el conjunto de los elementos de los elementos
-- de la familia f. Por ejemplo, 
--    λ> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]])
--    fromList [1,2,5]
elementosFamilia :: Ord a => Set (Set a) -> Set a
elementosFamilia = unions . toList

-- (nOcurrencias f x) es el número de conjuntos de la familia f a los
-- que pertenece el elemento x. Por ejemplo,
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1
nOcurrencias :: Ord a => Set (Set a) -> a -> Int
nOcurrencias f x =
  length (L.filter (x `member`) (toList f))

mayoritarios :: Ord a => Set (Set a) -> [a]
mayoritarios f =
  [x | x <- toList (elementosFamilia f)
     , nOcurrencias f x >= n]
  where n = (1 + size f) `div` 2

conjeturaFrankl :: Int -> Bool
conjeturaFrankl n =
  and [ not (L.null (mayoritarios f))
      | f <- fs
      , f /= fromList []
      , f /= fromList [empty]]
  where fs = toList (familiasEstables (fromList [1..n]))


-- conjeturaFrankl' :: Int -> Bool
conjeturaFrankl' n =
  [f | f <- fs
     , L.null (mayoritarios f)
     , f /= fromList []
     , f /= fromList [empty]]
  where fs = toList (familiasEstables (fromList [1..n]))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

import Data.Set as S ( Set

, delete

, deleteFindMin

, empty

, filter

, fromList

, insert

, map

, member

, null

, singleton

, size

, toList

, union

, unions

)

import Data.List as L ( filter

, null

)

esEstable :: Ord a => Set (Set a) -> Bool

esEstable xss =

and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss

, zs <- toList yss]

-- (seleccciones xs) es la lista de los pares formada por un elemento de

-- xs y los restantes elementos. Por ejemplo,

-- λ> selecciones (fromList [3,2,5])

-- [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])]

selecciones :: Ord a => Set a -> [(a,Set a)]

selecciones xs =

[(x,delete x xs) | x <- toList xs]

familiasEstables :: Ord a => Set a -> Set (Set (Set a))

familiasEstables xss =

S.filter esEstable (familias xss)

-- (familias c) es la familia formadas con elementos de c. Por ejemplo,

-- λ> mapM_ print (familias (fromList [1,2]))

-- fromList []

-- fromList [fromList []]

-- fromList [fromList [],fromList [1]]

-- fromList [fromList [],fromList [1],fromList [1,2]]

-- fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]

-- fromList [fromList [],fromList [1],fromList [2]]

-- fromList [fromList [],fromList [1,2]]

-- fromList [fromList [],fromList [1,2],fromList [2]]

-- fromList [fromList [],fromList [2]]

-- fromList [fromList [1]]

-- fromList [fromList [1],fromList [1,2]]

-- fromList [fromList [1],fromList [1,2],fromList [2]]

-- fromList [fromList [1],fromList [2]]

-- fromList [fromList [1,2]]

-- fromList [fromList [1,2],fromList [2]]

-- fromList [fromList [2]]

-- λ> size (familias (fromList [1,2]))

-- 16

-- λ> size (familias (fromList [1,2,3]))

-- 256

-- λ> size (familias (fromList [1,2,3,4]))

-- 65536

familias :: Ord a => Set a -> Set (Set (Set a))

familias c =

subconjuntos (subconjuntos c)

-- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo,

-- λ> mapM_ print (subconjuntos (fromList [1,2,3]))

-- fromList []

-- fromList [1]

-- fromList [1,2]

-- fromList [1,2,3]

-- fromList [1,3]

-- fromList [2]

-- fromList [2,3]

-- fromList [3]

subconjuntos :: Ord a => Set a -> Set (Set a)

subconjuntos c

| S.null c = singleton empty

| otherwise = S.map (insert x) sr `union` sr

where (x,rc) = deleteFindMin c

sr = subconjuntos rc

-- (elementosFamilia f) es el conjunto de los elementos de los elementos

-- de la familia f. Por ejemplo,

-- λ> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]])

-- fromList [1,2,5]

elementosFamilia :: Ord a => Set (Set a) -> Set a

elementosFamilia = unions . toList

-- (nOcurrencias f x) es el número de conjuntos de la familia f a los

-- que pertenece el elemento x. Por ejemplo,

-- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2

-- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0

-- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1

nOcurrencias :: Ord a => Set (Set a) -> a -> Int

nOcurrencias f x =

length (L.filter (x `member`) (toList f))

mayoritarios :: Ord a => Set (Set a) -> [a]

mayoritarios f =

[x | x <- toList (elementosFamilia f)

, nOcurrencias f x >= n]

where n = (1 + size f) `div` 2

conjeturaFrankl :: Int -> Bool

conjeturaFrankl n =

and [ not (L.null (mayoritarios f))

| f <- fs

, f /= fromList []

, f /= fromList [empty]]

where fs = toList (familiasEstables (fromList [1..n]))

-- conjeturaFrankl' :: Int -> Bool

conjeturaFrankl' n =

[f | f <- fs

, L.null (mayoritarios f)

, f /= fromList []

, f /= fromList [empty]]

where fs = toList (familiasEstables (fromList [1..n]))

Pensamiento

Pero tampoco es razón
desdeñar
consejo que es confesión.

Antonio Machado

Distancias entre primos consecutivos

PorJosé A. Alonso 4-abril-201711-abril-2017

Los 15 primeros números primos son

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

   1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

1	1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4

La distribución de las distancias es

   (1,1), (2,6), (4,5), (6,2)

1	(1,1), (2,6), (4,5), (6,2)

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

   (1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

1	(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

  cuentaDistancias        :: Int -> [(Int,Int)]
  frecuenciasDistancias   :: Int -> [(Int,Float)]
  graficas                :: [Int] -> IO ()
  distanciasMasFrecuentes :: Int -> [Int]

cuentaDistancias :: Int -> [(Int,Int)]

frecuenciasDistancias :: Int -> [(Int,Float)]

graficas :: [Int] -> IO ()

distanciasMasFrecuentes :: Int -> [Int]

tales que

(cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> cuentaDistancias 15
     [(1,1),(2,6),(4,5),(6,2)]
     λ> cuentaDistancias 100
     [(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

λ> cuentaDistancias 15

[(1,1),(2,6),(4,5),(6,2)]

λ> cuentaDistancias 100

[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

(frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> frecuenciasDistancias 15
     [(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
     λ> frecuenciasDistancias 30
     [(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

λ> frecuenciasDistancias 15

[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]

λ> frecuenciasDistancias 30

[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

(graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

(graficas [1000,2000,3000]) dibuja

y (graficas [100000,200000,300000]) dibuja
(distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,

     distanciasMasFrecuentes 15     ==  [2]
     distanciasMasFrecuentes 26     ==  [2,4]
     distanciasMasFrecuentes 32     ==  [4]
     distanciasMasFrecuentes 41     ==  [2,4,6]
     distanciasMasFrecuentes 77     ==  [6]
     distanciasMasFrecuentes 160    ==  [4,6]
     distanciasMasFrecuentes (10^6) == [6]

distanciasMasFrecuentes 15 == [2]

distanciasMasFrecuentes 26 == [2,4]

distanciasMasFrecuentes 32 == [4]

distanciasMasFrecuentes 41 == [2,4,6]

distanciasMasFrecuentes 77 == [6]

distanciasMasFrecuentes 160 == [4,6]

distanciasMasFrecuentes (10^6) == [6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Soluciones

import Data.Numbers.Primes
import qualified Data.Map as M 
import Graphics.Gnuplot.Simple
import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]
cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int
dicDistancias n =
  M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]
distancias n =
  zipWith (-) (tail xs) xs
  where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]
frecuenciasDistancias n =
  [(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]
  where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()
graficas ns =
  plotLists [Key Nothing]
            (map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]
distanciasMasFrecuentes n =
  M.keys (M.filter (==m) d)
  where d = dicDistancias n
        m = maximum (M.elems d)

-- La propiedad es
prop_distanciasMasFrecuentes :: Int -> Bool
prop_distanciasMasFrecuentes n =
  distanciasMasFrecuentes (161 + abs n) == [6]

import Data.Numbers.Primes

import qualified Data.Map as M

import Graphics.Gnuplot.Simple

import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]

cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int

dicDistancias n =

M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]

distancias n =

zipWith (-) (tail xs) xs

where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]

frecuenciasDistancias n =

[(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]

where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()

graficas ns =

plotLists [Key Nothing]

(map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]

distanciasMasFrecuentes n =

M.keys (M.filter (==m) d)

where d = dicDistancias n

m = maximum (M.elems d)

-- La propiedad es

prop_distanciasMasFrecuentes :: Int -> Bool

prop_distanciasMasFrecuentes n =

distanciasMasFrecuentes (161 + abs n) == [6]

Sucesión de trazas de dígitos de pi

PorJosé A. Alonso 17-febrero-201724-febrero-2017

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Las matrices de orden 1×1, 2×2, …, 5×5 formadas por los primeros dígitos de pi son

   ( 3 )  ( 3 1 )  ( 3 1 4 )  ( 3 1 4 1 )  ( 3 1 4 1 5 )
          ( 4 1 )  ( 1 5 9 )  ( 5 9 2 6 )  ( 9 2 6 5 3 )
                   ( 2 6 5 )  ( 5 3 5 8 )  ( 5 8 9 7 9 )
                              ( 9 7 9 3 )  ( 3 2 3 8 4 )
                                           ( 6 2 6 4 3 )

( 3 ) ( 3 1 ) ( 3 1 4 ) ( 3 1 4 1 ) ( 3 1 4 1 5 )

( 4 1 ) ( 1 5 9 ) ( 5 9 2 6 ) ( 9 2 6 5 3 )

( 2 6 5 ) ( 5 3 5 8 ) ( 5 8 9 7 9 )

( 9 7 9 3 ) ( 3 2 3 8 4 )

( 6 2 6 4 3 )

y sus trazas (es decir, sumas de los elementos de la diagonal principal) son 3, 4, 13, 20 y 25, respectivamente.

Definir la función

   trazas :: Int -> IO [Int]

1	trazas :: Int -> IO [Int]

tal que (trazas n) es la lista de las trazas de las matrices de orden 1×1, 2×2, 3×3, …, nxn formadas por los primeros dígitos de pi. Por ejemplo,

   λ> trazas 20
   [3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]
   λ> ts <- trazas 1000
   λ> maximum ts
   4644
   λ> maximum <$> trazas 1000
   4644

λ> trazas 20

[3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]

λ> ts <- trazas 1000

λ> maximum ts

4644

λ> maximum <$> trazas 1000

4644

Soluciones

import Data.Char (digitToInt)
import Data.Matrix (fromList, trace)

trazas :: Int -> IO [Int]
trazas n = do
  (d:_:ds) <- readFile "Digitos_de_pi.txt"
  let xs = map digitToInt (d:ds)
  return [trace (fromList k k xs) | k <- [1..n]]

import Data.Char (digitToInt)

import Data.Matrix (fromList, trace)

trazas :: Int -> IO [Int]

trazas n = do

(d:_:ds) <- readFile "Digitos_de_pi.txt"

let xs = map digitToInt (d:ds)

return [trace (fromList k k xs) | k <- [1..n]]

Conjetura de las familias estables por uniones

Soluciones

Otras soluciones

Conjetura de las familias estables por uniones

Soluciones

Pensamiento

Distancias entre primos consecutivos

Soluciones

Sucesión de trazas de dígitos de pi

Soluciones

Entradas recientes

Buscar

Correo electrónico