Conjetura de las familias estables por uniones

José A. Alonso

Misceláneas

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 {∅} 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

Distribución de diferencias de dígitos consecutivos de pi

José A. Alonso

Misceláneas

Usando la librería Data.Number.CReal, que se instala con

cabal install number

se pueden calcular el número pi con la precisión que se desee. Por ejemplo,

λ> import Data.Number.CReal
λ> showCReal 60 pi
"3.141592653589793238462643383279502884197169399375105820974945"

importa la librería y calcula el número pi con 60 decimales.

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros n dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

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

Las diferencias de sus elementos consecutivos es

2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

distribucionDDCpi :: Int -> [Int]
graficas :: [Int] -> FilePath -> IO ()

tales que

(distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

λ> distribucionDDCpi 18
[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
λ> distribucionDDCpi 100
[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
λ> distribucionDDCpi 200
[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
λ> distribucionDDCpi 1000
[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
λ> distribucionDDCpi 5000
[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

(graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] "distribucionDDCpi.png" se escribe en el fichero "distribucionDDCpi.png" la siguiente gráfica

Distribución de diferencias de dígitos consecutivos de pi

Cálculo de dígitos de pi y su distribución

José A. Alonso

Misceláneas

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]

Huecos de Aquiles

José A. Alonso

Misceláneas

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

Huecos de Aquiles

Árbol de divisores

José A. Alonso

Misceláneas

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.

El árbol de los divisores de un número x es el árbol que tiene como raíz el número x y cada nodo tiene como hijos sus divisores propios maximales. Por ejemplo, el árbol de divisores de 30 es

       30
       /|\
      / | \
     /  |  \
    /   |   \
   /    |    \
  6    10    15
 / \   / \   / \
2   3 2   5 3   5

Usando el tipo de dato

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

el árbol anterior se representa por

N 30
  [N 6
     [N 2 [N 1 []],
      N 3 [N 1 []]],
   N 10
     [N 2 [N 1 []],
      N 5 [N 1 []]],
   N 15
     [N 3 [N 1 []],
      N 5 [N 1 []]]]

Definir las funciones

arbolDivisores             :: Integer -> Arbol
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

tales que

(arbolDivisores x) es el árbol de los divisores del número x. Por ejemplo,

λ> arbolDivisores 30
N 30 [N 6  [N 2 [N 1 []],N 3 [N 1 []]],
      N 10 [N 2 [N 1 []],N 5 [N 1 []]],
      N 15 [N 3 [N 1 []],N 5 [N 1 []]]]

(nOcurrenciasArbolDivisores x y) es el número de veces que aparece el número x en el árbol de los divisores del número y. Por ejemplo,

nOcurrenciasArbolDivisores  3 30  ==  2
nOcurrenciasArbolDivisores  6 30  ==  1
nOcurrenciasArbolDivisores 30 30  ==  1
nOcurrenciasArbolDivisores  1 30  ==  6
nOcurrenciasArbolDivisores  9 30  ==  0
nOcurrenciasArbolDivisores  2 (product [1..10])  ==  360360
nOcurrenciasArbolDivisores  3 (product [1..10])  ==  180180
nOcurrenciasArbolDivisores  5 (product [1..10])  ==  90090
nOcurrenciasArbolDivisores  7 (product [1..10])  ==  45045
nOcurrenciasArbolDivisores  6 (product [1..10])  ==  102960
nOcurrenciasArbolDivisores 10 (product [1..10])  ==  51480
nOcurrenciasArbolDivisores 14 (product [1..10])  ==  25740

Triángulo de Euler

José A. Alonso

Misceláneas

El triángulo de Euler se construye a partir de las siguientes relaciones

A(n,1) = A(n,n) = 1
A(n,m) = (n-m)A(n-1,m-1) + (m+1)A(n-1,m).

Sus primeros términos son

1
1 1
1 4   1
1 11  11    1
1 26  66    26    1
1 57  302   302   57     1
1 120 1191  2416  1191   120   1
1 247 4293  15619 15619  4293  247   1
1 502 14608 88234 156190 88234 14608 502 1

Definir las siguientes funciones:

numeroEuler        :: Integer -> Integer -> Integer
filaTrianguloEuler :: Integer -> [Integer]
trianguloEuler     :: [[Integer]]

tales que

(numeroEuler n k) es el número de Euler A(n,k). Por ejemplo,

numeroEuler 8 3  == 15619
numeroEuler 20 6 == 21598596303099900
length (show (numeroEuler 1000 500)) == 2567

(filaTrianguloEuler n) es la n-ésima fila del triángulo de Euler. Por ejemplo,

filaTrianguloEuler 7  ==  [1,120,1191,2416,1191,120,1]
filaTrianguloEuler 8  ==  [1,247,4293,15619,15619,4293,247,1]
length (show (maximum (filaTrianguloEuler 1000)))  ==  2567

trianguloEuler es la lista con las filas del triángulo de Euler

λ> take 6 trianguloEuler
[[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]]
λ> length (show (maximum (trianguloEuler !! 999)))
2567

Subconjuntos divisibles

José A. Alonso

Misceláneas

Definir la función

subconjuntosDivisibles :: [Int] -> [[Int]]

tal que (subconjuntosDivisibles xs) es la lista de todos los subconjuntos de xs en los que todos los elementos tienen un factor común mayor que 1. Por ejemplo,

subconjuntosDivisibles []         ==  [[]]
subconjuntosDivisibles [1]        ==  [[]]
subconjuntosDivisibles [3]        ==  [[3],[]]
subconjuntosDivisibles [1,3]      ==  [[3],[]]
subconjuntosDivisibles [3,6]      ==  [[3,6],[3],[6],[]]
subconjuntosDivisibles [1,3,6]    ==  [[3,6],[3],[6],[]]
subconjuntosDivisibles [2,3,6]    ==  [[2,6],[2],[3,6],[3],[6],[]]
subconjuntosDivisibles [2,3,6,8]  ==  [[2,6,8],[2,6],[2,8],[2],[3,6],[3],[6,8],[6],[8],[]]
length (subconjuntosDivisibles [1..10])  ==  41
length (subconjuntosDivisibles [1..20])  ==  1097
length (subconjuntosDivisibles [1..30])  ==  33833
length (subconjuntosDivisibles [1..40])  ==  1056986

Matriz girada 180 grados

José A. Alonso

Misceláneas

Definir la función

matrizGirada180 :: Matrix a -> Matrix a

tal que (matrizGirada180 p) es la matriz obtenida girando 180 grados la matriz p. Por ejemplo,

λ> fromList 4 3 [1..]
(  1  2  3 )
(  4  5  6 )
(  7  8  9 )
( 10 11 12 )

λ> matrizGirada180 (fromList 4 3 [1..])
( 12 11 10 )
(  9  8  7 )
(  6  5  4 )
(  3  2  1 )

λ> fromList 3 4 [1..]
(  1  2  3  4 )
(  5  6  7  8 )
(  9 10 11 12 )

λ> matrizGirada180 (fromList 3 4 [1..])
( 12 11 10  9 )
(  8  7  6  5 )
(  4  3  2  1 )

Árboles cuyas ramas cumplen una propiedad

José A. Alonso

Misceláneas

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

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

Por ejemplo, los árboles

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

se representan por

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

Definir la función

todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool

tal que (todasDesdeAlguno p ar) se verifica si para toda rama existe un elemento a partir del cual todos los elementos de la rama verifican la propiedad p. Por ejemplo,

todasDesdeAlguno (>0) ej1 == True
todasDesdeAlguno (>0) ej2 == False
todasDesdeAlguno (>0) ej3 == True

El problema del número perdido

José A. Alonso

Misceláneas

Sea xs una lista de números consecutivos (creciente o decreciente), en la que puede faltar algún número. El problema del número perdido en xs consiste en lo siguiente:

si falta un único número z, devolver Just z
si no falta ninguno, devolver Nothing

Definir la función

numeroPerdido :: [Int] -> Maybe Int

tal que (numeroPerdido xs) es el resultado del problema del número perdidio en xs. Por ejemplo,

numeroPerdido [7,6,4,3]                     == Just 5
numeroPerdido [1,2,4,5,6]                   == Just 3
numeroPerdido [6,5..3]                      == Nothing
numeroPerdido [1..6]                        == Nothing
numeroPerdido ([5..10^6] ++ [10^6+2..10^7]) == Just 1000001

Matriz de mínimas distancias

José A. Alonso

Misceláneas

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

La sucesión ECG

José A. Alonso

Misceláneas

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 auú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 ()

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

La sucesión ECG

Siguiente mayor

José A. Alonso

Misceláneas

Definir la función

siguienteMayor :: Ord a => [a] -> [Maybe a]

tal que (siguienteMayos xs) es la lista obtenida sustiyendo cada elemento de xs por el primer elemento de xs a la derechha de x que sea mayor que x, si esxte y Nothing en caso contrario. Por ejemplo,

λ> siguienteMayor [4,5,2,3,9]
[Just 5,Just 9,Just 3,Just 9,Nothing]
λ> siguienteMayor [9,5,2,3,4]
[Nothing,Nothing,Just 3,Just 4,Nothing]
λ> siguienteMayor [9,5,2,2,4]
[Nothing,Nothing,Just 4,Just 4,Nothing]
λ> siguienteMayor "betis"
[Just 'e',Just 't',Nothing,Just 's',Nothing]
λ> siguienteMayor "sevilla"
[Just 'v',Just 'v',Nothing,Just 'l',Nothing,Nothing,Nothing]

Caminos minimales en un arbol numérico

José A. Alonso

Misceláneas

En la librería Data.Tree se definen los tipos de árboles y bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u.v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

Definir las siguientes funciones

mayoresDivisores :: Int -> [Int]
arbol            :: Int -> Tree Int
caminos          :: Int -> [[Int]]
caminosMinimales :: Int -> [[Int]]

tales que + (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

mayoresDivisores 24  ==  [12,8,6]
mayoresDivisores 16  ==  [8,4]
mayoresDivisores 10  ==  [5]
mayoresDivisores 17  ==  []

(arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbol 6)))
6
|
+- 5
|  |
|  `- 4
|     |
|     +- 3
|     |  |
|     |  `- 2
|     |     |
|     |     `- 1
|     |
|     `- 2
|        |
|        `- 1
|
`- 3
   |
   `- 2
      |
      `- 1

(caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> caminos 6
[[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

(caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> caminosMinimales 6
[[6,3,2,1]]
λ> caminosMinimales 17
[[17,16,4,2,1]]
λ> caminosMinimales 50
[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Permutación de elementos consecutivos

José A. Alonso

Misceláneas

Definir la función

permutaConsecutivos :: [a] -> [a]

tal que (permutaConsecutivos xs) es la lista obtenida permutando los elementos consecutivos de xs. Por ejemplo,

permutaConsecutivos [1..8]         ==  [2,1,4,3,6,5,8,7]
permutaConsecutivos [1..9]         ==  [2,1,4,3,6,5,8,7,9]
permutaConsecutivos "simplemente"  ==  "ispmelemtne"

Cambio con el menor número de monedas

José A. Alonso

Misceláneas

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

1, 1, 1, 1, 1, 1
1, 1, 1, 3
1, 1, 4
3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

monedas [1,3,4]  6                    ==  Just 2
monedas [2,5,10] 3                    ==  Nothing
monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

Máxima longitud de sublistas crecientes

José A. Alonso

Misceláneas

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

Diagonales invertidas

José A. Alonso

Misceláneas

Definir la función

diagonalesInvertidas :: Matrix a -> Matrix a

tal que (diagonalesInvertidas q) es la matriz obtenida invirtiendo el orden de los elementos de la diagonal principal y de la diagonal secundaria de q. Por ejemplo,

λ> fromList 5 5 [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 │
└                ┘
λ> diagonalesInvertidas (fromList 5 5 [1..])
┌                ┐
│ 25  2  3  4 21 │
│  6 19  8 17 10 │
│ 11 12 13 14 15 │
│ 16  9 18  7 20 │
│  5 22 23 24  1 │
└                ┘
λ> fromList 3 3 ['a','b'..]
┌             ┐
│ 'a' 'b' 'c' │
│ 'd' 'e' 'f' │
│ 'g' 'h' 'i' │
└             ┘
λ> diagonalesInvertidas (fromList 3 3 ['a','b'..])
┌             ┐
│ 'i' 'b' 'g' │
│ 'd' 'e' 'f' │
│ 'c' 'h' 'a' │
└             ┘

Números cíclopes

José A. Alonso

Misceláneas

Un número cíclope es un número natural cuya representación binaria sólo tiene un cero en el centro. Por ejemplo,

  0      es ciclope porque su representación binaria es 0
  1   no es ciclope porque su representación binaria es 1
  5      es ciclope porque su representación binaria es 101
  9   no es ciclope porque su representación binaria es 1001
 10   no es ciclope porque su representación binaria es 1010
 27      es ciclope porque su representación binaria es 11011
 85   no es ciclope porque su representación binaria es 1010101
101   no es ciclope porque su representación binaria es 1100101
111   no es ciclope porque su representación binaria es 1101111
119      es ciclope porque su representación binaria es 1110111

Definir las funciones

esCiclope       :: Integer -> Bool
ciclopes        :: [Integer]
graficaCiclopes :: Int -> IO ()

tales que

(esCiclope n) se verifica si el número natual n es cíclope. Por ejemplo,

esCiclope 0    ==  True
esCiclope 1    ==  False
esCiclope 5    ==  True
esCiclope 9    ==  False
esCiclope 10   ==  False
esCiclope 27   ==  True
esCiclope 85   ==  False
esCiclope 101  ==  False
esCiclope 111  ==  False
esCiclope 119  ==  True

ciclopes es la lista de los número cíclopes. Por ejemplo,

λ> take 12 ciclopes
[0,5,27,119,495,2015,8127,32639,130815,523775,2096127,8386559]
λ> length (show (ciclopes !! (10^5)))
60207

(graficaCiclopes n) dibuja la gráfica del último dígito de los n primeros números cíclopes. Por ejemplo, (graficaCiclopes n) dibuja

Números cíclopes

Combinaciones divisibles

José A. Alonso

Misceláneas

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.

Camino de máxima suma en una matriz

José A. Alonso

Misceláneas

(  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 (caminoMaxSuma3 (fromList 800 800 [1..]))
766721999
(1.68 secs, 1,082,106,856 bytes)

Suma de segmentos iniciales

José A. Alonso

Misceláneas

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

Números como suma de sus dígitos

José A. Alonso

Misceláneas

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

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

Números como suma de sus dígitos

Las torres de Hanói

José A. Alonso

Misceláneas

Las torres de Hanoi es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.

Los postes se pueden representar mediante el siguiente tipo de datos

data Poste = A | B | C
  deriving Show

Definir las funciones

movimientos :: Integer -> [(Integer,Poste,Poste)]
hanoi       :: Integer -> IO ()

tales que

(movimientos n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,

λ> movimientos 1
[(1,A,C)]
λ> movimientos 2
[(1,A,B),(2,A,C),(1,B,C)]
λ> movimientos 3
[(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)]

(hanoi n) escribe los mensajes de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,

λ> hanoi 3
Mueve el disco 1 de A a C
Mueve el disco 2 de A a B
Mueve el disco 1 de C a B
Mueve el disco 3 de A a C
Mueve el disco 1 de B a A
Mueve el disco 2 de B a C
Mueve el disco 1 de A a C

Hojas con caminos no decrecientes

José A. Alonso

Misceláneas

Número de descomposiciones en sumas de cuatro cuadrados

José A. Alonso

Misceláneas

Definir la función

nDescomposiciones       :: Int -> Int
graficaDescomposiciones :: Int -> IO ()

tales que

(nDescomposiciones x) es el número de listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.

nDescomposiciones 4      ==  1
nDescomposiciones 5      ==  0
nDescomposiciones 7      ==  4
nDescomposiciones 10     ==  6
nDescomposiciones 15     ==  12
nDescomposiciones 50000  ==  5682

(graficaDescomposiciones n) dibuja la gráfica del número de descomposiciones de los n primeros números naturales. Por ejemplo, (graficaDescomposiciones 500) dibuja

Número de descomposiciones en sumas de cuatro cuadrados

Descomposiciones en sumas de cuatro cuadrados

José A. Alonso

Misceláneas

Definir la función

descomposiciones :: Int -> [[Int]]

tal que (descomposiciones x) es la lista de las listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.

λ> descomposiciones 4
[[1,1,1,1]]
λ> descomposiciones 5
[]
λ> descomposiciones 7
[[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]]
λ> descomposiciones 10
[[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]]
λ> descomposiciones 15
[[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1],
[4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]]
λ> length (descomposiciones 50000)
5682

Numero de particiones de un conjunto

José A. Alonso

Misceláneas

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

{{1}, {2}, {3}}
{{1,2}, {3}}
{{1,3}, {2}}
{{1}, {2,3}}
{{1,2,3}}

Definir la función

nParticiones :: [a] -> Integer

tal que (nParticiones xs) es el número de particiones de xs. Por ejemplo,

nParticiones [1,2]                     ==  2
nParticiones [1,2,3]                   ==  5
nParticiones "abcd"                    ==  15
length (show (nParticiones [1..500]))  ==  844

Particiones de un conjunto

José A. Alonso

Misceláneas

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

{{1}, {2}, {3}}
{{1,2}, {3}}
{{1,3}, {2}}
{{1}, {2,3}}
{{1,2,3}}

Definir la función

particiones :: [a] -> [[[a]]]

tal que (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,

λ> particiones [1,2]
[[[1,2]],[[1],[2]]]
λ> particiones [1,2,3]
[[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]]
λ> particiones "abcd"
[["abcd"],["a","bcd"],["ab","cd"],["b","acd"],["abc","d"],["bc","ad"],
 ["ac","bd"],["c","abd"],["a","b","cd"],["a","bc","d"],["a","c","bd"],
 ["ab","c","d"],["b","ac","d"],["b","c","ad"],["a","b","c","d"]]

Inserciones en una lista de listas

José A. Alonso

Misceláneas

Definir la función

inserta :: a -> [[a]] -> [[[a]]]

tal que (inserta x yss) es la lista obtenida insertando x en cada uno de los elementos de yss. Por ejemplo,

λ> inserta 1 [[2,3],[4],[5,6,7]]
[[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]]
λ> inserta 'a' ["hoy","es","lunes"]
[["ahoy","es","lunes"],["hoy","aes","lunes"],["hoy","es","alunes"]]

Divisiones del círculo

José A. Alonso

Misceláneas

Dado 4 puntos de un círculo se pueden dibujar 2 cuerdas entre ellos de forma que no se corten. En efecto, si se enumeran los puntos del 1 al 4 en sentido de las agujas del reloj una forma tiene las cuerdas {1-2, 3-4} y la otra {1-4, 2-3}.

Definir la función

numeroFormas :: Integer -> Integer

tal que (numeroFormas n) es el número de formas que se pueden dibujar n cuerdas entre 2xn puntos de un círculo sin que se corten. Por ejemplo,

numeroFormas 1   ==  1
numeroFormas 2   ==  2
numeroFormas 4   ==  14
numeroFormas 75  ==  1221395654430378811828760722007962130791020
length (show (numeroFormas 1000))  ==  598

Número de sumandos en suma de cuadrados

José A. Alonso

Misceláneas

El teorema de Lagrange de los cuatro cuadrados asegura que cualquier número entero positivo es la suma de, como máximo,cuatro cuadrados de números enteros. Por ejemplo,

16 = 4²
29 = 2² + 5²
14 = 1^2 + 2^2 + 3^2
15 = 1^2 + 1^2 + 2^2 + 3^2

Definir las funciones

ordenLagrange        :: Integer -> Int
graficaOrdenLagrange :: Integer -> IO ()

tales que

(ordenLagrange n) es el menor número de cuadrados necesarios para escribir n como suma de cuadrados. Por ejemplo.

ordenLagrange 16     ==  1
ordenLagrange 29     ==  2
ordenLagrange 14     ==  3
ordenLagrange 15     ==  4
ordenLagrange 10000  ==  1
ordenLagrange 10001  ==  2
ordenLagrange 10002  ==  3
ordenLagrange 10007  ==  4

(graficaOrdenLagrange n) dibuja la gráfica de los órdenes de Lagrange de los n primeros números naturales. Por ejemplo, (graficaOrdenLagrange 100) dibuja

Número de sumandos en suma de cuadrados

Comprobar con QuickCheck que. para todo entero positivo k, el orden de Lagrange de k es menos o igual que 4, el de 4k+3 es distinto de 2 y el de 8k+7 es distinto de 3.

Mayor exponente

José A. Alonso

Misceláneas

Definir las funciones

mayorExponente        :: Integer -> Integer
graficaMayorExponente :: Integer -> IO ()

tales que

(mayorExponente n) es el mayor número b para el que existe un a tal que n = a^b. Se supone que n > 1. Por ejemplo,

mayorExponente 9   ==  2
mayorExponente 8   ==  3
mayorExponente 7   ==  1
mayorExponente 18  ==  1
mayorExponente 36  ==  2
mayorExponente (10^(10^5))  ==  100000

(graficaMayorExponente n) dibuja la gráfica de los mayores exponentes de los números entre 2 y n. Por ejemplo, (graficaMayorExponente 50) dibuja

Mayor exponente

Mezcla de listas

José A. Alonso

Misceláneas

Definir la función

mezcla :: [[a]] -> [a]

tal que (mezcla xss) es la lista tomando sucesivamente los elementos de xss en la misma posición. Cuando una de las listas de xss es vacía, se continua con las restantes. por ejemplo,

mezcla [[1,2],[3..7],[8..10]]            ==  [1,3,8,2,4,9,5,10,6,7]
mezcla ["Estamos","en","2019"]           ==  "Ee2sn0t1a9mos"
take 9 (mezcla [[3,6..],[5,7..],[0,1]])  ==  [3,5,0,6,7,1,9,9,12]

Ternas euclídeas

José A. Alonso

Misceláneas

Uno de los problemas planteados por Euclides en los Elementos consiste en encontrar tres números tales que cada uno de sus productos, dos a dos, aumentados en la unidad sea un cuadrado perfecto.

Diremos que (x,y,z) es una terna euclídea si es una solución del problema; es decir, si x <= y <= z y xy+1, yz+1 y zx+1 son cuadrados. Por ejemplo, (4,6,20) es una terna euclídea ya que

4x6+1 = 5^2, 6x20+1 = 11^2 y 20*4+1 = 9^2

Definir la funciones

ternasEuclideas        :: [(Integer,Integer,Integer)]
esMayorDeTernaEuclidea :: Integer -> Bool

tales que

ternasEuclideas es la lista de las ternas euclídeas. Por ejemplo,

λ> take 7 ternasEuclideas
[(1,3,8),(2,4,12),(1,8,15),(3,5,16),(4,6,20),(3,8,21),(5,7,24)]

(esMayorDeTernaEuclidea z) se verifica si existen x, y tales que (x,y,z) es una terna euclídea. Por ejemplo,

esMayorDeTernaEuclidea 20  ==  True
esMayorDeTernaEuclidea 22  ==  False

Comprobar con QuickCheck que z es el mayor de una terna euclídea si, y sólo si, existe un número natural x tal que 1 < x < z - 1 y x^2 es congruente con 1 módulo z.

Sucesión de Cantor de números innombrables

José A. Alonso

Misceláneas

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior:

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
(30) 99 100

Definir las funciones

sucCantor        :: [Integer]
graficaSucCantor :: Int -> IO ()

tales que

sucCantor es la lista cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,

λ> take 100 sucCantor
[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
6, 92,93,94,95,96, 29, 30 ,99,100]
λ> sucCantor2 !! (5+10^6)
544480
λ> sucCantor2 !! (6+10^6)
266086

(graficaSucCantor n) es la gráfica de los n primeros términos de la sucesión de Cantor. Por ejemplo, (graficaSucCantor 200) dibuja

Sucesión de Cantor de números innombrables

Simplificación de expresiones booleanas

José A. Alonso

Misceláneas

El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

data Expr = X
          | V
          | F
          | Neg Expr
          | Dis Expr Expr
          deriving (Eq, Ord)

Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

valor      :: Expr -> Bool -> Bool
simplifica :: Expr -> Expr

tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,

valor (Neg X) True           ==  False
valor (Neg F) True           ==  True
valor (Dis X (Neg X)) True   ==  True
valor (Dis X (Neg X)) False  ==  True

y (simplifica p) es una expresión obtenida aplicándole a p las siguientes reglas de simplificación:

Neg V       = F
Neg F       = V
Neg (Neg q) = q
Dis V q     = V
Dis F q     = q
Dis q V     = V
Dis q F     = F
Dis q q     = q

Por ejemplo,

simplifica (Dis X (Neg (Neg X)))                      ==  X
simplifica (Neg (Dis (Neg (Neg X)) F))                ==  Neg X
simplifica (Dis (Neg F) F)                            ==  V
simplifica (Dis (Neg V) (Neg (Dis (Neg X) F)))        ==  X
simplifica (Dis (Neg V) (Neg (Dis (Neg (Neg X)) F)))  ==  Neg X

Comprobar con QuickCheck que para cualquier fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Para la comprobación, de define el generador

instance Arbitrary Expr where
  arbitrary = sized expr
    where expr n | n <= 0    = atom
                 | otherwise = oneof [ atom
                                     , liftM Neg subexpr
                                     , liftM2 Dis subexpr subexpr ]
            where atom    = oneof [elements [X,V,F]]
                  subexpr = expr (n `div` 2)

que usa las funciones liftM y liftM2 de la librería Control.Monad que hay que importar al principio.

Cálculo de pi mediante la serie de Nilakantha

José A. Alonso

Misceláneas

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es

           4       4       4       4
pi = 3 + ----- - ----- + ----- - ------ + ···
         2x3x4   4x5x6   6x7x8   8x9x10

Definir las funciones

aproximacionPi :: Int -> Double
tabla          :: FilePath -> [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

aproximacionPi 0        ==  3.0
aproximacionPi 1        ==  3.1666666666666665
aproximacionPi 2        ==  3.1333333333333333
aproximacionPi 3        ==  3.145238095238095
aproximacionPi 4        ==  3.1396825396825396
aproximacionPi 5        ==  3.1427128427128426
aproximacionPi 10       ==  3.1414067184965018
aproximacionPi 100      ==  3.1415924109719824
aproximacionPi 1000     ==  3.141592653340544
aproximacionPi 10000    ==  3.141592653589538
aproximacionPi 100000   ==  3.1415926535897865
aproximacionPi 1000000  ==  3.141592653589787
pi                      ==  3.141592653589793

(tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

tabla "AproximacionesPi.txt" [0,10..100]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|   10 | 3.141406718497 | 0.000185935093 |
|   20 | 3.141565734659 | 0.000026918931 |
|   30 | 3.141584272675 | 0.000008380915 |
|   40 | 3.141589028941 | 0.000003624649 |
|   50 | 3.141590769850 | 0.000001883740 |
|   60 | 3.141591552546 | 0.000001101044 |
|   70 | 3.141591955265 | 0.000000698325 |
|   80 | 3.141592183260 | 0.000000470330 |
|   90 | 3.141592321886 | 0.000000331704 |
|  100 | 3.141592410972 | 0.000000242618 |
+------+----------------+----------------+

al evaluar la expresión

tabla "AproximacionesPi.txt" [0,500..5000]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|  500 | 3.141592651602 | 0.000000001988 |
| 1000 | 3.141592653341 | 0.000000000249 |
| 1500 | 3.141592653516 | 0.000000000074 |
| 2000 | 3.141592653559 | 0.000000000031 |
| 2500 | 3.141592653574 | 0.000000000016 |
| 3000 | 3.141592653581 | 0.000000000009 |
| 3500 | 3.141592653584 | 0.000000000006 |
| 4000 | 3.141592653586 | 0.000000000004 |
| 4500 | 3.141592653587 | 0.000000000003 |
| 5000 | 3.141592653588 | 0.000000000002 |
+------+----------------+----------------+

Sucesión de sumas de dos números abundantes

José A. Alonso

Misceláneas

Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.

Definir la sucesión

sumasDeDosAbundantes :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,

take 10 sumasDeDosAbundantes  ==  [24,30,32,36,38,40,42,44,48,50]

Particiones de enteros positivos

José A. Alonso

Misceláneas

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

particiones :: Int -> [[Int]]

tal que (particiones n) es la lista de las particiones del número n. Por ejemplo,

particiones 4  ==  [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
particiones 5  ==  [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
length (particiones 50)  ==  204226

Término ausente en una progresión aritmética

José A. Alonso

Misceláneas

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.

Aritmética lunar.

José A. Alonso

Misceláneas

En la aritmética lunar la suma y el producto se hace como en la terrícola salvo que sus tablas de sumar y de multiplicar son distintas. La suma lunar de dos dígitos es su máximo (por ejemplo, 1 + 3 = 3 y 7 + 4 = 7) y el producto lunar de dos dígitos es su mínimo (por ejemplo, 1 x 3 = 1 y 7 x 4 = 4). Por tanto,

  3 5 7        3 5 7
+   6 4      x   6 4
-------      -------
  3 6 7        3 4 4
             3 5 6
             -------
             3 5 6 4

Definir las funciones

suma     :: Integer -> Integer -> Integer
producto :: Integer -> Integer -> Integer

tales que

(suma x y) es la suma lunar de x e y. Por ejemplo,

suma 357 64  ==  367
suma 64 357  ==  367
suma 1 3     ==  3
suma 7 4     ==  7

(producto x y) es el producto lunar de x e y. Por ejemplo,

producto 357 64  ==  3564
producto 64 357  ==  3564
producto 1 3     ==  1
producto 7 4     ==  4

Comprobar con QuickCheck que la suma y el producto lunar son conmutativos.

Exterior de árboles

José A. Alonso

Misceláneas

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

data Arbol = H Int
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

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

se representan por

ejArbol1, ejArbol2, ejArbol3 :: Arbol
ejArbol1 = N 3
             (N 2
                (N 5 (H 1) (H 4))
                (H 7))
             (N 8 (H 6) (H 9))
ejArbol2 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (N 6 (H 1) (H 4))
                  (H 9))
ejArbol3 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (H 6)
                  (N 9 (H 1) (H 4)))

Definir la función

exterior :: Arbol -> [Int]

tal que (exterior a) es la lista de los elementos exteriores del árbol a. Por ejemplo,

exterior ejArbol1  ==  [3,2,5,1,4,7,6,9,8]
exterior ejArbol2  ==  [3,2,5,7,1,4,9,8]
exterior ejArbol3  ==  [3,2,5,7,6,1,4,9,8]

El orden de los elementos es desde la raíz hasta el extremo inferior izquierdo desde él hasta el inferior derecho y desde él hasta la raíz.

Medias de dígitos de pi

José A. Alonso

Misceláneas

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

mediasDigitosDePi        :: IO [Double]
graficaMediasDigitosDePi :: Int -> IO ()

tales que

mediasDigitosDePi es la sucesión cuyo n-ésimo elemento es la media de los n primeros dígitos de pi. Por ejemplo,

λ> xs <- mediasDigitosDePi
λ> take 5 xs
[1.0,2.5,2.0,2.75,4.0]
λ> take 10 xs
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
λ> take 10 <$> mediasDigitosDePi
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]

(graficaMediasDigitosDePi n) dibuja la gráfica de los n primeros términos de mediasDigitosDePi. Por ejemplo,
(graficaMediasDigitosDePi 20) dibuja
(graficaMediasDigitosDePi 200) dibuja
(graficaMediasDigitosDePi 2000) dibuja

Límites de sucesiones

José A. Alonso

Misceláneas

El límite de una sucesión, con una aproximación a y una amplitud n, es 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.

Definir la función

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

tal que (limite xs a n) es el límite de xs xon aproximación a y amplitud n. 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

Dígitos en las posiciones pares de cuadrados

José A. Alonso

Misceláneas

Definir las funciones

digitosPosParesCuadrado    :: Integer -> ([Integer],Int)
invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]

tales que

(digitosPosParesCuadrado n) es el par formados por los dígitos de n² en la posiciones pares y por el número de dígitos de n². Por ejemplo,

digitosPosParesCuadrado 8     ==  ([6],2)
digitosPosParesCuadrado 14    ==  ([1,6],3)
digitosPosParesCuadrado 36    ==  ([1,9],4)
digitosPosParesCuadrado 116   ==  ([1,4,6],5)
digitosPosParesCuadrado 2019  ==  ([4,7,3,1],7)

(invDigitosPosParesCuadrado (xs,k)) es la lista de los números n tales que xs es la lista de los dígitos de n² en la posiciones pares y k es el número de dígitos de n². Por ejemplo,

invDigitosPosParesCuadrado ([6],2)             ==  [8]
invDigitosPosParesCuadrado ([1,6],3)           ==  [14]
invDigitosPosParesCuadrado ([1,9],4)           ==  [36]
invDigitosPosParesCuadrado ([1,4,6],5)         ==  [116,136]
invDigitosPosParesCuadrado ([4,7,3,1],7)       ==  [2019,2139,2231]
invDigitosPosParesCuadrado ([1,2],3)           ==  []
invDigitosPosParesCuadrado ([1,2],4)           ==  [32,35,39]
invDigitosPosParesCuadrado ([1,2,3,4,5,6],11)  ==  [115256,127334,135254]

Comprobar con QuickCheck que para todo entero positivo n se verifica que para todo entero positivo m, m pertenece a (invDigitosPosParesCuadrado (digitosPosParesCuadrado n)) si, y sólo si, (digitosPosParesCuadrado m) es igual a (digitosPosParesCuadrado n)

Triángulo de Pascal binario

José A. Alonso

Misceláneas

Los triángulos binarios de Pascal se formas a partir de una lista de ceros y unos usando las reglas del triángulo de Pascal, donde cada uno de los números es suma módulo dos de los dos situados en diagonal por encima suyo. Por ejemplo, los triángulos binarios de Pascal correspondientes a [1,0,1,1,1] y [1,0,1,1,0] son

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

Sus finales, desde el extremo inferior al extremos superior derecho, son [0,1,0,0,1] y [1,0,1,1,0], respectivamente.

Una lista es Pascal capicúa si es igual a los finales de su triángulo binario de Pascal. Por ejemplo, [1,0,1,1,0] es Pascal capicúa.

Definir las funciones

trianguloPascalBinario :: [Int] -> [[Int]]
pascalCapicuas         :: Int -> [[Int]]
nPascalCapicuas        :: Int -> Integer

tales que

(trianguloPascalBinario xs) es el triágulo binario de Pascal correspondiente a la lista xs. Por ejemplo,

λ> trianguloPascalBinario [1,0,1,1,1]
[[1,0,1,1,1],[1,1,0,0],[0,1,0],[1,1],[0]]
λ> trianguloPascalBinario [1,0,1,1,0]
[[1,0,1,1,0],[1,1,0,1],[0,1,1],[1,0],[1]]

(pascalCapicuas n) es la lista de listas de Pascal capicúas de n elementos. Por ejemplo,

λ> pascalCapicuas 2
[[0,0],[1,0]]
λ> pascalCapicuas 3
[[0,0,0],[0,1,0],[1,0,0],[1,1,0]]
λ> pascalCapicuas 4
[[0,0,0,0],[0,1,1,0],[1,0,0,0],[1,1,1,0]]

(nPascalCapicuas n) es el número de listas de Pascal capicúas de n elementos. Por ejemplo,

λ> nPascalCapicuas 2
2
λ> nPascalCapicuas 3
4
λ> nPascalCapicuas 4
4
λ> nPascalCapicuas 400
1606938044258990275541962092341162602522202993782792835301376
λ> length (show (nPascalCapicuas (10^5)))
15052
λ> length (show (nPascalCapicuas (10^6)))
150515
λ> length (show (nPascalCapicuas (10^7)))
1505150

Impares en filas del triángulo de Pascal

José A. Alonso

Misceláneas

El triángulo de Pascal es un triángulo de números

       1
      1 1
     1 2 1
   1  3 3  1
  1 4  6  4 1
 1 5 10 10 5 1
...............

construido de la siguiente forma

la primera fila está formada por el número 1;
las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

Definir las funciones

imparesPascal          :: [[Integer]]
nImparesPascal         :: [Int]
grafica_nImparesPascal :: Int -> IO ()

tales que

imparesPascal es la lista de los elementos impares en cada una de las filas del triángulo de Pascal. Por ejemplo,

λ> take 8 imparesPascal
[[1],[1,1],[1,1],[1,3,3,1],[1,1],[1,5,5,1],[1,15,15,1],[1,7,21,35,35,21,7,1]]

nImparesPascal es la lista del número de elementos impares en cada una de las filas del triángulo de Pascal. Por ejemplo,

λ> take 32 nImparesPascal
[1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32]
λ> maximum (take (10^6) nImparesPascal3)
524288

(grafica_nImparesPascal n) dibuja la gráfica de los n primeros términos de nImparesPascal. Por ejemplo, (grafica_nImparesPascal 50) dibuja

Impares en filas del triángulo de Pascal

y (grafica_nImparesPascal 100) dibuja

Impares en filas del triángulo de Pascal

Comprobar con QuickCheck que todos los elementos de nImparesPascal son potencias de dos.

Árboles con n elementos

José A. Alonso

Misceláneas

Los árboles binarios se pueden representar con

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

Definir las funciones

arboles  :: Integer -> a -> [Arbol a]
nArboles :: [Integer]

tales que

(arboles n x) es la lista de todos los árboles binarios con n elementos iguales a x. Por ejemplo,

λ> arboles 0 7
[]
λ> arboles 1 7
[H 7]
λ> arboles 2 7
[]
λ> arboles 3 7
[N 7 (H 7) (H 7)]
λ> arboles 4 7
[]
λ> arboles 5 7
[N 7 (H 7) (N 7 (H 7) (H 7)),N 7 (N 7 (H 7) (H 7)) (H 7)]
λ> arboles 6 7
[]
λ> arboles 7 7
[N 7 (H 7) (N 7 (H 7) (N 7 (H 7) (H 7))),
 N 7 (H 7) (N 7 (N 7 (H 7) (H 7)) (H 7)),
 N 7 (N 7 (H 7) (H 7)) (N 7 (H 7) (H 7)),
 N 7 (N 7 (H 7) (N 7 (H 7) (H 7))) (H 7),
 N 7 (N 7 (N 7 (H 7) (H 7)) (H 7)) (H 7)]

nArboles es la sucesión de los números de árboles con k elementos iguales a 7, con k ∈ {1,3,5,...}. Por ejemplo,

λ> take 14 nArboles
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900]
λ> nArboles !! 100
896519947090131496687170070074100632420837521538745909320
λ> length (show (nArboles !! 1000))
598

Números con dígitos 1 y 2

José A. Alonso

Misceláneas

Definir las funciones

numerosCon1y2               :: Int -> [Int]
restosNumerosCon1y2         :: Int -> [Int]
grafica_restosNumerosCon1y2 :: Int -> IO ()

tales que

(numerosCon1y2 n) es la lista ordenada de números de n dígitos que se pueden formar con los dígitos 1 y 2. Por ejemplo,

numerosCon1y2 2  ==  [11,12,21,22]
numerosCon1y2 3  ==  [111,112,121,122,211,212,221,222]

(restosNumerosCon1y2 n) es la lista de los restos de dividir los elementos de (restosNumerosCon1y2 n) entre 2^n. Por ejemplo,

restosNumerosCon1y2 2 == [3,0,1,2]
restosNumerosCon1y2 3 == [7,0,1,2,3,4,5,6]
restosNumerosCon1y2 4 == [7,8,1,2,11,12,5,6,15,0,9,10,3,4,13,14]

(graficaRestosNumerosCon1y2 n) dibuja la gráfica de los restos de dividir los elementos de (restosNumerosCon1y2 n) entre 2^n. Por ejemplo, (graficaRestosNumerosCon1y2 3) dibuja

Números con dígitos 1 y 2

(graficaRestosNumerosCon1y2 4) dibuja

Números con dígitos 1 y 2

y (graficaRestosNumerosCon1y2 5) dibuja

Números con dígitos 1 y 2

Nota: En la definición usar la función plotListStyle y como segundo argumento usar

(defaultStyle {plotType = LinesPoints,
               lineSpec = CustomStyle [PointType 7]})

Comprobar con QuickCheck que todos los elementos de (restosNumerosCon1y2 n) son distintos.

Recorrido de árboles en espiral

José A. Alonso

Misceláneas

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

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

Por ejemplo, los árboles

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

se representan por

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

Definir la función

espiral :: Arbol a -> [a]

tal que (espiral x) es la lista de los nodos del árbol x recorridos en espiral; es decir, la raíz de x, los nodos del primer nivel de izquierda a derecha, los nodos del segundo nivel de derecha a izquierda y así sucesivamente. Por ejemplo,

espiral ej1  ==  [1,2,3,7,6,5,4]
espiral ej2  ==  [1,8,3,6,5,4]
espiral ej3  ==  [1,8,3,7,6,5,4]

Números primos en pi

José A. Alonso

Misceláneas

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

nOcurrenciasPrimosEnPi :: Int -> Int -> IO [Int]
graficaPrimosEnPi      :: Int -> Int -> IO ()

tales que

(nOcurrenciasPrimosEnPi n k) es la lista de longitud n cuyo i-ésimo elemento es el número de ocurrencias del i-ésimo número primo en los k primeros decimales del número pi. Por ejemplo,

nOcurrenciasPrimosEnPi 4 20 == [2,3,3,1]

ya que los 20 primeros decimales de pi son 14159265358979323846 y en ellos ocurre el 2 dos veces, el 3 ocurre 3 veces, el 5 ocurre 3 veces y el 7 ocurre 1 vez. Otros ejemplos son

λ> nOcurrenciasPrimosEnPi 10 100
[12,11,8,8,1,0,1,1,2,0]
λ> nOcurrenciasPrimosEnPi 10 (10^4)
[1021,974,1046,970,99,102,90,113,99,95]
λ> nOcurrenciasPrimosEnPi 10 (10^6)
[100026,100229,100359,99800,10064,10012,9944,10148,9951,9912]

(graficaPrimosEnPi n k) dibuja la gráfica del número de ocurrencias de los n primeros números primos en los k primeros dígitos de pi. Por ejemplo, (graficaPrimosEnPi 10 (10^4)) dibuja

(graficaPrimosEnPi 10 (10^6)) dibuja

Números primos en pi

y (graficaPrimosEnPi 50 (10^5)) dibuja

Números primos en pi

Sucesión triangular

José A. Alonso

Misceláneas

La sucesión triangular es la obtenida concatenando las listas [1], [1,2], [1,2,3], [1,2,3,4], .... Sus primeros términos son 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ...

Definir las funciones

sucTriangular        :: [Integer]
terminoSucTriangular :: Int -> Integer
graficaSucTriangular :: Int -> IO ()

tales que

sucTriangular es la lista de los términos de la sucesión triangular. Por ejemplo,

λ> take 30 sucTriangular
[1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,3,4,5,6,1,2,3,4,5,6,7,1,2]

(terminoSucTriangular n) es el término n-ésimo de la sucesión triangular. Por ejemplo,

terminoSucTriangular 5       ==  3
terminoSucTriangular 10      ==  1
terminoSucTriangular 20      ==  6
terminoSucTriangular 100     ==  10
terminoSucTriangular 1001    ==  12
terminoSucTriangular (10^5)  ==  320

(graficaSucTriangular n) dibuja la gráfica de los n primeros términos de la sucesión triangular. Por ejemplo, (graficaSucTriangular 300) dibuja

" Sucesión triangular

Soluciones de de un sistema

José A. Alonso

Misceláneas

Definir la función

soluciones :: [(Integer,Integer,Integer)]

tal que sus elementos son las ternas (x,y,k) de soluciones del sistema \[x² = y³ = k\] Por ejemplo,

λ> take 6 soluciones
[(0,0,0),(-1,1,1),(1,1,1),(-8,4,64),(8,4,64),(-27,9,729)]
λ> soluciones !! (6*10^5+6)
(27000810008100027,90001800009,729043741093514580109350437400729)

Intersección de listas infinitas crecientes

José A. Alonso

Misceláneas

Definir la función

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

tal que (interseccion xss) es la intersección de la lista no vacía de listas infinitas crecientes xss; es decir, la lista de los elementos que pertenecen a todas las listas de xss. Por ejemplo,

λ> take 10 (interseccion [[2,4..],[3,6..],[5,10..]])
[30,60,90,120,150,180,210,240,270,300]
λ> take 10 (interseccion [[2,5..],[3,5..],[5,7..]])
[5,11,17,23,29,35,41,47,53,59]

Mínimo número de operaciones para transformar un número en otro

José A. Alonso

Misceláneas

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

multiplicar por dos
restar uno.

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

4 ------> 8 ------> 7
   (*2)      (-1)

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

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

Definir las siguientes funciones

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

tales que

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

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

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

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

Posiciones del 2019 en el número pi

José A. Alonso

Misceláneas

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

posiciones :: String -> Int -> IO [Int]

tal que (posicion cs k) es es la lista de las posiciones iniciales de cs en la sucesión formada por los k primeros dígitos decimales del número pi. Por ejemplo,

λ> posiciones "141" 1000
[0,294]
λ> posiciones "4159" 10000
[1,5797,6955,9599]

Calcular la primera posición de 2019 en los decimales de pi y el número de veces que aparece 2019 en en el primer millón de decimales de pi.

Números altamente compuestos

José A. Alonso

Misceláneas

Un número altamente compuesto es un entero positivo con más divisores que cualquier entero positivo más pequeño. Por ejemplo,

4 es un número altamente compuesto porque es el menor con 3 divisores,
5 no es altamente compuesto porque tiene menos divisores que 4 y
6 es un número altamente compuesto porque es el menor con 4 divisores,

Los primeros números altamente compuestos son

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, ...

Definir las funciones

esAltamenteCompuesto       :: Int -> Bool
altamenteCompuestos        :: [Int]
graficaAltamenteCompuestos :: Int -> IO ()

tales que

(esAltamanteCompuesto x) se verifica si x es altamente compuesto. Por ejemplo,

esAltamenteCompuesto 4      ==  True
esAltamenteCompuesto 5      ==  False
esAltamenteCompuesto 6      ==  True
esAltamenteCompuesto 1260   ==  True
esAltamenteCompuesto 2520   ==  True
esAltamenteCompuesto 27720  ==  True

altamente compuestos es la sucesión de los números altamente compuestos. Por ejemplo,

λ> take 20 altamenteCompuestos
[1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560]

(graficaAltamenteCompuestos n) dibuja la gráfica de los n primeros números altamente compuestos. Por ejemplo, (graficaAltamenteCompuestos 25) dibuja

Números altamente compuestos

Representación de conjuntos mediante intervalos

José A. Alonso

Misceláneas

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

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

tal que (intervalos xs) es lista ordenada de intervalos que representa al conjunto xs. Por ejemplo,

λ> intervalos [2,7,4,3,9,6]
[(2,4),(6,7),(9,9)]
λ> intervalos [180,141,174,143,142,175]
[(141,143),(174,175),(180,180)]

Ofertas 3 por 2

José A. Alonso

Misceláneas

En una tienda tiene la "oferta 3 por 2" de forma que cada cliente que elige 3 artículos obtiene el más barato de forma gratuita. Por ejemplo, si los precios de los artículos elegidos por un cliente son 10, 2, 4, 5 euros pagará 19 euros si agrupa los artículos en (10,2,4) y (5) o pagará 17 si lo agupa en (5,10,4) y (2).

Definir la función

minimoConOferta :: [Int] -> Int

tal que (minimoConOferta xs) es lo mínimo que pagará el cliente si los precios de la compra son xs; es decir, lo que pagará agrupando los artículos de forma óptima para aplicar la oferta 3 por 2. Por ejemplo,

minimoConOferta [10,2,4,5]     ==  17
minimoConOferta [3,2,3,2]      ==  8
minimoConOferta [6,4,5,5,5,5]  ==  21

Mayor prefijo con suma acotada

José A. Alonso

Misceláneas

Definir la función

mayorPrefijoAcotado :: [Int] -> Int -> [Int]

tal que (mayorPrefijoAcotado xs y) es el mayor prefijo de la lista de los números enteros positivos xs cuya suma es menor o igual que y. Por ejemplo,

mayorPrefijoAcotado [45,30,55,20,80,20] 75   ==  [45,30]
mayorPrefijoAcotado [45,30,55,20,80,20] 140  ==  [45,30,55]
mayorPrefijoAcotado [45,30,55,20,80,20] 180  ==  [45,30,55,20]
length (mayorPrefijoAcotado (repeat 1) (8*10^6)) == 8000000

Subárboles monovalorados

José A. Alonso

Misceláneas

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

data Arbol = H Int
           | N Int Arbol Arbol
           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 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 la función

monovalorados :: Arbol -> [Arbol]

tal que (monovalorados a) es la lista de los subárboles monovalorados de a. Por ejemplo,

λ> monovalorados (N 5 (H 5) (H 5))
[N 5 (H 5) (H 5),H 5,H 5]
λ> monovalorados (N 5 (H 5) (H 6))
[H 5,H 6]
λ> monovalorados (N 9 (H 9) (N 9 (H 9) (H 9)))
[N 9 (H 9) (N 9 (H 9) (H 9)),H 9,N 9 (H 9) (H 9),H 9,H 9]
λ> monovalorados (N 9 (H 9) (N 7 (H 9) (H 9)))
[H 9,H 9,H 9]
λ> monovalorados (N 9 (H 9) (N 9 (H 7) (H 9)))
[H 9,H 7,H 9]

Numeración de las ternas de números naturales

José A. Alonso

Misceláneas

Las ternas de números naturales se pueden ordenar como sigue

(0,0,0),
(0,0,1),(0,1,0),(1,0,0),
(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),
(0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...
...

Definir la función

posicion :: (Int,Int,Int) -> Int

tal que (posicion (x,y,z)) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,

posicion (0,1,0)  ==  2
posicion (0,0,2)  ==  4
posicion (0,1,1)  ==  5

Comprobar con QuickCheck que

la posición de (x,0,0) es x(x²+6x+11)/6
la posición de (0,y,0) es y(y²+3y+ 8)/6
la posición de (0,0,z) es z(z²+3z+ 2)/6
la posición de (x,x,x) es x(9x²+14x+7)/2

Mínimo producto escalar

José A. Alonso

Misceláneas

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

Cadena descendiente de subnúmeros

José A. Alonso

Misceláneas

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.

El 2019 es un número de la suerte

José A. Alonso

Misceláneas

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

El 2019 es semiprimo

José A. Alonso

Misceláneas

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

El 2019 es malvado

José A. Alonso

Misceláneas

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

El 2019 es apocalíptico.

José A. Alonso

Misceláneas

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

El teorema de Navidad de Fermat

José A. Alonso

Misceláneas

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.

Árbol de subconjuntos

José A. Alonso

Misceláneas

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).

Reconocimiento de conmutatividad

José A. Alonso

Misceláneas

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

Reconocimiento de particiones

José A. Alonso

Misceláneas

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

Tablas de operaciones binarias

José A. Alonso

Misceláneas

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.

Número de divisores compuestos

José A. Alonso

Misceláneas

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

Divisores compuestos

José A. Alonso

Misceláneas

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

Árbol binario de divisores

José A. Alonso

Misceláneas

Divisores propios maximales

José A. Alonso

Misceláneas

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

Grado exponencial

José A. Alonso

Misceláneas

Números primos de Pierpont

José A. Alonso

Misceláneas

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

Intercambio de la primera y última columna de una matriz

José A. Alonso

Misceláneas

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

Superación de límites

José A. Alonso

Misceláneas

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)

Expresiones aritméticas generales

José A. Alonso

Misceláneas

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

Entre dos conjuntos

José A. Alonso

Misceláneas

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

Árbol de computación de Fibonacci

José A. Alonso

Misceláneas

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

Menor contenedor de primos

José A. Alonso

Misceláneas

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

Aproximación entre pi y e

José A. Alonso

Misceláneas

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:

Aproximación entre pi y e

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

Elemento del árbol binario completo según su posición

José A. Alonso

Misceláneas

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

Posiciones en árboles binarios completos

José A. Alonso

Misceláneas

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

Posiciones en árboles binarios

José A. Alonso

Misceláneas

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

Numeración de los árboles binarios completos

José A. Alonso

Misceláneas

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

Raíz cúbica entera

José A. Alonso

Misceláneas

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

Números colinas

José A. Alonso

Misceláneas

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

Elemento solitario

José A. Alonso

Misceláneas

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

Suma de inversos de potencias de cuatro

José A. Alonso

Misceláneas

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

Suma de inversos de potencias de cuatro

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

Números primos sumas de dos primos

José A. Alonso

Misceláneas

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

Ceros finales del factorial

José A. Alonso

Misceláneas

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

Relación definida por una partición

José A. Alonso

Misceláneas

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

Número de parejas

José A. Alonso

Misceláneas

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.

Números autodescriptivos

José A. Alonso

Misceláneas

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.