abril 2019 – Página 2

Reparto de escaños por la ley d’Hont

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

El sistema D’Hondt es una fórmula creada por Victor d’Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

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

1	reparto :: Int -> [Int] -> [(Int,Int)]

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

   ghci> reparto 7 [340000,280000,160000,60000,15000]
   [(1,3),(2,3),(3,1)]
   ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
   [(1,9),(2,7),(3,4),(4,1)]

ghci> reparto 7 [340000,280000,160000,60000,15000]

[(1,3),(2,3),(3,1)]

ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]

[(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Soluciones

import Data.List (sort, group)

-- Para los ejemplos que siguen, se usará la siguiente ditribución de
-- votos entre 5 partidos.
ejVotos :: [Int]
ejVotos = [340000,280000,160000,60000,15000]

-- 1ª solución
-- ===========

reparto :: Int -> [Int] -> [(Int,Int)]
reparto n vs = 
  [(x,1 + length xs) | (x:xs) <- group (sort (repartoAux n vs))] 

-- (repartoAux n vs) es el número de los partidos, cuyos votos son vs, que
-- obtienen los n escaños. Por ejemplo,
--    ghci> repartoAux 7 ejVotos
--    [1,2,1,3,2,1,2]
repartoAux :: Int -> [Int] -> [Int]
repartoAux n vs = map snd (repartoAux' n vs)

-- (repartoAux' n vs) es la lista formada por los n restos mayores
-- correspondientes a la lista de votos vs. Por ejemplo,
--    ghci> repartoAux' 7 ejVotos
--    [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),
--     (93333,2)]
repartoAux' :: Int -> [Int] -> [(Int,Int)]
repartoAux' n vs = 
  take n (reverse (sort (concatMap (restos n) (votosPartidos vs))))

-- (votosPartidos vs) es la lista con los pares formados por los votos y
-- el número de cada partido. Por ejemplo, 
--    ghci> votosPartidos ejVotos
--    [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]
votosPartidos :: [Int] -> [(Int,Int)]
votosPartidos vs = zip vs [1..]

-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.
-- Por ejemplo, 
--    ghci> restos 5 (340000,1)
--    [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]
restos :: Int -> (Int,Int) -> [(Int,Int)]
restos n (x,i) = [(x `div` k,i) | k <- [1..n]]

-- 2ª solución
-- ===========

reparto2 :: Int -> [Int] -> [(Int,Int)]
reparto2 n xs = 
  ( map (\x -> (head x, length x))  
  . group  
  . sort  
  . map snd  
  . take n  
  . reverse  
  . sort
  ) [(x `div` i, p) | (x,p) <- zip xs [1..], i <- [1..n]]

import Data.List (sort, group)

-- Para los ejemplos que siguen, se usará la siguiente ditribución de

-- votos entre 5 partidos.

ejVotos :: [Int]

ejVotos = [340000,280000,160000,60000,15000]

-- 1ª solución

-- ===========

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

reparto n vs =

[(x,1 + length xs) | (x:xs) <- group (sort (repartoAux n vs))]

-- (repartoAux n vs) es el número de los partidos, cuyos votos son vs, que

-- obtienen los n escaños. Por ejemplo,

-- ghci> repartoAux 7 ejVotos

-- [1,2,1,3,2,1,2]

repartoAux :: Int -> [Int] -> [Int]

repartoAux n vs = map snd (repartoAux' n vs)

-- (repartoAux' n vs) es la lista formada por los n restos mayores

-- correspondientes a la lista de votos vs. Por ejemplo,

-- ghci> repartoAux' 7 ejVotos

-- [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),

-- (93333,2)]

repartoAux' :: Int -> [Int] -> [(Int,Int)]

repartoAux' n vs =

take n (reverse (sort (concatMap (restos n) (votosPartidos vs))))

-- (votosPartidos vs) es la lista con los pares formados por los votos y

-- el número de cada partido. Por ejemplo,

-- ghci> votosPartidos ejVotos

-- [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]

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

votosPartidos vs = zip vs [1..]

-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.

-- Por ejemplo,

-- ghci> restos 5 (340000,1)

-- [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]

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

restos n (x,i) = [(x `div` k,i) | k <- [1..n]]

-- 2ª solución

-- ===========

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

reparto2 n xs =

( map (\x -> (head x, length x))

. group

. sort

. map snd

. take n

. reverse

. sort

) [(x `div` i, p) | (x,p) <- zip xs [1..], i <- [1..n]]

Pensamiento

Sus cantares llevan
agua de remanso,
que parece quieta.
Y que no lo está;
mas no tiene prisa
por ir a la mar.

Antonio Machado

Elementos no repetidos

PorJosé A. Alonso 22-abril-20191-mayo-2019

Definir la función

   noRepetidos :: Eq a => [a] -> [a]

1	noRepetidos :: Eq a => [a] -> [a]

tal que (noRepetidos xs) es la lista de los elementos no repetidos de la lista xs. Por ejemplo,

   noRepetidos [3,2,5,2,4,7,3]  ==  [5,4,7]
   noRepetidos "noRepetidos"    ==  "nRptids"
   noRepetidos "Roma"           ==  "Roma"

noRepetidos [3,2,5,2,4,7,3] == [5,4,7]

noRepetidos "noRepetidos" == "nRptids"

noRepetidos "Roma" == "Roma"

Soluciones

import Test.QuickCheck

-- 1ª solución
-- ===========

noRepetidos :: Eq a => [a] -> [a]
noRepetidos xs = 
  [x | x <- xs, ocurrencias x xs == 1]
  
-- (ocurrencias x ys) es el número de ocurrencias de x en ys. Por
-- ejemplo,
--    ocurrencias 3 [3,2,5,2,4,7,3]  ==  2
--    ocurrencias 5 [3,2,5,2,4,7,3]  ==  1
ocurrencias :: Eq a => a -> [a] -> Int
ocurrencias x ys = 
  length [y | y <- ys, y == x]

-- 2ª solución
-- ===========
noRepetidos2 :: Eq a => [a] -> [a]
noRepetidos2 [] = []
noRepetidos2 (x:xs) | elem x xs = noRepetidos2 [y | y <- xs, y /= x]
                    | otherwise = x : noRepetidos2 xs

-- Equivalencia
-- ============

-- La propiedad de equivalencia es
prop_equivalencia :: [Int] -> Bool
prop_equivalencia xs =
  noRepetidos xs == noRepetidos2 xs

-- La comprobación es
--    ghci> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª solución

-- ===========

noRepetidos :: Eq a => [a] -> [a]

noRepetidos xs =

[x | x <- xs, ocurrencias x xs == 1]

-- (ocurrencias x ys) es el número de ocurrencias de x en ys. Por

-- ejemplo,

-- ocurrencias 3 [3,2,5,2,4,7,3] == 2

-- ocurrencias 5 [3,2,5,2,4,7,3] == 1

ocurrencias :: Eq a => a -> [a] -> Int

ocurrencias x ys =

length [y | y <- ys, y == x]

-- 2ª solución

-- ===========

noRepetidos2 :: Eq a => [a] -> [a]

noRepetidos2 [] = []

noRepetidos2 (x:xs) | elem x xs = noRepetidos2 [y | y <- xs, y /= x]

| otherwise = x : noRepetidos2 xs

-- Equivalencia

-- ============

-- La propiedad de equivalencia es

prop_equivalencia :: [Int] -> Bool

prop_equivalencia xs =

noRepetidos xs == noRepetidos2 xs

-- La comprobación es

-- ghci> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

Pensamiento

Y en perfecto rimo
— así a la vera del agua
el doble chopo del río.

Antonio Machado

Variación de la conjetura de Goldbach.

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

La conjetura de Goldbach afirma que

Todo número entero mayor que 5 se puede escribir como suma de tres números primos.

En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.

Definir las funciones

   sumas3PrimosDistintos      :: Int -> [(Int,Int,Int)]
   conKsumas3PrimosDistintos  :: Int -> Int -> [Int]
   noSonSumas3PrimosDistintos :: Int -> [Int]

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

conKsumas3PrimosDistintos :: Int -> Int -> [Int]

noSonSumas3PrimosDistintos :: Int -> [Int]

tales que

(sumas3PrimosDistintos n) es la lista de las descomposiciones decrecientes de n como tres primos distintos. Por ejemplo,

   sumas3PrimosDistintos 26  ==  [(13,11,2),(17,7,2),(19,5,2)]
   sumas3PrimosDistintos 18  ==  [(11,5,2),(13,3,2)]
   sumas3PrimosDistintos 10  ==  [(5,3,2)]
   sumas3PrimosDistintos 11  ==  []

sumas3PrimosDistintos 26 == [(13,11,2),(17,7,2),(19,5,2)]

sumas3PrimosDistintos 18 == [(11,5,2),(13,3,2)]

sumas3PrimosDistintos 10 == [(5,3,2)]

sumas3PrimosDistintos 11 == []

(conKsumas3PrimosDistintos k n) es la lista de los números menores o iguales que n que se pueden escribir en k forma distintas como suma de tres primos distintos. Por ejemplo,

   conKsumas3PrimosDistintos 3 99  ==  [26,27,29,32,36,42,46,48,54,58,60]
   conKsumas3PrimosDistintos 2 99  ==  [18,20,21,22,23,24,25,28,30,34,64,70]
   conKsumas3PrimosDistintos 1 99  ==  [10,12,14,15,16,19,40]
   conKsumas3PrimosDistintos 0 99  ==  [11,13,17]

conKsumas3PrimosDistintos 3 99 == [26,27,29,32,36,42,46,48,54,58,60]

conKsumas3PrimosDistintos 2 99 == [18,20,21,22,23,24,25,28,30,34,64,70]

conKsumas3PrimosDistintos 1 99 == [10,12,14,15,16,19,40]

conKsumas3PrimosDistintos 0 99 == [11,13,17]

(noSonSumas3PrimosDistintos n) es la lista de los números menores o iguales que n que no se pueden escribir como suma de tres primos distintos. Por ejemplo,

   noSonSumas3PrimosDistintos 99   ==  [11,13,17]
   noSonSumas3PrimosDistintos 500  ==  [11,13,17]

1 2	noSonSumas3PrimosDistintos 99 == [11,13,17] noSonSumas3PrimosDistintos 500 == [11,13,17]

Soluciones

import Data.Numbers.Primes

sumas3PrimosDistintos :: Int -> [(Int,Int,Int)]
sumas3PrimosDistintos n =
  [(a,b,c) | a <- takeWhile (<=n-5) primes
           , b <- takeWhile (<a) primes
           , let c = n - a - b
           , c < b
           , isPrime c]

conKsumas3PrimosDistintos :: Int -> Int -> [Int]
conKsumas3PrimosDistintos k n =
  [x | x <- [10..n]
     , length (sumas3PrimosDistintos x) == k]

noSonSumas3PrimosDistintos :: Int -> [Int]
noSonSumas3PrimosDistintos = conKsumas3PrimosDistintos 0

import Data.Numbers.Primes

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

sumas3PrimosDistintos n =

[(a,b,c) | a <- takeWhile (<=n-5) primes

, b <- takeWhile (<a) primes

, let c = n - a - b

, c < b

, isPrime c]

conKsumas3PrimosDistintos :: Int -> Int -> [Int]

conKsumas3PrimosDistintos k n =

[x | x <- [10..n]

, length (sumas3PrimosDistintos x) == k]

noSonSumas3PrimosDistintos :: Int -> [Int]

noSonSumas3PrimosDistintos = conKsumas3PrimosDistintos 0

Pensamiento

En su claro verso
se canta y medita
sin grito ni ceño.

Antonio Machado

Matriz dodecafónica

PorJosé A. Alonso 10-abril-201925-abril-2019

Como se explica en Create a Twelve-Tone Melody With a Twelve-Tone Matrix una matriz dodecafónica es una matriz de 12 filas y 12 columnas construidas siguiendo los siguientes pasos:

Se escribe en la primera fila una permutación de los números del 1 al 12. Por ejemplo,

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( )

Escribir la primera columna de forma que, para todo i (entre 2 y 12), a(i,1) es el número entre 1 y 12 que verifica la siguiente condición

     (a(1,1) - a(i,1)) = (a(1,i) - a(1,1)) (módulo 12)

1	(a(1,1) - a(i,1)) = (a(1,i) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila y la 1ª columna es

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (  5                                  )
     (  9                                  )
     (  1                                  )
     (  2                                  )
     ( 12                                  )
     ( 10                                  )
     ( 11                                  )
     (  6                                  )
     (  8                                  )
     (  7                                  )
     (  4                                  )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 )

( 9 )

( 1 )

( 2 )

( 12 )

( 10 )

( 11 )

( 6 )

( 8 )

( 7 )

( 4 )

Escribir la segunda fila de forma que, para todo j (entre 2 y 12), a(j,2) es el número entre 1 y 12 que verifica la siguiente condición

     (a(2,j) - a(1,j)) = (a(2,1) - a(1,1)) (módulo 12)

1	(a(2,j) - a(1,j)) = (a(2,1) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila, 1ª columna y 2ª fila es

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (  5  3 11  7  6  8 10  9  2 12  1  4 )
     (  9                                  )
     (  1                                  )
     (  2                                  )
     ( 12                                  )
     ( 10                                  )
     ( 11                                  )
     (  6                                  )
     (  8                                  )
     (  7                                  )
     (  4                                  )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 3 11 7 6 8 10 9 2 12 1 4 )

( 9 )

( 1 )

( 2 )

( 12 )

( 10 )

( 11 )

( 6 )

( 8 )

( 7 )

( 4 )

Las restantes filas se completan como la 2ª; es decir, para todo i (entre 3 y 12) y todo j (entre 2 y 12), a(i,j) es el número entre 1 y 12 que verifica la siguiente relación.

     (a(i,j) - a(1,j)) = (a(i,1) - a(1,1)) (módulo 12)

1	(a(i,j) - a(1,j)) = (a(i,1) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz dodecafónica es

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (  5  3 11  7  6  8 10  9  2 12  1  4 )
     (  9  7  3 11 10 12  2  1  6  4  5  8 )
     (  1 11  7  3  2  4  6  5 10  8  9 12 )
     (  2 12  8  4  3  5  7  6 11  9 10  1 )
     ( 12 10  6  2  1  3  5  4  9  7  8 11 )
     ( 10  8  4 12 11  1  3  2  7  5  6  9 )
     ( 11  9  5  1 12  2  4  3  8  6  7 10 )
     (  6  4 12  8  7  9 11 10  3  1  2  5 )
     (  8  6  2 10  9 11  1 12  5  3  4  7 )
     (  7  5  1  9  8 10 12 11  4  2  3  6 )
     (  4  2 10  6  5  7  9  8  1 11 12  3 )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 3 11 7 6 8 10 9 2 12 1 4 )

( 9 7 3 11 10 12 2 1 6 4 5 8 )

( 1 11 7 3 2 4 6 5 10 8 9 12 )

( 2 12 8 4 3 5 7 6 11 9 10 1 )

( 12 10 6 2 1 3 5 4 9 7 8 11 )

( 10 8 4 12 11 1 3 2 7 5 6 9 )

( 11 9 5 1 12 2 4 3 8 6 7 10 )

( 6 4 12 8 7 9 11 10 3 1 2 5 )

( 8 6 2 10 9 11 1 12 5 3 4 7 )

( 7 5 1 9 8 10 12 11 4 2 3 6 )

( 4 2 10 6 5 7 9 8 1 11 12 3 )

Definir la función

   matrizDodecafonica :: [Int] -> Matrix Int

1	matrizDodecafonica :: [Int] -> Matrix Int

tal que (matrizDodecafonica xs) es la matriz dodecafónica cuya primera fila es xs (que se supone que es una permutación de los números del 1 al 12). Por ejemplo,

   λ> matrizDodecafonica [3,1,9,5,4,6,8,7,12,10,11,2]
   (  3  1  9  5  4  6  8  7 12 10 11  2 )
   (  5  3 11  7  6  8 10  9  2 12  1  4 )
   (  9  7  3 11 10 12  2  1  6  4  5  8 )
   (  1 11  7  3  2  4  6  5 10  8  9 12 )
   (  2 12  8  4  3  5  7  6 11  9 10  1 )
   ( 12 10  6  2  1  3  5  4  9  7  8 11 )
   ( 10  8  4 12 11  1  3  2  7  5  6  9 )
   ( 11  9  5  1 12  2  4  3  8  6  7 10 )
   (  6  4 12  8  7  9 11 10  3  1  2  5 )
   (  8  6  2 10  9 11  1 12  5  3  4  7 )
   (  7  5  1  9  8 10 12 11  4  2  3  6 )
   (  4  2 10  6  5  7  9  8  1 11 12  3 )

λ> matrizDodecafonica [3,1,9,5,4,6,8,7,12,10,11,2]

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 3 11 7 6 8 10 9 2 12 1 4 )

( 9 7 3 11 10 12 2 1 6 4 5 8 )

( 1 11 7 3 2 4 6 5 10 8 9 12 )

( 2 12 8 4 3 5 7 6 11 9 10 1 )

( 12 10 6 2 1 3 5 4 9 7 8 11 )

( 10 8 4 12 11 1 3 2 7 5 6 9 )

( 11 9 5 1 12 2 4 3 8 6 7 10 )

( 6 4 12 8 7 9 11 10 3 1 2 5 )

( 8 6 2 10 9 11 1 12 5 3 4 7 )

( 7 5 1 9 8 10 12 11 4 2 3 6 )

( 4 2 10 6 5 7 9 8 1 11 12 3 )

Comprobar con QuickCheck para toda matriz dodecafónica D se verifican las siguientes propiedades:

todas las filas de D son permutaciones de los números 1 a 12,
todos los elementos de la diagonal de D son iguales y
la suma de todos los elementos de D es 936.

Nota: Este ejercicio ha sido propuesto por Francisco J. Hidalgo.

Soluciones

import Data.List
import Test.QuickCheck
import Data.Matrix

-- 1ª solución
-- ===========

matrizDodecafonica :: [Int] -> Matrix Int
matrizDodecafonica xs = matrix 12 12 f
  where f (1,j) = xs !! (j-1)
        f (i,1) = modulo12 (2 * f (1,1) - f (1,i)) 
        f (i,j) = modulo12 (f (1,j) + f (i,1) - f (1,1)) 
        modulo12 0  = 12
        modulo12 12 = 12
        modulo12 x  = x `mod` 12
  
-- 2ª solución
-- ===========

matrizDodecafonica2 :: [Int] -> Matrix Int
matrizDodecafonica2 xs = fromLists (secuencias xs)

secuencias :: [Int] -> [[Int]]
secuencias xs = [secuencia a xs | a <- inversa xs]

inversa :: [Int] -> [Int]
inversa xs = map conv (map (\x -> (-x) + 2* (abs a)) xs)
  where a = head xs
        
secuencia :: Int -> [Int] -> [Int]
secuencia n xs = [conv (a+(n-b)) | a <- xs] 
  where b = head xs

conv :: Int -> Int
conv n | n == 0 = 12
       | n < 0 = conv (n+12)
       | n > 11 = conv (mod n 12)
       | otherwise = n          

-- Propiedades
-- ===========

-- Las propiedades son
prop_dodecafonica :: Int -> Property
prop_dodecafonica n = 
  n >= 0 ==>
  all esPermutacion (toLists d)
  && all (== d!(1,1)) [d!(i,i) | i <- [2..12]]
  && sum d == 936
  where xss = permutations [1..12]
        k   = n `mod` product [1..12]
        d   = matrizDodecafonica (xss !! k)
        esPermutacion ys = sort ys == [1..12]

-- La comprobación es
--    λ> quickCheck prop_dodecafonica
--    +++ OK, passed 100 tests.

import Data.List

import Test.QuickCheck

import Data.Matrix

-- 1ª solución

-- ===========

matrizDodecafonica :: [Int] -> Matrix Int

matrizDodecafonica xs = matrix 12 12 f

where f (1,j) = xs !! (j-1)

f (i,1) = modulo12 (2 * f (1,1) - f (1,i))

f (i,j) = modulo12 (f (1,j) + f (i,1) - f (1,1))

modulo12 0 = 12

modulo12 12 = 12

modulo12 x = x `mod` 12

-- 2ª solución

-- ===========

matrizDodecafonica2 :: [Int] -> Matrix Int

matrizDodecafonica2 xs = fromLists (secuencias xs)

secuencias :: [Int] -> [[Int]]

secuencias xs = [secuencia a xs | a <- inversa xs]

inversa :: [Int] -> [Int]

inversa xs = map conv (map (\x -> (-x) + 2* (abs a)) xs)

where a = head xs

secuencia :: Int -> [Int] -> [Int]

secuencia n xs = [conv (a+(n-b)) | a <- xs]

where b = head xs

conv :: Int -> Int

conv n | n == 0 = 12

| n < 0 = conv (n+12)

| n > 11 = conv (mod n 12)

| otherwise = n

-- Propiedades

-- ===========

-- Las propiedades son

prop_dodecafonica :: Int -> Property

prop_dodecafonica n =

n >= 0 ==>

all esPermutacion (toLists d)

&& all (== d!(1,1)) [d!(i,i) | i <- [2..12]]

&& sum d == 936

where xss = permutations [1..12]

k = n `mod` product [1..12]

d = matrizDodecafonica (xss !! k)

esPermutacion ys = sort ys == [1..12]

-- La comprobación es

-- λ> quickCheck prop_dodecafonica

-- +++ OK, passed 100 tests.

Pensamiento

Como el olivar,
mucho fruto lleva,
poca sombra da.

Antonio Machado

La conjetura de Collatz

PorJosé A. Alonso 9-abril-201926-marzo-2022

La conjetura de Collatz, conocida también como conjetura 3n+1, fue enunciada por Lothar Collatz en 1937 y, hasta la fecha, no se ha resuelto.

La conjetura hace referencia a una propiedad de las sucesiones de Siracusa. La sucesión de Siracusa de un número entero positivo x es la sucesión cuyo primer término es x y el siguiente de un término se obtiene dividiéndolo entre 2, si es par o multiplicándolo por 3 y sumándole 1, si es impar. Por ejemplo, la sucesión de Siracusa de 12 es

   12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

1	12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

La conjetura de Collatz afirma que para todo número entero positivo x, el 1 pertenece a la sucesión de Siracusa de x.

Definir las funciones

   siracusa        :: Integer -> [Integer]
   graficaSiracusa :: Int -> [Integer] -> IO ()

1 2	siracusa :: Integer -> [Integer] graficaSiracusa :: Int -> [Integer] -> IO ()

tales que

(siracusa x) es la sucesión de Siracusa de x. Por ejemplo,

     λ> take 20 (siracusa 12)
     [12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]
     λ> take 20 (siracusa 22)
     [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]

λ> take 20 (siracusa 12)

[12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]

λ> take 20 (siracusa 22)

[22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]

(graficaSiracusa n xs) dibuja los n primeros términos de las sucesiones de Siracusas de los elementos de xs. Por ejemplo, (graficaSiracusa 100 [27]) dibuja

y (graficaSiracusa 150 [1..1000]) dibuja

Comprobar con QuickCheck la conjetura de Collatz.

Soluciones

import Test.QuickCheck
import Graphics.Gnuplot.Simple

-- 1ª definición de siracusa
-- =========================

siracusa :: Integer -> [Integer]
siracusa n | even n    = n : siracusa (n `div` 2)
           | otherwise = n : siracusa (3*n+1)

-- 2ª definición de siracusa
-- =========================

siracusa2 :: Integer -> [Integer]
siracusa2 = iterate siguiente 
  where siguiente x | even x    = x `div` 2
                    | otherwise = 3*x+1

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> siracusa 12 !! (10^6)
--    4
--    (0.55 secs, 362,791,008 bytes)
--    λ> siracusa 12 !! (2*10^6)
--    2
--    (1.05 secs, 725,456,376 bytes)
--    λ> siracusa2 12 !! (10^6)
--    4
--    (1.66 secs, 647,189,664 bytes)
--    λ> siracusa2 12 !! (2*10^6)
--    2
--    (3.11 secs, 1,294,286,792 bytes)

-- Definición de graficaSiracusa
-- =============================

graficaSiracusa :: Int -> [Integer] -> IO ()
graficaSiracusa n xs =
  plotLists [ Key Nothing
            , PNG "La_conjetura_de_Collatz.png"
            ]
            [take n (siracusa x) | x <- xs]

-- Comprobación de la conjetura
-- ============================

-- La conjetura es
conjeturaCollatz :: Positive Integer -> Bool
conjeturaCollatz (Positive n) =
  1 `elem` siracusa n

-- La comprobación es
--    λ> quickCheck conjeturaCollatz
--    +++ OK, passed 100 tests.

import Test.QuickCheck

import Graphics.Gnuplot.Simple

-- 1ª definición de siracusa

-- =========================

siracusa :: Integer -> [Integer]

siracusa n | even n = n : siracusa (n `div` 2)

| otherwise = n : siracusa (3*n+1)

-- 2ª definición de siracusa

-- =========================

siracusa2 :: Integer -> [Integer]

siracusa2 = iterate siguiente

where siguiente x | even x = x `div` 2

| otherwise = 3*x+1

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> siracusa 12 !! (10^6)

-- 4

-- (0.55 secs, 362,791,008 bytes)

-- λ> siracusa 12 !! (2*10^6)

-- 2

-- (1.05 secs, 725,456,376 bytes)

-- λ> siracusa2 12 !! (10^6)

-- 4

-- (1.66 secs, 647,189,664 bytes)

-- λ> siracusa2 12 !! (2*10^6)

-- 2

-- (3.11 secs, 1,294,286,792 bytes)

-- Definición de graficaSiracusa

-- =============================

graficaSiracusa :: Int -> [Integer] -> IO ()

graficaSiracusa n xs =

plotLists [ Key Nothing

, PNG "La_conjetura_de_Collatz.png"

]

[take n (siracusa x) | x <- xs]

-- Comprobación de la conjetura

-- ============================

-- La conjetura es

conjeturaCollatz :: Positive Integer -> Bool

conjeturaCollatz (Positive n) =

1 `elem` siracusa n

-- La comprobación es

-- λ> quickCheck conjeturaCollatz

-- +++ OK, passed 100 tests.

Pensamiento

Que el caminante es suma del camino …

Antonio Machado

Meses: abril 2019

Elementos no repetidos

Soluciones

Pensamiento

Variación de la conjetura de Goldbach.

Soluciones

Pensamiento

Matriz dodecafónica

Soluciones

Pensamiento

La conjetura de Collatz

Soluciones

Pensamiento

Entradas recientes

Buscar

Correo electrónico