El producto escalar de los vectores [a1,a2,...,an] y [b1,b2,..., bn] es

a1·b1 + a2·b2 + ··· + an·bn.

Definir la función

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

tal que (menorProductoEscalar xs ys) es el mínimo de los productos escalares de las permutaciones de xs y de las permutaciones de ys. Por ejemplo,

menorProductoEscalar [3,2,5]  [1,4,6]         == 29
menorProductoEscalar [3,2,5]  [1,4,-6]        == -19
menorProductoEscalar [0..9]   [0..9]          == 120
menorProductoEscalar [0..99]  [0..99]         == 161700
menorProductoEscalar [0..999] [0..999]        == 166167000
menorProductoEscalar3 [0..9999] [0..9999]     == 166616670000
menorProductoEscalar3 [0..99999] [0..99999]   == 166661666700000
menorProductoEscalar3 [0..999999] [0..999999] == 166666166667000000

Leer más…

Una particularidad del 2019 es que se puede escribir como una cadena de dos subnúmeros consecutivos (el 20 y el 19).

Definir la función

cadena :: Integer -> [Integer]

tal que (cadena n) es la cadena de subnúmeros consecutivos de n cuya unión es n; es decir, es la lista de números [x,x-1,...x-k] tal que su concatenación es n. Por ejemplo,

cadena 2019         == [20,19]
cadena 2018         == [2018]
cadena 1009         == [1009]
cadena 110109       == [110,109]
cadena 201200199198 == [201,200,199,198]
cadena 3246         == [3246]
cadena 87654        == [8,7,6,5,4]
cadena 123456       == [123456]
cadena 1009998      == [100,99,98]
cadena 100908       == [100908]
cadena 1110987      == [11,10,9,8,7]
cadena 210          == [2,1,0]
cadena 1            == [1]
cadena 0            == [0]
cadena 312          == [312]
cadena 191          == [191]
length (cadena (read (concatMap show [2019,2018..0])))  ==  2020

Nota: Los subnúmeros no pueden empezar por cero. Por ejemplo, [10,09] no es una cadena de 1009 como se observa en el tercer ejemplo.

Leer más…

Un número de la suerte es un número natural que se genera por una criba, similar a la criba de Eratóstenes, como se indica a continuación:

Se comienza con la lista de los números enteros a partir de 1:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25...

Se eliminan los números de dos en dos

1,  3,  5,  7,  9,   11,   13,   15,   17,   19,   21,   23,   25...

Como el segundo número que ha quedado es 3, se eliminan los números restantes de tres en tres:

1,  3,      7,  9,         13,   15,         19,   21,         25...

Como el tercer número que ha quedado es 7, se eliminan los números restantes de siete en siete:

1,  3,      7,  9,         13,   15,               21,         25...

Este procedimiento se repite indefinidamente y los supervivientes son los números de la suerte:

1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79

Definir las funciones

numerosDeLaSuerte  :: [Int]
esNumeroDeLaSuerte :: Int -> Bool

tales que

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

λ> take 20 numerosDeLaSuerte
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]
λ> numerosDeLaSuerte !! 277
2019
λ> numerosDeLaSuerte !! 2000
19309

• (esNumeroDeLaSuerte n) que se verifica si n es un número de la suerte. Por ejemplo,

esNumeroDeLaSuerte 15    ==  True
esNumeroDeLaSuerte 16    ==  False
esNumeroDeLaSuerte 2019  ==  True

Leer más…

Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2x13) y 49 también lo es (porque 49 = 7x7).

Definir las funciones

esSemiprimo :: Integer -> Bool
semiprimos  :: [Integer]

tales que + (esSemiprimo n) se verifica si n es semiprimo. Por ejemplo,

esSemiprimo 26          ==  True
esSemiprimo 49          ==  True
esSemiprimo 8           ==  False
esSemiprimo 2019        ==  True
esSemiprimo (21+10^14)  ==  True

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

take 10 semiprimos   ==  [4,6,9,10,14,15,21,22,25,26]
semiprimos !! 579    ==  2019
semiprimos !! 10000  ==  40886

Leer más…

Un número malvado es un número natural cuya expresión en base 2 contiene un número par de unos. Por ejemplo, 6 es malvado porque su expresión en base 2 es 110 que tiene dos unos.

Definir las funciones

esMalvado       :: Integer -> Bool
malvados        :: [Integer]
posicionMalvada :: Integer -> Maybe Int

tales que + (esMalvado n) se verifica si n es un número malvado. Por ejemplo,

esMalvado 6              ==  True
esMalvado 7              ==  False
esMalvado 2019           ==  True
esMalvado (10^70000)     ==  True
esMalvado (10^(3*10^7))  ==  True

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

λ> take 20 malvados
[0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39]
malvados !! 1009    ==  2019
malvados !! 10      ==  20
malvados !! (10^2)  ==  201
malvados !! (10^3)  ==  2000
malvados !! (10^4)  ==  20001
malvados !! (10^5)  ==  200000
malvados !! (10^6)  ==  2000001

• (posicionMalvada n) es justo la posición de n en la sucesión de números malvados, si n es malvado o Nothing, en caso contrario. Por ejemplo,

posicionMalvada 6        ==  Just 3
posicionMalvada 2019     ==  Just 1009
posicionMalvada 2018     ==  Nothing
posicionMalvada 2000001  ==  Just 1000000
posicionMalvada (10^7)   ==  Just 5000000

Leer más…

Un número natural n es apocalíptico si 2^n contiene la secuencia 666. Por ejemplo, 157 es apocalíptico porque 2^157 es 182687704666362864775460604089535377456991567872 que contiene la secuencia 666.

Definir las funciones

esApocaliptico       :: Integer -> Bool
apocalipticos        :: [Integer]
posicionApocaliptica :: Integer -> Maybe Int

tales que

• (esApocaliptico n) se verifica si n es un número apocalíptico. Por ejemplo,

esApocaliptico 157   ==  True
esApocaliptico 2019  ==  True
esApocaliptico 2018  ==  False

• apocalipticos es la lista de los números apocalípticos. Por ejemplo,

take 9 apocalipticos  ==  [157,192,218,220,222,224,226,243,245]
apocalipticos !! 450  ==  2019

• (posicionApocalitica n) es justo la posición de n en la sucesión de números apocalípticos, si n es apocalíptico o Nothing, en caso contrario. Por ejemplo,

posicionApocaliptica 157   ==  Just 0
posicionApocaliptica 2019  ==  Just 450
posicionApocaliptica 2018  ==  Nothing

Leer más…

El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat.

Definir las funciones

representaciones :: Integer -> [(Integer,Integer)]
primosImparesConRepresentacionUnica :: [Integer]
primos4nM1 :: [Integer]

tales que

• (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo.

representaciones  20           ==  [(2,4)]
representaciones  25           ==  [(0,5),(3,4)]
representaciones 325           ==  [(1,18),(6,17),(10,15)]
representaciones 100000147984  ==  [(0,316228)]
length (representaciones (10^10))    ==  6
length (representaciones (4*10^12))  ==  7

• primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,

λ> take 20 primosImparesConRepresentacionUnica
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

• primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,

λ> take 20 primos4nM1
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

Comprobar con QuickCheck el torema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Leer más…

Se dice que A es un subconjunto maximal de B si A ⊂ B y no existe ningún C tal que A ⊂ C y C ⊂ B. Por ejemplo, {2,5} es un subconjunto maximal de {2,3,5], pero {3] no lo es.

El árbol de los subconjuntos de un conjunto A es el árbol que tiene como raíz el conjunto A y cada nodo tiene como hijos sus subconjuntos maximales. Por ejemplo, el árbol de subconjuntos de [2,3,5] es

       [2, 3, 5]
       /   |  \
      /    |   \
     /     |    \
    /      |     \
   /       |      \
 [5,3]   [2,3]   [2,5]
 /  \    /  \    /  \
[3] [5] [3] [2] [5] [2]
 |   |   |   |   |   |
[ ] [ ] [ ] [ ] [ ] [ ]

Usando el tipo de dato

data Arbol = N Integer [Arbol]
  deriving (Eq, Show)

el árbol anterior se representa por

N [2,5,3]
  [N [5,3]
     [N [3]
        [N [] []],
      N [5]
        [N [] []]],
   N [2,3]
     [N [3]
        [N [] []],
      N [2]
        [N [] []]],
   N [2,5]
     [N [5]
        [N [] []],
      N [2]
        [N [] []]]]

Definir las funciones

arbolSubconjuntos :: [Int] -> Arbol
nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int

tales que

• (arbolSubconjuntos x) es el árbol de los subconjuntos de xs. Por ejemplo,

λ> arbolSubconjuntos [2,5,3]
N [2,5,3] [N [5,3] [N [3] [N [] []],N [5] [N [] []]],
           N [2,3] [N [3] [N [] []],N [2] [N [] []]],
           N [2,5] [N [5] [N [] []],N [2] [N [] []]]]

• (nOcurrenciasArbolSubconjuntos xs ys) es el número de veces que aparece el conjunto xs en el árbol de los subconjuntos de ys. Por ejemplo,

nOcurrenciasArbolSubconjuntos []      [2,5,3]  ==  6
nOcurrenciasArbolSubconjuntos [3]     [2,5,3]  ==  2
nOcurrenciasArbolSubconjuntos [3,5]   [2,5,3]  ==  1
nOcurrenciasArbolSubconjuntos [3,5,2] [2,5,3]  ==  1

Comprobar con QuickChek que, para todo entero positivo n, el número de ocurrencia de un subconjunto xs de [1..n] en el árbol de los subconjuntos de [1..n] es el factorial de n-k (donde k es el número de elementos de xs).

Leer más…

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

0 1 2    0 2 1
1 2 0    1 0 2
2 0 1    2 1 0
Suma     Resta

Definir la función

conmutativa :: [[Int]] -> Bool

tal que (conmutativa xss) se verifica si la operación cuya tabla es xss es conmutativa. Por ejemplo,

conmutativa [[0,1,2],[1,0,1],[2,1,0]]  ==  True
conmutativa [[0,1,2],[1,0,0],[2,1,0]]  ==  False
conmutativa [[i+j `mod` 2000 | j <- [0..1999]] | i <- [0..1999]] == True
conmutativa [[i-j `mod` 2000 | j <- [0..1999]] | i <- [0..1999]] == False

Leer más…

Una partición de un conjunto es una división del mismo en subconjuntos disjuntos no vacíos.

Definir la función

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

tal que (esParticion xss) se verifica si xss es una partición; es decir sus elementos son listas no vacías disjuntas. Por ejemplo.

esParticion [[1,3],[2],[9,5,7]]  ==  True
esParticion [[1,3],[2],[9,5,1]]  ==  False
esParticion [[1,3],[],[9,5,7]]   ==  False
esParticion [[2,3,2],[4]]        ==  True

Leer más…

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

0 1 2    0 2 1
1 2 0    1 0 2
2 0 1    2 1 0
Suma     Resta

Definir las funciones

tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
tablaSuma      :: Int -> [[Int]]
tablaResta     :: Int -> [[Int]]
tablaProducto  :: Int -> [[Int]]

tales que

• (tablaOperacion f n) es la tabla de la operación f módulo n en [0..n-1]. Por ejemplo,

tablaOperacion (+) 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
tablaOperacion (-) 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
tablaOperacion (-) 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
tablaOperacion (\x y -> abs (x-y)) 3  ==  [[0,1,2],[1,0,1],[2,1,0]]

• (tablaSuma n) es la tabla de la suma módulo n en [0..n-1]. Por ejemplo,

tablaSuma 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
tablaSuma 4  ==  [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]

• (tablaResta n) es la tabla de la resta módulo n en [0..n-1]. Por ejemplo,

tablaResta 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
tablaResta 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]

• (tablaProducto n) es la tabla del producto módulo n en [0..n-1]. Por ejemplo,

tablaProducto 3  ==  [[0,0,0],[0,1,2],[0,2,1]]
tablaProducto 4  ==  [[0,0,0,0],[0,1,2,3],[0,2,0,2],[0,3,2,1]]

Comprobar con QuickCheck, si parato entero positivo n de verificar las siguientes propiedades:

• La suma, módulo n, de todos los números de (tablaSuma n) es 0.
• La suma, módulo n, de todos los números de (tablaResta n) es 0.
• La suma, módulo n, de todos los números de (tablaProducto n) es n/2 si n es el doble de un número impar y es 0, en caso contrario.

Leer más…

Definir la función

nDivisoresCompuestos :: Integer -> Integer

tal que (nDivisoresCompuestos x) es el número de divisores de x que son compuestos (es decir, números mayores que 1 que no son primos). Por ejemplo,

nDivisoresCompuestos 30  ==  4
nDivisoresCompuestos (product [1..11])  ==  534
nDivisoresCompuestos (product [1..25])  ==  340022
length (show (nDivisoresCompuestos (product [1..3*10^4]))) == 1948

Leer más…

Definir la función

divisoresCompuestos :: Integer -> [Integer]

tal que (divisoresCompuestos x) es la lista de los divisores de x que son números compuestos (es decir, números mayores que 1 que no son primos). Por ejemplo,

divisoresCompuestos 30  ==  [6,10,15,30]
length (divisoresCompuestos (product [1..11]))  ==  534
length (divisoresCompuestos (product [1..14]))  ==  2585
length (divisoresCompuestos (product [1..16]))  ==  5369
length (divisoresCompuestos (product [1..25]))  ==  340022

Leer más…

Leer más…

Se dice que a es un divisor propio maximal de un número b si a es un divisor de b distinto de b y no existe ningún número c tal que a < c < b, a es un divisor de c y c es un divisor de b. Por ejemplo, 15 es un divisor propio maximal de 30, pero 5 no lo es.

Definir las funciones

divisoresPropiosMaximales  :: Integer -> [Integer]
nDivisoresPropiosMaximales :: Integer -> Integer

tales que

• (divisoresPropiosMaximales x) es la lista de los divisores propios maximales de x. Por ejemplo,

divisoresPropiosMaximales 30   ==  [6,10,15]
divisoresPropiosMaximales 420  ==  [60,84,140,210]
divisoresPropiosMaximales 7    ==  [1]
length (divisoresPropiosMaximales (product [1..3*10^4])) == 3245

• (nDivisoresPropiosMaximales x) es el número de divisores propios maximales de x. Por ejemplo,

nDivisoresPropiosMaximales 30   ==  3
nDivisoresPropiosMaximales 420  ==  4
nDivisoresPropiosMaximales 7    ==  1
nDivisoresPropiosMaximales (product [1..3*10^4])  ==  3245

Leer más…

Leer más…

Un número primo de Pierpont es un número primo de la forma \(2^{u}3^{v}+1\), para u y v enteros no negativos.

Definir la sucesión

primosPierpont :: [Integer]

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

λ> take 20 primosPierpont
[2,3,5,7,13,17,19,37,73,97,109,163,193,257,433,487,577,769,1153,1297]
λ> primosPierpont !! 49
8503057

Leer más…

Las matrices se pueden representar mediante listas de listas. Por ejemplo, la matriz

8 9 7 6
4 7 6 5
3 2 1 8

se puede representar por la lista

[[8,9,7,6],[4,7,6,5],[3,2,1,8]]

Definir la función

intercambia :: [[a]] -> [[a]]

tal que (intercambia xss) es la matriz obtenida intercambiando la primera y la última columna de xss. Por ejemplo,

λ> intercambia [[8,9,7,6],[4,7,6,5],[3,2,1,8]]
[[6,9,7,8],[5,7,6,4],[8,2,1,3]]

Leer más…

Una sucesión de puntuaciones se puede representar mediante una lista de números. Por ejemplo, [7,5,9,9,4,5,4,2,5,9,12,1]. En la lista anterior, los puntos en donde se alcanzan un nuevo máximo son 7, 9 y 12 (porque son mayores que todos sus anteriores) y en donde se alcanzan un nuevo mínimo son 7, 5, 4, 2 y 1 (porque son menores que todos sus anteriores). Por tanto, el máximo se ha superado 2 veces y el mínimo 4 veces.

Definir las funciones

nuevosMaximos :: [Int] -> [Int]
nuevosMinimos :: [Int] -> [Int]
nRupturas     :: [Int] -> (Int,Int)

tales que

• (nuevosMaximos xs) es la lista de los nuevos máximos de xs. Por ejemplo,

nuevosMaximos [7,5,9,9,4,5,4,2,5,9,12,1]  ==  [7,9,12]

• (nuevosMinimos xs) es la lista de los nuevos mínimos de xs. Por ejemplo,

nuevosMinimos [7,5,9,9,4,5,4,2,5,9,12,1]  ==  [7,5,4,2,1]

• (nRupturas xs) es el par formado por el número de veces que se supera el máximo y el número de veces que se supera el mínimo en xs. Por ejemplo,

nRupturas [7,5,9,9,4,5,4,2,5,9,12,1]  ==  (2,4)

Leer más…

Las expresiones aritméticas. generales se contruyen con las sumas generales (sumatorios) y productos generales (productorios). Su tipo es

data Expresion = N Int
               | S [Expresion]
               | P [Expresion]
  deriving Show

Por ejemplo, la expresión

(2·(1 + 2 + 1)·(2 + 3)) + 1

se representa por

S [P [N 2,
      S [N 1, N 2, N 1],
      S [N 2, N 3]],
   N 1]

Definir la función

valor :: Expresion -> Int

tal que (valor e) es el valor de la expresión e. Por ejemplo,

λ> valor (S [P [N 2, S [N 1, N 2, N 1], S [N 2, N 3]], N 1])
41

Leer más…

Se dice que un x número se encuentra entre dos conjuntos xs e ys si x es divisible por todos los elementos de xs y todos los elementos de zs son divisibles por x. Por ejemplo, 12 se encuentra entre los conjuntos {2, 6} y {24, 36}.

Definir la función

entreDosConjuntos :: [Int] -> [Int] -> [Int]

tal que (entreDosConjuntos xs ys) es la lista de elementos entre xs e ys (se supone que xs e ys son listas no vacías de números enteros positivos). Por ejemplo,

entreDosConjuntos [2,6] [24,36]     ==  [6,12]
entreDosConjuntos [2,4] [32,16,96]  ==  [4,8,16]

Otros ejemplos

λ> (xs,a) = ([1..15],product xs)
λ> length (entreDosConjuntos5 xs [a,2*a..10*a])
270
λ> (xs,a) = ([1..16],product xs)
λ> length (entreDosConjuntos5 xs [a,2*a..10*a])
360

Leer más…

La sucesión de Fibonacci es

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,...

cuyos dos primeros términos son 0 y 1 y los restantentes se obtienen sumando los dos anteriores.

El árbol de computación de su 5º término es

             5
            / \
           /   \
          /     \
         /       \
        /         \
       3           2
      / \         / \
     /   \       1   1
    2     1     / \
   / \   / \   1   0
  1   1 1   0
 / \
1   0

que, usando los árboles definidos por

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

se puede representar por

N 5
  (N 3
     (N 2
        (N 1 (H 1) (H 0))
        (H 1))
     (N 1 (H 1) (H 0)))
  (N 2
     (N 1 (H 1) (H 0))
     (H 1))

Definir las funciones

arbolFib           :: Int -> Arbol
nElementosArbolFib :: Int -> Int

tales que

• (arbolFib n) es el árbol de computación del n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

λ> arbolFib 5
N 5
  (N 3
     (N 2
        (N 1 (H 1) (H 0))
        (H 1))
     (N 1 (H 1) (H 0)))
  (N 2
     (N 1 (H 1) (H 0))
     (H 1))
λ> arbolFib 6
N 8
  (N 5
     (N 3
        (N 2
           (N 1 (H 1) (H 0))
           (H 1))
        (N 1 (H 1) (H 0)))
     (N 2
        (N 1 (H 1) (H 0))
        (H 1)))
  (N 3
     (N 2
        (N 1 (H 1) (H 0)) (H 1))
     (N 1 (H 1) (H 0)))

• (nElementosArbolFib n) es el número de elementos en el árbol de computación del n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

nElementosArbolFib 5   ==  15
nElementosArbolFib 6   ==  25
nElementosArbolFib 30  ==  2692537

Leer más…

El n-ésimo menor contenenedor de primos es el menor número que contiene como subcadenas los primeros n primos. Por ejemplo, el 6º menor contenedor de primos es 113257 ya que es el menor que contiene como subcadenas los 6 primeros primos (2, 3, 5, 7, 11 y 13).

Definir la función

menorContenedor :: Int -> Int

tal que (menorContenedor n) es el n-ésimo menor contenenedor de primos. Por ejemplo,

menorContenedor 1  ==  2
menorContenedor 2  ==  23
menorContenedor 3  ==  235
menorContenedor 4  ==  2357
menorContenedor 5  ==  112357
menorContenedor 6  ==  113257

Leer más…

El día 11 de noviembre, se publicó en la cuenta de Twitter de Fermat's Library la siguiente curiosa identidad que relaciona los números e y pi:

Definir las siguientes funciones:

sumaTerminos :: Int -> Double
aproximacion :: Double -> Int

tales que

• (sumaTerminos n) es la suma de los primeros n términos de la serie 1/(π²+ 1) + 1/(4π²+1) + 1/(9π²+1) + 1/(16π²+ ) + ... Por ejemplo,

sumaTerminos 10     ==  0.14687821811081034
sumaTerminos 100    ==  0.15550948345688423
sumaTerminos 1000   ==  0.15641637221314514
sumaTerminos 10000  ==  0.15650751113789382

• (aproximación x) es el menor número de términos que hay que sumar de la serie anterior para que se diferencie (en valor absoluto) de 1/(e²-1) menos que x. Por ejemplo,

aproximacion 0.1     ==  1
aproximacion 0.01    ==  10
aproximacion 0.001   ==  101
aproximacion 0.0001  ==  1013

Leer más…

Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

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

Los árboles binarios se puede representar mediante el siguiente tipo

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

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 9 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

data Movimiento = I | D deriving (Show, Eq)
type Posicion   = [Movimiento]

Definir la función

elementoEnPosicion :: Posicion -> Integer

tal que (elementoEnPosicion ms) es el elemento en la posición ms. Por ejemplo,

elementoEnPosicion [D,I]    ==  6
elementoEnPosicion [D,D]    ==  7
elementoEnPosicion [I,I,D]  ==  9
elementoEnPosicion []       ==  1

Leer más…

Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

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

Los árboles binarios se puede representar mediante el siguiente tipo

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

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 9 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

data Movimiento = I | D deriving (Show, Eq)
type Posicion   = [Movimiento]

Definir la función

posicionDeElemento :: Integer -> Posicion

tal que (posicionDeElemento n) es la posición del elemento n en el árbol binario completo. Por ejemplo,

posicionDeElemento 6  ==  [D,I]
posicionDeElemento 7  ==  [D,D]
posicionDeElemento 9  ==  [I,I,D]
posicionDeElemento 1  ==  []

length (posicionDeElemento2 (10^50000))  ==  166096

Leer más…

Los árboles binarios con datos en los nodos se definen por

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

Por ejemplo, el árbol

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

se representa por

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

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 4 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

data Movimiento = I | D deriving (Show, Eq)
type Posicion   = [Movimiento]

Definir la función

posiciones :: Eq b => b -> Arbol b -> [Posicion]

tal que (posiciones n a) es la lista de las posiciones del elemento n en el árbol a. Por ejemplo,

posiciones 0 ejArbol  ==  [[I],[I,D],[D,I]]
posiciones 2 ejArbol  ==  [[I,I,I]]
posiciones 3 ejArbol  ==  [[],[D,D]]
posiciones 4 ejArbol  ==  [[I,I,D]]
posiciones 5 ejArbol  ==  [[I,I],[D]]
posiciones 1 ejArbol  ==  []

Leer más…

Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

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

Los árboles binarios se puede representar mediante el siguiente tipo

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

Definir la función

arbolBinarioCompleto :: Int -> Arbol

tal que (arbolBinarioCompleto n) es el árbol binario completo con n nodos. Por ejemplo,

λ> arbolBinarioCompleto 4
N 1 (N 2 (N 4 H H) H) (N 3 H H)
λ> arbolBinarioCompleto 9
N 1
  (N 2
     (N 4
        (N 8 H H)
        (N 9 H H))
     (N 5 H H))
  (N 3
     (N 6 H H)
     (N 7 H H))

Leer más…

Un número x es un cubo si existe un y tal que x = y^3. Por ejemplo, 8 es un cubo porque 8 = 2^3.

Definir la función

raizCubicaEntera :: Integer -> Maybe Integer.

tal que (raizCubicaEntera x n) es justo la raíz cúbica del número natural x, si x es un cubo y Nothing en caso contrario. Por ejemplo,

raizCubicaEntera 8             ==  Just 2
raizCubicaEntera 9             ==  Nothing
raizCubicaEntera 27            ==  Just 3
raizCubicaEntera 64            ==  Just 4
raizCubicaEntera (2^30)        ==  Just 1024
raizCubicaEntera (10^9000)     ==  Just (10^3000)
raizCubicaEntera (5 + 10^9000) ==  Nothing

Leer más…

Se dice que un número natural n es una colina si su primer dígito es igual a su último dígito, los primeros dígitos son estrictamente creciente hasta llegar al máximo, el máximo se puede repetir y los dígitos desde el máximo al final son estrictamente decrecientes.

Definir la función

esColina :: Integer -> Bool

tal que (esColina n) se verifica si n es un número colina. Por ejemplo,

esColina 12377731  ==  True
esColina 1237731   ==  True
esColina 123731    ==  True
esColina 12377730  ==  False
esColina 12377730  ==  False
esColina 10377731  ==  False
esColina 12377701  ==  False
esColina 33333333  ==  True

Leer más…

Definir la función

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

tal que (solitario xs) es el único elemento que ocurre una vez en la lista xs (se supone que la lista xs tiene al menos 3 elementos y todos son iguales menos uno que es el solitario). Por ejemplo,

solitario [2,2,7,2]  ==  7
solitario [2,2,2,7]  ==  7
solitario [7,2,2,2]  ==  7
solitario (replicate (2*10^7) 1 ++ [2])  ==  2

Leer más…

Esta semana se ha publicado en Twitter una demostración visual de la suma de inversos de potencias de 4:

1/4 + 1/4² + 1/4³ + ... = 1/3

Definir las funciones

sumaInversosPotenciasDeCuatro :: [Double]
aproximacion :: Double -> Int

tales que

• sumaInversosPotenciasDeCuatro es la lista de las suma de la serie de los inversos de las potencias de cuatro. Por ejemplo,

λ> take 6 sumaInversosPotenciasDeCuatro
[0.25,0.3125,0.328125,0.33203125,0.3330078125,0.333251953125]

• (aproximacion e) es el menor número de términos de la serie anterior que hay que sumar para que el valor absoluto de su diferencia con 1/3 sea menor que e. Por ejemplo,

aproximacion 0.001  ==  4
aproximacion 1e-3   ==  4
aproximacion 1e-6   ==  9
aproximacion 1e-20  ==  26
sumaInversosPotenciasDeCuatro !! 26  ==  0.3333333333333333

Leer más…

Definir las funciones

esPrimoSumaDeDosPrimos :: Integer -> Bool

primosSumaDeDosPrimos :: [Integer] tales que

• (esPrimoSumaDeDosPrimos x) se verifica si x es un número primo que se puede escribir como la suma de dos números primos. Por ejemplo,

esPrimoSumaDeDosPrimos 19  ==  True
esPrimoSumaDeDosPrimos 20  ==  False
esPrimoSumaDeDosPrimos 23  ==  False

• primosSumaDeDosPrimos es la lista de los números primos que se pueden escribir como la suma de dos números primos. Por ejemplo,

λ> take 17 primosSumaDeDosPrimos
[5,7,13,19,31,43,61,73,103,109,139,151,181,193,199,229,241]
λ> primosSumaDeDosPrimos !! (10^5)
18409543

Leer más…

Definir la función

cerosDelFactorial :: Integer -> Integer

tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,

cerosDelFactorial 24                           ==  4
cerosDelFactorial 25                           ==  6
length (show (cerosDelFactorial (1234^5678)))  ==  17552

Leer más…

Dos elementos están relacionados por una partición xss si pertenecen al mismo elemento de xss.

Definir la función

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

tal que (relacionados xss y z) se verifica si los elementos y y z están relacionados por la partición xss. Por ejemplo,

relacionados [[1,3],[2],[9,5,7]] 7 9  ==  True
relacionados [[1,3],[2],[9,5,7]] 3 9  ==  False
relacionados [[1,3],[2],[9,5,7]] 4 9  ==  False

Leer más…

Definir la función

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

tal que (nParejas xs) es el número de parejas de elementos iguales en xs. Por ejemplo,

nParejas [1,2,2,1,1,3,5,1,2]        ==  3
nParejas [1,2,1,2,1,3,2]            ==  2
nParejas [1..2*10^6]                ==  0
nParejas2 ([1..10^6] ++ [1..10^6])  ==  1000000

En el primer ejemplos las parejas son (1,1), (1,1) y (2,2). En el segundo ejemplo, las parejas son (1,1) y (2,2).

Comprobar con QuickCheck que para toda lista de enteros xs, el número de parejas de xs es igual que el número de parejas de la inversa de xs.

Leer más…

Un número n es autodescriptivo cuando para cada posición k de n (empezando a contar las posiciones a partir de 0), el dígito en la posición k es igual al número de veces que ocurre k en n. Por ejemplo, 1210 es autodescriptivo porque tiene 1 dígito igual a "0", 2 dígitos iguales a "1", 1 dígito igual a "2" y ningún dígito igual a "3".

Definir la función

autodescriptivo :: Integer -> Bool

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

λ> autodescriptivo 1210
True
λ> [x | x <- [1..100000], autodescriptivo x]
[1210,2020,21200]
λ> autodescriptivo 9210000001000
True

Nota: se puede usar la función genericLength.

Leer más…

Leer más…

Un número entero positivo es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

libreDeCuadrados :: Integer -> Bool

tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,

libreDeCuadrados 70                    ==  True
libreDeCuadrados 40                    ==  False
libreDeCuadrados 510510                ==  True
libreDeCuadrados (((10^10)^10)^10)     ==  False

Leer más…

La diferencia simétrica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica de {2,5,3} y {4,2,3,7} es {4,5,7}.

Definir la función

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

tal que (diferenciaSimetrica xs ys) es la diferencia simétrica de xs e ys. Por ejemplo,

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

Leer más…

El factorial de 7 es

7! = 1·2·3·4·5·6·7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

ultimoNoNuloFactorial  7  == 4
ultimoNoNuloFactorial 10  == 8
ultimoNoNuloFactorial 12  == 6
ultimoNoNuloFactorial 97  == 2
ultimoNoNuloFactorial  0  == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Leer más…

La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).

Definir la función

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

tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,

distancia "romano" "comino"  ==  2
distancia "romano" "camino"  ==  3
distancia "roma"   "comino"  ==  2
distancia "roma"   "camino"  ==  3
distancia "romano" "ron"     ==  1
distancia "romano" "cama"    ==  2
distancia "romano" "rama"    ==  1

Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad

distancia(xs,ys) = 0 si, y sólo si, xs = ys

y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.

Leer más…

Una lista de números naturales es equidigital si todos sus elementos tienen el mismo número de dígitos.

Definir la función

equidigital :: [Int] -> Bool

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

equidigital [343,225,777,943]   ==  True
equidigital [343,225,777,94,3]  ==  False

Leer más…

Un número medio es número natural que es igual a la media aritmética de las permutaciones de sus dígitos. Por ejemplo, 370 es un número medio ya que las permutaciones de sus dígitos es 073, 037, 307, 370, 703 y 730 cuya media es 2220/6 que es igual a 370.

Definir las siguientes funciones

numeroMedio                :: Integer -> Bool
densidadesNumeroMedio      :: [Double]
graficaDensidadNumeroMedio :: Int -> IO ()

tales que

• (numeroMedio n) se verifica si n es un número medio. Por ejemplo,

λ> numeroMedio 370
True
λ> numeroMedio 371
False
λ> numeroMedio 485596707818930041152263374
True
λ> filter numeroMedio [100..600]
[111,222,333,370,407,444,481,518,555,592]
λ> filter numeroMedio [3*10^5..6*10^5]
[333333,370370,407407,444444,481481,518518,555555,592592]

• densidades es la lista cuyo elemento n-ésimo (empezando a contar en 1) es la densidad de números medios en el intervalo [1,n]; es decir, la cantidad de números medios menores o iguales que n dividida por n. Por ejemplo,

λ> mapM_ print (take 30 densidades)
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.9
0.9090909090909091
0.8333333333333334
0.7692307692307693
0.7142857142857143
0.6666666666666666
0.625
0.5882352941176471
0.5555555555555556
0.5263157894736842
0.5
0.47619047619047616
0.5
0.4782608695652174
0.4583333333333333
0.44
0.4230769230769231
0.4074074074074074
0.39285714285714285
0.3793103448275862
0.36666666666666664

• (graficaDensidadNumeroMedio n) dibuja la gráfica de las densidades de los intervalos [1,k] para k desde 1 hasta n. Por ejemplo, (graficaDensidadNumeroMedio 100) dibuja

y (graficaDensidadNumeroMedio 1000) dibuja

Leer más…

Si n es el número natural cuya expansión decimal es abc... , el tren de potencias de n es a^bc^d... donde el último exponente es 1, si n tiene un número impar de dígitos. Por ejemplo

trenDePotencias 2453  = 2^4*5^3     = 2000
trenDePotencias 24536 = 2^4*5^3*6^1 = 12000

Definir las funciones

trenDePotencias            :: Integer -> Integer
esPuntoFijoTrenDePotencias :: Integer -> Bool
puntosFijosTrenDePotencias :: [Integer]
tablaTrenDePotencias       :: Integer -> Integer -> IO ()

tales que

• (trenDePotencias n) es el tren de potencia de n. Por ejemplo.

trenDePotencias 20   ==  1
trenDePotencias 21   ==  2
trenDePotencias 24   ==  16
trenDePotencias 39   ==  19683
trenDePotencias 623  ==  108

• (esPuntoFijoTrenDePotencias n) se verifica si n es un punto fijo de trenDePotencias; es decir, (trenDePotencias n) es igual a n. Por ejemplo,

esPuntoFijoTrenDePotencias 2592                        ==  True
esPuntoFijoTrenDePotencias 24547284284866560000000000  ==  True

• puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,

take 10 puntosFijosTrenDePotencias  ==  [1,2,3,4,5,6,7,8,9,2592]

• (tablaTrenDePotencias a b) es la tabla de los trenes de potencias de los números entre a y b. Por ejemplo,

λ> tablaTrenDePotencias 20 39
| 20 |     1 |
| 21 |     2 |
| 22 |     4 |
| 23 |     8 |
| 24 |    16 |
| 25 |    32 |
| 26 |    64 |
| 27 |   128 |
| 28 |   256 |
| 29 |   512 |
| 30 |     1 |
| 31 |     3 |
| 32 |     9 |
| 33 |    27 |
| 34 |    81 |
| 35 |   243 |
| 36 |   729 |
| 37 |  2187 |
| 38 |  6561 |
| 39 | 19683 |
λ> tablaTrenDePotencias 2340 2359
| 2340 |        8 |
| 2341 |       32 |
| 2342 |      128 |
| 2343 |      512 |
| 2344 |     2048 |
| 2345 |     8192 |
| 2346 |    32768 |
| 2347 |   131072 |
| 2348 |   524288 |
| 2349 |  2097152 |
| 2350 |        8 |
| 2351 |       40 |
| 2352 |      200 |
| 2353 |     1000 |
| 2354 |     5000 |
| 2355 |    25000 |
| 2356 |   125000 |
| 2357 |   625000 |
| 2358 |  3125000 |
| 2359 | 15625000 |

Comprobar con QuickCheck que entre 2593 y 24547284284866559999999999 la función trenDePotencias no tiene puntos fijos.

Leer más…

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]

Leer más…

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

type Punto = (Int,Int)
type Mapa  = Array Punto Int

mapa1, mapa2 :: Mapa
mapa1 = listArray ((1,1),(3,4))
                  [1,1,0,0,
                   0,1,0,0,
                   1,0,0,0]
mapa2 = listArray ((1,1),(10,20))
                  [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
                   0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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]

Definir las funciones

alcanzables :: Mapa -> Punto -> [Punto]
esAlcanzable :: Mapa -> Punto -> Punto -> Bool

tales que

• (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,

alcanzables mapa1 (1,1)  ==  [(2,2),(1,2),(1,1)]
alcanzables mapa1 (1,2)  ==  [(2,2),(1,1),(1,2)]
alcanzables mapa1 (1,3)  ==  [(3,2),(3,4),(3,3),(2,3),(2,4),(1,4),(1,3)]
alcanzables mapa1 (3,1)  ==  [(3,1)]

• (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,

esAlcanzable mapa1 (1,4) (3,2)    ==  True
esAlcanzable mapa1 (1,4) (3,1)    ==  False
esAlcanzable mapa2 (2,3) (8,16)   ==  True
esAlcanzable mapa2 (8,1) (7,3)    ==  True
esAlcanzable mapa2 (1,1) (10,20)  ==  False

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Leer más…

El recorrido en ZigZag de una matriz consiste en pasar de la primera fila hasta la última, de izquierda a derecha en las filas impares y de derecha a izquierda en las filas pares, como se indica en la figura.

/             \
| 1 -> 2 -> 3 |
|           | |
|           v |
| 4 <- 5 <- 6 |   =>  Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]
| |           |
| v           |
| 7 -> 8 -> 9 |
\             /