El artículo de esta semana de Antonio Roldán en su blog Números y hoja de cálculo es Máximo producto en la partición de un número (1).

Una partición de un entero positivo n es una forma de descomponer n como suma de enteros positivos. Dos sumas se considerarán iguales si solo difieren en el orden de los sumandos. Por ejemplo, las 11 particiones de 6 (con sus correspondientes productos) son

6 = 6                      |  6                     = 6
6 = 5 + 1                  |  5 x 1                 = 5
6 = 4 + 2                  |  4 x 2                 = 8
6 = 4 + 1 + 1              |  4 x 1 x 1             = 4
6 = 3 + 3                  |  3 x 3                 = 9
6 = 3 + 2 + 1              |  3 x 2 x 1             = 6
6 = 3 + 1 + 1 + 1          |  3 x 1 x 1 x 1         = 3
6 = 2 + 2 + 2              |  2 x 2 x 2             = 8
6 = 2 + 2 + 1 + 1          |  2 x 2 x 1 x 1         = 4
6 = 2 + 1 + 1 + 1 + 1      |  2 x 1 x 1 x 1 x 1     = 2
6 = 1 + 1 + 1 + 1 + 1 + 1  |  1 x 1 x 1 x 1 x 1 x 1 = 1

Se observa que el máximo producto de las particiones de 6 es 9.

Definir la función

maximoProductoParticiones :: Int -> Int

tal que (maximoProductoParticiones n) es el máximo de los productos de las particiones de n. Por ejemplo,

maximoProductoParticiones 4     ==  4
maximoProductoParticiones 5     ==  6
maximoProductoParticiones 6     ==  9
maximoProductoParticiones 7     ==  12
maximoProductoParticiones 8     ==  18
maximoProductoParticiones 9     ==  27
maximoProductoParticiones 50    ==  86093442
maximoProductoParticiones 100   ==  7412080755407364
maximoProductoParticiones 200   ==  61806308765265224723841283607058
length (show (maximoProductoParticiones (10^7)))  ==  1590405

Comprobar con QuickChek que los únicos posibles factores de (maximoProductoParticiones n) son 2 y 3.

Leer más…

Un número se dice ondulante si sus cifras alternan entre dos valores. Por ejemplo, 272 es ondulante, así como 2727. El primer cuadrado ondulante no trivial (todos los cuadrados de dos cifras son ondulantes) es 121 = 11^2.

Definir la función

cuadradosOndulantes :: Integer -> [Integer]

tal que (cuadradosOndulantes n) es la lista de los cuadrados ondulantes menores que n^2. Por ejemplo,

λ> cuadradosOndulantes 50000
[0,1,4,9,16,25,36,49,64,81,121,484,676,69696]

Leer más…

La persistencia multiplicativa de un número es la cantidad de pasos requeridos para reducirlo a una cifra multiplicando sus dígitos. Por ejemplo, la persistencia de 39 es 3 porque 3×9 = 27, 2×7 = 14 y 1×4 = 4.

Definir las funciones

persistencia     :: Integer -> Integer
menorPersistente :: Integer -> Integer

tales que

• (persistencia x) es la persistencia de x. Por ejemplo,

persistencia 39                             ==   3
persistencia 2677889                        ==   8
persistencia 26888999                       ==   9
persistencia 3778888999                     ==  10
persistencia 277777788888899                ==  11
persistencia 77777733332222222222222222222  ==  11

• (menorPersistente n) es el menor número con persistencia n. Por ejemplo,

menorPersistente 0  ==  1
menorPersistente 1  ==  10
menorPersistente 2  ==  25
menorPersistente 3  ==  39
menorPersistente 4  ==  77
menorPersistente 5  ==  679
menorPersistente 6  ==  6788
menorPersistente 7  ==  68889

Comprobar con QuickCheck si todos los números menores que 10^233 tienen una persistencia multiplicativa menor o igual que 11.

Leer más…

Un número perfecto es un número entero positivo que es igual a la suma de sus divisores propios. Por ejemplo, el 28 es perfecto porque sus divisores propios son 1, 2, 4, 7 y 14 y 1+2+4+7+14 = 28.

Un entero positivo x es un número cojonudo si existe un n tal que n > 0, x = 2^n·(2^(n+1)-1) y 2^(n+1)-1 es primo. Por ejemplo, el 28 es cojonudo ya que para n = 2 se verifica que 2 > 0, 28 = 2^2·(2^3-1) y 2^3-1 = 7 es primo.

Definir la funciones

esPerfecto                      :: Integer -> Bool
esCojonudo                      :: Integer -> Bool
equivalencia_CojonudosPerfectos :: Integer -> Bool

tales que

• (esPerfecto x) se verifica si x es perfecto. Por ejemplo,

esPerfecto 28  ==  True
esPerfecto 30  ==  False

• (esCojonudo x) se verifica si x es cojonudo. Por ejemplo,

esCojonudo 28                   ==  True
esCojonudo 30                   ==  False
esCojonudo 2305843008139952128  ==  True

• (equivalenciaCojonudosPerfectos n) se verifica si para todos los números x menores o iguales que n se tiene que x es perfecto si, y sólo si, x es cojonudo. Por ejemplo,

equivalenciaCojonudosPerfectos 3000  ==  True

Leer más…

Definir la función

subconjuntosAcotados :: [a] -> Int -> [[a]]

tal que (subconjuntosAcotados xs k) es la lista de los subconjuntos de xs con k elementos como máximo. Por ejemplo,

λ> subconjuntosAcotados "abcd" 1
["a","b","c","d",""]
λ> subconjuntosAcotados "abcd" 2
["ab","ac","ad","a","bc","bd","b","cd","c","d",""]
λ> subconjuntosAcotados "abcd" 3
["abc","abd","ab","acd","ac","ad","a",
 "bcd","bc","bd","b","cd","c","d",""]
λ> length (subconjuntosAcotados [1..1000] 2)
500501
λ> length (subconjuntosAcotados2 [1..2000] 2)
2001001

Leer más…

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]

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

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

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

Leer más…

El artículo de esta semana del blog Números y hoja de cálculo está dedicado a la Conjetura de Rassias. Dicha conjetura afirma que

Para cada número primo p > 2 existen dos primos a y b, con a < b, tales que (p-1)a = b+1

Dado un primo p > 2, los pares de Rassia de p son los pares de primos (a,b), con a < b, tales que (p-1)a = b+1. Por ejemplo, (2,7) y (3,11) son pares de Rassia de 5 ya que

• 2 y 7 son primos, 2 < 7 y (5-1)·2 = 7+1
• 3 y 11 son primos, 3 < 11 y (5-1)·3 = 11+1

Definir las siguientes funciones

paresRassias     :: Integer -> [(Integer,Integer)]
conjeturaRassias :: Integer -> Bool

tales que

• (paresRassias p) es la lista de los pares de Rassias del primo p (que se supone que es mayor que 2). Por ejemplo,

take 3 (paresRassias 5)    == [(2,7),(3,11),(5,19)]
take 3 (paresRassias 1229) == [(71,87187),(113,138763),(191,234547)]

• (conjeturaRassia x) se verifica si para todos los primos menores que x (y mayores que 2) se cumple la conjetura de Rassia. Por ejemplo,

conjeturaRassias (10^5)  ==  True

Leer más…

Definir la función

primoAnterior :: Integer -> Integer

tal que (primoAnterior n) es el mayor primo menor que n (donde n > 2). Por ejemplo,

primoAnterior 10     ==  7
primoAnterior 17     ==  13
primoAnterior 30     ==  29
primoAnterior 2016   ==  2011
primoAnterior 15726  ==  15683

Calcular el menor número cuya distancia a su primo anterior es mayor que 40.

Leer más…

Un número primo se dice que es un primo de Kamenetsky si al anteponerlo cualquier dígito se obtiene un número compuesto. Por ejemplo, el 5 es un primo de Kamenetsky ya que 15, 25, 35, 45, 55, 65, 75, 85 y 95 son compuestos. También lo es 149 ya que 1149, 2149, 3149, 4149, 5149, 6149, 7149, 8149 y 9149 son compuestos.

Definir la sucesión

primosKamenetsky :: [Integer]

tal que sus elementos son los números primos de Kamenetsky. Por ejemplo,

take 5 primosKamenetsky  ==  [2,5,149,401,509]

Leer más…

Un número de Harshad es un entero divisible entre la suma de sus dígitos. Por ejemplo, 201 es un número de Harshad porque es divisible por 3 (la suma de sus dígitos). Cuando se elimina el último dígito de 201 se obtiene 20 que también es un número de Harshad. Cuando se elimina el último dígito de 20 se obtiene 2 que también es un número de Harshad. Los números como el 201 que son de Harshad y que los números obtenidos eliminando sus últimos dígitos siguen siendo de Harshad se llaman números de Harshad hereditarios por la derecha. Definir la función

numeroHHD :: Int -> Bool

tal que (numeroHHD n) se verifica si n es un número de Harshad hereditario por la derecha. Por ejemplo,

numeroHHD 201  ==  True
numeroHHD 140  ==  False
numeroHHD 1104 ==  False

Calcular el mayor número de Harshad hereditario por la derecha con tres dígitos.

Leer más…

Un triángulo geométrico es un triángulo de lados enteros, representados por la terna (a,b,c) tal que a ≤ b ≤ c y están en progresión geométrica, es decir, b^2 = a*c. Por ejemplo, un triángulo de lados a = 144, b = 156 y c = 169.

Definir la función

numeroTG :: Integer -> Int

tal que (numeroTG n) es el número de triángulos geométricos de perímetro menor o igual que n. Por ejemplo

numeroTG 10  == 3
numeroTG 100 == 42
numeroTG 200 == 91

Nota: Los triángulos geométricos de perímetro menor o igual que 20 son

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

Se observa que (1,2,4) aunque cumple que 1+2+4 <= 10 y 2^2 = 1*4 no pertenece a la lista ya que 1+2 > 4 y, por tanto, no hay ningún triángulo cuyos lados midan 1, 2 y 4.

Leer más…

Leer más…

El complemento de un número positivo x se calcula por el siguiente procedimiento:

• si x es mayor que 9, se toma cada dígito por su valor posicional y se resta del mayor los otro dígitos. Por ejemplo, el complemento de 1448 es 1000 - 400 - 40 - 8 = 552. Para
• si x es menor que 10, su complemento es x.

Definir las funciones

cadena    :: Integer -> [Integer]
conCadena :: Int -> [Integer]

tales que

• (cadena x) es la cadena de primos a partir de x tal que cada uno es el complemento del anterior. Por ejemplo,

cadena 8         == []
cadena 7         == [7]
cadena 13        == [13,7]
cadena 643       == [643,557,443]
cadena 18127     == [18127,1873,127,73,67,53,47]
cadena 18181213  == [18181213,1818787,181213,18787,1213,787,613,587]

• (conCadena n) es la lista de números cuyas cadenas tienen n elementos. Por ejemplo,

take 6 (conCadena 3)                == [23,31,61,67,103,307]
[head (conCadena n) | n <- [4..8]]  == [37,43,157,18127,181873]

Leer más…

Los árboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo

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

Por ejemplo, el árbol

     9
    / \
   /   \
  3     7
 / \
2   4

se representa por

N 9 (N 3 (H 2) (H 4)) (H 7)

Definir las siguientes funciones

preorden :: Arbol a -> [a]
inorden  :: Arbol a -> [a]
arboles  :: Eq a => [a] -> [a] -> [Arbol a]

tales que

• (preorden x) es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo,

preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]

• (inorden x) es la lista correspondiente al recorrido inorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación visita la raíz del árbol y, finalmente, recorre el subárbol derecho. Por ejemplo,

inorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,3,4,9,7]

• (arboles xs ys) es la lista de los árboles con recorrido preorden xs y recorrido inorden de ys. Por ejemplo,

λ> arboles [9,3,2,4,7] [2,3,4,9,7]
[N 9 (N 3 (H 2) (H 4)) (H 7)]
λ> arboles [9,3,2,4,7] [2,4,3,9,7]
[]
λ> arboles [1,1,1,2,3] [1,1,2,1,3]
[N 1 (H 1) (N 1 (H 2) (H 3)),
N 1 (N 1 (H 1) (H 2)) (H 3)]
λ> let x = N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))
λ> arboles (preorden x) (inorden x)
[N 1 (H 1) (N 1 (H 3) (N 1 (H 1) (N 1 (H 2) (H 3)))),
N 1 (H 1) (N 1 (H 3) (N 1 (N 1 (H 1) (H 2)) (H 3))),
N 1 (N 1 (H 1) (H 3)) (N 1 (H 1) (N 1 (H 2) (H 3))),
N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))]

Comprobar con QuickCheck, que para todo árbol x se verifican las siguientes propiedades

prop_arboles1 :: Arbol Int -> Bool
prop_arboles1 x =
    x `elem` arboles (preorden x) (inorden x)

prop_arboles2 :: Arbol Int -> Bool
prop_arboles2 x =
    and [preorden a == xs && inorden a == ys | a <- as]
    where xs = preorden x
          ys = inorden x
          as = arboles xs ys

Nota: Para la comprobación, se usa el siguiente generador

import Control.Monad

instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbol
    where
      arbol 0       = liftM H arbitrary
      arbol n | n>0 = oneof [liftM H arbitrary,
                             liftM3 N arbitrary subarbol subarbol]
                      where subarbol = arbol (div n 2)

Leer más…

El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.

Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.

Para representar los caminos se definen los siguientes tipos de datos:

data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]

Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].

Definir las funciones

caminos  :: Int -> Int -> [Camino]
nCaminos :: Int -> Int -> Integer

tales que

• (caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

λ> caminos 2 2
[[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]
λ> caminos 1 3
[[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]
λ> caminos 2 3
[[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],
[D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

• (nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

nCaminos 2 2  ==  6
nCaminos 1 3  ==  4
nCaminos 2 3  ==  10
length (show (nCaminos 20000 30000))  ==  14612
length (show (nCaminos 30000 20000))  ==  14612

Leer más…

Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.

Definir la función

centro :: (Num a, Eq a) => [a] -> Maybe Int

tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,

centro [1,3,4,5,-2,1]           ==  Just 2
centro [1,6,4,5,-2,1]           ==  Nothing
centro [1,2,3,4,3,2,1]          ==  Just 3
centro [1,100,50,-51,1,1]       ==  Just 1
centro [1,2,3,4,5,6]            ==  Nothing
centro [20,10,30,10,10,15,35]   ==  Just 3
centro [20,10,-80,10,10,15,35]  ==  Just 0
centro [10,-80,10,10,15,35,20]  ==  Just 6
centro [0,0,0,0,0]              ==  Just 0
centro [-1,-2,-3,-4,-3,-2,-1]   ==  Just 3

Leer más…

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

( 0 1 0 )
( 1 0 0 )
( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

torres  :: Int -> [Matrix Int]
nTorres :: Int -> Integer

tales que + (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

λ> torres 3
[( 1 0 0 )
 ( 0 1 0 )
 ( 0 0 1 )
,( 1 0 0 )
 ( 0 0 1 )
 ( 0 1 0 )
,( 0 1 0 )
 ( 1 0 0 )
 ( 0 0 1 )
,( 0 1 0 )
 ( 0 0 1 )
 ( 1 0 0 )
,( 0 0 1 )
 ( 1 0 0 )
 ( 0 1 0 )
,( 0 0 1 )
 ( 0 1 0 )
 ( 1 0 0 )
]

• (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,

λ> nTorres 3
6
λ> length (show (nTorres (10^4)))
35660

Leer más…

La cadena infinita "1234321234321234321...", formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la serie de los números naturales, como se observa a continuación:

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ...
1, 2, 3, 4,  5,   6,  7,    8,   9,   10,    11, ...

Definir la lista

reloj :: [Integer]

cuyos elementos son los términos de la sucesión anterior. Por ejemplo,

λ> take 11 reloj
[1,2,3,4,32,123,43,2123,432,1234,32123]

Nota: La relación entre la sucesión y el funcionamiento del reloj se puede ver en The Mathematics Behind Prague's Horloge Introduction.

Leer más…

Leer más…

Definir la función

particionesFijas :: Int -> Int -> [[Int]]

tal que (particionesFijas n k) es la lista de listas de k números naturales no crecientes cuya suma es n. Por ejemplo,

λ> particionesFijas 8 2
[[4,4],[5,3],[6,2],[7,1]]
λ> particionesFijas 8 3
[[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]
λ> particionesFijas 9 3
[[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]
λ> length (particionesFijas 67 5)
8056

Leer más…

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.

Definir, mediante búsqueda en espacio de estados, la función

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

tal (jarras (a,b,c)) es la lista de las soluciones del problema de las jarras (a,b,c). Por ejemplo,

λ> take 2 (map snd (sort [(length xs,xs) | xs <- jarras (4,3,2)]))
[[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
 [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:

• (0,0) se inicia con las dos jarras vacías,
• (4,0) se llena la jarra de 4 con el grifo,
• (1,3) se llena la de 3 con la de 4,
• (1,0) se vacía la de 3,
• (0,1) se pasa el contenido de la primera a la segunda,
• (4,1) se llena la primera con el grifo,
• (2,3) se llena la segunda con la primera.

Otros ejemplos

λ> (snd . head . sort) [(length xs,xs) | xs <- jarras (15,10,5)]
[(0,0),(15,0),(5,10)]
λ> jarras (15,10,4)
[]

Nota: Las librerías necesarias se encuentran en la página de códigos.

Leer más…

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir, mediante búsqueda en espacio de estados, la función

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

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

λ> domino [(1,2),(2,3),(1,4)]
[[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]
λ> domino [(1,2),(1,1),(1,4)]
[[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]
λ> domino [(1,2),(3,4),(2,3)]
[[(1,2),(2,3),(3,4)]]
λ> domino [(1,2),(2,3),(5,4)]
[]
λ> domino [(x,y) | x <- [1..2], y <- [x..2]]
[[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]
λ> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])
[(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]
[(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]
[(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]
[(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]
[(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]
[(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]
[(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]
[(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]
[(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]
λ> length (domino [(x,y) | x <- [1..4], y <- [x..4]])
0

Nota: Las librerías necesarias se encuentran en la página de códigos.

Leer más…

Para cada entero positivo n, existe una única sucesión que empieza en 1, termina en n y en la que cada uno de sus elementos es el doble de su anterior o el doble más uno. Dicha sucesión se llama la sucesión duplicadora de n. Por ejemplo, la sucesión duplicadora de 13 es [1, 3, 6, 13], ya que

 3 = 2*1 +1
 6 = 2*3
13 = 2*6 +1

Definir la función

duplicadora :: Integer -> [Integer]

tal que (duplicadora n) es la sucesión duplicadora de n. Por ejemplo,

duplicadora 13                   ==  [1,3,6,13]
duplicadora 17                   ==  [1,2,4,8,17]
length (duplicadora (10^40000))  ==  132878

Leer más…

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puestas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

• Inicialmente todas las puertas están cerradas.
• El primer camarero cambia de estado las puertas de todas las habitaciones.
• El segundo cambia de estado de las puertas de las habitaciones pares.
• El tercero cambia de estado todas las puertas que son múltiplos de 3.
• El cuarto cambia de estado todas las puertas que son múltiplos de 4
• Así, hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

Los estados de las puertas se representan por el siguiente tipo de datos

data Estado = Abierta | Cerrada
              deriving (Eq, Show)

Definir la función

final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

λ> final 5
[Abierta,Cerrada,Cerrada,Abierta,Cerrada]
λ> final 7
[Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Leer más…

Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.

Definir la función

soluciones :: [String] -> String -> [[String]]

tal que (soluciones bs cs) es la lista de las soluciones del juego de los bloque usando los bloques bs (cada bloque es una cadena de dos letras mayúsculas) para formar la palabra cs. Por ejemplo,

λ> soluciones ["AB","NO","OA"] "ANA"
[["AB","NO","OA"],["OA","NO","AB"]]
λ> soluciones ["AB","NE","OA"] "Bea"
[["AB","NE","OA"]]
λ> soluciones ["AB","NE","OA"] "EvA"
[]
λ> soluciones ["AB","NO","OA","NC"] "ANA"
[["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]
λ> soluciones ["AB","NO","OA","NC"] "Anca"
[["AB","NO","NC","OA"],["OA","NO","NC","AB"]]
λ> soluciones (["AB","NO","OA"] ++ replicate (10^6) "PQ") "ANA"
[["AB","NO","OA"],["OA","NO","AB"]]

Leer más…

Un número entero positivo se dice que es

• creciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 134479.
• decreciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 664210.
• no monótono si no es creciente ni decreciente; por ejemplo, 155369.

Para cada entero positivo n, la densidad números no monótonos hasta n es el cociente entre la cantidad de n números no monótonos entre menores o iguales que n y el número n. Por ejemplo, hasta 150 hay 19 números no monótonos (101, 102, 103, 104, 105, 106, 107, 108, 109, 120, 121, 130, 131, 132, 140, 141, 142, 143 y 150); por tanto, la densidad hasta 150 es 19/150 = 0.12666667

Definir las siguientes funciones

densidad              :: Integer -> Float
menorConDensidadMayor :: Float -> Integer

tales que

• (densidad n) es la densidad de números no monótonos hasta n. Por ejemplo,

densidad 100  ==  0.0
densidad 200  ==  0.265
densidad 400  ==  0.4375
densidad 800  ==  0.53375

• (menorConDensidadMayor x) es el menor número n tal que la densidad de números no monótonos hasta n es mayor o igual que x. Por ejemplo,

menorConDensidadMayor 0.5   ==  538
densidad 537                ==  0.49906892
densidad 538                ==  0.5
menorConDensidadMayor 0.9   ==  21780
densidad 21779              ==  0.8999954
densidad 21780              ==  0.9
menorConDensidadMayor 0.99  ==  1586996

Leer más…

La sucesión fractal

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2,
10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

• los términos pares forman la sucesión de los números naturales

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

• los términos impares forman la misma sucesión original

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

sucFractal     :: [Integer]
sumaSucFractal :: Integer -> Integer

tales que

• sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
sucFractal !! 30     == 15
sucFractal !! (10^7) == 5000000

• (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

sumaSucFractal 10      == 13
sumaSucFractal (10^5)  == 1666617368
sumaSucFractal (10^10) == 16666666661668691669
sumaSucFractal (10^15) == 166666666666666166673722792954
sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
length (show (sumaSucFractal (10^15000))) == 30000
sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

Leer más…

Un conjunto de primos emparejables es un conjunto S de números primos tales que al concatenar cualquier par de elementos de S se obtiene un número primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.

Definir la función

emparejables :: Integer -> Integer -> [[Integer]]

tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,

take 5 (emparejables 2   10)  ==  [[3,7]]
take 5 (emparejables 3   10)  ==  []
take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]
take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]
take 5 (emparejables 4  100)  ==  []
take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]

Leer más…

Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].

Definir la función

cadenasDivisores :: Int -> [[Int]]

tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,

λ> cadenasDivisores 12
[[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]
λ> length (cadenaDivisores 48)
48
λ> length (cadenaDivisores 120)
132

Leer más…

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

mcd(a,b) = a,                   si b = 0
         = b,                   si a = 0
         = mcd (a módulo b, b), si a > b
         = mcd (a, b módulo a), si b >= a

Definir la función

mcdYdivisiones :: Int -> Int -> (Int,Int)

tal que (mcdYdivisiones a b) es el número de divisiones usadas en el cálculo del máximo común divisor de a y b mediante el algoritmo de Euclides. Por ejemplo,

mcdYdivisiones 252 198 == (18,4)

ya que los 4 divisiones del cálculo son

  mcd 252 198
= mcd  54 198
= mcd  54  36
= mcd  18  36
= mcd  18   0

Comprobar con QuickCheck que el número de divisiones requeridas por el algoritmo de Euclides para calcular el MCD de a y b es igual o menor que cinco veces el número de dígitos de menor de los números a y b.

Leer más…

El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período "abababab" es "ab" ya que "abababab" se obtiene repitiendo tres veces la lista "ab".

Definir la función

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

tal que (periodo xs) es el período de xs. Por ejemplo,

periodo "ababab"      ==  "ab"
periodo "buenobueno"  ==  "bueno"
periodo "oooooo"      ==  "o"
periodo "sevilla"     ==  "sevilla"

Leer más…

Definir la función

mezclaTodas :: Ord a => [[a]] -> [a]

tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,

λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
[2,3,4,5,6,7,8,9,10,11]
λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
[2,4,6,8,9,10,12,14,16,18]

Leer más…

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

data Expr = Var String
          | S Expr Expr
          | P Expr Expre

Por ejemplo, x.(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.

Definir las funciones

esTermino, esNormal :: Expr -> Bool

tales que

• (esTermino a) se verifica si a es un término. Por ejemplo,

esTermino (V "x")                                    == True
esTermino (P (V "x") (P (V "y") (V "z")))            == True
esTermino (P (V "x") (S (V "y") (V "z")))            == False
esTermino (S (V "x") (P (V "y") (V "z")))            == False

• (esNormal a) se verifica si a está en forma normal. Por ejemplo,

esNormal (V "x")                                     == True
esNormal (P (V "x") (P (V "y") (V "z")))             == True
esNormal (S (V "x") (P (V "y") (V "z")))             == True
esNormal (P (V "x") (S (V "y") (V "z")))             == False
esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

Leer más…

Una serie de potencias es una serie de la forma

a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

type Serie a = [a]

Definir las siguientes funciones

opuesta      :: Num a => Serie a -> Serie a
suma         :: Num a => Serie a -> Serie a -> Serie a
resta        :: Num a => Serie a -> Serie a -> Serie a
producto     :: Num a => Serie a -> Serie a -> Serie a
cociente     :: Fractional a => Serie a -> Serie a -> Serie a
derivada     :: (Num a, Enum a) => Serie a -> Serie a
integral     :: (Fractional a, Enum a) => Serie a -> Serie a
expx         :: Serie Rational

tales que

• (opuesta xs) es la opuesta de la serie xs. Por ejemplo,

λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]

• (suma xs ys) es la suma de las series xs e ys. Por ejemplo,

λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]

• (resta xs ys) es la resta de las series xs es ys. Por ejemplo,

λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]

• (producto xs ys) es el producto de las series xs e ys. Por ejemplo,

λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]

• (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]

• (derivada xs) es la derivada de la serie xs. Por ejemplo,

λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]

• (integral xs) es la integral de la serie xs. Por ejemplo,

λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]

• expx es la serie de la función exponencial. Por ejemplo,

λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Leer más…

Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.

Definir la constante

pandigitalesPrimos :: [Int]

tal que sus elementos son los números pandigitales, ordenados de mayor a menor. Por ejemplo,

take 3 pandigitalesPrimos       ==  [7652413,7642513,7641253]
2143 `elem` pandigitalesPrimos  ==  True
length pandigitalesPrimos       ==  538

Leer más…

Definir la función

nMinimoCambios :: Ord a => [a] -> Int

tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,

nMinimoCambios [3,5,3,7,9,6]      ==  4
nMinimoCambios [3,5,3,7,3,3]      ==  2
nMinimoCambios "Salamanca"        ==  5
nMinimoCambios (4 : [1..500000])  ==  499999

En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.

Leer más…

Sea \(\{b_i \mid i \geq 1\}\) una sucesión infinita de números enteros mayores que 1. Entonces, todo entero \(x\) mayor que cero se puede escribir de forma única como \[ x = x_0 + x_1 b_1 + x_2 b_1 b_2 + \dots + x_n b_1 b_2 \dotsm b_n, \] donde cada \(x_i\) satisface la condición \(0 \leq x_i < b_{i+1}\). Se dice que \([x_n, x_{n-1}, \dots, x_2, x_1, x_0]\) es la representación de \(x\) en la base \((b_i).

Por ejemplo, la representación de 377 en la base \((2i)_{i \geq 1}\) es \([7,5,0,1]\), ya que \[ 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6, \] y además: \[ 0 \leq 1 < 2, \quad 0 \leq 0 < 4, \quad 0 \leq 5 < 6, \quad 0 \leq 7 < 8. \]

Definir las funciones

decimalAmultiple :: [Int] -> Int -> [Int]
multipleAdecimal :: [Int] -> [Int] -> Int

tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,

decimalAmultiple [2,4..] 377                      ==  [7,5,0,1]
multipleAdecimal [2,4..] [7,5,0,1]                ==  377
decimalAmultiple [2,5..] 377                      ==  [4,5,3,1]
multipleAdecimal [2,5..] [4,5,3,1]                ==  377
decimalAmultiple [2^n | n <- [1..]] 2015          ==  [1,15,3,3,1]
multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1]  ==  2015
decimalAmultiple (repeat 10) 2015                 ==  [2,0,1,5]
multipleAdecimal (repeat 10) [2,0,1,5]            ==  2015

Comprobar con QuickCheck que se verifican las siguientes propiedades

prop_inversas :: [Int] -> Int -> Property
prop_inversas bs x =
    x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x

prop_coeficientes :: [Int] -> Int -> Property
prop_coeficientes bs x =
    x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs]
    where cs = reverse (decimalAmultiple bs x)

para distintas bases dadas. Por ejemplo,

λ> quickCheck (prop_inversas [2,4..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_inversas [3,5..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_coeficientes [2,4..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_coeficientes [3,5..])
+++ OK, passed 100 tests.