Ir al contenido principal

Mínimo producto escalar

Misceláneas

El producto escalar de los vectores \([a_1,a_2,...,a_n]\) y \([b_1,b_2,..., b_n]\) es \[ a_1·b_1 + a_2·b_2 + ··· + a_n·b_n \]

Definir la función

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

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

   menorProductoEscalar [3,2,5]  [1,4,6]    == 29
   menorProductoEscalar [3,2,5]  [1,4,-6]   == -19
   menorProductoEscalar [1..10^2] [1..10^2] == 171700
   menorProductoEscalar [1..10^3] [1..10^3] == 167167000
   menorProductoEscalar [1..10^4] [1..10^4] == 166716670000
   menorProductoEscalar [1..10^5] [1..10^5] == 166671666700000
   menorProductoEscalar [1..10^6] [1..10^6] == 166667166667000000

Leer más…

Números con dígitos primos

Misceláneas

Definir la lista

   numerosConDigitosPrimos :: [Integer]

cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,

   λ> take 22 numerosConDigitosPrimos
   [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223]
   λ> numerosConDigitosPrimos !! (10^7)
   322732232572

Leer más…

Representación de Zeckendorf

Listas infinitas

Los primeros números de Fibonacci son

   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.

El teorema de Zeckendorf establece que entero positivo n se puede representar, de manera única, como la suma de números de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representación de Zeckendorf de n. Por ejemplo, la representación de Zeckendorf de 100 es

   100 = 89 + 8 + 3

Hay otras formas de representar 100 como sumas de números de Fibonacci; por ejemplo,

   100 = 89 +  8 + 2 + 1
   100 = 55 + 34 + 8 + 3

pero no son representaciones de Zeckendorf porque 1 y 2 son números de Fibonacci consecutivos, al igual que 34 y 55.

Definir la función

   zeckendorf :: Integer -> [Integer]

tal que (zeckendorf n) es la representación de Zeckendorf de n. Por ejemplo,

   zeckendorf 100 == [89,8,3]
   zeckendorf 200 == [144,55,1]
   zeckendorf 300 == [233,55,8,3,1]
   length (zeckendorf (10^50000)) == 66097

Leer más…

Descomposiciones triangulares

Teoría de números

Los números triangulares se forman como sigue

   *     *      *
        * *    * *
              * * *
   1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

    1 = 1
    3 = 1 + 2
    6 = 1 + 2 + 3
   10 = 1 + 2 + 3 + 4
   15 = 1 + 2 + 3 + 4 + 5

Definir la función

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

tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,

   λ> descomposicionesTriangulares3 4
   []
   λ> descomposicionesTriangulares3 5
   [(1,1,3)]
   λ> descomposicionesTriangulares3 12
   [(1,1,10),(3,3,6)]
   λ> descomposicionesTriangulares3 30
   [(1,1,28),(3,6,21),(10,10,10)]
   λ> descomposicionesTriangulares3 61
   [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
   λ> descomposicionesTriangulares3 52
   [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
   λ> descomposicionesTriangulares3 82
   [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
   λ> length (descomposicionesTriangulares3 (5*10^5))
   124

Leer más…

Conjunto de primos relativos

Misceláneas

Dos números enteros positivos son primos relativos si no tienen ningún factor primo en común; es decir, si 1 es su único divisor común. Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3.

Definir la función

   primosRelativos :: [Int] -> Bool

tal que primosRelativos xs se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,

   primosRelativos [6,35]         ==  True
   primosRelativos [6,27]         ==  False
   primosRelativos [2,3,4]        ==  False
   primosRelativos [6,35,11]      ==  True
   primosRelativos [6,35,11,221]  ==  True
   primosRelativos [6,35,11,231]  ==  False

Leer más…

Diferencia simétrica

Misceláneas

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

Definir la función

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

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

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

Leer más…

Matrices de Toepliz

Misceláneas

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

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

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

Las anteriores matrices se pueden definir por

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

Definir la función

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

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

   esToeplitz ej1  ==  True
   esToeplitz ej2  ==  False

Leer más…

Diagonales principales de una matriz

Misceláneas

La lista de las diagonales principales de la matriz

   1  2  3  4
   5  6  7  8
   9 10 11 12

es

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

Definir la función

   diagonalesPrincipales :: Array (Int,Int) a -> [[a]]

tal que diagonalesPrincipales p es la lista de las diagonales principales de p. Por ejemplo,

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

Leer más…

Posiciones de las diagonales principales

Misceláneas

Las posiciones de una matriz con 3 filas y 4 columnas son

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

La posiciones de sus 6 diagonales principales son

  [(3,1)]
  [(2,1),(3,2)]
  [(1,1),(2,2),(3,3)]
  [(1,2),(2,3),(3,4)]
  [(1,3),(2,4)]
  [(1,4)]

Definir la función

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

tal que posicionesdiagonalesprincipales m n es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,

  λ> mapM_ print (posicionesDiagonalesPrincipales 3 4)
  [(3,1)]
  [(2,1),(3,2)]
  [(1,1),(2,2),(3,3)]
  [(1,2),(2,3),(3,4)]
  [(1,3),(2,4)]
  [(1,4)]
  λ> mapM_ print (posicionesDiagonalesPrincipales 4 4)
  [(4,1)]
  [(3,1),(4,2)]
  [(2,1),(3,2),(4,3)]
  [(1,1),(2,2),(3,3),(4,4)]
  [(1,2),(2,3),(3,4)]
  [(1,3),(2,4)]
  [(1,4)]
  λ> mapM_ print (posicionesDiagonalesPrincipales 4 3)
  [(4,1)]
  [(3,1),(4,2)]
  [(2,1),(3,2),(4,3)]
  [(1,1),(2,2),(3,3)]
  [(1,2),(2,3)]
  [(1,3)]

Leer más…

Números triangulares con n cifras distintas

Misceláneas

Los números triangulares se forman como sigue

   *     *      *
        * *    * *
              * * *
   1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

    1 = 1
    3 = 1 + 2
    6 = 1 + 2 + 3
   10 = 1 + 2 + 3 + 4
   15 = 1 + 2 + 3 + 4 + 5

Definir la función

   triangularesConCifras :: Int -> [Integer]

tal que triangularesConCifras n es la lista de los números triangulares con n cifras distintas. Por ejemplo,

   take 6 (triangularesConCifras 1)   ==  [1,3,6,55,66,666]
   take 6 (triangularesConCifras 2)   ==  [10,15,21,28,36,45]
   take 6 (triangularesConCifras 3)   ==  [105,120,136,153,190,210]
   take 5 (triangularesConCifras 4)   ==  [1035,1275,1326,1378,1485]
   take 2 (triangularesConCifras 10)  ==  [1062489753,1239845706]

Leer más…