Definir las funciones

sumas  :: Integer -> Integer -> [[Integer]]
esSuma :: Integer -> Integer -> Bool

tales que

• (sumas n k) es la lista de las descomposiones de n en k sumandos pares y distintos. Por ejemplo,

sumas 16 3  ==  [[2,4,10],[2,6,8]]
sumas 18 4  ==  []

• (esSuma n k) se verifica si n se puede escribir como suma de k sumandos pares y distintos. Por ejemplo,

esSuma 16 3  ==  True
esSuma 18 4  ==  False
esSuma (10^5000) (10^7)  ==  True
esSuma (11^5000) (10^7)  ==  False

Leer más…

El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

Definir la función

menor :: Integer -> Integer

tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,

menor 1  ==  2
menor 2  ==  6
menor 3  ==  24
menor 4  ==  120
length (show (menor (4*10^4)))  ==  207945

Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.

Leer más…

Una terna (a,b,c) de números enteros positivos es especial si se verifica que ab-c, bc-a y ca-b son potencias de 2. Por ejemplo, (3,5,7) es especial ya que

3 * 5 - 7 =  8 = 2^3
5 * 7 - 3 = 32 = 2^5
7 * 3 - 5 = 16 = 2^4

Definir las funciones

esEspecial       :: (Integer,Integer,Integer) -> Bool
ternasEspeciales :: [(Integer,Integer,Integer)]

tales que

• (esEspecial t) se verifica si t es una terna especial. Por ejemplo,

esEspecial (3,5,7)  ==  True
esEspecial (5,7,9)  ==  False

• ternasEspeciales es la lista de las ternasEspeciales ordenadas según su suma y las de la misma suma por orden lexicográfico. Por ejemplo,

λ> take 16 ternasEspeciales
[(2,2,2),
 (2,2,3),(2,3,2),(3,2,2),
 (3,5,7),(3,7,5),(5,3,7),(5,7,3),(7,3,5),(7,5,3),
 (2,6,11),(2,11,6),(6,2,11),(6,11,2),(11,2,6),(11,6,2)]

Comprobar con QuickCheck que sólo hay 16 ternas especiales; es decir, para toda terna t de enteros positivos, t pertenece a la lista de los 16 primeros elementos de ternasEspeciales o no es una terna especial.

Nota: Este ejercicio está basado en el problema N5 de la Olimpíada Internacional de Matemáticas (IMO) del 2015.

Leer más…

Las ternas de números enteros positivos se pueden ordenar por su suma y las de la misma suma por orden lexicográfico. Por ejemplo,

• ternas de suma 3:

(1,1,1)

• ternas de suma 4:

(1,1,2),(1,2,1),(2,1,1)

• ternas de suma 5:

(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)

• ternas de suma 6

(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)

y así sucesivamente.

Definir la función

ternas :: [(integer,integer,integer)]

tal que ternas es la lista de las ternas de enteros positivos con el orden descrito anteriormente. por ejemplo,

λ> take 20 ternas
[(1,1,1),
 (1,1,2),(1,2,1),(2,1,1),
 (1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1),
 (1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)]

Leer más…

Definir la función

mayorBorrando :: Int -> Integer -> Integer

tal que (mayorBorrando k n) es el mayor número obtenido borrando k dígitos de n (se supone que n tiene más de k dígitos). Por ejemplo,

mayorBorrando 1 6782334  ==  782334
mayorBorrando 3 6782334  ==  8334
mayorBorrando 3 10020    ==  20
mayorBorrando 1000000 (4256 + 10^1000004) == 14256

Leer más…

Definir la función

borra :: Int -> [a] -> [[a]]

tal que (borra n xs) es la lista de las listas obtenidas borrando n elementos de xs. Por ejemplo,

borra 0 "abcd"  ==  ["abcd"]
borra 1 "abcd"  ==  ["abc","abd","acd","bcd"]
borra 2 "abcd"  ==  ["ab","ac","ad","bc","bd","cd"]
borra 3 "abcd"  ==  ["a","b","c","d"]
borra 4 "abcd"  ==  [""]
borra 5 "abcd"  ==  []
borra 6 "abcd"  ==  []
length (borra 2 [1..300])  ==  44850

Leer más…

Definir la función

paresNoDivisible :: [(Integer, Integer)]

tal que paresNoDivisible es la lista de los pares (n,k) tales que n < k y k no es divisible por n. Por ejemplo,

λ> take 10 paresNoDivisible
[(2,3),(3,4),(2,5),(3,5),(4,5),(4,6),(5,6),(2,7),(3,7),(4,7)]

Se observa que en el resultado los pares se ordenan primero según su segundo elemento y los que tienen el mismo segundo elemento se ordenan por el primer elemento.

Un par especial es un par de enteros positivos (n,k) tales que existe algún s tal que \(s \times n\) y \(s \times k\) tienen el mismo número de divisores. Por ejemplo, (3,4) es un par especial ya que \(2 \times 3\) y \(2 \times 4\) tienen 4 divisores.

Comprobar con QuickCheck todos los elementos de paresNoDivisible son pares especiales.

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2018.

Leer más…

Los números armónicos son las sumas de los inversos de de los primeros números enteros positivos; es decir, el n-ésimo número armónico es

H(n) = 1 + 1/2 + 1/3 + ··· + 1/n

Los primeros números armónicos son

1, 3/2, 11/6, 25/12, 137/60, ..

Definir, usando la librería de los números racionales (Data.Ratio), las funciones

armonico  :: Integer -> Rational
armonicos :: [Rational]
esEntero  :: Rational -> Bool

tales que

• (armonico n) es el n-ésimo número armónico. Por ejemplo,

armonico 2  ==    3 % 2
armonico 3  ==   11 % 6
armonico 4  ==   25 % 12
armonico 5  ==  137 % 60

• armonicos es la lista de los números armónicos. Por ejemplo,

take 5 armonicos  ==  [1 % 1,3 % 2,11 % 6,25 % 12,137 % 60]

• (esEntero x) se verifica si x es un número entero. Por ejemplo,

esEntero (1 % 7)           ==  False
esEntero (1 % 7 + 20 % 7)  ==  True

Comprobar con QuickCheck que

• nigún número armónico, excepto el primero, es un número entero y

• la diferencia de dos números armónicos distintos nunca es un número entero.

Nota: Este ejercicio está basado en el artículo Sums of consecutive reciprocals publicado por John D. Cook en su blog el 23 de enero de 2021.

Leer más…

Definir la función

particion :: Int -> [Int] -> [[Int]]

tal que (particion n xs) es la lista de los elementos de xs, en el mismo orden, agrupados en listas con sumas menores o iguales que n. Por ejemplo,

particion 6 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1,3],[2,2,2],[1,2,2],[3]]
particion 5 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3,2],[2,2,1],[2,2],[3]]
particion 4 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3],[2,2],[2,1],[2,2],[3]]
particion 3 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3],[2],[2],[2,1],[2],[2],[3]]
particion 2 [1,1,1,3,2,2,2,1,2,2,3] == []

Leer más…

Definir las funciones

numerosConNueve :: [Integer]
conNueve :: Integer -> Integer

tales que

• numerosConNueve es la lista de los números con algún dígito igual a 9. Por ejemplo,

λ> take 20 numerosConNueve
[9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99,109]

• (conNueve n) es la cantidad de números enteros no negativos menores o iguales que n con algún dígito igual a 9. Por ejemplo,

conNueve 1   ==  0
conNueve 10  ==  1
conNueve 90  ==  10
length (show (conNueve (10^3)))      ==  3
length (show (conNueve (10^30)))     ==  30
length (show (conNueve (10^300)))    ==  300
length (show (conNueve (10^3000)))   ==  3000
length (show (conNueve (10^30000)))  ==  30000

Leer más…

La terna (n,a,b) es una terna pitagórica si n² = a²+b² y b < a < n. Por ejemplo, (5,4,3) y (10,8,6) son ternas pitagóricas.

Una terna pitagórica es primitiva si sus tres componentes son primos entre sí. Por ejemplo, (5,4,3) es una terna pitagórica primitiva y (10,8,6) es una terna pitagórica no primitiva (ya que sus tres lados son divisibles por 2).

Los elementos (n,a,b) de una terna pitagórica son las longitudes de los lados de un triágulo rectángulo; concretamente n es la longitud de la hipotenusa, a la del cateto mayor y b la del cateto menor. Su perímetro es n+a+b.

Definir la función

ternasPPPDC :: [(Integer,Integer,Integer)]

tal que ternasPPPDC es la lista de las ternas pitagóricas primitivas tales que su perímetro es divisibe por alguno de los catetos. Por ejemplo,

λ> take 5 ternasPPPDC
[(5,4,3),(13,12,5),(17,15,8),(25,24,7),(37,35,12)]
λ> [n | (n,a,b) <- take 15 ternasPPPDC]
[5,13,17,25,37,41,61,65,85,101,113,145,145,181,197]
λ> ternasPPPDC !! 80
(4705,4704,97)

Comprobar con QuickCheck que existen infinitas ternas pitagóricas primitivas tales que su perímetro es divisibe por alguno de los catetos; es decir, para todo x existe alguna terna (n,a,b) en ternasPPPDC tal que n es mayor que x.

Referencia: Este ejercicio está basado en el artículo Terna pitagórica en la que el perímetro es múltiplo de uno de los catetos publicado por Antonio Roldán en "Números y hoja de cálculo" el 21 de enero de 2021.

Leer más…

La sucesión de Dottie correspondiente a un número x se obtiene a partir de x aplicándole la función coseno al término anterior. Por ejemplo, empezando en el 2021 los términos de la sucesión de Dottie son

d(0) = 2021
d(1) = cos(2021)                = -0.5768544484396986
d(2) = cos(-0.5768544484396986) = 0.8381823464377144
d(3) = cos(0.8381823464377144)  = 0.6688152257126013
d(4) = cos(0.6688152257126013)  = 0.7845568438177061
d(5) = cos(0.7845568438177061)  = 0.7077014336446841
d(6) = cos(0.7077014336446841)  = 0.7598581544800473
d(7) = cos(0.7598581544800473)  = 0.7249337238692606
d(8) = cos(0.7249337238692606)  = 0.7485433703735275

Definir las funciones

sucesionDottie :: Double -> [Double]
limite :: [Double] -> Double -> Int -> Double

tales que

• (sucesionDottie x) es la lista de los términos de la sucesión de Dottie correspondiente a x. Por ejemplo,

λ> mapM_ print (take 10 (sucesionDottie 2021))
2021.0
-0.5768544484396986
0.8381823464377144
0.6688152257126013
0.7845568438177061
0.7077014336446841
0.7598581544800473
0.7249337238692606
0.7485433703735275
0.7326809874975466
λ> mapM_ print (take 10 (drop 85 (sucesionDottie 2021)))
0.7390851332151601
0.739085133215161
0.7390851332151605
0.7390851332151608
0.7390851332151606
0.7390851332151607
0.7390851332151607
0.7390851332151607
0.7390851332151607
0.7390851332151607

• (limite xs a n) es el límite de xs con aproximación a y amplitud n; es decir, el primer término x de la sucesión tal que el valor absoluto de x y cualquiera de sus n siguentes elementos es menor que a. Por ejemplo,

λ> limite [(2*n+1)/(n+5) | n <- [1..]] 0.001 300
1.993991989319092
λ> limite [(2*n+1)/(n+5) | n <- [1..]] 1e-6 300
1.9998260062637745
λ> limite [(1+1/n)**n | n <- [1..]] 0.001 300
2.7155953364173175
λ> limite (sucesionDottie 2021) 1e-16 100
0.7390851332151607
λ> limite (sucesionDottie 27) 1e-16 100
0.7390851332151607

Comprobar con QuickCheck que, para todo número x, el límite de la sucesión de Dottie generada por x es mismo; es decir, si x e y son dos números cualesquiera, entonces

limite (sucesionDottie x) 1e-16 100 ==
limite (sucesionDottie y) 1e-16 100

Dicho límite es el número de Dottie.

Referencia: Este ejercicio está basado en el artículo El número de Dottie publicado por Miguel Ángel Morales en Gaussianos el 20 de enero de 2021.

Leer más…

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

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

Por ejemplo, el árbol

      7
     / \
    /   \
   /     \
  4       9
 / \     / \
1   3   5   6

se puede representar por

N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

Un árbol está acotado por un conjunto ys si todos los valores de sus hojas y sus nodos pertenecen a ys. Por ejemplo, el árbol anterior está acotado por [1..10] pero no lo está por [1..7].

Un árbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes árboles sólo son monovalorados los dos primeros

  5          9           5          9
 / \        / \         / \        / \
5   5      9   9       5   6      9   7
              / \                    / \
             9   9                  9   9

Definir las funciones

acotado :: Eq a => Arbol a -> [a] -> Bool
monovalorados :: Arbol -> [Arbol]

tales que

• (acotado a ys) se verifica si a está acotado por ys. Por ejemplo,

acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..10] == True
acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..7]  == False

• (monovalorado a) se verifica si a es monovalorado. Por ejemplo,

monovalorado (N 5 (H 5) (H 5))              ==  True
monovalorado (N 5 (H 5) (H 6))              ==  False
monovalorado (N 9 (H 9) (N 9 (H 9) (H 9)))  ==  True
monovalorado (N 9 (H 9) (N 7 (H 9) (H 9)))  ==  False
monovalorado (N 9 (H 9) (N 9 (H 7) (H 9)))  ==  False

Leer más…

Definir la función

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

tal que (conRepeticionesAcotadas xs n) es una lista que contiene cada elemento de xs como máximo n veces sin reordenar (se supone que n es un número positivo).. Por ejemplo,

conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 1  ==  [1,2,3,5]
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 2  ==  [1,2,3,1,2,3,5]
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 3  ==  [1,2,3,1,2,1,3,2,3,5]
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 4  ==  [1,2,3,1,2,1,3,2,3,5]

Leer más…

Definir la función

potenciasDeDosMasCercanas :: [Integer] -> [Integer]

tal que (potenciasDeDosMasCercanas xs) es la lista sustituyendo cada elemento de xs por su potencia de dos más cercana (en el caso de que haya dos equidistantes se elige la menor). Por ejemplo,

potenciasDeDosMasCercanas2 [6,7,8,9,2021]  ==  [4,8,8,8,2048]

Leer más…

En este ejercicio se considerará la serie

1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 10 + ···

Definir las funciones

serie     :: [Integer]
sumaSerie :: Integer -> Integer

tales que

• serie es lalista de los términos de la serie anterior; es decir,

take 7 serie  ==  [1,-2,3,-4,5,-6,7]

• (sumaSerie n) es la suma de los n primeros términos de la serie. Por ejemplo,

sumaSerie 5     ==  3
sumaSerie 6     ==  -3
sumaSerie 2021  ==  1011
length (show (sumaSerie (10^1000)))  ==  1001

Comprobar con QuickCheck que

• la suma de la serie se puede hacer tan grande como se desee; es decir, que para todo número a existe un n tal que la suma de los n primeros términos de la serie es mayor que a;
• la suma de la serie se puede hacer tan pequeña como se desee; es decir, que para todo número a existe un n tal que la suma de los n primeros términos de la serie es menor que a.

Leer más…

Dado un conjunto de números enteros positivos S su clausura del valor absoluto de la diferencia de pares es el menor conjunto T tal que T contiene a S y para cualquier par de elementos x e y de T (con x distinto de y) el valor absoluto de (x-y) también es un elemento de T. Por ejemplo, si S = {12, 30}, entonces

• 12 ∈ T, porque 12 ∈ S
• 30 ∈ T, porque 20 ∈ S
• 18 = |12 - 30| ∈ T
• 6 = |18 - 12| ∈ T
• 24 = |30 - 6| ∈ T

Por tanto, T = {12, 30, 18, 6, 24}.

Definir las funciones

clausura :: [Int] -> [Int]
longitudClausura :: [Int] -> Int

tales que

• (clausura xs) es la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,

clausura [12,30]  ==  [12,30,18,6,24]
clausura [3,5,2]  ==  [3,5,2,1,4]

• (longitudClausura xs) es el número de elementos de la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,

longitudClausura [12,30]        ==  5
longitudClausura [3,5,2]        ==  5
longitudClausura [3,23..10^6]   ==  999983

Leer más…

Las potencias de dos son

1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,...

Se observa que la primera potencia de dos que contiene al 638 es la 14 ya que 2^14 = 16384.

Definir la función

potenciasContenedoras :: Integer -> [Integer]

tal que (potenciasContenedoras x) es la lista de las potencias de 2 que contienen a x. Por ejemplo,

λ> head (potenciasContenedoras 638)
14
λ> head (potenciasContenedoras 2021)
452
λ> take 20 (potenciasContenedoras 4)
[2,6,10,11,12,14,18,19,20,22,25,26,27,28,30,31,32,33,34,35]
λ> [head (potenciasContenedoras n) | n <- [0..20]]
[10,4,1,5,2,8,4,15,3,12,10,40,7,17,18,21,4,27,30,13,11]

Comprobar con QuickCheck si todos los números naturales están contenenidos en alguna potencia de 2.

Leer más…

La sucesión de los números primos es

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

Las parejas de primos equidistantes de 5 en dicha sucesión son (3, 7) y (2, 11). Se observa que el cuadrado de 5 es mayor que el producto de los elementos de dichas parejas; es decir,

5^2 = 25 > 21 = 3 x 7
5^2 = 25 > 22 = 2 x 11

En cambio, el 7 tiene una pareja de primos equidistantes (la (5, 11)) cuyo producto es mayor que el cuadrado de 7.

7^2 = 49 < 55 = 5 x 11

Un buen primo es un número primo cuyo cuadrado es mayor que el producto de dos primos cualesquiera equidistantes de él en la sucesión de primos. Por ejemplo, 5 es un buen primo pero 7 no lo es.

Definir las funciones

esBuenPrimo  :: Integer -> Bool
buenosPrimos :: [Integer]

tales que

• (esBuenPrimo n) se verifica si n es un buen primo. Por ejemplo,

esBuenPrimo 5        ==  True
esBuenPrimo 7        ==  False
esBuenPrimo 8746811  ==  True

• buenosPrimos es la lista de los buenos primos. Por ejemplo,

λ> take 12 buenosPrimos
[2,5,11,17,29,37,41,53,59,67,71,97]

Comprobar con QuickCheck que la lista de los buenos primos es infinita; es decir, para cualquier entero positivo n existe un número mayor que n que es un buen primo.

Leer más…

Un número equidigital es un número natural que tiene el mismo número de dígitos que el número de dígitos en su factorización prima, incluidos los exponentes mayores que 1. Por ejemplo,

• 10 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (2 x 5).
• 25 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (5^2).
• 121 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (11^2).
• 175 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (5^2 x 7).
• 1125 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3^2 x 5^3).
• 2021 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (43 x 47).
• 3072 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3 x 2^10).

Definir las funciones

esEquidigital :: Int -> Bool
equidigitales :: [Int]

tal que

• (esEquidigital x) se verifica si x es un número equidigital. Por ejemplo.

esEquidigital 10    ==  True
esEquidigital 11    ==  True
esEquidigital 2021  ==  True
esEquidigital 2022  ==  False

• equidigitales es la lista de los números equidigitales. Por ejemplo,

λ> take 20 equidigitales
[2,3,5,7,10,11,13,14,15,16,17,19,21,23,25,27,29,31,32,35]
λ> equidigitales !! 755
2021
λ> equidigitales !! 100000
405341

Comprobar con QuickChek que el conjunto de los números equidigitales es infinito; es decir, para cada entero n existe un equidigital mayor que n.

Leer más…

Un número compuesto persistente es un número compuesto que no se puede transformar en un número primo cambiando sólo uno de sus dígitos. Por ejemplo,

• 20 no es un compuesto persistente porque cambiando su último dígito por un 3 se transforma en 23 que es primo.
• 25 no es un compuesto persistente porque cambiando su primer dígito por un 0 se transforma en 5 que es primo.
• 200 es un compuesto persistente ya que al cambiar su útimo dígito por un impar se obtienen los números 201, 203, 207, 205 y 209 que no son primos y todos sus demás transformados son pares y, por tanto, tampoco son primos.

Definir las funciones

esCompuestoPersistente :: Integer -> Bool
compuestosPersistentes :: [Integer]

tales que

• (esCompuestoPersistente n) se verifica si n es un número compuesto persistente. Por ejemplo,

esCompuestoPersistente 20    ==  False
esCompuestoPersistente 200   ==  True
esCompuestoPersistente 2021  ==  False

• compuestosPersistentes es la lista de los números compuestos persistentes. Por ejemplo,

λ> take 10 compuestoPersistentes
[200,204,206,208,320,322,324,325,326,328]

Comprobar con QuickCheck que todos los números de la forma 510+2310*k son números compuestos persistentes.

Leer más…

Se dice que y es un generador de x si x es igual a la suma de y los dígitos de y. Por ejemplo, 1996 y 2014 son generadores de 2021 ya que

2021 = 1996 + 1 + 9 + 9 + 6
2021 = 2014 + 2 + 0 + 1 + 4

Un número bigenerado es un número que tiene exactamente 2 generadores. Por ejemplo,

• 2021 es un número bigenerados y sus generadores son 1996 y 2014
• 20 no es bigenerador porque no tiene ningún generador
• 21 no es bigenerador porque tiene sólo un generador (el 15).
• 101 es el menor número bigenerado y sus generadores son 91 y 100.

Definir las funciones

esBigenerado :: Integer -> Bool
bigenerados  :: [Integer]

tales que

• (esBigenerado x) se verifica si x es bigenerado. Por ejemplo,

esBigenerado 2021  ==  True
esBigenerado 20    ==  False
esBigenerado 21    ==  False
esBigenerado 101   ==  True

• bigenerados es la lista de los números bigenerados. Por ejemplo,

λ> take 12 bigenerados
[101,103,105,107,109,111,113,115,117,202,204,206]

Comprobar con QuickCheck que la lista de los números bigenerados es infinita; es decir, para cualquier número positivo n existe un y mayor que x que es bigenerado.

Leer más…

La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo,

• φ(15) = 8 ya que los números menores o iguales a 36 y coprimos con 36 son ocho: 1, 2, 4, 7, 8, 11, 13 y 14.
• φ(21) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 y 20.

Un número n es un número cíclico si n y φ(n) no tiene ningún divisor primo común. Por ejemplo, el número 15 es cíclico ya que 15 y 8 (que es φ(15)) no tiene ningún divisor primo común; en cambio, el número 21 no es cíclico ya 21 y 12 (que es φ(21)) son divisibles por 3.

Definir las funciones

esCiclico :: Integer -> Bool
ciclicos  :: [Integer]

tales que

• (esCiclico n) se verifica si n es un número cíclico. Por ejemplo,

esCiclico 15    ==  True
esCiclico 16    ==  False
esCiclico 2021  ==  True
esCiclico (product [1..10^4])  ==  False

• ciclicos es la lista de los números cíclicos. Por ejemplo,

λ> take 20 ciclicos
[2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]
λ> ciclicos !! (10^5)
336059

Comprobar con QuickCheck que todos los números primos mayores que 2 son cíclicos.

Leer más…

Los números duffinianos, llamados así por Richard Duffy, son los números compuestos n que son coprimos con la suma de sus divisores; es decir, n y la suma de los divisores de n no tienen ningún factor primo común.

Por ejemplo, 35 es un número duffiniano ya que la suma de sus divisores es 1 + 5 + 7 + 35 = 48 que es coprimo con 35.

Definir las funciones

esDuffiniano :: Integer -> Bool
duffinianos :: [Integer]

tales que

• (esDuffiniano n) se verifica si n es duffiniano. Por ejemplo,

esDuffiniano 35    ==  True
esDuffiniano 2021  ==  True
esDuffiniano 11    ==  False
esDuffiniano 12    ==  False
esDuffiniano (product [1..2*10^4])  ==  False

• duffinianos es la sucesión de los números duffinianos. Por ejemplo,

take 12 duffinianos  ==  [4,8,9,16,21,25,27,32,35,36,39,49]
length (takeWhile (<10^5) duffinianos)  ==  24434

Comprobar con QuickCheck que los números de la forma p^k, con p un primo mayor que 2 y k un entero mayor que 1, son duffinianos.

Leer más…

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Leer más…

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Leer más…

El número 23 se puede escribir de 4 formas como suma de sus dígitos

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

minimoSumandosDigitos        :: Integer -> Integer
graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

• (minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,

minimoSumandosDigitos 23    ==  8
minimoSumandosDigitos 232   ==  78
minimoSumandosDigitos 2323  ==  775
map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

• (graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Leer más…

Leer más…

La sucesión ECG estás definida por a(1) = 1, a(2) = 2 y, para n >= 3, a(n) es el menor natural que aún no está en la sucesión tal que a(n) tiene algún divisor común con a(n-1).

Los primeros términos de la sucesión son 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

Al dibujar su gráfica, se parece a la de los electrocardiogramas (abreviadamente, ECG). Por ello, la sucesión se conoce como la sucesión ECG.

Definir las funciones

sucECG :: [Integer]
graficaSucECG :: Int -> IO ()

tales que

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

λ> take 20 sucECG
[1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11]
λ> sucECG !! 6000
6237

• (graficaSucECG n) dibuja la gráfica de los n primeros términos de la sucesión ECG. Por ejemplo, (graficaSucECG 160) dibuja

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…

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

• (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

• (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Leer más…

Definir la función

sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

ghci> sinDobleCero 2
[[1,0],[1,1],[0,1]]
ghci> sinDobleCero 3
[[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
ghci> sinDobleCero 4
[[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
 [0,1,1,0],[0,1,1,1],[0,1,0,1]]

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…

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…

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

• f(0) es x
• f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

• Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...
• Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
• Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
• Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, ...
• Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

• la generada por 2 converge a 2
• la generada por 3 converge a 26
• la generada por 4 converge a 4
• la generada por 5 converge a 26

Definir las siguientes funciones

omis           :: Integer -> [Integer]
rgencia        :: Integer -> Integer
caConvergencia :: [Integer] -> IO ()

 que

cLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

λ> take 15 (sucLoomis 1)
[1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 2)
[2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 3)
[3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 4)
[4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
λ> take 15 (sucLoomis 5)
[5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 20)
[20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
λ> take 15 (sucLoomis 100)
[100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
λ> sucLoomis 1 !! (2*10^5)
235180736652

• (convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

convergencia  2      ==  2
convergencia  3      ==  26
convergencia  4      ==  4
convergencia 17      ==  38
convergencia 19      ==  102
convergencia 43      ==  162
convergencia 27      ==  202
convergencia 58      ==  474
convergencia 63      ==  150056
convergencia 81      ==  150056
convergencia 89      ==  150056
convergencia (10^12) ==  1000101125092

• (graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Leer más…

El problema de las N reinas consiste en colocar N reinas en tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal. Por ejemplo, una solución para el problema de las 4 reinas es

|---|---|---|---|
|   | R |   |   |
|---|---|---|---|
|   |   |   | R |
|---|---|---|---|
| R |   |   |   |
|---|---|---|---|
|   |   | R |   |
|---|---|---|---|

Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.

Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].

Usando la librería de árboles Data.Tree, definir las funciones

arbolReinas :: Int -> Tree [Int]
nEstados    :: Int -> Int
soluciones  :: Int -> [[Int]]
nSoluciones :: Int -> Int

tales que

• (arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbolReinas 4)))
[]
|
+- [1]
|  |
|  +- [3,1]
|  |
|  `- [4,1]
|     |
|     `- [2,4,1]
|
+- [2]
|  |
|  `- [4,2]
|     |
|     `- [1,4,2]
|        |
|        `- [3,1,4,2]
|
+- [3]
|  |
|  `- [1,3]
|     |
|     `- [4,1,3]
|        |
|        `- [2,4,1,3]
|
`- [4]
   |
   +- [1,4]
   |  |
   |  `- [3,1,4]
   |
   `- [2,4]

λ> putStrLn (drawTree (fmap show (arbolReinas 5)))
[]
|
+- [1]
|  |
|  +- [3,1]
|  |  |
|  |  `- [5,3,1]
|  |     |
|  |     `- [2,5,3,1]
|  |        |
|  |        `- [4,2,5,3,1]
|  |
|  +- [4,1]
|  |  |
|  |  `- [2,4,1]
|  |     |
|  |     `- [5,2,4,1]
|  |        |
|  |        `- [3,5,2,4,1]
|  |
|  `- [5,1]
|     |
|     `- [2,5,1]
|
+- [2]
|  |
|  +- [4,2]
|  |  |
|  |  `- [1,4,2]
|  |     |
|  |     `- [3,1,4,2]
|  |        |
|  |        `- [5,3,1,4,2]
|  |
|  `- [5,2]
|     |
|     +- [1,5,2]
|     |  |
|     |  `- [4,1,5,2]
|     |
|     `- [3,5,2]
|        |
|        `- [1,3,5,2]
|           |
|           `- [4,1,3,5,2]
|
+- [3]
|  |
|  +- [1,3]
|  |  |
|  |  `- [4,1,3]
|  |     |
|  |     `- [2,4,1,3]
|  |        |
|  |        `- [5,2,4,1,3]
|  |
|  `- [5,3]
|     |
|     `- [2,5,3]
|        |
|        `- [4,2,5,3]
|           |
|           `- [1,4,2,5,3]
|
+- [4]
|  |
|  +- [1,4]
|  |  |
|  |  +- [3,1,4]
|  |  |  |
|  |  |  `- [5,3,1,4]
|  |  |     |
|  |  |     `- [2,5,3,1,4]
|  |  |
|  |  `- [5,1,4]
|  |     |
|  |     `- [2,5,1,4]
|  |
|  `- [2,4]
|     |
|     `- [5,2,4]
|        |
|        `- [3,5,2,4]
|           |
|           `- [1,3,5,2,4]
|
`- [5]
   |
   +- [1,5]
   |  |
   |  `- [4,1,5]
   |
   +- [2,5]
   |  |
   |  `- [4,2,5]
   |     |
   |     `- [1,4,2,5]
   |        |
   |        `- [3,1,4,2,5]
   |
   `- [3,5]
      |
      `- [1,3,5]
         |
         `- [4,1,3,5]
            |
            `- [2,4,1,3,5]

• (nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,

nEstados 4            ==  17
nEstados 5            ==  54
map nEstados [0..10]  ==  [1,2,3,6,17,54,153,552,2057,8394,35539]

• (soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,

λ> soluciones 4
[[3,1,4,2],[2,4,1,3]]
λ> soluciones 5
[[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
 [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]

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

nSoluciones 4            ==  2
nSoluciones 5            ==  10
map nSoluciones [0..10]  ==  [1,1,0,0,2,10,4,40,92,352,724]

Leer más…

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)...d(k-1)d(k) de ceros y unos tal que

n = d(0)*F(2) + d(1)*F(3) +...+ d(k-1)*F(k+1)
d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci.

0,1,1,2,3,5,8,13,21,34,...

Por ejemplo. La codificación de Fibonacci de 4 es "1011" ya que los dos últimos elementos son iguales a 1 y

1*F(2) + 0*F(3) + 1*F(4) = 1*1 + 0*2 + 1*3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

 1  = 1     = F(2)           ≡       11
 2  = 2     = F(3)           ≡      011
 3  = 3     = F(4)           ≡     0011
 4  = 1+3   = F(2)+F(4)      ≡     1011
 5  = 5     = F(5)           ≡    00011
 6  = 1+5   = F(2)+F(5)      ≡    10011
 7  = 2+5   = F(3)+F(5)      ≡    01011
 8  = 8     = F(6)           ≡   000011
 9  = 1+8   = F(2)+F(6)      ≡   100011
10  = 2+8   = F(3)+F(6)      ≡   010011
11  = 3+8   = F(4)+F(6)      ≡   001011
12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
13  = 13    = F(7)           ≡  0000011
14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

λ> codigoFib 65
"0100100011"
λ> [codigoFib n | n <- [1..7]]
["11","011","0011","1011","00011","10011","01011"]

Leer más…

Los números de Perrin se definen por la elación de recurrencia

P(n) = P(n - 2) + P(n - 3) si n > 2,

con los valores iniciales

P(0) = 3, P(1) = 0 y P(2) = 2.

Definir la sucesión

sucPerrin :: [Integer]

cuyos elementos son los números de Perrin. Por ejemplo,

λ> take 15 sucPerrin
[3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
λ> length (show (sucPerrin !! (2*10^5)))
24425

Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.

Leer más…

Definir la función

frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000

Leer más…

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

3 + 7x - 5x^3
4 + 5x^3 + x^5

se definen por

ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

• (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

λ> sumaPol ejPol1 ejPol2
fromList [(0,7),(1,7),(5,1)]
λ> sumaPol ejPol1 ejPol1
fromList [(0,6),(1,14),(3,-10)]

• (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,

λ> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
fromList [(2,12),(4,3)]

• (multPol p q) es el producto de los polinomios p y q. Por ejemplo,

λ> multPol ejPol1 ejPol2
fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
λ> multPol ejPol1 ejPol1
fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
λ> multPol ejPol2 ejPol2
fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

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…

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…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

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

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

caminoMaxSuma :: Matrix Int -> [Int]

tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[1,7,12,8,4,9]
λ> sum (caminoMaxSuma (fromList 800 800 [1..]))
766721999

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

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

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El máximo de las suma de los caminos es 41.

Definir la función

maximaSuma :: Matrix Int -> Int

tal que (maximaSuma m) es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
41
λ> maximaSuma (fromList 800 800 [1..])
766721999

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

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

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Definir la función

   caminos :: Matrix Int -> [[Int]]

tal que (caminos m) es la lista de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[[1,7, 3,8,4,9],
 [1,7,12,8,4,9],
 [1,7,12,3,4,9],
 [1,7,12,3,8,9],
 [1,6,12,8,4,9],
 [1,6,12,3,4,9],
 [1,6,12,3,8,9],
 [1,6,11,3,4,9],
 [1,6,11,3,8,9],
 [1,6,11,2,8,9]]
λ> length (caminos (fromList 12 13 [1..]))
1352078

Nota: Se recomiend usar programación dinámica.

Leer más…

Definir la función

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

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
3
λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
6
λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
6
λ> longitudMayorSublistaCreciente [1..2000]
2000
λ> longitudMayorSublistaCreciente [2000,1999..1]
1
λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> longitudMayorSublistaCreciente2 xs
61
λ> longitudMayorSublistaCreciente3 xs
61

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Leer más…

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

sylvester        :: Integer -> Integer
graficaSylvester :: Integer -> Integer -> IO ()

tales que

• (sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

λ> [sylvester n | n <- [0..7]]
[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
λ> length (show (sylvester 25))
6830085

• (graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
• (graficaSylvester 3 30) dibuja
• (graficaSylvester 4 30) dibuja
• (graficaSylvester 5 30) dibuja

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…

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…

Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

|2 5 1 6|       |2 5 1 6|
|4 2 5 1|       |4 2 6 1|
|7 4 2 5|       |7 4 2 5|
|9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,

esToeplitz ej1  ==  True
esToeplitz ej2  ==  False

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…

Un capicúa es un número que es igual leído de izquierda a derecha que de derecha a izquierda.

Definir la función

mayorCapicuaP :: Integer -> Integer

tal que (mayorCapicuaP n) es el mayor capicúa que es el producto de dos números de n cifras. Por ejemplo,

mayorCapicuaP 2  ==  9009
mayorCapicuaP 3  ==  906609
mayorCapicuaP 4  ==  99000099
mayorCapicuaP 5  ==  9966006699
mayorCapicuaP 6  ==  999000000999
mayorCapicuaP 7  ==  99956644665999

Leer más…

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (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 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…

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

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

Definir la función

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

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

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

es decir, en el primer ejemplo,

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

Leer más…

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

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

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

Definir las funciones

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

tales que

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

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

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

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

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

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

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

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

Leer más…

Un número de Aquiles es un número natural n que es potente (es decir, si p es un divisor primo de n, entonces p² también lo es) y no es una potencia perfecta (es decir, no existen números naturales m y k tales que n es igual a m^k). Por ejemplo,

• 108 es un número de Aquiles proque es un número potente (ya que su factorización es 2^2 · 3^3, sus divisores primos son 2 and 3 y sus cuadrados (2^2 = 4 y 3^2 = 9) son divisores de 108. Además, 108 no es una potencia perfecta.
• 360 no es un número de Aquiles ya que 5 es un divisor primo de 360, pero 5^2 = 15 no lo es.
• 784 no es un número de Aquiles porque, aunque es potente, es una potencia perfecta ya que 784 = 28^2.

Los primeros números de Aquiles son

72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, ...

Definir las funciones

esAquiles              :: Integer -> Bool
huecosDeAquiles        :: [Integer]
graficaHuecosDeAquiles :: Int -> IO ()

tales que

• (esAquiles x) se verifica si x es un número de Aquiles. Por ejemplo,

esAquiles 108         ==  True
esAquiles 360         ==  False
esAquiles 784         ==  False
esAquiles 5425069447  ==  True
esAquiles 5425069448  ==  True

• huecosDeAquiles es la sucesión de la diferencias entre los números de Aquiles consecutivos. Por ejemplo,

λ> take 15 huecosDeAquiles
[36,92,88,104,40,68,148,27,125,64,104,4,153,27,171]

• (graficaHuecosDeAquiles n) dibuja la gráfica de los n primeros huecos de Aquiles. Por ejemplo, (graficaHuecosDeAquiles 160) dibuja

Leer más…

Definir las funciones

minimasDistancias             :: Matrix Int -> Matrix Int
sumaMinimaDistanciasIdentidad :: Int -> Int

tales que

• (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])
( 1 0 0 )
( 2 1 0 )
λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])
( 1 1 0 )
( 0 1 1 )
λ> minimasDistancias (identity 5)
( 0 1 2 3 4 )
( 1 0 1 2 3 )
( 2 1 0 1 2 )
( 3 2 1 0 1 )
( 4 3 2 1 0 )

• (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

sumaMinimaDistanciasIdentidad 5       ==  40
sumaMinimaDistanciasIdentidad (10^2)  ==  333300
sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000
sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000

Leer más…

Definir la función

tieneCombinacionDivisible :: [Int] -> Int -> Bool

tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,

tieneCombinacionDivisible [1,3,4,6] 4  ==  True
tieneCombinacionDivisible [1,3,9]   2  ==  False

En el primer ejemplo, 1 - 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son

 1 + 3 + 9 =  13
-1 + 3 + 9 =  11
 1 - 3 + 9 =   7
-1 - 3 + 9 =   5
 1 + 3 - 9 =  -5
-1 + 3 - 9 =  -7
 1 - 3 - 9 = -11
-1 - 3 - 9 = -13

y ninguna de las 4 es divisible por 2.

Leer más…

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

sumaSegmentosIniciales [3,1,2,5]     ==  24
sumaSegmentosIniciales3 [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

sumaSegmentosIniciales (genericReplicate n 1)

es igual a

n * (n + 1) `div` 2

Leer más…

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

   data Arbol = N Int [Arbol]
     deriving Show

Por ejemplo, los árboles

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

se representan por

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

Definir la función

hojasEnNoDecreciente :: Arbol -> [Int]

tal que (hojasEnNoDecreciente a) es el conjunto de las hojas de a que se encuentran en alguna rama no decreciente. Por ejemplo,

hojasEnNoDecreciente ej1  ==  [4,5,7]
hojasEnNoDecreciente ej2  ==  [4,6,8]
hojasEnNoDecreciente ej3  ==  []

Leer más…

Las matrices de Hadamard se definen recursivamente como sigue

λ> hadamard 0
( 1 )

λ> hadamard 1
(  1  1 )
(  1 -1 )

λ> hadamard 2
(  1  1  1  1 )
(  1 -1  1 -1 )
(  1  1 -1 -1 )
(  1 -1 -1  1 )

λ> hadamard 3
(  1  1  1  1  1  1  1  1 )
(  1 -1  1 -1  1 -1  1 -1 )
(  1  1 -1 -1  1  1 -1 -1 )
(  1 -1 -1  1  1 -1 -1  1 )
(  1  1  1  1 -1 -1 -1 -1 )
(  1 -1  1 -1 -1  1 -1  1 )
(  1  1 -1 -1 -1 -1  1  1 )
(  1 -1 -1  1 -1  1  1 -1 )

En general, la n-ésima matriz de Hadamard, H(n), es

( H(n-1)  H(n-1) )
( H(n-1) -H(n-1) )

Definir la función

hadamard :: Int -> Matrix Int

tal que (hadamard n) es la n-ésima matriz de Hadamard.

Comprobar con QuickCheck que para todo número natural n, el producto de la n-ésima matriz de Hadamard y su traspuesta es igual al producto de 2^n por la matriz identidad de orden 2^n.

Leer más…

Definir la función

menorNoSuma :: [Integer] -> Integer

tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,

menorNoSuma [6,1,2]    ==  4
menorNoSuma [1,2,3,9]  ==  7
menorNoSuma [5]        ==  1
menorNoSuma [1..20]    ==  211
menorNoSuma [1..10^6]  ==  500000500001

Comprobar con QuickCheck que para todo n,

menorNoSuma [1..n] == 1 + sum [1..n]

Leer más…

El orden de divisibilidad de un número x es el mayor n tal que para todo i menor o igual que n, los i primeros dígitos de n es divisible por i. Por ejemplo, el orden de divisibilidad de 74156 es 3 porque

7       es divisible por 1
74      es divisible por 2
741     es divisible por 3
7415 no es divisible por 4

Definir la función

ordenDeDivisibilidad :: Integer -> Int

tal que (ordenDeDivisibilidad x) es el orden de divisibilidad de x. Por ejemplo,

ordenDeDivisibilidad 74156                      ==  3
ordenDeDivisibilidad 3608528850368400786036725  ==  25

Leer más…

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]               ==  5
ausente [3,5,9,11]               ==  7
ausente [3,5,7,11]               ==  9
ausente ([1..9]++[11..])         ==  10
ausente ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.

Leer más…

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua

La primeras aproximaciones son

a(1) = 3+1                = 4.0
a(2) = 3+(1/(6+9))        = 3.066666666666667
a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

aproximacionPi 1     ==  4.0
aproximacionPi 2     ==  3.066666666666667
aproximacionPi 3     ==  3.158974358974359
aproximacionPi 10    ==  3.141287132741557
aproximacionPi 100   ==  3.141592398533554
aproximacionPi 1000  ==  3.1415926533392926

• (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja (grafica [10..100]) dibuja y (grafica [100..200]) dibuja

Leer más…

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro "Introductio in Analysis Infinitorum" (1748).

El desarrollo es el siguiente y se obtiene a partir de la serie armónica modificando sólo el signo de algunos términos según el siguiente criterio:

• Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
• Cambiamos a - si el denominador de la fracción es un primo de la forma 4m+1.
• Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

• la de denominador 3 = 4x1-1 lleva un +,
• la de denominador 5 = 4x1+1 lleva un -,
• la de denominador 13 = 4x3+1 lleva un -,
• la de denominador 6 = 2x3 lleva un + (porque los dos llevan un +),
• la de denominador 10 = 2x5 lleva un - (porque el 2 lleva un + y el 5 lleva un -) y
• la de denominador 50 = 5x5x2 lleva un + (un - por el primer 5, otro - por el segundo 5 y un + por el 2).

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: Int -> IO ()

tales que

• (aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

aproximacionPi 1        ==  1.0
aproximacionPi 10       ==  2.3289682539682537
aproximacionPi 100      ==  2.934318000847734
aproximacionPi 1000     ==  3.0603246224585128
aproximacionPi 10000    ==  3.1105295744825403
aproximacionPi 100000   ==  3.134308801935256
aproximacionPi 1000000  ==  3.1395057903490806

• (grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Leer más…

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi c0on la función digitosPi definida por

digitosPi :: [Integer]
digitosPi = g(1,0,1,1,3,3) where
g (q,r,t,k,n,l) =
if 4*q+r-t < n*t
then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

Por ejemplo,

λ> take 25 digitosPi
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, ...

Usando digitosPi, definir las siguientes funciones

distribucionDigitosPi :: Int -> [Int]
frecuenciaDigitosPi   :: Int -> [Double]

tales que

• (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,

λ> distribucionDigitosPi 10
[0,2,1,2,1,2,1,0,0,1]
λ> distribucionDigitosPi 100
[8,8,12,12,10,8,9,8,12,13]
λ> distribucionDigitosPi 1000
[93,116,103,103,93,97,94,95,101,105]
λ> distribucionDigitosPi 5000
[466,531,496,460,508,525,513,488,492,521]

• (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,

λ> frecuenciaDigitosPi 10
[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
λ> frecuenciaDigitosPi 100
[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
λ> frecuenciaDigitosPi 1000
[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
λ> frecuenciaDigitosPi 5000
[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Leer más…

La fórmula de Gregory-Leibniz para calcular pi es

y la de Beeler es

Definir las funciones

aproximaPiGL     :: Int -> Double
aproximaPiBeeler :: Int -> Double
graficas         :: [Int] -> IO ()