enero 2016 – Exercitium

Agrupamiento por propiedad

PorJosé A. Alonso 29-enero-20165-febrero-2016

Definir la función

   agrupa :: (a -> Bool) -> [a] -> [[a]]

1	agrupa :: (a -> Bool) -> [a] -> [[a]]

tal que (agrupa p xs) es la lista obtenida separando los elementos consecutivos de xs que verifican la propiedad p de los que no la verifican. Por ejemplo,

   agrupa odd   [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[2,0,4],[9],[6,4],[5,7],[2]]
   agrupa even  [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1],[2,0,4],[9],[6,4],[5,7],[2]]
   agrupa (> 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1,2,0,4],[9,6],[4],[5,7],[2]]
   agrupa (< 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[1,2,0],[4,9,6,4,5,7],[2]]

agrupa odd [1,2,0,4,9,6,4,5,7,2] == [[1],[2,0,4],[9],[6,4],[5,7],[2]]

agrupa even [1,2,0,4,9,6,4,5,7,2] == [[],[1],[2,0,4],[9],[6,4],[5,7],[2]]

agrupa (> 4) [1,2,0,4,9,6,4,5,7,2] == [[],[1,2,0,4],[9,6],[4],[5,7],[2]]

agrupa (< 4) [1,2,0,4,9,6,4,5,7,2] == [[1,2,0],[4,9,6,4,5,7],[2]]

Comprobar con QuickCheck que para cualquier propiedad p y cualquier lista xs, la concatenación de (agrupa p xs) es xs; es decir,

   prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool
   prop_agrupa (Blind p) xs =
       concat (agrupa1 p xs) == xs

prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool

prop_agrupa (Blind p) xs =

concat (agrupa1 p xs) == xs

Nota. Usar la librería Test.QuickCheck.Modifiers.

Soluciones

import Test.QuickCheck
import Test.QuickCheck.Modifiers

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

agrupa1 :: (a -> Bool) -> [a] -> [[a]]
agrupa1 p [] = []
agrupa1 p xs = takeWhile p xs : agrupa1 (not . p) (dropWhile p xs)

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

agrupa2 :: (a -> Bool) -> [a] -> [[a]]
agrupa2 p [] = []
agrupa2 p xs = ys : agrupa2 (not . p) zs
    where (ys,zs) = span p xs

-- Propiedad
-- =========

-- La propiedad es
prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool
prop_agrupa (Blind p) xs =
    concat (agrupa1 p xs) == xs

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

import Test.QuickCheck

import Test.QuickCheck.Modifiers

-- 1ª solución

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

agrupa1 :: (a -> Bool) -> [a] -> [[a]]

agrupa1 p [] = []

agrupa1 p xs = takeWhile p xs : agrupa1 (not . p) (dropWhile p xs)

-- 2ª solución

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

agrupa2 :: (a -> Bool) -> [a] -> [[a]]

agrupa2 p [] = []

agrupa2 p xs = ys : agrupa2 (not . p) zs

where (ys,zs) = span p xs

-- Propiedad

-- =========

-- La propiedad es

prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool

prop_agrupa (Blind p) xs =

concat (agrupa1 p xs) == xs

-- La comprobación es

-- λ> quickCheck prop_agrupa

-- +++ OK, passed 100 tests.

De árboles a listas

PorJosé A. Alonso 27-enero-20163-febrero-2016

Los árboles binarios con datos en nodos y hojas se definen por

   data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

1	data Arbol a = H a \| N a (Arbol a) (Arbol a) deriving Show

Por ejemplo, el árbol

          3
         / \
        /   \
       4     7
      / \   / \
     5   0 0   3
    / \
   2   0

/ \

4 7

/ \ / \

5 0 0 3

/ \

2 0

se representa por

   ejArbol :: Arbol Integer
   ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

1 2	ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

Definir la función

   sucesores :: Arbol a -> [(a,[a])]

1	sucesores :: Arbol a -> [(a,[a])]

tal que (sucesores t) es la lista de los pares formados por los elementos del árbol t junto con sus sucesores. Por ejemplo,

   λ> sucesores ejArbol
   [(3,[4,7]),(4,[5,0]),(5,[2,0]),(2,[]),(0,[]),(0,[]),
    (7,[0,3]),(0,[]),(3,[])]

λ> sucesores ejArbol

[(3,[4,7]),(4,[5,0]),(5,[2,0]),(2,[]),(0,[]),(0,[]),

(7,[0,3]),(0,[]),(3,[])]

Soluciones

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

ejArbol :: Arbol Integer
ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

sucesores :: Arbol a -> [(a,[a])]
sucesores (H x)     = [(x,[])]
sucesores (N x i d) = (x, [raiz i, raiz d]) : sucesores i ++ sucesores d

raiz :: Arbol a -> a
raiz (H x)      = x
raiz (N x _ _ ) = x

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

ejArbol :: Arbol Integer

ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

sucesores :: Arbol a -> [(a,[a])]

sucesores (H x) = [(x,[])]

sucesores (N x i d) = (x, [raiz i, raiz d]) : sucesores i ++ sucesores d

raiz :: Arbol a -> a

raiz (H x) = x

raiz (N x _ _ ) = x

Conjunto de funciones

PorJosé A. Alonso 26-enero-20162-febrero-2016

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

[(1,2),(3,6)] es una función de [1,3] en [2,4,6];
[(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
[(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primer elemento es 1.

Definir la función

   funciones :: [a] -> [a] -> [[(a,a)]]

1	funciones :: [a] -> [a] -> [[(a,a)]]

tal que (funciones xs ys) es el conjunto de las funciones de xs en ys. Por ejemplo,

   λ> funciones [] [2,4,6]
   [[]]
   λ> funciones [3] [2,4,6]
   [[(3,2)],[(3,4)],[(3,6)]]
   λ> funciones [1,3] [2,4,6]
   [[(1,2),(3,2)], [(1,2),(3,4)], [(1,2),(3,6)], [(1,4),(3,2)], [(1,4),(3,4)],
    [(1,4),(3,6)], [(1,6),(3,2)], [(1,6),(3,4)], [(1,6),(3,6)]]

λ> funciones [] [2,4,6]

[[]]

λ> funciones [3] [2,4,6]

[[(3,2)],[(3,4)],[(3,6)]]

λ> funciones [1,3] [2,4,6]

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

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

Comprobar con QuickCheck que si xs es un conjunto con n elementos e ys un conjunto con m elementos, entonces (funciones xs ys) tiene m^n elementos.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

   λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones
   +++ OK, passed 100 tests.

1 2	λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones +++ OK, passed 100 tests.

Soluciones

import Test.QuickCheck

funciones :: [a] -> [a] -> [[(a,a)]]
funciones [] _      = [[]]
funciones (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]
    where fs = funciones xs ys

prop_funciones :: [Int] -> [Int] -> Bool
prop_funciones xs ys =
    length (funciones xs ys) == (length ys)^(length xs)

import Test.QuickCheck

funciones :: [a] -> [a] -> [[(a,a)]]

funciones [] _ = [[]]

funciones (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]

where fs = funciones xs ys

prop_funciones :: [Int] -> [Int] -> Bool

prop_funciones xs ys =

length (funciones xs ys) == (length ys)^(length xs)

Sumas digitales de primos consecutivos

PorJosé A. Alonso 22-enero-20161-mayo-2016

Definir la función

   primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

1	primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

tal que (primosConsecutivosConSumasDigitalesPrimas k) es la sucesión de listas de k primos consecutivos tales que las sumas ordenadas de sus dígitos también son primos consecutivos. Por ejemplo,

   λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2)
   [[2,3],[3,5],[5,7],[41,43],[43,47]]
   λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3)
   [[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]]
   λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4)
   [[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]]
   λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50
   [129197,129209,129221,129223]

λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2)

[[2,3],[3,5],[5,7],[41,43],[43,47]]

λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3)

[[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]]

λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4)

[[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]]

λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50

[129197,129209,129221,129223]

Soluciones

import Data.Char (digitToInt)
import Data.List (isPrefixOf, sort, tails)
import Data.Numbers.Primes

primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]
primosConsecutivosConSumasDigitalesPrimas k = 
    [xs | xs <- map (take k) (tails primes),
          primosConsecutivos (sort (map sumaDigital xs))]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [d] | d <- show n]

-- (sumaDigital n) es la suma de los dígitos de n. Por ejemplo, 
--    sumaDigital 325  ==  10
sumaDigital :: Integer -> Integer
sumaDigital = sum . digitos

-- (primosConsecutivos xs) se verifica si xs es una lista de primos
-- consecutivos. Por ejemplo,
--    primosConsecutivos [5,7,11]  ==  True
--    primosConsecutivos [5,7,17]  ==  False
primosConsecutivos :: [Integer] -> Bool
primosConsecutivos (x:xs) =
    isPrefixOf (x:xs) (dropWhile (<x) primes)

import Data.Char (digitToInt)

import Data.List (isPrefixOf, sort, tails)

import Data.Numbers.Primes

primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

primosConsecutivosConSumasDigitalesPrimas k =

[xs | xs <- map (take k) (tails primes),

primosConsecutivos (sort (map sumaDigital xs))]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 325 == [3,2,5]

digitos :: Integer -> [Integer]

digitos n = [read [d] | d <- show n]

-- (sumaDigital n) es la suma de los dígitos de n. Por ejemplo,

-- sumaDigital 325 == 10

sumaDigital :: Integer -> Integer

sumaDigital = sum . digitos

-- (primosConsecutivos xs) se verifica si xs es una lista de primos

-- consecutivos. Por ejemplo,

-- primosConsecutivos [5,7,11] == True

-- primosConsecutivos [5,7,17] == False

primosConsecutivos :: [Integer] -> Bool

primosConsecutivos (x:xs) =

isPrefixOf (x:xs) (dropWhile (<x) primes)

Referencias

Basado en el artículo DigitSums of some consecutive primes del blog Fun With Num3ers.

Antiimágenes en una función creciente

PorJosé A. Alonso 20-enero-201626-marzo-2022

Definir la función

   antiimagen :: (Int -> Int) -> Int -> Maybe Int

1	antiimagen :: (Int -> Int) -> Int -> Maybe Int

tal que (antiimagen f y) es justo el x tal que f(x) = y, si y pertenece a la imagen de la función creciente f, o nada, en caso contrario. Por ejemplo,

   antiimagen (^2) 25  ==  Just 5
   antiimagen (^3) 25  ==  Nothing

1 2	antiimagen (^2) 25 == Just 5 antiimagen (^3) 25 == Nothing

Nota. Se supone que f está definida sobre los números naturales.

Soluciones

-- 1ª definición
-- =============

antiimagen1 :: (Int -> Int) -> Int -> Maybe Int
antiimagen1 f y 
    | estaEnImagen f y = Just x
    | otherwise        = Nothing
    where x = head [x | x <- [0..], f x == y]

-- (estaEnImagen f y) se verifica si pertenece a la imagen de f. Por
-- ejemplo, 
--    estaEnImagen (^2) 25 == True
--    estaEnImagen (^2) 30 == False
estaEnImagen :: (Int -> Int) -> Int -> Bool
estaEnImagen f y = elem y (takeWhile (<=y) (imagen f)) 

-- (imagen f) es la imagen de f. Por ejemplo,
--    take 10 (imagen (^2))  ==  [0,1,4,9,16,25,36,49,64,81]
--    take 10 (imagen (*3))  ==  [0,3,6,9,12,15,18,21,24,27]
imagen :: (Int -> Int) -> [Int]
imagen f = map f [0..]

-- 2ª definición (con lookup y maxBound)
-- =====================================

antiimagen2 :: (Int -> Int) -> Int -> Maybe Int
antiimagen2 f y =
    lookup y (takeWhile (<= (y,maxBound)) [(f x, x) | x <- [0..]])

-- 1ª definición

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

antiimagen1 :: (Int -> Int) -> Int -> Maybe Int

antiimagen1 f y

| estaEnImagen f y = Just x

| otherwise = Nothing

where x = head [x | x <- [0..], f x == y]

-- (estaEnImagen f y) se verifica si pertenece a la imagen de f. Por

-- ejemplo,

-- estaEnImagen (^2) 25 == True

-- estaEnImagen (^2) 30 == False

estaEnImagen :: (Int -> Int) -> Int -> Bool

estaEnImagen f y = elem y (takeWhile (<=y) (imagen f))

-- (imagen f) es la imagen de f. Por ejemplo,

-- take 10 (imagen (^2)) == [0,1,4,9,16,25,36,49,64,81]

-- take 10 (imagen (*3)) == [0,3,6,9,12,15,18,21,24,27]

imagen :: (Int -> Int) -> [Int]

imagen f = map f [0..]

-- 2ª definición (con lookup y maxBound)

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

antiimagen2 :: (Int -> Int) -> Int -> Maybe Int

antiimagen2 f y =

lookup y (takeWhile (<= (y,maxBound)) [(f x, x) | x <- [0..]])

Relleno de matrices

PorJosé A. Alonso 19-enero-201626-enero-2016

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

   0 0 0 0 0    1 0 0 1 0
   0 0 0 0 0    1 0 0 1 0
   0 0 0 1 0    1 1 1 1 1
   1 0 0 0 0    1 1 1 1 1
   0 0 0 0 0    1 0 0 1 0

0 0 0 0 0 1 0 0 1 0

0 0 0 1 0 1 1 1 1 1

1 0 0 0 0 1 1 1 1 1

0 0 0 0 0 1 0 0 1 0

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

   type Matriz = Array (Int,Int) Int

1	type Matriz = Array (Int,Int) Int

por ejemplo, la matriz de la izquierda de la figura anterior se define por

   ej :: Matriz                  
   ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                                 0, 0, 0, 0, 0,
                                 0, 0, 0, 1, 0,
                                 1, 0, 0, 0, 0,
                                 0, 0, 0, 0, 0]

ej :: Matriz

ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,

0, 0, 0, 0, 0,

0, 0, 0, 1, 0,

1, 0, 0, 0, 0,

0, 0, 0, 0, 0]

Definir la función

   relleno :: Matriz -> Matriz

1	relleno :: Matriz -> Matriz

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

   λ> elems (relleno ej)
   [1,0,0,1,0,
    1,0,0,1,0,
    1,1,1,1,1,
    1,1,1,1,1,
    1,0,0,1,0]

λ> elems (relleno ej)

[1,0,0,1,0,

1,0,0,1,0,

1,1,1,1,1,

1,0,0,1,0]

Soluciones

import Data.Array

type Matriz = Array (Int,Int) Int

ej :: Matriz                  
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                              0, 0, 0, 0, 0,
                              0, 0, 0, 1, 0,
                              1, 0, 0, 0, 0,
                              0, 0, 0, 0, 0]

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

relleno1 :: Matriz -> Matriz
relleno1 p = 
    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    where (_,(m,n)) = bounds p
          f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1
                | 1 `elem` [p!(k,j) | k <- [1..m]] = 1
                | otherwise                        = 0

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

relleno2 :: Matriz -> Matriz
relleno2 p = 
    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    where (_,(m,n)) = bounds p
          filas     = filasConUno p
          columnas  = columnasConUno p
          f i j | i `elem` filas    = 1
                | j `elem` columnas = 1
                | otherwise         = 0

-- (filasConUno p) es la lista de las filas de p que tienen algún
-- uno. Por ejemplo,
--    filasConUno ej  ==  [3,4]
filasConUno :: Matriz -> [Int]
filasConUno p = [i | i <- [1..m], filaConUno p i]
    where (_,(m,n)) = bounds p

-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por
-- ejemplo, 
--    filaConUno ej 3  ==  True
--    filaConUno ej 2  ==  False
filaConUno :: Matriz -> Int -> Bool
filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]
    where (_,(_,n)) = bounds p

-- (columnasConUno p) es la lista de las columnas de p que tienen algún
-- uno. Por ejemplo,
--    columnasConUno ej  ==  [1,4]
columnasConUno :: Matriz -> [Int]
columnasConUno p = [j | j <- [1..n], columnaConUno p j]
    where (_,(m,n)) = bounds p

-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por
-- ejemplo, 
--    columnaConUno ej 1  ==  True
--    columnaConUno ej 2  ==  False
columnaConUno :: Matriz -> Int -> Bool
columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]
    where (_,(m,_)) = bounds p

-- 3ª solución
-- ===========

relleno3 :: Matriz -> Matriz
relleno3 p = p // ([((i,j),1) | i <- filas,  j <- [1..n]] ++ 
                   [((i,j),1) | i <- [1..m], j <- columnas])
  where (_,(m,n)) = bounds p
        filas     = filasConUno p
        columnas  = columnasConUno p


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

--    λ> let f i j = if i == j then 1 else 0 
--    λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]
--    
--    λ> sum (elems (relleno1 (q 200)))
--    40000
--    (6.90 secs, 1,877,369,544 bytes)
--    
--    λ> sum (elems (relleno2 (q 200)))
--    40000
--    (0.46 secs, 57,354,168 bytes)
--    
--    λ> sum (elems (relleno3 (q 200)))
--    40000
--    (0.34 secs, 80,465,144 bytes)
--    
--    λ> sum (elems (relleno2 (q 500)))
--    250000
--    (4.33 secs, 353,117,640 bytes)
--    
--    λ> sum (elems (relleno3 (q 500)))
--    250000
--    (2.40 secs, 489,630,048 bytes)

100

101

import Data.Array

type Matriz = Array (Int,Int) Int

ej :: Matriz

ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,

0, 0, 0, 0, 0,

0, 0, 0, 1, 0,

1, 0, 0, 0, 0,

0, 0, 0, 0, 0]

-- 1ª solución

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

relleno1 :: Matriz -> Matriz

relleno1 p =

array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]

where (_,(m,n)) = bounds p

f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1

| 1 `elem` [p!(k,j) | k <- [1..m]] = 1

| otherwise = 0

-- 2ª solución

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

relleno2 :: Matriz -> Matriz

relleno2 p =

array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]

where (_,(m,n)) = bounds p

filas = filasConUno p

columnas = columnasConUno p

f i j | i `elem` filas = 1

| j `elem` columnas = 1

| otherwise = 0

-- (filasConUno p) es la lista de las filas de p que tienen algún

-- uno. Por ejemplo,

-- filasConUno ej == [3,4]

filasConUno :: Matriz -> [Int]

filasConUno p = [i | i <- [1..m], filaConUno p i]

where (_,(m,n)) = bounds p

-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por

-- ejemplo,

-- filaConUno ej 3 == True

-- filaConUno ej 2 == False

filaConUno :: Matriz -> Int -> Bool

filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]

where (_,(_,n)) = bounds p

-- (columnasConUno p) es la lista de las columnas de p que tienen algún

-- uno. Por ejemplo,

-- columnasConUno ej == [1,4]

columnasConUno :: Matriz -> [Int]

columnasConUno p = [j | j <- [1..n], columnaConUno p j]

where (_,(m,n)) = bounds p

-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por

-- ejemplo,

-- columnaConUno ej 1 == True

-- columnaConUno ej 2 == False

columnaConUno :: Matriz -> Int -> Bool

columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]

where (_,(m,_)) = bounds p

-- 3ª solución

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

relleno3 :: Matriz -> Matriz

relleno3 p = p // ([((i,j),1) | i <- filas, j <- [1..n]] ++

[((i,j),1) | i <- [1..m], j <- columnas])

where (_,(m,n)) = bounds p

filas = filasConUno p

columnas = columnasConUno p

-- Comparación de eficiencia

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

-- λ> let f i j = if i == j then 1 else 0

-- λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]

-- λ> sum (elems (relleno1 (q 200)))

-- 40000

-- (6.90 secs, 1,877,369,544 bytes)

-- λ> sum (elems (relleno2 (q 200)))

-- 40000

-- (0.46 secs, 57,354,168 bytes)

-- λ> sum (elems (relleno3 (q 200)))

-- 40000

-- (0.34 secs, 80,465,144 bytes)

-- λ> sum (elems (relleno2 (q 500)))

-- 250000

-- (4.33 secs, 353,117,640 bytes)

-- λ> sum (elems (relleno3 (q 500)))

-- 250000

-- (2.40 secs, 489,630,048 bytes)

Referencias

Basado en Matrix Fill-In del blog Programming Praxis.

Primos que contienen al 2016

PorJosé A. Alonso 18-enero-201625-enero-2016

Definir la sucesión

   primosCon2016 :: [Integer]

1	primosCon2016 :: [Integer]

tal que sus elementos son los números primos que contienen al 2016. Por ejemplo,

   take 5 primosCon2016  ==  [20161,120163,120167,201611,201623]
   primosCon2016 !! 111  ==  3020167

1 2	take 5 primosCon2016 == [20161,120163,120167,201611,201623] primosCon2016 !! 111 == 3020167

Soluciones

import Data.List (isInfixOf)
import Data.Numbers.Primes (primes)

primosCon2016 :: [Integer]
primosCon2016 = 
    [x | x <- primes, isInfixOf "2016" (show x)]

import Data.List (isInfixOf)

import Data.Numbers.Primes (primes)

primosCon2016 :: [Integer]

primosCon2016 =

[x | x <- primes, isInfixOf "2016" (show x)]

Referencias

Basado en el artículo Prime numbers containing 2016 del blog Fun With Num3ers.

Lista tautológica de literales

PorJosé A. Alonso 14-enero-201621-enero-2016

En lógica matemática, un literal http://bit.ly/1RQ5yJU es una fórmula atómica o su negación. Se puede definir por el tipo de dato

   data Literal = Atom String
                | Neg Literal
                deriving (Eq, Show)

data Literal = Atom String

| Neg Literal

deriving (Eq, Show)

Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom «p») y (Neg (Atom «q»)), respectivamente.

Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.

Definir la función

   tautologia :: [Literal] -> Bool

1	tautologia :: [Literal] -> Bool

tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,

   λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]
   True
   λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]
   False
   λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]
   False

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]

True

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]

False

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]

False

Soluciones

[schedule expon=’2016-01-21′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 21 de enero.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-01-21′ at=»06:00″]

import Data.List (intersect)

data Literal = Atom String
             | Neg Literal
             deriving (Eq, Show)

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

tautologia1 :: [Literal] -> Bool
tautologia1 xs = or [elem x xs && elem (Neg x) xs | x <- xs]

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

tautologia2 :: [Literal] -> Bool
tautologia2 xs = 
    not (null (intersect ns (map neg ps)))
    where (ps,ns) = span esPositivo xs
          neg x   = Neg x

esPositivo :: Literal -> Bool
esPositivo (Atom _) = True
esPositivo _        = False

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

--    λ> tautologia1 (replicate 4000 (Atom "p"))
--    False
--    (6.70 secs, 1031428 bytes)
--    λ> tautologia2 (replicate 4000 (Atom "p"))
--    False
--    (0.01 secs, 1061604 bytes)

import Data.List (intersect)

data Literal = Atom String

| Neg Literal

deriving (Eq, Show)

-- 1ª solución

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

tautologia1 :: [Literal] -> Bool

tautologia1 xs = or [elem x xs && elem (Neg x) xs | x <- xs]

-- 2ª solución

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

tautologia2 :: [Literal] -> Bool

tautologia2 xs =

not (null (intersect ns (map neg ps)))

where (ps,ns) = span esPositivo xs

neg x = Neg x

esPositivo :: Literal -> Bool

esPositivo (Atom _) = True

esPositivo _ = False

-- Comparación de eficiencia

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

-- λ> tautologia1 (replicate 4000 (Atom "p"))

-- False

-- (6.70 secs, 1031428 bytes)

-- λ> tautologia2 (replicate 4000 (Atom "p"))

-- False

-- (0.01 secs, 1061604 bytes)

[/schedule]

Puntos visibles en la cuadrícula de un plano

PorJosé A. Alonso 13-enero-20161-mayo-2016

La cuadrícula entera de lado n, Cₙ, es el conjunto de los puntos (x,y) donde x e y son números enteros tales que 1 ≤ x, y ≤ n.

Un punto (x,y) de Cₙ es visible desde el origen si el máximo común divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque está ocultado por el (2,3); en cambio, el (2,3) sí es visible.

El conjunto de los puntos visibles en la cuadrícula entera de lado 6 son (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1) y (6,5).

Definir la función

   nVisibles :: Integer -> Integer

1	nVisibles :: Integer -> Integer

tal que (nVisibles n) es el número de los puntos visibles en la cuadrícula de lado n.Por ejemplo,

   nVisibles 6       ==  23
   nVisibles 10      ==  63
   nVisibles 100     ==  6087
   nVisibles 1000    ==  608383
   nVisibles 10000   ==  60794971
   nVisibles 100000  ==  6079301507

nVisibles 6 == 23

nVisibles 10 == 63

nVisibles 100 == 6087

nVisibles 1000 == 608383

nVisibles 10000 == 60794971

nVisibles 100000 == 6079301507

Soluciones

import Data.List (genericLength, group, sort)
import Data.Numbers.Primes (primeFactors)

type Punto = (Integer,Integer)

-- (visible p) se verifica si el punto p es visible. Por ejemplo,
--    visible (4,5)  ==  True
--    visible (4,6)  ==  False
visible :: Punto -> Bool
visible (x,y) = gcd x y == 1

-- (visibles n) es el conjunto de los puntos visibles en la cuadrícula
-- de lado 1. Por ejemplo,
-- cuadrado 1 <= x, y <= n. Por ejemplo,
--    λ> sort (visibles 6)
--    [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),
--     (3,5),(4,1),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4),(5,6),(6,1),(6,5)]

-- 1ª definición de visibles
visibles1 :: Integer -> [Punto]
visibles1 n = [(x,y) | x <- [1..n], y <- [1..n], visible (x,y)]

-- 2ª definición de visibles
visibles2 :: Integer -> [Punto]
visibles2 n = (1,1) : ps ++ [(y,x) | (x,y) <- ps] 
    where ps = [(x,y) | x <- [1..n], y <- [x+1..n], visible (x,y)]

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

--    λ> length (visibles1 1000)
--    608383
--    (3.40 secs, 758,346,208 bytes)
--    λ> length (visibles2 1000)
--    608383
--    (2.22 secs, 464,276,856 bytes)

-- Usaremos la 2ª definición de visibles
visibles :: Integer -> [Punto]
visibles = visibles2

-- 1ª definición de nVisibles
nVisibles1 :: Integer -> Integer
nVisibles1 = genericLength . visibles


-- 2ª definición de nVisibles
nVisibles2 :: Integer -> Integer
nVisibles2 n = 
    1 + 2 * genericLength [(x,y) | x <- [1..n], 
                                   y <- [x+1..n], 
                                   visible (x,y)]

-- 3ª definición de nVisibles
nVisibles3 :: Integer -> Integer
nVisibles3 1 = 1
nVisibles3 n = nVisibles3 (n-1) + (2 * phi n)

-- La función φ de Euler (del ejercicio anterior).
phi :: Integer -> Integer
phi n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n] 
    
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
    [(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- 4ª definición de nVisibles
nVisibles4 :: Integer -> Integer
nVisibles4 n = 2 * sum [phi x | x <- [1..n]] - 1

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

--    λ> nVisibles1 1000
--    608383
--    (2.69 secs, 521,599,512 bytes)
--    λ> nVisibles2 1000
--    608383
--    λ> nVisibles3 1000
--    608383
--    (0.05 secs, 0 bytes)
--    λ> nVisibles4 1000
--    608383
--    (0.04 secs, 0 bytes)

import Data.List (genericLength, group, sort)

import Data.Numbers.Primes (primeFactors)

type Punto = (Integer,Integer)

-- (visible p) se verifica si el punto p es visible. Por ejemplo,

-- visible (4,5) == True

-- visible (4,6) == False

visible :: Punto -> Bool

visible (x,y) = gcd x y == 1

-- (visibles n) es el conjunto de los puntos visibles en la cuadrícula

-- de lado 1. Por ejemplo,

-- cuadrado 1 <= x, y <= n. Por ejemplo,

-- λ> sort (visibles 6)

-- [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),

-- (3,5),(4,1),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4),(5,6),(6,1),(6,5)]

-- 1ª definición de visibles

visibles1 :: Integer -> [Punto]

visibles1 n = [(x,y) | x <- [1..n], y <- [1..n], visible (x,y)]

-- 2ª definición de visibles

visibles2 :: Integer -> [Punto]

visibles2 n = (1,1) : ps ++ [(y,x) | (x,y) <- ps]

where ps = [(x,y) | x <- [1..n], y <- [x+1..n], visible (x,y)]

-- Comparación de eficiencia

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

-- λ> length (visibles1 1000)

-- 608383

-- (3.40 secs, 758,346,208 bytes)

-- λ> length (visibles2 1000)

-- 608383

-- (2.22 secs, 464,276,856 bytes)

-- Usaremos la 2ª definición de visibles

visibles :: Integer -> [Punto]

visibles = visibles2

-- 1ª definición de nVisibles

nVisibles1 :: Integer -> Integer

nVisibles1 = genericLength . visibles

-- 2ª definición de nVisibles

nVisibles2 :: Integer -> Integer

nVisibles2 n =

1 + 2 * genericLength [(x,y) | x <- [1..n],

y <- [x+1..n],

visible (x,y)]

-- 3ª definición de nVisibles

nVisibles3 :: Integer -> Integer

nVisibles3 1 = 1

nVisibles3 n = nVisibles3 (n-1) + (2 * phi n)

-- La función φ de Euler (del ejercicio anterior).

phi :: Integer -> Integer

phi n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]

factorizacion :: Integer -> [(Integer,Integer)]

factorizacion n =

[(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- 4ª definición de nVisibles

nVisibles4 :: Integer -> Integer

nVisibles4 n = 2 * sum [phi x | x <- [1..n]] - 1

-- Comparación de eficiencia

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

-- λ> nVisibles1 1000

-- 608383

-- (2.69 secs, 521,599,512 bytes)

-- λ> nVisibles2 1000

-- 608383

-- λ> nVisibles3 1000

-- 608383

-- (0.05 secs, 0 bytes)

-- λ> nVisibles4 1000

-- 608383

-- (0.04 secs, 0 bytes)

Referencias

N.J.A. Sloane, Sucesión A018805 en OEIS.

Cambios de signo

PorJosé A. Alonso 12-enero-201620-enero-2016

En una lista xs se produce un cambio de signo por cada elemento x de la lista junto el primero de los elementos de xs con signo opuesto al de x. Por ejemplo,en la lista [6,5,-4,0,-2,-7,0,-8,-1,4] hay 2 cambios de signo (entre (5,-4) y (-1,4)) y en la lista [6,5,-4,0, 2,-7,0,-8,-1,4] hay 4 cambios de signo (entre (5,-4), (-4,2), (2,-7) y(-1,4)).

Definir la función

   nCambios :: (Num a, Ord a) => [a] -> Int

1	nCambios :: (Num a, Ord a) => [a] -> Int

tal que (nCambios xs) es el número de cambios de signos de la lista xs. Por ejemplo,

   nCambios []                          ==  0
   nCambios [6,5,-4,0,-2,-7,0,-8,-1,4]  ==  2
   nCambios [6,5,-4,0, 2,-7,0,-8,-1,4]  ==  4

nCambios [] == 0

nCambios [6,5,-4,0,-2,-7,0,-8,-1,4] == 2

nCambios [6,5,-4,0, 2,-7,0,-8,-1,4] == 4

Soluciones

import Data.List (group)

-- 1ª definición
nCambios1 :: (Num a, Ord a) => [a] -> Int
nCambios1 = length . cambios

-- (cambios xs) es la lista de los pares de elementos de xs entre los
-- que se producen cambios de signo. Por ejemplo,
--    cambios [6,5,-4,0,-2,-7,0,-8,-1,4]  ==  [(5,-4),(-1,4)]
--    cambios [6,5,-4,0, 2,-7,0,-8,-1,4]  ==  [(5,-4),(-4,2),(2,-7),(-1,4)]
cambios :: (Num a, Ord a) => [a] -> [(a,a)]
cambios xs =
    [(x,y) | (x,y) <- zip ys (tail ys), x*y < 0]
    where ys = filter (/=0) xs

-- 2ª definición
nCambios2 :: (Num a, Ord a) => [a] -> Int
nCambios2 [] = 0
nCambios2 xs = length (group (filter (/=0) (map signum xs))) - 1

-- 3ª definición
nCambios3 :: (Num a, Ord a) => [a] -> Int
nCambios3 = pred . length . group . filter (/=0) . map signum

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

--    λ> nCambios1 (take (2*10^6) (cycle [3,0,-3]))
--    1333332
--    (3.84 secs, 679,805,392 bytes)
--    λ> nCambios2 (take (2*10^6) (cycle [3,0,-3]))
--    1333332
--    (0.98 secs, 694,247,368 bytes)
--    λ> nCambios3 (take (2*10^6) (cycle [3,0,-3]))
--    1333332
--    (0.95 secs, 708,118,976 bytes)

import Data.List (group)

-- 1ª definición

nCambios1 :: (Num a, Ord a) => [a] -> Int

nCambios1 = length . cambios

-- (cambios xs) es la lista de los pares de elementos de xs entre los

-- que se producen cambios de signo. Por ejemplo,

-- cambios [6,5,-4,0,-2,-7,0,-8,-1,4] == [(5,-4),(-1,4)]

-- cambios [6,5,-4,0, 2,-7,0,-8,-1,4] == [(5,-4),(-4,2),(2,-7),(-1,4)]

cambios :: (Num a, Ord a) => [a] -> [(a,a)]

cambios xs =

[(x,y) | (x,y) <- zip ys (tail ys), x*y < 0]

where ys = filter (/=0) xs

-- 2ª definición

nCambios2 :: (Num a, Ord a) => [a] -> Int

nCambios2 [] = 0

nCambios2 xs = length (group (filter (/=0) (map signum xs))) - 1

-- 3ª definición

nCambios3 :: (Num a, Ord a) => [a] -> Int

nCambios3 = pred . length . group . filter (/=0) . map signum

-- Comparación de eficiencia

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

-- λ> nCambios1 (take (2*10^6) (cycle [3,0,-3]))

-- 1333332

-- (3.84 secs, 679,805,392 bytes)

-- λ> nCambios2 (take (2*10^6) (cycle [3,0,-3]))

-- 1333332

-- (0.98 secs, 694,247,368 bytes)

-- λ> nCambios3 (take (2*10^6) (cycle [3,0,-3]))

-- 1333332

-- (0.95 secs, 708,118,976 bytes)

Parte libre de cuadrados y parte cuadrada de un número

PorJosé A. Alonso 11-enero-201618-enero-2016

La parte libre de cuadrados de un número n es el producto de todos sus divisores primos con exponente impar en la factorización prima de n. Por ejemplo, la parte libre de cuadrados de 360 es 10 ya que 360 = 2³3²5 y 2.5 = 10; además, 360 = 10.6²

La parte cuadrada de un número n es el mayor número cuadrado que divide a n. Por ejemplo, la parte cuadrada de 360 es 6.

Definir las funciones

   parteLibre    :: Integer -> Integer
   parteCuadrada :: Integer -> Integer

1 2	parteLibre :: Integer -> Integer parteCuadrada :: Integer -> Integer

tales que

(parteLibre x) es la parte libre de x. Por ejemplo,

     parteLibre 360                 ==  10
     parteLibre 1800                ==  2
     [parteLibre n | n <- [1..14]]  ==  [1,2,3,1,5,6,7,2,1,10,11,3,13,14]

parteLibre 360 == 10

parteLibre 1800 == 2

[parteLibre n | n <- [1..14]] == [1,2,3,1,5,6,7,2,1,10,11,3,13,14]

(parteCuadrada x) es la parte cuadrada de x. Por ejemplo,

     parteCuadrada 360                 ==  36
     parteCuadrada 1800                ==  900
     [parteCuadrada n | n <- [1..14]]  ==  [1,1,1,4,1,1,1,4,9,1,1,4,1,1]

parteCuadrada 360 == 36

parteCuadrada 1800 == 900

[parteCuadrada n | n <- [1..14]] == [1,1,1,4,1,1,1,4,9,1,1,4,1,1]

Soluciones

import Data.List (group, genericLength)
import Data.Numbers.Primes (primeFactors)

parteLibre :: Integer -> Integer
parteLibre n = product [p | (p,e) <- factorizacion n, odd e]

-- (factorizacion n) es la factorización de n. Por ejemplo, 
--    factorizacion  600  ==  [(2,3),(3,1),(5,2)]
--    factorizacion 1400  ==  [(2,3),(5,2),(7,1)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
    [(head xs,genericLength xs) | xs <- group (primeFactors n)]

parteCuadrada :: Integer -> Integer
parteCuadrada n = n `div` parteLibre n

import Data.List (group, genericLength)

import Data.Numbers.Primes (primeFactors)

parteLibre :: Integer -> Integer

parteLibre n = product [p | (p,e) <- factorizacion n, odd e]

-- (factorizacion n) es la factorización de n. Por ejemplo,

-- factorizacion 600 == [(2,3),(3,1),(5,2)]

-- factorizacion 1400 == [(2,3),(5,2),(7,1)]

factorizacion :: Integer -> [(Integer,Integer)]

factorizacion n =

[(head xs,genericLength xs) | xs <- group (primeFactors n)]

parteCuadrada :: Integer -> Integer

parteCuadrada n = n `div` parteLibre n

Referencias

N.J.A. Sloane, Sequence A008833 en OEIS.
N.J.A. Sloane, Sequence A007913 en OEIS.
E.W. Weisstein, Square part en MathWorld.
E.W. Weisstein, Squarefree part en MathWorld.

Fórmula dual

PorJosé A. Alonso 7-enero-201615-enero-2016

Las fórmulas proposicionales construidas con las constantes verdadero (⊤), falso (⊥), las variables proposicionales y las conectivas de negación (¬), conjunción (∧) y disyunción (∨) se pueden definir usando el siguiente tipo de datos

   data Prop = Const Bool
             | Var Char
             | Neg Prop
             | Conj Prop Prop
             | Disj Prop Prop
             deriving (Eq, Show)

data Prop = Const Bool

| Var Char

| Neg Prop

| Conj Prop Prop

| Disj Prop Prop

deriving (Eq, Show)

Por ejemplo, la fórmula (A ∧ ⊥) ∨ (⊤ ∧ B) se representa por

   Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))

1	Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))

La fórmula dual de una fórmula p es la fórmula obtenida intercambiando en p las ∧ por ∨ y también las ⊤ por ⊥. Por ejemplo, la dual de (A ∧ ⊥) ∨ (⊤ ∧ B) es (A ∨ ⊤) ∧ (⊥ ∨ B)

Definir la función

   dual :: Prop -> Prop

1	dual :: Prop -> Prop

tal que (dual p) es la dual de p. Por ejemplo,

   λ> dual (Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B')))
   Conj (Disj (Var 'A') (Const True)) (Disj (Const False) (Var 'B'))

1 2	λ> dual (Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))) Conj (Disj (Var 'A') (Const True)) (Disj (Const False) (Var 'B'))

Soluciones

data Prop = Const Bool
          | Var Char
          | Neg Prop
          | Conj Prop Prop
          | Disj Prop Prop
          deriving (Eq, Show)

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

dual1 :: Prop -> Prop
dual1 (Const True)  = Const False
dual1 (Const False) = Const True
dual1 (Var x)       = Var x
dual1 (Neg p)       = Neg  (dual1 p)
dual1 (Conj p q)    = Disj (dual1 p) (dual1 q) 
dual1 (Disj p q)    = Conj (dual1 p) (dual1 q) 

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

dual2 :: Prop -> Prop
dual2 (Const b)  = Const (not b)
dual2 (Conj p q) = Disj (dual2 p) (dual2 q)
dual2 (Disj p q) = Conj (dual2 p) (dual2 q)
dual2 p          = p

data Prop = Const Bool

| Var Char

| Neg Prop

| Conj Prop Prop

| Disj Prop Prop

deriving (Eq, Show)

-- 1ª solución

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

dual1 :: Prop -> Prop

dual1 (Const True) = Const False

dual1 (Const False) = Const True

dual1 (Var x) = Var x

dual1 (Neg p) = Neg (dual1 p)

dual1 (Conj p q) = Disj (dual1 p) (dual1 q)

dual1 (Disj p q) = Conj (dual1 p) (dual1 q)

-- 2ª solución

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

dual2 :: Prop -> Prop

dual2 (Const b) = Const (not b)

dual2 (Conj p q) = Disj (dual2 p) (dual2 q)

dual2 (Disj p q) = Conj (dual2 p) (dual2 q)

dual2 p = p

Puntos en una región

PorJosé A. Alonso 5-enero-20161-mayo-2016

Definir la función

   puntos :: Integer -> [(Integer,Integer)]

1	puntos :: Integer -> [(Integer,Integer)]

tal que (puntos n) es la lista de los puntos (x,y) con coordenadas enteras de
la cuadrícula [1..n]x[1..n] (es decir, 1 ≤ x,y ≤ n) tales que |x²-xy-y²| = 1. Por ejemplo,

   length (puntos 10)          ==  5
   length (puntos 100)         ==  10
   length (puntos 1000)        ==  15
   length (puntos (10^50000))  ==  239249

length (puntos 10) == 5

length (puntos 100) == 10

length (puntos 1000) == 15

length (puntos (10^50000)) == 239249

Soluciones

-- 1ª definición
-- =============

puntos1 :: Integer -> [(Integer,Integer)]
puntos1 n =
    [(x,y) | x <- [1..n],
             y <- [1..n],
             abs (x^2-x*y-y^2) == 1] 

-- 2ª definición
-- =============

-- Calculando algunos elementos
--    λ> puntos1 10
--    [(1,1),(2,1),(3,2),(5,3),(8,5)]
--    λ> puntos1 20
--    [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8)]
--    λ> puntos1 100
--    [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)]
--    λ> puntos1 89
--    [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)]
-- se observa una ley de construcción de cada elemento a partir del anterior.

puntos2 :: Integer -> [(Integer,Integer)]
puntos2 n = takeWhile menor (iterate siguiente (1,1))
    where siguiente (x,y) = (x+y,x)
          menor (x,y)     = x <= n

-- 3ª definición
-- =============

-- Se observa que la lista de las segundas componentes
--    1,1,2,3,5,8,13,21,34,55,89,...
-- y la lista de las primeras componentes es el resto de la segunda. 

puntos3 :: Integer -> [(Integer,Integer)]
puntos3 n = zip (tail xs) xs
    where xs = takeWhile (<=n) fibonacci

-- fibonacci es la sucesión de Fibonacci. Por ejemplo,
--    take 11 fibonacci  ==  [1,1,2,3,5,8,13,21,34,55,89]
fibonacci :: [Integer]
fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)

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

-- λ> length (puntos1 (10^3))
-- 15
-- (7.96 secs, 1,092,368,200 bytes)
-- λ> length (puntos2 (10^3))
-- 15
-- (0.02 secs, 0 bytes)
-- 
-- λ> length (puntos2 (10^30000))
-- 143549
-- (1.14 secs, 974,239,544 bytes)
-- λ> length (puntos3 (10^30000))
-- 143549
-- (3.28 secs, 967,206,560 bytes)

-- 1ª definición

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

puntos1 :: Integer -> [(Integer,Integer)]

puntos1 n =

[(x,y) | x <- [1..n],

y <- [1..n],

abs (x^2-x*y-y^2) == 1]

-- 2ª definición

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

-- Calculando algunos elementos

-- λ> puntos1 10

-- [(1,1),(2,1),(3,2),(5,3),(8,5)]

-- λ> puntos1 20

-- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8)]

-- λ> puntos1 100

-- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)]

-- λ> puntos1 89

-- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)]

-- se observa una ley de construcción de cada elemento a partir del anterior.

puntos2 :: Integer -> [(Integer,Integer)]

puntos2 n = takeWhile menor (iterate siguiente (1,1))

where siguiente (x,y) = (x+y,x)

menor (x,y) = x <= n

-- 3ª definición

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

-- Se observa que la lista de las segundas componentes

-- 1,1,2,3,5,8,13,21,34,55,89,...

-- y la lista de las primeras componentes es el resto de la segunda.

puntos3 :: Integer -> [(Integer,Integer)]

puntos3 n = zip (tail xs) xs

where xs = takeWhile (<=n) fibonacci

-- fibonacci es la sucesión de Fibonacci. Por ejemplo,

-- take 11 fibonacci == [1,1,2,3,5,8,13,21,34,55,89]

fibonacci :: [Integer]

fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)

-- Comparación de eficiencia

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

-- λ> length (puntos1 (10^3))

-- 15

-- (7.96 secs, 1,092,368,200 bytes)

-- λ> length (puntos2 (10^3))

-- 15

-- (0.02 secs, 0 bytes)

-- λ> length (puntos2 (10^30000))

-- 143549

-- (1.14 secs, 974,239,544 bytes)

-- λ> length (puntos3 (10^30000))

-- 143549

-- (3.28 secs, 967,206,560 bytes)

2016 es un número práctico

PorJosé A. Alonso 4-enero-20161-mayo-2016

Un entero positivo n es un número práctico si todos los enteros positivos menores que él se pueden expresar como suma de distintos divisores de n. Por ejemplo, el 12 es un número práctico, ya que todos los enteros positivos menores que 12 se pueden expresar como suma de divisores de 12 (1, 2, 3, 4 y 6) sin usar ningún divisor más de una vez en cada suma:

    1 = 1
    2 = 2
    3 = 3
    4 = 4
    5 = 2 + 3
    6 = 6
    7 = 1 + 6
    8 = 2 + 6
    9 = 3 + 6
   10 = 4 + 6
   11 = 1 + 4 + 6

1 = 1

2 = 2

3 = 3

4 = 4

5 = 2 + 3

6 = 6

7 = 1 + 6

8 = 2 + 6

9 = 3 + 6

10 = 4 + 6

11 = 1 + 4 + 6

En cambio, 14 no es un número práctico ya que 6 no se puede escribir como suma, con sumandos distintos, de divisores de 14.

Definir la función

   esPractico :: Integer -> Bool

1	esPractico :: Integer -> Bool

tal que (esPractico n) se verifica si n es un número práctico. Por ejemplo,

   esPractico 12                                      ==  True
   esPractico 14                                      ==  False
   esPractico 2016                                    ==  True
   esPractico 42535295865117307932921825928971026432  ==  True

esPractico 12 == True

esPractico 14 == False

esPractico 2016 == True

esPractico 42535295865117307932921825928971026432 == True

Soluciones

import Data.List (genericLength, group, nub, sort, subsequences)
import Data.Numbers.Primes (primeFactors)
import Graphics.Gnuplot.Simple

-- 1ª definición
-- =============

esPractico1 :: Integer -> Bool
esPractico1 n =
    takeWhile (<n) (sumas (divisores n)) == [0..n-1]

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 12  ==  [1,2,3,4,6]
--    divisores 14  ==  [1,2,7]
divisores :: Integer -> [Integer]
divisores n = [k | k <- [1..n-1], n `mod` k == 0]

-- (sumas xs) es la lista ordenada de números que se pueden obtener como
-- sumas de elementos de xs sin usar ningún elemento más de una vez en
-- cada suma. Por ejemplo,  
--    sumas [1,2,3]  ==  [0,1,2,3,4,5,6]
--    sumas [1,2,7]  ==  [0,1,2,3,7,8,9,10]
sumas :: [Integer] -> [Integer]
sumas xs = sort (nub (map sum (subsequences xs)))

-- 2ª definición
-- =============

esPractico2 :: Integer -> Bool
esPractico2 n = all (esSumable (divisores n)) [1..n-1]

-- (esSumable xs n) se verifica si n se puede escribir como una suma de
-- elementos distintos de la lista creciente xs. Por ejemplo,
--    esSumable [1,2,7] 8  ==  True
--    esSumable [1,2,7] 6  ==  False
--    esSumable [1,2,7] 4  ==  False
--    esSumable [1,2,7] 2  ==  True
--    esSumable [1,2,7] 0  ==  True
esSumable :: [Integer] -> Integer -> Bool
esSumable _ 0  = True
esSumable [] _ = False
esSumable (x:xs) n = x <= n && (esSumable xs (n-x) || esSumable xs n)

-- 3ª definición
-- =============

-- Usando la caracterización de Stewart y Sierpiński: un entero n >= 2
-- es práctico syss para su factorización prima
--    n = p(1)^e(1) * p(2)*e(2) *...* p(k)^e(k)
-- se cumple que p(1) = 2 y, para cada i de 2 a k se cumple que
--                         1+e(j) 
--                i-1  p(j)       - 1
--    p(i) <= 1 +  ∏  ----------------
--                j=1     p(j) - 1

esPractico3 :: Integer -> Bool
esPractico3 1 = True
esPractico3 n = 
    x == 2 &&
    and [p <= 1 + c | (p,c) <- zip bases cotas]
    where xss       = factorizacion n
          (x:bases) = map fst xss
          cotas     = scanl1 (*) [(p^(1+e)-1) `div` (p-1) | (p,e) <- xss]

-- (factorizacion n) es la factorización de n. Por ejemplo, 
--    factorizacion  600  ==  [(2,3),(3,1),(5,2)]
--    factorizacion 1400  ==  [(2,3),(5,2),(7,1)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
    [(head xs,genericLength xs) | xs <- group (primeFactors n)]

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

--    λ> length [n | n <- [1..400], esPractico1 n]
--    92
--    (40.21 secs, 8,378,539,464 bytes)
--    λ> length [n | n <- [1..400], esPractico2 n]
--    92
--    (8.29 secs, 1,109,669,760 bytes)
--    λ> length [n | n <- [1..400], esPractico3 n]
--    92
--    (0.02 secs, 0 bytes)

import Data.List (genericLength, group, nub, sort, subsequences)

import Data.Numbers.Primes (primeFactors)

import Graphics.Gnuplot.Simple

-- 1ª definición

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

esPractico1 :: Integer -> Bool

esPractico1 n =

takeWhile (<n) (sumas (divisores n)) == [0..n-1]

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 12 == [1,2,3,4,6]

-- divisores 14 == [1,2,7]

divisores :: Integer -> [Integer]

divisores n = [k | k <- [1..n-1], n `mod` k == 0]

-- (sumas xs) es la lista ordenada de números que se pueden obtener como

-- sumas de elementos de xs sin usar ningún elemento más de una vez en

-- cada suma. Por ejemplo,

-- sumas [1,2,3] == [0,1,2,3,4,5,6]

-- sumas [1,2,7] == [0,1,2,3,7,8,9,10]

sumas :: [Integer] -> [Integer]

sumas xs = sort (nub (map sum (subsequences xs)))

-- 2ª definición

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

esPractico2 :: Integer -> Bool

esPractico2 n = all (esSumable (divisores n)) [1..n-1]

-- (esSumable xs n) se verifica si n se puede escribir como una suma de

-- elementos distintos de la lista creciente xs. Por ejemplo,

-- esSumable [1,2,7] 8 == True

-- esSumable [1,2,7] 6 == False

-- esSumable [1,2,7] 4 == False

-- esSumable [1,2,7] 2 == True

-- esSumable [1,2,7] 0 == True

esSumable :: [Integer] -> Integer -> Bool

esSumable _ 0 = True

esSumable [] _ = False

esSumable (x:xs) n = x <= n && (esSumable xs (n-x) || esSumable xs n)

-- 3ª definición

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

-- Usando la caracterización de Stewart y Sierpiński: un entero n >= 2

-- es práctico syss para su factorización prima

-- n = p(1)^e(1) * p(2)*e(2) *...* p(k)^e(k)

-- se cumple que p(1) = 2 y, para cada i de 2 a k se cumple que

-- 1+e(j)

-- i-1 p(j) - 1

-- p(i) <= 1 + ∏ ----------------

-- j=1 p(j) - 1

esPractico3 :: Integer -> Bool

esPractico3 1 = True

esPractico3 n =

x == 2 &&

and [p <= 1 + c | (p,c) <- zip bases cotas]

where xss = factorizacion n

(x:bases) = map fst xss

cotas = scanl1 (*) [(p^(1+e)-1) `div` (p-1) | (p,e) <- xss]

-- (factorizacion n) es la factorización de n. Por ejemplo,

-- factorizacion 600 == [(2,3),(3,1),(5,2)]

-- factorizacion 1400 == [(2,3),(5,2),(7,1)]

factorizacion :: Integer -> [(Integer,Integer)]

factorizacion n =

[(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- Comparación de eficiencia

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

-- λ> length [n | n <- [1..400], esPractico1 n]

-- 92

-- (40.21 secs, 8,378,539,464 bytes)

-- λ> length [n | n <- [1..400], esPractico2 n]

-- 92

-- (8.29 secs, 1,109,669,760 bytes)

-- λ> length [n | n <- [1..400], esPractico3 n]

-- 92

-- (0.02 secs, 0 bytes)

Referencias

Basado en el artículo de Gaussianos Feliz Navidad y Feliz Año (número práctico) 2016.

Otras referencias

M. Margenstern (1991), Les nombres pratiques: théorie, observations et conjectures.
G. Melfi, Practical numbers.
G. Melfi (2008), A survey on practical numbers.
OEIS, Sucesión A005153.
PlanetMath.org, Practical number.
E.W. Weisstein, Practical number.
A. Weingartner (2015), Practical numbers and the distribution of divisors.
Wikipedia, Practical number.

Suma con redondeos

PorJosé A. Alonso 1-enero-20167-enero-2016

Definir las funciones

   sumaRedondeos       :: Integer -> [Integer]
   limiteSumaRedondeos :: Integer -> Integer

1 2	sumaRedondeos :: Integer -> [Integer] limiteSumaRedondeos :: Integer -> Integer

tales que

(sumaRedondeos n) es la sucesión cuyo k-ésimo término es

     redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

1	redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

Por ejemplo,

     take 5 (sumaRedondeos 1000)  ==  [500,750,875,937,968]

1	take 5 (sumaRedondeos 1000) == [500,750,875,937,968]

(limiteSumaRedondeos n) es la suma de la serie

     redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

1	redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

Por ejemplo,

     limiteSumaRedondeos 2000                    ==  1999
     limiteSumaRedondeos 2016                    ==  2016
     limiteSumaRedondeos (10^308) `mod` (10^10)  ==  123839487

limiteSumaRedondeos 2000 == 1999

limiteSumaRedondeos 2016 == 2016

limiteSumaRedondeos (10^308) `mod` (10^10) == 123839487

Soluciones

-- 1ª definición
-- =============

sumaRedondeos1 :: Integer -> [Integer]
sumaRedondeos1 n =
    [sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] | m <- [1..]]
    where n' = fromIntegral n

limiteSumaRedondeos1 :: Integer -> Integer
limiteSumaRedondeos1 = limite . sumaRedondeos1

limite :: [Integer] -> Integer
limite xs = head [x | (x,y) <- zip xs (tail xs), x == y]

-- 2ª definición
sumaRedondeos2 :: Integer -> [Integer]
sumaRedondeos2 n =
    scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..]]
    where n' = fromIntegral n

limiteSumaRedondeos2 :: Integer -> Integer
limiteSumaRedondeos2 = limite . sumaRedondeos2

-- 3ª definición
sumaRedondeos3 :: Integer -> [Integer]
sumaRedondeos3 n = map fst (iterate f (round (n'/2),4))
    where f (s,d) = (s + round (n'/(fromIntegral d)), 2*d)
          n'      = fromIntegral n

limiteSumaRedondeos3 :: Integer -> Integer
limiteSumaRedondeos3 = limite . sumaRedondeos3

-- 4ª definición
sumaRedondeos4 :: Integer -> [Integer]
sumaRedondeos4 n = xs ++ repeat x
    where n' = fromIntegral n
          m  = round (logBase 2 n')
          xs = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..m]]
          x  = last xs

limiteSumaRedondeos4 :: Integer -> Integer
limiteSumaRedondeos4 = limite . sumaRedondeos4

-- Comparación de eficiencia
--    λ> (sumaRedondeos1 4) !! 20000
--    3
--    (0.92 secs, 197,782,232 bytes)
--    λ> (sumaRedondeos1 4) !! 30000
--    3
--    (2.20 secs, 351,084,816 bytes)
--    λ> (sumaRedondeos3 4) !! 20000
--    3
--    (0.30 secs, 53,472,392 bytes)
--    λ> (sumaRedondeos4 4) !! 20000
--    3
--    (0.01 secs, 0 bytes)

-- En lo que sigue, usaremos la 3ª definición
sumaRedondeos :: Integer -> [Integer]
sumaRedondeos = sumaRedondeos3

-- 5ª definición
-- =============

limiteSumaRedondeos5 :: Integer -> Integer
limiteSumaRedondeos5 n = 
    sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]]
    where n' = fromIntegral n
          m  = round (logBase 2 n')

-- 1ª definición

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

sumaRedondeos1 :: Integer -> [Integer]

sumaRedondeos1 n =

[sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] | m <- [1..]]

where n' = fromIntegral n

limiteSumaRedondeos1 :: Integer -> Integer

limiteSumaRedondeos1 = limite . sumaRedondeos1

limite :: [Integer] -> Integer

limite xs = head [x | (x,y) <- zip xs (tail xs), x == y]

-- 2ª definición

sumaRedondeos2 :: Integer -> [Integer]

sumaRedondeos2 n =

scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..]]

where n' = fromIntegral n

limiteSumaRedondeos2 :: Integer -> Integer

limiteSumaRedondeos2 = limite . sumaRedondeos2

-- 3ª definición

sumaRedondeos3 :: Integer -> [Integer]

sumaRedondeos3 n = map fst (iterate f (round (n'/2),4))

where f (s,d) = (s + round (n'/(fromIntegral d)), 2*d)

n' = fromIntegral n

limiteSumaRedondeos3 :: Integer -> Integer

limiteSumaRedondeos3 = limite . sumaRedondeos3

-- 4ª definición

sumaRedondeos4 :: Integer -> [Integer]

sumaRedondeos4 n = xs ++ repeat x

where n' = fromIntegral n

m = round (logBase 2 n')

xs = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..m]]

x = last xs

limiteSumaRedondeos4 :: Integer -> Integer

limiteSumaRedondeos4 = limite . sumaRedondeos4

-- Comparación de eficiencia

-- λ> (sumaRedondeos1 4) !! 20000

-- 3

-- (0.92 secs, 197,782,232 bytes)

-- λ> (sumaRedondeos1 4) !! 30000

-- 3

-- (2.20 secs, 351,084,816 bytes)

-- λ> (sumaRedondeos3 4) !! 20000

-- 3

-- (0.30 secs, 53,472,392 bytes)

-- λ> (sumaRedondeos4 4) !! 20000

-- 3

-- (0.01 secs, 0 bytes)

-- En lo que sigue, usaremos la 3ª definición

sumaRedondeos :: Integer -> [Integer]

sumaRedondeos = sumaRedondeos3

-- 5ª definición

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

limiteSumaRedondeos5 :: Integer -> Integer

limiteSumaRedondeos5 n =

sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]]

where n' = fromIntegral n

m = round (logBase 2 n')

Meses: enero 2016

Agrupamiento por propiedad

Soluciones

De árboles a listas

Soluciones

Conjunto de funciones

Soluciones

Sumas digitales de primos consecutivos

Soluciones

Referencias

Antiimágenes en una función creciente

Soluciones

Relleno de matrices

Soluciones

Referencias

Primos que contienen al 2016

Soluciones

Referencias

Lista tautológica de literales

Soluciones

Fórmula dual

Soluciones

Puntos en una región

Soluciones

Suma con redondeos

Soluciones

Entradas recientes

Buscar

Correo electrónico