Ir al contenido principal

Relleno de matrices

Misceláneas

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

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

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

type Matriz = Array (Int,Int) Int

por ejemplo, la matriz de la izquierda de la figura anterior se define por

ej :: Matriz
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                              0, 0, 0, 0, 0,
                              0, 0, 0, 1, 0,
                              1, 0, 0, 0, 0,
                              0, 0, 0, 0, 0]

Definir la función

relleno :: Matriz -> Matriz

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

λ> elems (relleno ej)
[1,0,0,1,0,
 1,0,0,1,0,
 1,1,1,1,1,
 1,1,1,1,1,
 1,0,0,1,0]

Leer más…

Huecos maximales entre primos

Misceláneas

El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son

Primo Hueco
 2    1
 3    2
 7    4
11    2

El hueco de un número primo p es maximal si es mayor que los huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es

Primo Hueco
  2    1
  3    2
  7    4
 23    6
 89    8
113   14
523   18
887   20

Definir la sucesión

primosYhuecosMaximales :: [(Integer,Integer)]

cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,

λ> take 8 primosYhuecosMaximales
[(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]
λ> primosYhuecosMaximales !! 20
(2010733,148)

Leer más…

Lista tautológica de literales

Misceláneas

En lógica matemática, un literal es una fórmula atómica o su negación. Se puede definir por el tipo de dato

data Literal = Atom String
             | Neg Literal
             deriving (Eq, Show)

Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom "p") y (Neg (Atom "q")), respectivamente.

Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.

Definir la función

tautologia :: [Literal] -> Bool

tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]
True
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]
False
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]
False

Leer más…

Puntos visibles en la cuadrícula de un plano

Misceláneas

La cuadrícula entera de lado n, Cₙ, es el conjunto de los puntos (x,y) donde x e y son números enteros tales que 1 ≤ x, y ≤ n.

Un punto (x,y) de Cₙ es visible desde el origen si el máximo común divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque está ocultado por el (2,3); en cambio, el (2,3) sí es visible.

El conjunto de los puntos visibles en la cuadrícula entera de lado 6 son (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1) y (6,5).

Definir la función

nVisibles :: Integer -> Integer

tal que (nVisibles n) es el número de los puntos visibles en la cuadrícula de lado n.Por ejemplo,

nVisibles 6       ==  23
nVisibles 10      ==  63
nVisibles 100     ==  6087
nVisibles 1000    ==  608383
nVisibles 10000   ==  60794971
nVisibles 100000  ==  6079301507

Leer más…

Cambios de signo

Misceláneas

En una lista xs se produce un cambio de signo por cada elemento x de la lista junto el primero de los elementos de xs con signo opuesto al de x. Por ejemplo,en la lista [6,5,-4,0,-2,-7,0,-8,-1,4] hay 2 cambios de signo (entre (5,-4) y (-1,4)) y en la lista [6,5,-4,0, 2,-7,0,-8,-1,4] hay 4 cambios de signo (entre (5,-4), (-4,2), (2,-7) y(-1,4)).

Definir la función

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

tal que (nCambios xs) es el número de cambios de signos de la lista xs. Por ejemplo,

nCambios []                          ==  0
nCambios [6,5,-4,0,-2,-7,0,-8,-1,4]  ==  2
nCambios [6,5,-4,0, 2,-7,0,-8,-1,4]  ==  4

Leer más…

Parte libre de cuadrados y parte cuadrada de un número

Misceláneas

La parte libre de cuadrados de un número n es el producto de todos sus divisores primos con exponente impar en la factorización prima de n. Por ejemplo, la parte libre de cuadrados de 360 es 10 ya que 360 = 2³3²5 y 2.5 = 10; además, 360 = 10.6²

La parte cuadrada de un número n es el mayor número cuadrado que divide a n. Por ejemplo, la parte cuadrada de 360 es 6.

Definir las funciones

parteLibre    :: Integer -> Integer
parteCuadrada :: Integer -> Integer

tales que

  • (parteLibre x) es la parte libre de x. Por ejemplo,
parteLibre 360                 ==  10
parteLibre 1800                ==  2
[parteLibre n | n <- [1..14]]  ==  [1,2,3,1,5,6,7,2,1,10,11,3,13,14]
  • (parteCuadrada x) es la parte cuadrada de x. Por ejemplo,
parteCuadrada 360                 ==  36
parteCuadrada 1800                ==  900
[parteCuadrada n | n <- [1..14]]  ==  [1,1,1,4,1,1,1,4,9,1,1,4,1,1]

Leer más…

La función indicatriz de Euler

Misceláneas

La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo, φ(36) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.

Definir la función

phi :: Integer -> Integer

tal que (phi n) es igual a φ(n). Por ejemplo,

phi 36                     ==  12
map phi [10..20]           ==  [4,10,4,12,6,8,8,16,6,18,8]
phi (3^10^5) `mod` (10^9)  ==  681333334

Comprobar con QuickCheck que, para todo n > 0, φ(10ⁿ) tiene n dígitos.

Leer más…

Fórmula dual

Misceláneas

Las fórmulas proposicionales construidas con las constantes verdadero (⊤), falso (⊥), las variables proposicionales y las conectivas de negación (¬), conjunción (∧) y disyunción (∨) se pueden definir usando el siguiente tipo de datos

data Prop = Const Bool
          | Var Char
          | Neg Prop
          | Conj Prop Prop
          | Disj Prop Prop
          deriving (Eq, Show)

Por ejemplo, la fórmula (A ∧ ⊥) ∨ (⊤ ∧ B) se representa por

Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))

La fórmula dual de una fórmula p es la fórmula obtenida intercambiando en p las ∧ por ∨ y también las ⊤ por ⊥. Por ejemplo, la dual de (A ∧ ⊥) ∨ (⊤ ∧ B) es (A ∨ ⊤) ∧ (⊥ ∨ B)

Definir la función

dual :: Prop -> Prop

tal que (dual p) es la dual de p. Por ejemplo,

λ> dual (Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B')))
Conj (Disj (Var 'A') (Const True)) (Disj (Const False) (Var 'B'))

Leer más…

Sucesión de suma de cuadrados de los dígitos

Misceláneas

Definir la función

sucSumaCuadradosDigitos :: Integer -> [Integer]

tal que (sucSumaCuadradosDigitos n) es la sucesión cuyo primer término es n y los restantes se obtienen sumando los cuadrados de los dígitos de su término anterior. Por ejemplo,

λ> take 20 (sucSumaCuadradosDigitos 2016)
[2016,41,17,50,25,29,85,89,145,42,20,4,16,37,58,89,145,42,20,4]
λ> take 20 (sucSumaCuadradosDigitos 1976)
[1976,167,86,100,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
λ> sucSumaCuadradosDigitos 2016 !! (10^8)
145

Leer más…