Se dice que un elemento x de una lista xs respeta la ordenación si x es mayor o igual que todos lo que tiene delante en xs y es menor o igual que todos lo que tiene detrás en xs. Por ejemplo, en la lista lista [3,2,1,4,6,5,7,9,8] el número 4 respeta la ordenación pero el número 5 no la respeta (porque es mayor que el 6 que está delante).

Definir la función

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

tal que (respetuosos xs) es la lista de los elementos de xs que respetan la ordenación. Por ejemplo,

respetuosos [3,2,1,4,6,4,7,9,8]  ==  [4,7]
respetuosos [2,1,3,4,6,4,7,8,9]  ==  [3,4,7,8,9]
respetuosos "abaco"              ==  "aco"
respetuosos "amor"               ==  "amor"
respetuosos "romanos"            ==  "s"
respetuosos [1..9]               ==  [1,2,3,4,5,6,7,8,9]
respetuosos [9,8..1]             ==  []

Comprobar con QuickCheck que para cualquier lista de enteros xs se verifican las siguientes propiedades:

• todos los elementos de (sort xs) respetan la ordenación y
• en la lista (nub (reverse (sort xs))) hay como máximo un elemento que respeta la ordenación.

Leer más…

Definir la función

sinCerosFinales :: Int -> Int

tal que (sinCerosFinales n) es el número obtenido eliminando los ceros finales de n. Por ejemplo,

sinCerosFinales 104050     == 10405
sinCerosFinales 960000     == 96
sinCerosFinales 100050     == 10005
sinCerosFinales (-10050)   == -1005
sinCerosFinales 12         == 12
sinCerosFinales 0          == 0

Comprobar con QuickCheck que, para cualquier número entero n,

sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

Leer más…

Una lista de listas es engarzada si el último elemento de cada lista coincide con el primero de la siguiente.

Definir la función

engarzada :: Eq a => [[a]] -> Bool

tal que (engarzada xss) se verifica si xss es una lista engarzada. Por ejemplo,

engarzada [[1,2,3], [3,5], [5,9,0]] == True
engarzada [[1,4,5], [5,0], [1,0]]   == False
engarzada [[1,4,5], [], [1,0]]      == False
engarzada [[2]]                     == True

Leer más…

Una lista de números enteros se llama alternada si sus elementos son alternativamente par/impar o impar/par.

Definir la función

alternada :: [Int] -> Bool

tal que (alternada xs) se verifica si xs es una lista alternada. Por ejemplo,

alternada [1,2,3]     == True
alternada [1,4,6,5]   == False
alternada [1,4,3,5]   == False
alternada [8,1,2,3,4] == True
alternada [8,1,2,3]   == True
alternada [8]         == True
alternada [7]         == True

Leer más…

Definir la función

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

tal que (sumasParesImpares) xs es el par formado por la suma de los elementos de xs en posiciones pares y por la suma de los elementos de xs en posiciones impares. Por ejemplo,

sumasParesImpares []         ==  (0,0)
sumasParesImpares [3]        ==  (3,0)
sumasParesImpares [3,2]      ==  (3,2)
sumasParesImpares [3,2,1]    ==  (4,2)
sumasParesImpares [3,2,1,5]  ==  (4,7)
sumasParesImpares [1..10^7]  ==  (25000000000000,25000005000000)

Leer más…

El problema de la particiones óptimas consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una partición óptima de xs. Por ejemplo, la partición óptima de [2,3,5] es ([2,3],[5]) ya que |(2+3) - 5| = 0. Una lista puede terner distintas particiones óptimas. Por ejemplo, [1,1,2,3] tiene dos particiones óptimas ([1,2],[1,3]) y ([1,1,2],[3]) ambas con diferencia 1 (es decir, 1 = |(1+2)-(1+3)| = |(1+1+2)-3|.

Definir la función

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

tal que (particionesOptimas xs) es la lista de las particiones óptimas de xs. Por ejemplo,

particionesOptimas [2,3,5]    ==  [([2,3],[5])]
particionesOptimas [1,1,2,3]  ==  [([1,2],[1,3]),([1,1,2],[3])]
particionesOptimas [5,0,5]    ==  [([0,5],[5])]
particionesOptimas [5,5]      ==  [([5],[5])]
particionesOptimas [5]        ==  [([],[5])]

Leer más…

El teorema de Euclides afirma que existen infinitos números primos. En palabras de Euclides,

"Hay más números primos que cualquier cantidad propuesta de números primos." (Proposición 20 del Libro IX de "Los Elementos").

Su demostración se basa en que si p₁,...,pₙ son los primeros n números primos, entonces entre 1+pₙ y 1+p₁·p₂·...·pₙ hay algún número primo. La cantidad de dichos números primos se llama el n-ésimo hueco de Euclides. Por ejemplo, para n = 3 se tiene que p₁ = 2, p₂ = 3 y p₃ = 5 entre 1+p₃ = 6 y 1+p₁·p₂·p₃ = 31 hay 8 números primos (7, 11, 13, 17, 19, 23, 29 y 31), por lo que el valor del tercer hueco de Euclides es 8.

Definir la función

hueco :: Int -> Integer

tal que (hueco n) es el n-ésimo hueco de Eulides. Por ejemplo,

hueco 3                   ==  8
[hueco n | n <- [1..8]]   ==  [1,2,8,43,339,3242,42324,646021]

Leer más…

Un número de Carol es un número entero de la forma \(4^n-2^{n+1}-1\) o, equivalentemente, \((2^n-1)^2-2\). Los primeros números de Carol son -1, 7, 47, 223, 959, 3967, 16127, 65023, 261119, 1046527.

Definir las funciones

carol        :: Integer -> Integer
carolBinario :: Integer -> Integer

tales que

• (carol n) es el n-ésimo número de Carol. Por ejemplo,

carol  3  ==  47
carol  4  ==  223
carol 25  ==  1125899839733759

• (carolBinario n) es la representación binaria del n-ésimo número de Carol. Por ejemplo,

carolBinario 3  ==  101111
carolBinario 4  ==  11011111
carolBinario 5  ==  1110111111

Comprobar con QuickCheck que, para n > 2, la representación binaria del n-ésimo número de Carol es el número formado por n-2 veces el dígito 1, seguido por un 0 y a continuación n+1 veces el dígito 1.

Leer más…

Se considera el siguiente par de operaciones sobre los números:

• multiplicar por dos
• restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

4 ------> 8 ------> 7
   (x2)      (-1)

y el menor número de operaciones para transformar 2 en 5 es 4

2 ------> 4 ------> 3 ------> 6 ------> 5
   (x2)      (-1)      (x2)      (-1)

Definir las siguientes funciones

arbolOp :: Int -> Int -> Arbol
minNOp  :: Int -> Int -> Int

tales que

• (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

    λ> arbolOp 4 1
    N 4 (H 8) (H 3)
    λ> arbolOp 4 2
    N 4 (N 8 (H 16) (H 7))
        (N 3 (H 6) (H 2))
    λ> arbolOp 2 3
    N 2 (N 4
           (N 8 (H 16) (H 7))
           (N 3 (H 6) (H 2)))
        (N 1
           (N 2 (H 4) (H 1))
           (H 0))
    λ> arbolOp 2 4
    N 2 (N 4 (N 8
                (N 16 (H 32) (H 15))
                (N 7 (H 14) (H 6)))
             (N 3
                (N 6 (H 12) (H 5))
                (N 2 (H 4) (H 1))))
        (N 1 (N 2
                (N 4 (H 8) (H 3))
                (N 1 (H 2) (H 0)))
             (H 0))

• (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

minNOp 4 7  ==  2
minNOp 2 5  ==  4

Leer más…

Definir las siguientes funciones

potenciasDe2  :: Integer -> [Integer]
menorPotenciaDe2 :: Integer -> Integer

tales que

• (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,

λ> take 5 (potenciasDe2 3)
[32,32768,33554432,34359738368,35184372088832]
λ> take 2 (potenciasDe2 102)
[1024,102844034832575377634685573909834406561420991602098741459288064]

• (menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,

λ> menorPotenciaDe2 10
1024
λ> menorPotenciaDe2 25
256
λ> menorPotenciaDe2 62
6277101735386680763835789423207666416102355444464034512896
λ> menorPotenciaDe2 425
42535295865117307932921825928971026432
λ> menorPotenciaDe2 967140655691
9671406556917033397649408
λ> [menorPotenciaDe2 a | a <- [1..10]]
[1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.

Leer más…

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
               deriving Show

Por ejemplo, los árboles

  1         1             1
 / \       / \           / \
2   3     2   3         2   3
    |        /|\       /|\  |
    4       4 5 6     4 5 6 7

se representan por

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]
ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

En el primer ejemplo la máxima ramificación es 2 (en el nodo 1 que tiene 2 hijos), la del segundo es 3 (en el nodo 3 que tiene 3 hijos) y la del tercero es 3 (en el nodo 3 que tiene 3 hijos).

Definir la función

maximaRamificacion :: Arbol a -> Int

tal que (maximaRamificacion a) es la máxima ramificación del árbol a. Por ejemplo,

maximaRamificacion ej1  ==  2
maximaRamificacion ej2  ==  3
maximaRamificacion ej3  ==  3

Leer más…

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función

menorSerieCompuesta :: Integer -> (Integer,Integer)

tal que (menorSerieCompuesta n) es la menor serie compuesta (es decir, la que tiene menores elementos) de longitud 3. Por ejemplo,

menorSerieCompuesta 3    ==  (8,10)
menorSerieCompuesta 4    ==  (24,27)
menorSerieCompuesta 5    ==  (24,28)
menorSerieCompuesta 150  ==  (4652354,4652503)

Comprobar con QuickCheck que para n > 1, el primer elemento de (menorSerieCompuesta n) es igual al primero de (menorSerieCompuesta (n-1)) o al primero de (menorSerieCompuesta (n+1)).

Leer más…

Una lista binaria es ondulante si sus elementos son alternativamente 0 y 1. Por ejemplo, las listas [0,1,0,1,0] y [1,0,1,0] son ondulantes.

Definir la función

minConmutacionesOndulante :: [Int] -> Int

tal que (minConmutacionesOndulante xs) es el mínimo número de conmutaciones (es decir, cambios de 0 a 1 o de 1 a 0) necesarias para transformar xs en una lista ondulante. Por ejemplo,

minConmutacionesOndulante [1,1,1]                ==  1
minConmutacionesOndulante [0,0,0,1,0,1,0,1,1,1]  ==  2

En el primer ejemplo basta conmutar el elemento en la posición 1 para obtener [1,0,1] y el segundo ejemplo los elementos en las posiciones 1 y 8 para obtener [0,1,0,1,0,1,0,1,0,1].

Leer más…

La semana pasada, Pepe Muñoz Santonja publicó en su blog Algo más que números el artículo Números de Dudeney en la base OEIS.

Un número de Dudeney es un número entero n tal que el cubo de la suma de sus dígitos es igual a n. Por ejemplo, 512 es un número de Dudeney ya que (5+1+2)^3 = 8^3 = 512.

Se puede generalizar variando el exponente: Un número de Dudeney de orden k es un número entero n tal que la potencia k-ésima de la suma de sus dígitos es igual a n. Por ejemplo, 2401 es un número de Dudeney de orden 4 ya que (2+4+0+1)^4 = 7^4 = 2401.

Definir la función

numerosDudeney :: Integer -> [Integer]

tal que (numerosDudeney k) es la lista de los números de Dudeney oe orden k. Por ejemplo,

take 6 (numerosDudeney 3)  == [1,512,4913,5832,17576,19683]
take 6 (numerosDudeney 4)  == [1,2401,234256,390625,614656,1679616]
take 2 (numerosDudeney 20) == [1,1215766545905692880100000000000000000000]

Comprobar con QuickCheck que 19683 es el mayor número de Dudeney de orden 3.

Leer más…

Un número es poderoso si es igual a la suma de sus dígitos elevados a sus respectivas posiciones. Por ejemplo, los números 89, 135 y 1306 son poderosos ya que

  89 = 8^1 + 9^2
 135 = 1^1 + 3^2 + 5^3.
1306 = 1^1 + 3^2 + 0^3 + 6^4

Definir la función

esPoderoso :: Integer -> Bool

tal que (esPoderoso n) se verifica si n es poderoso. Por ejemplo,

λ> esPoderoso 135
True
λ> esPoderoso 80
False
λ> esPoderoso 89
True
λ> esPoderoso 12157692622039623539
True
λ> [n | n <- [10..30000], esPoderoso n]
[89,135,175,518,598,1306,1676,2427]

Comprobar con QuickCheck que 12157692622039623539 es el mayor número poderoso.

Leer más…

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