Ir al contenido principal

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

Misceláneas

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]                ==  5
ausente [3,5,9,11]                ==  7
ausente [3,5,7,11]                ==  9
ausente ([1..9]++[11..])          ==  10
ausente2 ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay exactamente un término de la progresión aritmética que no está en la lista.

Leer más…

Matriz zigzagueante

Misceláneas

La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es

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

La colocación de los elementos se puede ver gráficamente en Matriz zigzagueante

Definir la función

zigZag :: Int -> Array (Int,Int) Int

tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,

λ> elems (zigZag 3)
[0,1,5, 2,4,6, 3,7,8]
λ> elems (zigZag 4)
[0,1,5,6, 2,4,7,12, 3,8,11,13, 9,10,14,15]
λ> elems (zigZag 5)
[0,1,5,6,14, 2,4,7,13,15, 3,8,12,16,21, 9,11,17,20,22, 10,18,19,23,24]
λ> take 15 (elems (zigZag 1000))
[0,1,5,6,14,15,27,28,44,45,65,66,90,91,119]

Leer más…

Mínima diferencia entre elementos de una lista

Misceláneas

Definir la función

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

tal que (minimaDiferencia xs) es el menor valor absoluto de las diferencias entre todos los pares de elementos de xs (que se supone que tiene al menos 2 elementos). Por ejemplo,

minimaDiferencia [1,5,3,19,18,25]  ==  1
minimaDiferencia [30,5,20,9]       ==  4
minimaDiferencia [30,5,20,9,5]     ==  0
minimaDiferencia [1..10^6]         ==  1

En el primer ejemplo la menor diferencia es 1 y se da entre los elementos 19 y 18; en el 2ª es 4 entre los elementos 5 y 9 y en la 3ª es 0 porque el elemento 5 está repetido.

Leer más…

Números como sumas de primos consecutivos

Misceláneas

En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas

41 =  2 +  3 +  5 + 7 + 11 + 13
41 = 11 + 13 + 17

el 240 se puede escribir de tres formas

240 =  17 +  19 + 23 + 29 + 31 + 37 + 41 + 43
240 =  53 +  59 + 61 + 67
240 = 113 + 127

y el 311 se puede escribir de 4 formas

311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
311 =  53 +  59 +  61 + 67 + 71
311 = 101 + 103 + 107

Definir la función

sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,

λ> sumas 41
[[2,3,5,7,11,13],[11,13,17]]
λ> sumas 240
[[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]
λ> sumas 311
[[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],[53,59,61,67,71],[101,103,107]]
λ> maximum [length (sumas n) | n <- [1..600]]
4

Leer más…

Suma de los elementos de las diagonales matrices espirales

Misceláneas

Empezando con el número 1 y moviéndose en el sentido de las agujas del reloj se obtienen las matrices espirales

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

La suma los elementos de sus diagonales es

  • en la 2x2: 1+3+2+4 = 10
  • en la 3x3: 1+3+5+7+9 = 25
  • en la 4x4: 1+2+3+4+7+10+13+16 = 56
  • en la 5x5: 1+3+5+7+9+13+17+21+25 = 101

Definir la función

sumaDiagonales :: Integer -> Integer

tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.

sumaDiagonales 1         ==  1
sumaDiagonales 2         ==  10
sumaDiagonales 3         ==  25
sumaDiagonales 4         ==  56
sumaDiagonales 5         ==  101
sumaDiagonales (1+10^6)  ==  666669166671000001
sumaDiagonales (10^2)    ==         671800
sumaDiagonales (10^3)    ==        667168000
sumaDiagonales (10^4)    ==       666716680000
sumaDiagonales (10^5)    ==      666671666800000
sumaDiagonales (10^6)    ==     666667166668000000
sumaDiagonales (10^7)    ==    666666716666680000000
sumaDiagonales (10^8)    ==   666666671666666800000000
sumaDiagonales (10^9)    ==  666666667166666668000000000

Comprobar con QuickCheck que el último dígito de (sumaDiagonales n) es 0, 4 ó 6 si n es par y es 1, 5 ó 7 en caso contrario.

Leer más…

Descomposiciones con sumandos 1 ó 2

Misceláneas

Definir la funciones

sumas  :: Int -> [[Int]]
nSumas :: Int -> Integer

tales que

  • (sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
sumas 1            ==  [[1]]
sumas 2            ==  [[1,1],[2]]
sumas 3            ==  [[1,1,1],[1,2],[2,1]]
sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
length (sumas 26)  ==  196418
length (sumas 33)  ==  5702887
  • (nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
nSumas 4                      ==  5
nSumas 123                    ==  36726740705505779255899443
length (show (nSumas 123456)) ==  25801

Leer más…

Caminos reducidos

Misceláneas

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Leer más…

Primos permutables

Misceláneas

Un primo permutable es un número primo tal que todos los números obtenidos permutando sus cifras son primos. Por ejemplo, 337 es un primo permutable ya que 337, 373 y 733 son primos.

Definir las funciones

esPrimoPermutable :: Integer -> Bool
primosPermutables :: [Integer]

tales que

  • (esPrimoPermutable x) se verifica si x es un primo permutable. Por ejemplo,
esPrimoPermutable 97  ==  True
esPrimoPermutable 337 ==  True
esPrimoPermutable 23  ==  False
  • primosPermutables es la lista de los primos permutables. Por ejemplo,
λ> take 20 primosPermutables
[2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,199,311,337,373,733]

Leer más…

Números de Lucas

Misceláneas

Los números de Lucas son los elementos de la sucesión L(n) definida por

L(0) = 2
L(1) = 1
L(n) = L(n-1) + L(n-2), si n > 1.

Los primeros números de Lucas son

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

Definir las funciones

nLucas :: Integer -> Integer
lucas  :: [Integer]

tales que

  • (nLucas n) es el n-ésimo número de Lucas. Por ejemplo,
nLucas 5                       ==  11
nLucas 32                      ==  4870847
length (show (nLucas (10^5)))  ==  20899
  • lucas es la lista de los números de Lucas. Por ejemplo,
take 11 lucas ==  [2,1,3,4,7,11,18,29,47,76,123]

Leer más…

Inverso multiplicativo modular

Misceláneas

El inverso multiplicativo modular de un entero n módulo p es el número m, entre 1 y p-1, tal que

mn = 1 (mod p)

Por ejemplo, el inverso multiplicativo de 2 módulo 5 es 3, ya que 1 <= 3 <= 4 y 2x3 = 1 (mod 5).

El inverso multipicativo de n módulo p existe si y sólo si n y p son coprimos; es decir, si mcd(n,p) = 1.

Definir la función

invMod :: Integer -> Integer -> Maybe Integer

tal que (invMod n p) es justo el inverso multiplicativo de n módulo p, si existe y Nothing en caso contrario. Por ejemplo,

λ> invMod 2 5
Just 3
λ> invMod 2 6
Nothing
λ> [(x,invMod x 5) | x <- [0..4]]
[(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]
λ> [(x,invMod x 6) | x <- [0..5]]
[(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]
λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)
True

Leer más…