Ir al contenido principal

Precisión de aproximaciones de pi

Misceláneas

La precisión de una aproximación x de pi es el número de dígitos comunes entre el inicio de x y de pi. Por ejemplo, puesto que 355/113 es 3.1415929203539825 y pi es 3.141592653589793, la precisión de 355/113 es 7.

Definir las siguientes funciones

mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
precisionPi       :: Double -> Int
precisionPiCR     :: CReal -> Int

tales que

  • (mayorPrefijoComun xs ys) es el mayor prefijo común de xs e ys. Por ejemplo,
mayorPrefijoComun []      [2,3,4,5]  ==  []
mayorPrefijoComun [2,3,5] []         ==  []
mayorPrefijoComun [2,3,5] [2,3,4,5]  ==  [2,3]
mayorPrefijoComun [2,3,5] [2,5,3,4]  ==  [2]
mayorPrefijoComun [2,3,5] [5,2,3,4]  ==  []
  • (precisionPi x) es la precisión de la aproximación de pi x. Por ejemplo,
precisionPi (25/8)              ==  2
precisionPi (22/7)              ==  3
precisionPi (sqrt 2 + sqrt 3)   ==  3
precisionPi (377/120)           ==  4
precisionPi (31**(1/3))         ==  4
precisionPi (7^7/4^9)           ==  5
precisionPi (355/113)           ==  7
precisionPi ((2143/22)**(1/4))  ==  9
  • (precisionPiCR x) es la precisión de la aproximación de pi x, como números reales. Por ejemplo,
precisionPiCR (log (640320^3+744)/(sqrt 163))                        == 31
precisionPiCR (log (5280^3*(236674+30303*sqrt 61)^3+744)/(sqrt 427)) == 53

Nota: Para la definición precisionPiCR se usa la librería Data.Number.CReal que se instala con

cabal install numbers

Leer más…

Cálculo de pi mediante el método de Newton

Misceláneas

El método de Newton para el cálculo de pi se basa en la relación

Cálculo de pi mediante el método de Newton

y en el desarrollo del arco seno

Cálculo de pi mediante el método de Newton

de donde se obtiene la fórmula

Cálculo de pi mediante el método de Newton

La primeras aproximaciones son

a(0) = 6*(1/2)                               = 3.0
a(1) = 6*(1/2+1/(2*3*2^3))                   = 3.125
a(2) = 6*(1/2+1/(2*3*2^3)+(1*3)/(2*4*5*2^5)) = 3.1390625

Definir las funciones

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

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Newton. Por ejemplo,
aproximacionPi 0   ==  3.0
aproximacionPi 1   ==  3.125
aproximacionPi 2   ==  3.1390625
aproximacionPi 10  ==  3.1415926468755613
aproximacionPi 21  ==  3.141592653589793
pi                 ==  3.141592653589793
  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..30]) dibuja

Cálculo de pi mediante el método de Newton

Leer más…

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

Misceláneas

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

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

y la de Beeler es

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

Definir las funciones

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

tales que

  • (aproximaPiGL n) es la aproximación de pi con los primeros n términos de la fórmula de Gregory-Leibniz. Por ejemplo,
aproximaPiGL 1       ==  4.0
aproximaPiGL 2       ==  2.666666666666667
aproximaPiGL 3       ==  3.466666666666667
aproximaPiGL 10      ==  3.0418396189294032
aproximaPiGL 100     ==  3.1315929035585537
aproximaPiGL 1000    ==  3.140592653839794
aproximaPiGL 10000   ==  3.1414926535900345
aproximaPiGL 100000  ==  3.1415826535897198
  • (aproximaPiBeeler n) es la aproximación de pi con los primeros n términos de la fórmula de Beeler. Por ejemplo,
aproximaPiBeeler 1   ==  2.0
aproximaPiBeeler 2   ==  2.6666666666666665
aproximaPiBeeler 3   ==  2.933333333333333
aproximaPiBeeler 10  ==  3.140578169680337
aproximaPiBeeler 60  ==  3.141592653589793
pi                   ==  3.141592653589793
  • (graficas xs) dibuja la gráfica de las k-ésimas aproximaciones de pi, donde k toma los valores de la lista xs, con las fórmulas de Gregory-Leibniz y de Beeler. Por ejemplo, (graficas [1..50]) dibuja

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

donde la línea morada corresponde a la aproximación de Gregory-Leibniz y la verde a la de Beeler.

Leer más…

Cálculo de pi mediante la fracción continua de Lange

Misceláneas

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

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

La primeras aproximaciones son

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

Definir las funciones

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

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,
aproximacionPi 1     ==  4.0
aproximacionPi 2     ==  3.066666666666667
aproximacionPi 3     ==  3.158974358974359
aproximacionPi 10    ==  3.141287132741557
aproximacionPi 100   ==  3.141592398533554
aproximacionPi 1000  ==  3.1415926533392926
  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja

Cálculo de pi mediante la fracción continua de Lange

(grafica [10..100]) dibuja

Cálculo de pi mediante la fracción continua de Lange

y (grafica [100..200]) dibuja

Cálculo de pi mediante la fracción continua de Lange

Leer más…

Cálculo de pi mediante la variante de Euler de la serie armónica

Misceláneas

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

El desarrollo es el siguiente

Cálculo de pi mediante la variante de Euler de la serie armónica

y se obtiene a partir de la serie armónica

Cálculo de pi mediante la variante de Euler de la serie armónica

modificando sólo el signo de algunos términos según el siguiente criterio:

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

Por ejemplo,

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

Definir las funciones

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

tales que

  • (aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.
aproximacionPi 1        ==  1.0
aproximacionPi 10       ==  2.3289682539682537
aproximacionPi 100      ==  2.934318000847734
aproximacionPi 1000     ==  3.0603246224585128
aproximacionPi 10000    ==  3.1105295744825403
aproximacionPi 100000   ==  3.134308801935256
aproximacionPi 1000000  ==  3.1395057903490806
  • (grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Cálculo de pi mediante la variante de Euler de la serie armónica

Leer más…

Regresión lineal

Misceláneas

Dadas dos listas de valores

xs = [x(1), x(2), ..., x(n)]
ys = [y(1), y(2), ..., y(n)]

la ecuación de la recta de regresión de ys sobre xs es y = a+bx, donde \[b = \frac{n \sum x_i y_i - \sum x_i \sum y_i}{n \sum x_i^2 - \left(\sum x_i\right)^2}\] \[a = \frac{\sum y_i - b \sum x_i}{n}\]

Definir la función

regresionLineal :: [Double] -> [Double] -> (Double,Double)

tal que (regresionLineal xs ys) es el par (a,b) de los coeficientes de la recta de regresión de ys sobre xs. Por ejemplo, para los valores

ejX, ejY :: [Double]
ejX = [5,  7, 10, 12, 16, 20, 23, 27, 19, 14]
ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

se tiene

λ> regresionLineal ejX ejY
(5.195045748716805,0.9218924347243919)

Para comprobar la definición se define el procedimiento

grafica :: [Double] -> [Double] -> IO ()
grafica xs ys =
    plotPathsStyle
      [YRange (0,10+mY)]
      [(defaultStyle {plotType = Points,
                      lineSpec = CustomStyle [LineTitle "Datos",
                                              PointType 2,
                                              PointSize 2.5]},
                     zip xs ys),
       (defaultStyle {plotType = Lines,
                      lineSpec = CustomStyle [LineTitle "Ajuste",
                                              LineWidth 2]},
                     [(x,a+b*x) | x <- [0..mX]])]
    where (a,b) = regresionLineal xs ys
          mX    = maximum xs
          mY    = maximum ys

tal que (grafica xs ys) pintea los puntos correspondientes a las listas de valores xs e ys y su recta de regresión. Por ejemplo, con (grafica ejX ejY) se obtiene el siguiente dibujo

Regresión lineal

Leer más…

Sucesión de trazas de dígitos de pi

Misceláneas

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

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Las matrices de orden 1x1, 2x2, ..., 5x5 formadas por los primeros dígitos de pi son

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

y sus trazas (es decir, sumas de los elementos de la diagonal principal) son 3, 4, 13, 20 y 25, respectivamente.

Definir la función

trazas :: Int -> IO [Int]

tal que (trazas n) es la lista de las trazas de las matrices de orden 1x1, 2x2, 3x3, ..., nxn formadas por los primeros dígitos de pi. Por ejemplo,

λ> trazas 20
[3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]
λ> ts <- trazas 1000
λ> maximum ts
4644
λ> maximum <$> trazas 1000
4644

Leer más…

Distribución de dígitos de pi

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, con la función digitosPi definida por

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

Por ejemplo,

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

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

Usando digitosPi, definir las siguientes funciones

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

tales que

  • (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,
λ> distribucionDigitosPi 10
[0,2,1,2,1,2,1,0,0,1]
λ> distribucionDigitosPi 100
[8,8,12,12,10,8,9,8,12,13]
λ> distribucionDigitosPi 1000
[93,116,103,103,93,97,94,95,101,105]
λ> distribucionDigitosPi 5000
[466,531,496,460,508,525,513,488,492,521]
  • (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,
λ> frecuenciaDigitosPi 10
[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
λ> frecuenciaDigitosPi 100
[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
λ> frecuenciaDigitosPi 1000
[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
λ> frecuenciaDigitosPi 5000
[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Leer más…

Búsqueda en los dígitos de pi

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

posicion :: String -> IO (Maybe Int)

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

λ> posicion "15"
Just 3
λ> posicion "2017"
Just 8897
λ> posicion "022017"
Just 382052
λ> posicion "14022017"
Nothing
λ> posicion "999999"
Just 762
λ> posicion "458151"
Just 999995

Leer más…

Cálculo de pi usando la fórmula de Vieta

Misceláneas

La fórmula de Vieta para el cálculo de pi es la siguiente \[ \pi = 2 \times \frac{2}{\sqrt{2}} \times \frac{2}{\sqrt{2 + \sqrt{2}}} \times \frac{2}{\sqrt{2 + \sqrt{2 + \sqrt{2}}}} \times \frac{2}{\sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2}}}}} \times \cdots \]

Definir las funciones

aproximacionPi :: Int -> Double
errorPi :: Double -> Int

tales que

  • (aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo,
aproximacionPi  5  ==  3.140331156954753
aproximacionPi 10  ==  3.1415914215112
aproximacionPi 15  ==  3.141592652386592
aproximacionPi 20  ==  3.1415926535886207
aproximacionPi 25  ==  3.141592653589795
  • (errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo,
errorPi 0.1        ==  2
errorPi 0.01       ==  4
errorPi 0.001      ==  6
errorPi 0.0001     ==  7
errorPi 1e-4       ==  7
errorPi 1e-14      ==  24
pi                 ==  3.141592653589793
aproximacionPi 24  ==  3.1415926535897913

Leer más…

Cálculo de pi usando el producto de Wallis

Misceláneas

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que: \[ \frac{\pi}{2} = \frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdot \frac{8}{7} \cdot \frac{8}{9} \cdots \]

Definir las funciones

factoresWallis  :: [Rational]
productosWallis :: [Rational]
aproximacionPi  :: Int -> Double
errorPi         :: Double -> Int

tales que + factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

λ> take 10 factoresWallis
[2 % 1,2 % 3,4 % 3,4 % 5,6 % 5,6 % 7,8 % 7,8 % 9,10 % 9,10 % 11]
  • productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,
λ> take 7 productosWallis
[2 % 1,4 % 3,16 % 9,64 % 45,128 % 75,256 % 175,2048 % 1225]
  • (aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,
aproximacionPi 20     ==  3.2137849402931895
aproximacionPi 200    ==  3.1493784731686008
aproximacionPi 2000   ==  3.142377365093878
aproximacionPi 20000  ==  3.141671186534396
  • (errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,
errorPi 0.1     ==  14
errorPi 0.01    ==  155
errorPi 0.001   ==  1569
errorPi 0.0001  ==  15707

Leer más…

Caminos en un árbol binario con suma dada

Misceláneas

Los árboles binarios se pueden representar con el de tipo de dato algebraico

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

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

se representan por

ej1, ej2, ej3 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))
ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))
(N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))

Definir las funciones

caminos     :: Arbol -> [[Int]]
caminosSuma :: Arbol -> Int -> [[Int]]

tales que

  • (caminos a) es la lista de los caminos entre dos nodos cualesquiera del árbol a. Por ejemplo,
λ> caminos ej1
[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5],
 [2],[2,1],[2,7],[1],[7],[4],[4,5],[5]]
λ> caminos ej2
[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9],
 [5],[5,6],[6],[8],[8,4],[8,9],[4],[9]]
λ> length (caminos ej3)
33
  • (caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del árbol a cuya suma es k. Por ejemplo,
λ> caminosSuma ej1 3
[[3],[2,1]]
λ> caminosSuma ej3 3
[[3],[-1,4]]
λ> caminosSuma ej3 4
[[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]]
λ> caminosSuma ej3 5
[[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]]
λ> caminosSuma ej3 6
[[1,3,2],[1,3,1,1],[1,-1,4,2],[4,2],[6]]
λ> caminosSuma ej3 7
[]

Leer más…

Máximo común divisor de x e y veces n

Misceláneas

Definir las funciones

repite :: Int -> Integer -> Integer
mcdR   :: Integer -> Int -> Int -> Integer

tales que

  • (repite x n) es el número obtenido repitiendo x veces el número n. Por ejemplo.
repite 3 123  ==  123123123
  • (mcdR n x y) es el máximo común divisor de los números obtenidos repitiendo x veces e y veces el número n. Por ejemplo.
mcdR 123 2 3                     ==  123
mcdR 4 4 6                       ==  44
mcdR 2017 (10^1000) (2+10^1000)  ==  20172017

Leer más…

Caminos desde la raíz en un árbol binario

Misceláneas

Los árboles binarios se pueden representar con el de tipo de dato algebraico

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

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

se representan por

ej1, ej2 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

Definir la función

caminosDesdeRaiz :: Arbol -> [[Int]]

tal que (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la raíz de a hasta cualquiera de sus nodos. Por ejemplo.

λ> caminosDesdeRaiz ej1
[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]
λ> caminosDesdeRaiz ej2
[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]

Leer más…

Prefijo con suma acotada

Misceláneas

Definir la función

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

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

prefijoAcotado 10 [3,2,5,7]  ==  [3,2]
prefijoAcotado 10 [1..]      ==  [1,2,3]

Leer más…

Aplicaciones de operaciones

Misceláneas

Definir la función

aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]

tal que (aplicaciones os xs ys) es la lista obtenida aplicando las operaciones de os a los elementos de xs es ys. Por ejemplo,

λ> aplicaciones [(+),(*)] [1,2] [5,8]
[6,9,7,10,5,8,10,16]
λ> aplicaciones [(+),(*)] [1,2] [5]
[6,7,5,10]
λ> aplicaciones [(<),(>)] ["ab","c"] ["def","c"]
[True,True,True,False,False,False,False,False]
λ> import Data.List
λ> aplicaciones [(++),intersect] ["ab","c"] ["bd","cf"]
["abbd","abcf","cbd","ccf","b","","","c"]

Leer más…

Sucesión de Cantor de números innombrables

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 como se indica a continuación:

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 la sucesión

sucCantor :: [Integer]

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

Leer más…

Particiones de una lista

Misceláneas

Definir la función

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

tal que (particiones xs) es la lista de las particiones de xs en segmentos de elementos consecutivos. Por ejemplo,

λ> particiones [1..3]
[[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]
λ> mapM_ print (particiones "abcd")
["a","b","c","d"]
["a","b","cd"]
["a","bc","d"]
["a","bcd"]
["ab","c","d"]
["ab","cd"]
["abc","d"]
["abcd"]
λ> length (particiones [1..22])
2097152

Comprobar con QuickCheck que la concatenación de cada uno de los elementos de (particiones xs) es igual a xs.

Nota: En la comprobación usar ejemplos pequeños como se indica a continuación

quickCheckWith (stdArgs {maxSize=10}) prop_particiones

Leer más…

Subrayado de un carácter

Misceláneas

Definir el procedimiento

subraya :: String -> Char -> IO ()

tal que (subraya cs c) escribe la cadena cs y debajo otra subrayando las ocurrencias de c. Por ejemplo,

λ> subraya "Salamanca es castellana" 'a'
Salamanca es castellana
 ^ ^ ^  ^     ^     ^ ^
λ> subraya "Salamanca es castellana" 'n'
Salamanca es castellana
      ^              ^
λ> subraya "Salamanca es castellana" ' '
Salamanca es castellana
         ^  ^

Leer más…

Eliminación de triplicados

Misceláneas

Definir la función

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

tal que (sinTriplicados xs) es la lista obtenida dejando en xs sólo las dos primeras ocurrencias de cada uno de sus elementos. Por ejemplo,

sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
sinTriplicados "xxxxx"            ==  "xx"
sinTriplicados "abcabc"           ==  "abcabc"
sinTriplicados "abcdabcaba"       ==  "abcdabc"
sinTriplicados "abacbadcba"       ==  "abacbdc"
sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
sinTriplicados (show (5^4^3))     ==  "54210108624757363989"
sinTriplicados (show (8^8^8))     ==  "60145207536139279488"

Leer más…

Máximo producto de pares en la lista.

Misceláneas

Definir la función

maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir como producto de dos elementos distintos de xs o Nothing, en el caso de que ningún elemento de xs se pueda escribir como producto de dos elementos distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
maximoProducto [2,4]                    ==  Nothing
maximoProducto [2, 5, 7, 8]             ==  Nothing
maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Leer más…

Suma minimal de productos de pares de elementos consecutivos

Misceláneas

Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:

  • 10, por ejemplo con [1,4,2,3] ya que 1x4+2x3 = 10
  • 11, por ejemplo con [1,3,2,4] ya que 1x3+2x4 = 11
  • 14, por ejemplo con [1,2,3,4] ya que 1x2+3x4 = 14

Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].

Definir las funciones

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

tales que

  • (minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,
minimaSumaProductos [1..4]             ==  10
minimaSumaProductos [3,2,5,7,1,6]      ==  34
minimaSumaProductos [9,2,8,4,5,7,6,0]  ==  74
minimaSumaProductos [1,2,1,4,0,5,6,0]  ==  6
  • (permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,
permutacionMinimal [1..4]             ==  [1,4,3,2]
permutacionMinimal [3,2,5,7,1,6]      ==  [1,7,2,6,3,5]
permutacionMinimal [9,2,8,4,5,7,6,0]  ==  [0,9,2,8,4,7,5,6]
permutacionMinimal [1,2,1,4,0,5,6,0]  ==  [0,6,0,5,1,4,1,2]

Leer más…

Máxima potencia que divide al factorial

Misceláneas

La máxima potencia de 2 que divide al factorial de 5 es 3, ya que 5! = 120, 120 es divisible por 2^3 y no lo es por 2^4.

Definir la función

maxPotDivFact :: Integer -> Integer -> Integer

tal que (maxPotDivFact p n), para cada primo p, es el mayor k tal que p^k divide al factorial de n. Por ejemplo,

maxPotDivFact 2 5       ==  3
maxPotDivFact 3 6       ==  2
maxPotDivFact 2 10      ==  8
maxPotDivFact 3 10      ==  4
maxPotDivFact 2 (10^2)  ==  97
maxPotDivFact 2 (10^3)  ==  994
maxPotDivFact 2 (10^4)  ==  9995
maxPotDivFact 2 (10^5)  ==  99994
maxPotDivFact 2 (10^6)  ==  999993
maxPotDivFact 3 (10^5)  ==  49995
maxPotDivFact 3 (10^6)  ==  499993
maxPotDivFact 7 (10^5)  ==  16662
maxPotDivFact 7 (10^6)  ==  166664
length (show (maxPotDivFact 2 (10^20000)))  ==  20000

Leer más…

Árboles continuos

Misceláneas

Los árboles binarios se pueden representar con el de tipo de dato algebraico

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

Por ejemplo, los árboles

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

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))

Un árbol binario es continuo si el valor absoluto de la diferencia de los elementos adyacentes es 1. Por ejemplo, el árbol ej1 es continuo ya que el valor absoluto de sus pares de elementos adyacentes son

|3-2| = |2-1| = |2-3| = |3-4| = |4-5| = 1

En cambio, el ej2 no lo es ya que |8-10| ≠ 1.

Definir la función

esContinuo :: (Num a, Eq a) => Arbol a -> Bool

tal que (esContinuo x) se verifica si el árbol x es continuo. Por ejemplo,

esContinuo ej1  ==  True
esContinuo ej2  ==  False

Leer más…

La sucesión "Mira y di"

Misceláneas

La sucesión "Mira y di" (en inglés, Look-and-Say) es una sucesión de números naturales en donde cada término se obtiene agrupando las cifras iguales del anterior y recitándolas. Por ejemplo, si x(0) = 1 se lee como "un uno" y por tanto x(1) = 11. Análogamente,

x(1) = 11     (dos unos                          --> 21)
x(2) = 21     (un dos un uno                     --> 1211)
x(3) = 1211   (un uno un dos dos unos            --> 111221)
x(4) = 111221 (tres unos dos doses un uno        --> 312211)
x(5) = 312211 (un tres un uno dos doses dos unos --> 13112221)

Definir la función

sucMiraYDi :: Integer -> [Integer]

tal que (sucMiraYDi n) es la sucesión "Mira y di" cuyo primer término es n. Por ejemplo,

λ> take 9 (sucMiraYdi 1)
[1,11,21,1211,111221,312211,13112221,1113213211,31131211131221]
λ> take 5 (sucMiraYdi 2017)
[2017,12101117,111211103117,31123110132117,1321121321101113122117]
λ> take 7 (sucMiraYDi 22)
[22,22,22,22,22,22,22]
λ> (sucMiraYDi 1) !! 11
3113112221232112111312211312113211
λ> (sucMiraYDi 1) !! 12
1321132132111213122112311311222113111221131221

Independientemente del término inicial x(0) elegido (con la única salvedad del 22), la sucesión diverge y la razón entre el número de cifras de x(n) y el de x(n-1) tiende a un valor fijo que es la constante de Conway λ ≈ 1.303577269. Por ejemplo, para x(0) = 1, las razones son

2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

Definir la función

aproximacionConway :: Integer -> Double -> Int

tal que (aproximacionConway n e) es el menor k tal que la diferencia entre la constante de Conway y la razón entre el número de cifras de x(k) x(k-1) es, en valor absoluto, menor que e. Por ejemplo,

aproximacionConway 1 0.3     ==  3
aproximacionConway 1 0.1     ==  5
aproximacionConway 1 0.01    ==  9
aproximacionConway 1 0.001   ==  24
aproximacionConway 1 0.0001  ==  43
aproximacionConway 2 0.0001  ==  47

Leer más…

Cadena de primos

Misceláneas

La lista de los primeros números primos es

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

Los primeros elementos de la cadena obtenida concatenado los números primos es

"23571113171923293137414347535961677173798389971011"

Definir la función

primoEnPosicion :: Int -> Integer

tal que (primoEnPosicion n) es el número primo que tiene algún dígito en la posición n de la cadena obtenida concatenado los números primos. Por ejemplo,

primoEnPosicion 0       ==  2
primoEnPosicion 1       ==  3
primoEnPosicion 4       ==  11
primoEnPosicion 5       ==  11
primoEnPosicion 6       ==  13
primoEnPosicion 1022    ==  2011
primoEnPosicion 1023    ==  2017
primoEnPosicion 1026    ==  2017
primoEnPosicion 1027    ==  2027
primoEnPosicion (10^7)  ==  21242357

Leer más…

Notación polaca inversa

Misceláneas

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente

""                 []
"20"               [20]
"20 4"             [4, 20]
"20 4 3"           [3, 4, 20]
"20 4 3 +"         [7, 20]
"20 4 3 + 2"       [2, 7, 20]
"20 4 3 + 2 *"     [14, 20]
"20 4 3 + 2 * -"   [6]

Definir la función

valor :: String -> Float

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

valor "4"               ==  4.0
valor "4 3 +"           ==  7.0
valor "4 3 + 2 *"       ==  14.0
valor "20 4 3 + 2 * -"  ==  6.0
valor "3 7 + 2 /"       ==  5.0

Leer más…

La conjetura de Rodolfo

Misceláneas

El pasado 1 de enero, Claudio Meller publicó el artículo La conjetura de Rodolfo que afirma que

Todos los números naturales se pueden números pueden expresarse como la suma de un capicúa y un capicúa especial (siendo los capicúas especiales los números que al quitarles los ceros finales son capicúas; por ejemplo, 32300, 50500 y 78987).

Definir las funciones

descomposiciones               :: Integer -> [(Integer, Integer)]
contraejemplosConjeturaRodolfo :: [Integer]

tales que

  • (descomposiciones x) es la lista de las descomposiciones de x como la suma de un capicúa y un capicúa especial. Por ejemplo,
descomposiciones 1980  ==  [(99,1881),(979,1001)]
descomposiciones 2016  ==  [(575,1441),(606,1410)]
descomposiciones 1971  ==  [(161,1810),(1771,200),(1881,90)]
  • contraejemplosConjeturaRodolfo es la lista de contraejemplos de la conjetura de Rodolfo; es decir, de los números que no pueden expresarse com la suma de un capicúa y un capicúa especial. Por ejemplo,
λ> take 12 contraejemplosConjeturaRodolfo
[1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
[3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

Leer más…

Sustitución en una posición

Misceláneas

Los árboles binarios se pueden representar con el de dato algebraico

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

Por ejemplo, los árboles

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

se pueden representar por

ej1, ej2:: Arbol Int
ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H

Para indicar las posiciones del árbol se define el tipo

type Posicion = [Direccion]

donde

data Direccion = D | I
  deriving Eq

representa un movimiento hacia la derecha (D) o a la izquierda. Por ejemplo, las posiciones de los elementos del ej1 son

9 []
8 [I]
3 [I,I]
2 [I,D]
6 [D]
4 [D,I]
5 [D,D]

Definir la función

sustitucion :: Posicion -> a -> Arbol a -> Arbol a

tal que (sustitucion ds z x) es el árbol obtenido sustituyendo el elemento de x en la posición ds por z. Por ejemplo,

λ> sustitucion [I,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 7 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [D,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 7 H H))
λ> sustitucion [I] 7 ej1
N 9 (N 7 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [] 7 ej1
N 7 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Leer más…

Sumas de dos capicúas

Misceláneas

Definir las funciones

sumas2Capicuas  :: Integer -> [(Integer, Integer)]
noSuma2Capicuas :: [Integer]

tales que

  • (sumas2Capicuas x) es la lista de las descomposiciones de x como suma de dos capicúas (con el primer sumando menor o igual que el segundo). Por ejemplo,
sumas2Capicuas 17  == [(6,11),(8,9)]
sumas2Capicuas 187 == [(6,181),(66,121),(88,99)]
sumas2Capicuas 165 == [(4,161),(44,121),(66,99),(77,88)]
sumas2Capicuas 382 == [(9,373),(191,191)]
sumas2Capicuas 151 == [(0,151)]
sumas2Capicuas 201 == []
  • noSuma2Capicuas es la sucesión de los números que no se pueden escribir como suma de dos capicúas. Por ejemplo,
λ> take 15 noSuma2Capicuas
[21,32,43,54,65,76,87,98,201,1031,1041,1042,1051,1052,1053]
λ> noSuma2Capicuas !! 3000
19941

Leer más…

Inversa del factorial

Misceláneas

Definir la función

inversaFactorial :: Integer -> Maybe Integer

tal que (inversaFactorial x) es (Just n) si el factorial de n es x y es Nothing si no existe ningún número n tal que el factorial de n es x. Por ejemplo,

inversaFactorial 24  ==  Just 4
inversaFactorial 25  ==  Nothing

Leer más…

Suma ordenada de listas infinitas ordenadas

Misceláneas

Definir la función

sumaOrdenada :: [Integer] -> [Integer] -> [Integer]

tal que (sumaOrdenada xs ys) es la suma ordenada de las listas infinitas crecientes xs e ys. Por ejemplo,

λ> take 15 (sumaOrdenada [5,10..] [7,14..])
[12,17,19,22,24,26,27,29,31,32,33,34,36,37,38]
λ> take 15 (sumaOrdenada [2^n | n <- [0..]] [3^n | n <- [0..]])
[2,3,4,5,7,9,10,11,13,17,19,25,28,29,31]

Leer más…

Sumas de tres capicúas

Misceláneas

Definir la función

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

tales que (sumas3Capicuas x) es la lista de las descomposiciones de x como suma de tres capicúas (con los sumandos no decrecientes). Por ejemplo,

sumas3Capicuas 0  ==  [(0,0,0)]
sumas3Capicuas 1  ==  [(0,0,1)]
sumas3Capicuas 2  ==  [(0,0,2),(0,1,1)]
sumas3Capicuas 3  ==  [(0,0,3),(0,1,2),(1,1,1)]
sumas3Capicuas 4  ==  [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]
length (sumas3Capicuas 17)      ==  17
length (sumas3Capicuas 2017)    ==  47
length (sumas3Capicuas 999999)  ==  15266

Comprobar con QuickCheck que todo número natural se puede escribir como suma de tres capicúas.

Leer más…

Sucesión de capicúas

Misceláneas

Definir las funciones

capicuas        :: [Integer]
posicionCapicua :: Integer -> Integer

tales que

  • capicuas es la sucesión de los números capicúas. Por ejemplo,
λ> take 45 capicuas
[0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
 303,313,323,333,343,353]
λ> capicuas !! (10^5)
900010009
  • (posicionCapicua x) es la posición del número capicúa x en la sucesión de los capicúas. Por ejemplo,
λ> posicionCapicua 353
44
λ> posicionCapicua 900010009
100000
λ> let xs = show (123^30)
λ> posicionCapicua (read (xs ++ reverse xs))
1497912859868342793044999075260564303046944727069807798026337448
λ> posicionCapicua (read (xs ++ "7" ++ reverse xs))
5979128598683427930449990752605643030469447270698077980263374496

Leer más…

Sumas y restas alternativas

Misceláneas

Definir la función

sumasYrestas :: Num a => [a] -> a

tal que (sumasYrestas xs) es el resultado de alternativamente los elementos de xs. Por ejemplo,

sumasYrestas [3,2,4,1,7] = 3 - 2 + 4 - 1 + 7
                         = 11

Otros ejemplos,

sumasYrestas [3,2,4]              ==  5
sumasYrestas [3,2,4,1]            ==  4
sumasYrestas [3,2,4,1,7]          ==  11
sumasYrestas (replicate (10^6) 1) ==  0

Leer más…

Números dorados

Misceláneas

Los dígitos del número 2375 se pueden separar en dos grupos de igual tamaño ([7,2] y [5,3]) tales que para los correspondientes números (72 y 53) se verifique que la diferencia de sus cuadrados sea el número original (es decir, 72^2 - 53^2 = 2375).

Un número x es dorado si sus dígitos se pueden separar en dos grupos de igual tamaño tales que para los correspondientes números (a y b) se verifique que la diferencia de sus cuadrados sea el número original (es decir, b^2 - a^2 = x).

Definir la función

esDorado :: Integer -> Bool

tales que (esDorado x) se verifica si x es un número dorado. Por ejemplo,

λ> esDorado 2375
True
λ> take 5 [x | x <- [1..], esDorado x]
[48,1023,1404,2325,2375]

Leer más…

Sucesión de cuadrados reducidos

Misceláneas

La sucesión de cuadrados de orden n definida a partir de un número x se forma iniciándola en x y, para cada término z el siguiente es el número formado por los n primeros dígitos del cuadrado de z. Por ejemplo, para n = 4 y x = 1111, el primer término de la sucesión es 1111, el segundo es 1234 (ya que 1111^2 = 1234321) y el tercero es 1522 (ya que 1234^2 = 1522756).

Definir la función

sucCuadrados :: Int -> Integer -> [Integer]

tal que (sucCuadrados n x) es la sucesión de cuadrados de orden n definida a partir de x. Por ejemplo,

λ> take 10 (sucCuadrados 4 1111)
[1111,1234,1522,2316,5363,2876,8271,6840,4678,2188]
λ> take 10 (sucCuadrados 3 457)
[457,208,432,186,345,119,141,198,392,153]
λ> take 20 (sucCuadrados 2 55)
[55,30,90,81,65,42,17,28,78,60,36,12,14,19,36,12,14,19,36,12]

Leer más…

Familias de números con algún dígito en común

Misceláneas

Una familia de números es una lista de números tal que todos tienen la misma cantidad de dígitos y, además, dichos números tienen al menos un dígito común.

Por ejemplo, los números 72, 32, 25 y 22 pertenecen a la misma familia ya que son números de dos dígitos y todos tienen el dígito 2, mientras que los números 123, 245 y 568 no pertenecen a la misma familia, ya que no hay un dígito que aparezca en los tres números.

Definir la función

esFamilia :: [Integer] -> Bool

tal que (esFamilia ns) se verifica si ns es una familia de números. Por ejemplo,

esFamilia [72, 32, 25, 22]  ==  True
esFamilia [123,245,568]     ==  False
esFamilia [72, 32, 25, 223] ==  False

Leer más…

Estratificación de un árbol

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         8   3
    |        /|\       /|\  |
    4       4 5 6     4 5 6 7

se representan por

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 8 [],N 3 [N 4 []]]
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 []]]

Un estrato de un árbol es la lista de nodos que se encuentran al mismo nivel de profundidad. Por ejemplo, los estratos del árbol ej1 son [1], [8,3] y [4].

Definir la función

estratos :: Arbol a -> [[a]]

tal que (estratos x) es la lista de los estratos del árbol x. Por ejemplo,

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

Leer más…

Terminaciones de Fibonacci

Misceláneas

Definir la sucesión

sucFinalesFib :: [(Integer,Integer)]

cuyos elementos son los pares (n,x), donde x es el n-ésimo término de la sucesión de Fibonacci, tales que la terminación de x es n. Por ejemplo,

λ> take 6 sucFinalesFib
[(0,0),(1,1),(5,5),(25,75025),(29,514229),(41,165580141)]
λ> head [(n,x) | (n,x) <- sucFinalesFib, n > 200]
(245,712011255569818855923257924200496343807632829750245)
λ> head [n | (n,_) <- sucFinalesFib, n > 10^4]
10945

Leer más…

Segmentos comunes maximales

Misceláneas

Los segmentos de de "abcd" son

["","a","ab","abc","abcd","b","bc","bcd","c","cd","d"]

Los segmentos comunes de "abcd" y "axbce" son

["","a","b","bc","c"]

Los segmentos comunes maximales de "abcd" y "axbce" son

["a","bc"]

Definir la función

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

tal que (segmentosComunesMaximales xs ys) es la lista de los segmentos comunes maximales de xs e ys. Por ejemplo,

segmentosComunesMaximales "abcd" "axbce"  ==  ["a","bc"]

Leer más…

Números de Perrin

Misceláneas

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

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

con los valores iniciales

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

Definir la sucesión

sucPerrin :: [Integer]

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

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

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

Leer más…

Mínima suma de las ramas de un árbol

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     5   3         5   3
    |        /|\       /|\  |
    4       4 7 6     4 7 6 7

se representan por

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

Definir la función

minimaSuma :: Arbol Int -> Int

tal que (minimaSuma a) es el mínimo de las sumas de las ramas del árbol a. Por ejemplo,

minimaSuma ej1  ==  8
minimaSuma ej2  ==  6
minimaSuma ej3  ==  10

Leer más…

Números super pandigitales

Misceláneas

Un entero positivo n es pandigital en base b si su expresión en base b contiene todos los dígitos de 0 a b-1 al menos una vez. Por ejemplo,

  • el 2 es pandigital en base 2 porque 2 en base 2 es 10,
  • el 11 es pandigital en base 3 porque 11 en base 3 es 102 y
  • el 75 es pandigital en base 4 porque 75 en base 4 es 1023.

Un número n es super pandigital de orden m si es pandigital en todas las bases desde 2 hasta m. Por ejemplo, 978 es super pandigital de orden 5 pues

  • en base 2 es: 1111010010
  • en base 3 es: 1100020
  • en base 4 es: 33102
  • en base 5 es: 12403

Definir la función

superPandigitales :: Integer -> [Integer]

tal que (superPandigitales m) es la lista de los números super pandigitales de orden m. Por ejemplo,

take 3 (superPandigitales 3) == [11,19,21]
take 3 (superPandigitales 4) == [75,99,114]
take 3 (superPandigitales 5) == [978,1070,1138]

Leer más…

Ternas coprimas

Misceláneas

Definir la lista

ternasCoprimas :: [(Integer,Integer,Integer)]

cuyos elementos son ternas de primos relativos (a,b,c) tales que a < b y a + b == c. Por ejemplo,

λ> take 7 ternasCoprimas
[(1,2,3),(1,3,4),(2,3,5),(1,4,5),(3,4,7),(1,5,6),(2,5,7)]
λ> ternasCoprimas !! 300000
(830,993,1823)

Leer más…

Listas duplicadas

Misceláneas

Se observa que en la cadena "aabbccddeffgg" todos los caracteres están duplicados excepto el 'e'. Al añadirlo obtenemos la lista "aabbccddeeffgg" y se dice que esta última está duplicada.

También se observa que "aaaabbbccccdd" no está duplicada (porque hay un número impar de 'b' consecutivas). Añadiendo una 'b' se obtiene "aaaabbbbccccdd" que está duplicada.

Definir las funciones

esDuplicada :: Eq a => [a] -> Bool
duplica     :: Eq a => [a] -> [a]

tales que

  • (esDuplicada xs) se verifica si xs es una lista duplicada. Por ejemplo,
esDuplicada "aabbccddeffgg"   ==  False
esDuplicada "aabbccddeeffgg"  ==  True
esDuplicada "aaaabbbccccdd"   ==  False
esDuplicada "aaaabbbbccccdd"  ==  True
  • (duplica xs) es la lista obtenida duplicando los elementos de xs que no lo están. Por ejemplo,
duplica "b"        ==  "bb"
duplica "abba"     ==  "aabbaa"
duplica "Betis"    ==  "BBeettiiss"
duplica [1,1,1]    ==  [1,1,1,1]
duplica [1,1,1,1]  ==  [1,1,1,1]

Comprobar con QuickCheck que, para cualquier lista de enteros xs, se verifica la siguiente propiedad:

esDuplicada (duplica xs)

Leer más…

Ordenación por una fila

Misceláneas

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

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

se puede representar por

ej :: [[Int]]
ej = [[1,2,5],
      [3,0,7],
      [9,1,6],
      [6,4,2]]

Definir la función

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

tal que (ordenaPorFila xss k) es la matriz obtenida ordenando xs por los elementos de la fila k. Por ejemplo,

ordenaPorFila ej 1  ==  [[2,1,5],[0,3,7],[1,9,6],[4,6,2]]
ordenaPorFila ej 2  ==  [[2,5,1],[0,7,3],[1,6,9],[4,2,6]]
ordenaPorFila ej 3  ==  [[5,2,1],[7,0,3],[6,1,9],[2,4,6]]

Leer más…

Día de la semana

Misceláneas

Definir la función

dia :: Int -> Int -> Int -> String

tal que (dia d m a) es el día de la semana correspondiente al día d del mes m del año a. Por ejemplo,

dia 21 12 2016  ==  "Miercoles"
dia 14  4 1936  ==  "Martes"

Leer más…

Ordenación por una columna

Misceláneas

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

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

se puede representar por

ej :: [[Int]]
ej = [[1,2,5],
      [3,0,7],
      [9,1,6],
      [6,4,2]]

Definir la función

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

tal que (ordenaPor xss k) es la matriz obtenida ordenando xs por los elementos de la columna k. Por ejemplo,

ordenaPor ej 0  ==  [[1,2,5],[3,0,7],[6,4,2],[9,1,6]]
ordenaPor ej 1  ==  [[3,0,7],[9,1,6],[1,2,5],[6,4,2]]
ordenaPor ej 2  ==  [[6,4,2],[1,2,5],[9,1,6],[3,0,7]]

Leer más…

Selección por posición

Misceláneas

Definir la función

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

tal que (seleccion xs ps) es la lista ordenada de los elementos que ocupan las posiciones indicadas en la lista ps. Por ejemplo,

seleccion [6,2,4,7] [2,0]      ==  [4,6]
seleccion ['a'..'z'] [0,2..10] ==  "acegik"

Leer más…

Números de la suerte

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 la sucesión

numerosDeLaSuerte :: [Int]

cuyos elementos son 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 !! 1500
13995

Leer más…

Posiciones de equilibrio

Misceláneas

Se dice que k es una posición de equilibrio de una lista xs si la suma de los elementos de xs en las posiciones menores que k es igual a la suma de los elementos de xs en las posiciones mayores que k. Por ejemplo, en la lista [-7,1,5,2,-4,3,0] el 3 es una posición de equilibrio ya que -7+1+5 = -4+3+0; también lo es el 6 ya que -7+1+5+2+(-4)+3 = 0.

Definir la función,

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

tal que (equilibrios xs) es la lista de las posiciones de equilibrio de xs. Por ejemplo,

equilibrios [-7,1,5,2,-4,3,0]  ==  [3,6]
equilibrios [1..10^6]          ==  []

Leer más…

Distancia a Erdős

Misceláneas

Una de las razones por la que el matemático húngaro Paul Erdős es conocido es por la multitud de colaboraciones que realizó durante toda su carrera, un total de 511. Tal es así que se establece la distancia a Erdős como la distancia que has estado de coautoría con Erdős. Por ejemplo, si eres Paul Erdős tu distancia a Erdős es 0, si has escrito un artículo con Erdős tu distancia es 1, si has escrito un artículo con alguien que ha escrito un artículo con Erdős tu distancia es 2, etc. El objetivo de este problema es definir una función que a partir de una lista de pares de coautores y un número natural n calcular la lista de los matemáticos a una distancia n de Erdős.

Para el problema se considerará la siguiente lista de coautores

coautores :: [(String,String)]
coautores =
  [("Paul Erdos","Ernst Straus"),("Paul Erdos","Pascual Jordan"),
   ("Paul Erdos","D. Kleitman"),("Albert Einstein","Ernst Straus"),
   ("John von Newmann","David Hilbert"),("S. Glashow","D. Kleitman"),
   ("John von Newmann","Pascual Jordan"), ("David Pines","D. Bohm"),
   ("Albert Einstein","Otto Stern"),("S. Glashow", "M. Gell-Mann"),
   ("Richar Feynman","M. Gell-Mann"),("M. Gell-Mann","David Pines"),
   ("David Pines","A. Bohr"),("Wolfgang Pauli","Albert Einstein"),
   ("D. Bohm","L. De Broglie"), ("Paul Erdos","J. Conway"),
   ("J. Conway", "P. Doyle"),("Paul Erdos","A. J. Granville"),
   ("A. J. Granville","B. Mazur"),("B. Mazur","Andrew Wiles")]

Definir la función

numeroDeErdos :: [(String, String)] -> Int -> [String]

tal que (numeroDeErdos xs n) es la lista de lista de los matemáticos de la lista de coautores xs que se encuentran a una distancia n de Erdős. Por ejemplo,

λ> numeroDeErdos coautores 0
["Paul Erdos"]
λ> numeroDeErdos coautores 1
["Ernst Straus","Pascual Jordan","D. Kleitman","J. Conway","A. J. Granville"]
λ> numeroDeErdos coautores 2
["Albert Einstein","John von Newmann","S. Glashow","P. Doyle","B. Mazur"]

Leer más…

Mayores que la mitad

Misceláneas

Definir la función

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

tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,

sort (mayoresMitad [1,6,3,4])    ==  [4,6]
sort (mayoresMitad [1,6,3,4,7])  ==  [4,6,7]
sort (mayoresMitad [1,6,3,4,2])  ==  [3,4,6]
length (mayoresMitad3 [1..10^6]) ==  500000

Nota: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.

Leer más…

Caracteres en la misma posición que en el alfabeto

Misceláneas

Un carácter c de una cadena cs está bien colocado si la posición de c en cs es la misma que en el abecedario (sin distinguir entre mayúsculas y minúsculas). Por ejemplo, los elementos bien colocados de la cadena "aBaCEria" son 'a', 'B' y 'E'.

Definir la función

nBienColocados :: String -> Int

tal que (nBienColocados cs) es el número de elementos bien colocados de la cadena cs. Por ejemplo,

nBienColocados "aBaCEria"                    ==  3
nBienColocados "xBxxExxxIxxxxNxxxxxTxxxXYZ"  ==  8

Leer más…

Suma de los máximos de los subconjuntos

Misceláneas

Los subconjuntos distinto del vacío del conjunto {3, 2, 5}, junto con sus máximos elementos, son

{3}       su máximo es 3
{2}       su máximo es 2
{5}       su máximo es 5
{3, 2}    su máximo es 3
{3, 5}    su máximo es 5
{2, 5}    su máximo es 5
{3, 2, 5} su máximo es 5

Por tanto, la suma de los máximos elementos de los subconjuntos de {3, 2, 5} es 3 + 2 + 5 + 3 + 5 + 5 + 5 = 28.

Definir la función

sumaMaximos :: [Integer] -> Integer

tal que (sumaMaximos xs) es la suma de los máximos elementos de los subconjuntos de xs. Por ejemplo,

sumaMaximos [3,2,5]    ==  28
sumaMaximos [4,1,6,3]  ==  71
sumaMaximos [1..100]   ==  125497409422594710748173617332225
length (show (sumaMaximos [1..10^5]))  ==  30108
sumaMaximos [1..10^5] `mod` (10^7)     ==  4490625

Leer más…

Elementos que respetan la ordenación

Misceláneas

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

Definir la función

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

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

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

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

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

Leer más…

Sin ceros finales

Misceláneas

Definir la función

sinCerosFinales :: Int -> Int

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

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

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

sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

Leer más…

Listas engarzadas

Misceláneas

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

Definir la función

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

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

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

Leer más…

Listas alternadas

Misceláneas

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

Definir la función

alternada :: [Int] -> Bool

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

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

Leer más…

Sumas de posiciones pares e impares

Misceláneas

Definir la función

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

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

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

Leer más…

Problema de las particiones óptimas

Misceláneas

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

Definir la función

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

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

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

Leer más…

Huecos de Euclides

Misceláneas

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

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

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

Definir la función

hueco :: Int -> Integer

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

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

Leer más…

Representación binaria de los números de Carol

Misceláneas

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

Definir las funciones

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

tales que

  • (carol n) es el n-ésimo número de Carol. Por ejemplo,
carol  3  ==  47
carol  4  ==  223
carol 25  ==  1125899839733759
  • (carolBinario n) es la representación binaria del n-ésimo número de Carol. Por ejemplo,
carolBinario 3  ==  101111
carolBinario 4  ==  11011111
carolBinario 5  ==  1110111111

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

Leer más…

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

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
   (x2)      (-1)

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

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

Definir las siguientes funciones

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

tales que

  • (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,
    λ> arbolOp 4 1
    N 4 (H 8) (H 3)
    λ> arbolOp 4 2
    N 4 (N 8 (H 16) (H 7))
        (N 3 (H 6) (H 2))
    λ> arbolOp 2 3
    N 2 (N 4
           (N 8 (H 16) (H 7))
           (N 3 (H 6) (H 2)))
        (N 1
           (N 2 (H 4) (H 1))
           (H 0))
    λ> arbolOp 2 4
    N 2 (N 4 (N 8
                (N 16 (H 32) (H 15))
                (N 7 (H 14) (H 6)))
             (N 3
                (N 6 (H 12) (H 5))
                (N 2 (H 4) (H 1))))
        (N 1 (N 2
                (N 4 (H 8) (H 3))
                (N 1 (H 2) (H 0)))
             (H 0))
  • (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,
minNOp 4 7  ==  2
minNOp 2 5  ==  4

Leer más…

Menor potencia de 2 comenzando un número dado

Misceláneas

Definir las siguientes funciones

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

tales que

  • (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,
λ> take 5 (potenciasDe2 3)
[32,32768,33554432,34359738368,35184372088832]
λ> take 2 (potenciasDe2 102)
[1024,102844034832575377634685573909834406561420991602098741459288064]
  • (menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,
λ> menorPotenciaDe2 10
1024
λ> menorPotenciaDe2 25
256
λ> menorPotenciaDe2 62
6277101735386680763835789423207666416102355444464034512896
λ> menorPotenciaDe2 425
42535295865117307932921825928971026432
λ> menorPotenciaDe2 967140655691
9671406556917033397649408
λ> [menorPotenciaDe2 a | a <- [1..10]]
[1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

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

Leer más…

Máxima ramificación

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
 / \       / \           / \
2   3     2   3         2   3
    |        /|\       /|\  |
    4       4 5 6     4 5 6 7

se representan por

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

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

Definir la función

maximaRamificacion :: Arbol a -> Int

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

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

Leer más…

Números consecutivos compuestos

Misceláneas

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

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

Definir la función

menorSerieCompuesta :: Integer -> (Integer,Integer)

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

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

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

Leer más…

Conmutaciones ondulantes

Misceláneas

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

Definir la función

minConmutacionesOndulante :: [Int] -> Int

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

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

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

Leer más…

Números de Dudeney

Misceláneas

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

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

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

Definir la función

numerosDudeney :: Integer -> [Integer]

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

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

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

Leer más…

Números poderosos

Misceláneas

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

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

Definir la función

esPoderoso :: Integer -> Bool

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

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

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

Leer más…

Máximo producto en la partición de un número

Misceláneas

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

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

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

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

Definir la función

maximoProductoParticiones :: Int -> Int

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

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

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

Leer más…

Cuadrados ondulantes

Misceláneas

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

Definir la función

cuadradosOndulantes :: Integer -> [Integer]

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

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

Leer más…

Persistencia multiplicativa de un número

Misceláneas

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

Definir las funciones

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

tales que

  • (persistencia x) es la persistencia de x. Por ejemplo,
persistencia 39                             ==   3
persistencia 2677889                        ==   8
persistencia 26888999                       ==   9
persistencia 3778888999                     ==  10
persistencia 277777788888899                ==  11
persistencia 77777733332222222222222222222  ==  11
  • (menorPersistente n) es el menor número con persistencia n. Por ejemplo,
menorPersistente 0  ==  1
menorPersistente 1  ==  10
menorPersistente 2  ==  25
menorPersistente 3  ==  39
menorPersistente 4  ==  77
menorPersistente 5  ==  679
menorPersistente 6  ==  6788
menorPersistente 7  ==  68889

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

Leer más…

Números perfectos y cojonudos

Misceláneas

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

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

Definir la funciones

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

tales que

  • (esPerfecto x) se verifica si x es perfecto. Por ejemplo,
esPerfecto 28  ==  True
esPerfecto 30  ==  False
  • (esCojonudo x) se verifica si x es cojonudo. Por ejemplo,
esCojonudo 28                   ==  True
esCojonudo 30                   ==  False
esCojonudo 2305843008139952128  ==  True
  • (equivalenciaCojonudosPerfectos n) se verifica si para todos los números x menores o iguales que n se tiene que x es perfecto si, y sólo si, x es cojonudo. Por ejemplo,
equivalenciaCojonudosPerfectos 3000  ==  True

Leer más…

Subconjuntos acotados

Misceláneas

Definir la función

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

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

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

Leer más…

Variación de la conjetura de Goldbach

Misceláneas

La conjetura de Goldbach afirma que

Todo número entero mayor que 5 se puede escribir como suma de tres números primos.

En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.

Definir las funciones

sumas3PrimosDistintos      :: Int -> [(Int,Int,Int)]
conKsumas3PrimosDistintos  :: Int -> Int -> [Int]
noSonSumas3PrimosDistintos :: Int -> [Int]

tales que

  • (sumas3PrimosDistintos n) es la lista de las descomposiciones decrecientes de n como tres primos distintos. Por ejemplo,
sumas3PrimosDistintos 26  ==  [(13,11,2),(17,7,2),(19,5,2)]
sumas3PrimosDistintos 18  ==  [(11,5,2),(13,3,2)]
sumas3PrimosDistintos 10  ==  [(5,3,2)]
sumas3PrimosDistintos 11  ==  []
  • (conKsumas3PrimosDistintos k n) es la lista de los números menores o iguales que n que se pueden escribir en k forma distintas como suma de tres primos distintos. Por ejemplo,
conKsumas3PrimosDistintos 3 99  ==  [26,27,29,32,36,42,46,48,54,58,60]
conKsumas3PrimosDistintos 2 99  ==  [18,20,21,22,23,24,25,28,30,34,64,70]
conKsumas3PrimosDistintos 1 99  ==  [10,12,14,15,16,19,40]
conKsumas3PrimosDistintos 0 99  ==  [11,13,17]
  • (noSonSumas3PrimosDistintos n) es la lista de los números menores o iguales que n que no se pueden escribir como suma de tres primos distintos. Por ejemplo,
noSonSumas3PrimosDistintos 99   ==  [11,13,17]
noSonSumas3PrimosDistintos 500  ==  [11,13,17]

Leer más…

Conjetura de Rassias

Misceláneas

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

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

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

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

Definir las siguientes funciones

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

tales que

  • (paresRassias p) es la lista de los pares de Rassias del primo p (que se supone que es mayor que 2). Por ejemplo,
take 3 (paresRassias 5)    == [(2,7),(3,11),(5,19)]
take 3 (paresRassias 1229) == [(71,87187),(113,138763),(191,234547)]
  • (conjeturaRassia x) se verifica si para todos los primos menores que x (y mayores que 2) se cumple la conjetura de Rassia. Por ejemplo,
conjeturaRassias (10^5)  ==  True

Leer más…

Primo anterior

Misceláneas

Definir la función

primoAnterior :: Integer -> Integer

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

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

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

Leer más…

Primos de Kamenetsky

Misceláneas

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

Definir la sucesión

primosKamenetsky :: [Integer]

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

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

Leer más…

Números de Harshad hereditarios

Misceláneas

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

numeroHHD :: Int -> Bool

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

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

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

Leer más…

Triángulos geométricos

Misceláneas

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

Definir la función

numeroTG :: Integer -> Int

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

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

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

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

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

Leer más…

Cadenas de primos complementarios

Misceláneas

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

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

Definir las funciones

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

tales que

  • (cadena x) es la cadena de primos a partir de x tal que cada uno es el complemento del anterior. Por ejemplo,
cadena 8         == []
cadena 7         == [7]
cadena 13        == [13,7]
cadena 643       == [643,557,443]
cadena 18127     == [18127,1873,127,73,67,53,47]
cadena 18181213  == [18181213,1818787,181213,18787,1213,787,613,587]
  • (conCadena n) es la lista de números cuyas cadenas tienen n elementos. Por ejemplo,
take 6 (conCadena 3)                == [23,31,61,67,103,307]
[head (conCadena n) | n <- [4..8]]  == [37,43,157,18127,181873]

Leer más…

Construcción del árbol a partir de los recorridos preorden e inorden

Misceláneas

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

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

Por ejemplo, el árbol

     9
    / \
   /   \
  3     7
 / \
2   4

se representa por

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

Definir las siguientes funciones

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

tales que

  • (preorden x) es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo,
preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]
  • (inorden x) es la lista correspondiente al recorrido inorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación visita la raíz del árbol y, finalmente, recorre el subárbol derecho. Por ejemplo,
inorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,3,4,9,7]
  • (arboles xs ys) es la lista de los árboles con recorrido preorden xs y recorrido inorden de ys. Por ejemplo,
λ> arboles [9,3,2,4,7] [2,3,4,9,7]
[N 9 (N 3 (H 2) (H 4)) (H 7)]
λ> arboles [9,3,2,4,7] [2,4,3,9,7]
[]
λ> arboles [1,1,1,2,3] [1,1,2,1,3]
[N 1 (H 1) (N 1 (H 2) (H 3)),
N 1 (N 1 (H 1) (H 2)) (H 3)]
λ> let x = N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))
λ> arboles (preorden x) (inorden x)
[N 1 (H 1) (N 1 (H 3) (N 1 (H 1) (N 1 (H 2) (H 3)))),
N 1 (H 1) (N 1 (H 3) (N 1 (N 1 (H 1) (H 2)) (H 3))),
N 1 (N 1 (H 1) (H 3)) (N 1 (H 1) (N 1 (H 2) (H 3))),
N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))]

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

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

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

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

import Control.Monad

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

Leer más…

Caminos en una retícula

Misceláneas

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

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

Caminos en una retícula

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

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

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

Definir las funciones

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

tales que

  • (caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,
λ> caminos 2 2
[[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]
λ> caminos 1 3
[[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]
λ> caminos 2 3
[[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],
[D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]
  • (nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,
nCaminos 2 2  ==  6
nCaminos 1 3  ==  4
nCaminos 2 3  ==  10
length (show (nCaminos 20000 30000))  ==  14612
length (show (nCaminos 30000 20000))  ==  14612

Leer más…

Centro de gravedad de una lista

Misceláneas

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

Definir la función

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

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

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

Leer más…

El problema de las N torres

Misceláneas

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

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

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

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

Definir las funciones

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

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

λ> torres 3
[( 1 0 0 )
 ( 0 1 0 )
 ( 0 0 1 )
,( 1 0 0 )
 ( 0 0 1 )
 ( 0 1 0 )
,( 0 1 0 )
 ( 1 0 0 )
 ( 0 0 1 )
,( 0 1 0 )
 ( 0 0 1 )
 ( 1 0 0 )
,( 0 0 1 )
 ( 1 0 0 )
 ( 0 1 0 )
,( 0 0 1 )
 ( 0 1 0 )
 ( 1 0 0 )
]
  • (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,
λ> nTorres 3
6
λ> length (show (nTorres (10^4)))
35660

Leer más…

La sucesión del reloj astronómico de Praga

Misceláneas

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

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

Definir la lista

reloj :: [Integer]

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

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

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

Leer más…

Particiones de longitud fija

Misceláneas

Definir la función

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

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

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

Leer más…

Problema de las jarras

Misceláneas

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

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

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

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

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

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

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

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

Otros ejemplos

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

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

Leer más…

Problema del dominó

Misceláneas

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

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

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

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

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

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

Leer más…

Sucesión duplicadora

Misceláneas

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

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

Definir la función

duplicadora :: Integer -> [Integer]

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

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

Leer más…

Problema de las puertas

Misceláneas

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

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

Por ejemplo, para n = 5

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

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

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

Definir la función

final :: Int -> [Estado]

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

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

Leer más…

Juego de bloques con letras

Misceláneas

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

Definir la función

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

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

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

Leer más…

Densidad de números no monótonos

Misceláneas

Un número entero positivo se dice que es

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

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

Definir las siguientes funciones

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

tales que

  • (densidad n) es la densidad de números no monótonos hasta n. Por ejemplo,
densidad 100  ==  0.0
densidad 200  ==  0.265
densidad 400  ==  0.4375
densidad 800  ==  0.53375
  • (menorConDensidadMayor x) es el menor número n tal que la densidad de números no monótonos hasta n es mayor o igual que x. Por ejemplo,
menorConDensidadMayor 0.5   ==  538
densidad 537                ==  0.49906892
densidad 538                ==  0.5
menorConDensidadMayor 0.9   ==  21780
densidad 21779              ==  0.8999954
densidad 21780              ==  0.9
menorConDensidadMayor 0.99  ==  1586996

Leer más…

Sucesión fractal

Misceláneas

La sucesión fractal

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

está construida de la siguiente forma:

  • los términos pares forman la sucesión de los números naturales
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
  • los términos impares forman la misma sucesión original
0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

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

tales que

  • sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,
take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
sucFractal !! 30     == 15
sucFractal !! (10^7) == 5000000
  • (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,
sumaSucFractal 10      == 13
sumaSucFractal (10^5)  == 1666617368
sumaSucFractal (10^10) == 16666666661668691669
sumaSucFractal (10^15) == 166666666666666166673722792954
sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
length (show (sumaSucFractal (10^15000))) == 30000
sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

Leer más…