Continuación de Exercitium en GitHub
A partir del 29 de mayo de 2024, los nuevos problemas se publicarán en Exercitium en GitHub.
Descomposiciones triangulares
Los números triangulares se forman como sigue
|
1 2 3 4 |
* * * * * * * * * * 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 2 3 4 5 |
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5 |
Definir la función
|
1 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
λ> descomposicionesTriangulares 4 [] λ> descomposicionesTriangulares 5 [(1,1,3)] λ> descomposicionesTriangulares 12 [(1,1,10),(3,3,6)] λ> descomposicionesTriangulares 30 [(1,1,28),(3,6,21),(10,10,10)] λ> descomposicionesTriangulares 61 [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] λ> descomposicionesTriangulares 52 [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] λ> descomposicionesTriangulares 82 [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)] λ> length (descomposicionesTriangulares (5*10^5)) 124 |
Conjunto de primos relativos
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
|
1 |
primosRelativos :: [Int] -> Bool |
tal que primosRelativos xs se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,
|
1 2 3 4 5 6 |
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 |
Diferencia simétrica
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
|
1 |
diferenciaSimetrica :: Ord a => [a] -> [a] -> [a] |
tal que diferenciaSimetrica xs ys es la diferencia simétrica de xs e ys. Por ejemplo,
|
1 2 3 4 5 |
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] |
Matrices de Toepliz
Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,
|
1 2 3 4 |
|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
|
1 2 3 |
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
|
1 |
esToeplitz :: Eq a => Array (Int,Int) a -> Bool |
tal que esToeplitz p se verifica si la matriz p es de Toeplitz. Por ejemplo,
|
1 2 |
esToeplitz ej1 == True esToeplitz ej2 == False |
Diagonales principales de una matriz
La lista de las diagonales principales de la matriz
|
1 2 3 |
1 2 3 4 5 6 7 8 9 10 11 12 |
es
|
1 |
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] |
Definir la función
|
1 |
diagonalesPrincipales :: Array (Int,Int) a -> [[a]] |
tal que diagonalesPrincipales p es la lista de las diagonales principales de p. Por ejemplo,
|
1 2 |
λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] |
Posiciones de las diagonales principales
Las posiciones de una matriz con 3 filas y 4 columnas son
|
1 2 3 |
(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
|
1 2 3 4 5 6 |
[(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
|
1 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
λ> 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)] |
Números triangulares con n cifras distintas
Los números triangulares se forman como sigue
|
1 2 3 4 |
* * * * * * * * * * 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 2 3 4 5 |
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5 |
Definir la función
|
1 |
triangularesConCifras :: Int -> [Integer] |
tal que triangularesConCifras n es la lista de los números triangulares con n cifras distintas. Por ejemplo,
|
1 2 3 4 5 |
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] |
Numeración de las ternas de números naturales
Las ternas de números naturales se pueden ordenar como sigue
|
1 2 3 4 5 |
(0,0,0), (0,0,1),(0,1,0),(1,0,0), (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0), (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),... ... |
Definir la función
|
1 |
posicion :: (Int,Int,Int) -> Int |
tal que posicion (x,y,z) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,
|
1 2 3 |
posicion (0,1,0) == 2 posicion (0,0,2) == 4 posicion (0,1,1) == 5 |
Comprobar con QuickCheck que
- la posición de (x,0,0) es x(x²+6x+11)/6
- la posición de (0,y,0) es y(y²+3y+ 8)/6
- la posición de (0,0,z) es z(z²+3z+ 2)/6
- la posición de (x,x,x) es x(9x²+14x+7)/2
Primos equidistantes
Definir la función
|
1 |
primosEquidistantes :: Integer -> [(Integer,Integer)] |
tal que primosEquidistantes k es la lista de los pares de primos cuya diferencia es k. Por ejemplo,
|
1 2 3 4 5 |
take 3 (primosEquidistantes 2) == [(3,5),(5,7),(11,13)] take 3 (primosEquidistantes 4) == [(7,11),(13,17),(19,23)] take 3 (primosEquidistantes 6) == [(23,29),(31,37),(47,53)] take 3 (primosEquidistantes 8) == [(89,97),(359,367),(389,397)] primosEquidistantes 4 !! (10^5) == (18467047,18467051) |
Números amigos
Dos números amigos son dos números positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.
Definir la función
|
1 |
amigos :: Integer -> Integer -> Bool |
tal que amigos x y se verifica si los números x e y son amigos. Por ejemplo,
|
1 2 3 |
amigos 220 284 == True amigos 220 23 == False amigos 42262694537514864075544955198125 42405817271188606697466971841875 == True |
Máxima suma de caminos en un triángulo
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
|
1 2 3 4 |
3 7 4 2 4 6 8 5 9 3 |
se representa por
|
1 |
[[3],[7,4],[2,4,6],[8,5,9,3]] |
Definir la función
|
1 |
maximaSuma :: [[Integer]] -> Integer |
tal que (maximaSuma xss) es el máximo de las sumas de los de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
maximaSuma [[3],[7,4]] == 10 maximaSuma [[3],[7,4],[2,4,6]] == 14 maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]] == 23 maximaSuma [[n..n+n] | n <- [0..100]] == 10100 maximaSuma [[n..n+n] | n <- [0..1000]] == 1001000 maximaSuma [[n..n+n] | n <- [0..2000]] == 4002000 maximaSuma [[n..n+n] | n <- [0..3000]] == 9003000 maximaSuma [[n..n+n] | n <- [0..4000]] == 16004000 |
Caminos en un triángulo
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
|
1 2 3 4 |
3 7 4 2 4 6 8 5 9 3 |
se representa por
|
1 |
[[3],[7,4],[2,4,6],[8,5,9,3]] |
Definir la función
|
1 |
caminos :: [[a]] -> [[a]] |
tal que (caminos xss) es la lista de los caminos en el triángulo donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,
|
1 2 3 4 5 6 |
λ> caminos [[3],[7,4]] [[3,7],[3,4]] λ> caminos [[3],[7,4],[2,4,6]] [[3,7,2],[3,7,4],[3,4,4],[3,4,6]] λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]] [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]] |
Máximos locales
Un máximo local de una lista es un elemento de la lista que es mayor que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).
Definir la función
|
1 |
maximosLocales :: Ord a => [a] -> [a] |
tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,
|
1 2 3 |
maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6] maximosLocales [1..100] == [] maximosLocales "adbpmqexyz" == "dpq" |
Mayor órbita de la sucesión de Collatz
Se considera la siguiente operación, aplicable a cualquier número entero positivo:
- Si el número es par, se divide entre 2.
- Si el número es impar, se multiplica por 3 y se suma 1.
Dado un número cualquiera, podemos calcular su órbita; es decir, las imágenes sucesivas al iterar la función. Por ejemplo, la órbita de 13 es
|
1 |
13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,... |
Si observamos este ejemplo, la órbita de 13 es periódica, es decir,
se repite indefinidamente a partir de un momento dado). La conjetura
de Collatz dice que siempre alcanzaremos el 1 para cualquier número
con el que comencemos. Ejemplos:
- Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.
- Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
- Empezando en n = 27, la sucesión tiene 112 pasos, llegando hasta
9232 antes de descender a 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Definir la función
|
1 |
mayoresGeneradores :: Integer -> [Integer] |
tal que (mayoresGeneradores n) es la lista de los números menores o iguales que n cuyas órbitas de Collatz son las de mayor longitud. Por ejemplo,
|
1 2 |
mayoresGeneradores 20 == [18,19] mayoresGeneradores (10^6) == [837799] |
Exponente en la factorización
Definir la función
|
1 |
exponente :: Integer -> Integer -> Int |
tal que (exponente x n) es el exponente de x en la factorización prima de n (se supone que x > 1 y n > 0). Por ejemplo,
|
1 2 3 4 |
exponente 2 24 == 3 exponente 3 24 == 1 exponente 6 24 == 0 exponente 7 24 == 0 |
Reconocimiento de potencias de 4
Definir la función
|
1 |
esPotenciaDe4 :: Integral a => a -> Bool |
tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,
|
1 2 3 4 |
esPotenciaDe4 16 == True esPotenciaDe4 17 == False esPotenciaDe4 (4^(4*10^5)) == True esPotenciaDe4 (1 + 4^(4*10^5)) == False |
Producto de los elementos de la diagonal principal
Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.
Definir la función
|
1 |
productoDiagonalPrincipal :: Num a => [[a]] -> a |
tal que (productoDiagonalPrincipal xss) es el producto de los elementos de la diagonal principal de la matriz cuadrada xss. Por ejemplo,
|
1 2 3 |
productoDiagonal [[3,5,2],[4,7,1],[6,9,8]] == 168 productoDiagonal (replicate 5 [1..5]) == 120 length (show (productoDiagonal (replicate 30000 [1..30000]))) == 121288 |
Read More «Producto de los elementos de la diagonal principal»
Reiteración de suma de consecutivos
La reiteración de la suma de los elementos consecutivos de la lista [1,5,3] es 14 como se explica en el siguiente diagrama
|
1 2 3 4 5 |
1 + 5 = 6 \ ==> 14 / 5 + 3 = 8 |
y la de la lista [1,5,3,4] es 29 como se explica en el siguiente diagrama
|
1 2 3 4 5 6 7 8 9 |
1 + 5 = 6 \ ==> 14 / \ 5 + 3 = 8 ==> 29 \ / ==> 15 / 3 + 4 = 7 |
Definir la función
|
1 |
sumaReiterada :: Num a => [a] -> a |
tal que (sumaReiterada xs) es la suma reiterada de los elementos consecutivos de la lista no vacía xs. Por ejemplo,
|
1 2 |
sumaReiterada [1,5,3] == 14 sumaReiterada [1,5,3,4] == 29 |
Suma fila del triángulo de los impares
Se condidera el siguiente triángulo de números impares
|
1 2 3 4 5 6 |
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 ... |
Definir la función
|
1 |
sumaFilaTrianguloImpares :: Integer -> Integer |
tal que (sumaFilaTrianguloImpares n) es la suma de la n-ésima fila del triángulo de los números impares. Por ejemplo,
|
1 2 3 4 5 |
sumaFilaTrianguloImpares 1 == 1 sumaFilaTrianguloImpares 2 == 8 length (show (sumaFilaTrianguloImpares (10^500))) == 1501 length (show (sumaFilaTrianguloImpares (10^5000))) == 15001 length (show (sumaFilaTrianguloImpares (10^50000))) == 150001 |
Duplicación de cada elemento
Definir la función
|
1 |
duplicaElementos :: [a] -> [a] |
tal que (duplicaElementos xs) es la lista obtenida duplicando cada elemento de xs. Por ejemplo,
|
1 2 |
duplicaElementos [3,2,5] == [3,3,2,2,5,5] duplicaElementos "Haskell" == "HHaasskkeellll" |
Sistema factorádico de numeración
El sistema factorádico es un sistema numérico basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el número «341010» en el sistema factorádico es 463 en el sistema decimal ya que
|
1 |
3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463 |
En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente.
Con los dígitos del 0 al 9 el mayor número que podemos codificar es el 10!-1 = 3628799. En cambio, si lo ampliamos con las letras A a Z podemos codificar hasta 36!-1 = 37199332678990121746799944815083519999999910.
Definir las funciones
|
1 2 |
factoradicoAdecimal :: String -> Integer decimalAfactoradico :: Integer -> String |
tales que
- (factoradicoAdecimal cs) es el número decimal correspondiente al número factorádico cs. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> factoradicoAdecimal "341010" 463 λ> factoradicoAdecimal "2441000" 2022 λ> factoradicoAdecimal "A0000000000" 36288000 λ> map factoradicoAdecimal ["10","100","110","200","210","1000","1010","1100","1110","1200"] [1,2,3,4,5,6,7,8,9,10] λ> factoradicoAdecimal "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210" 37199332678990121746799944815083519999999 |
- (decimalAfactoradico n) es el número factorádico correpondiente al número decimal n. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> decimalAfactoradico 463 "341010" λ> decimalAfactoradico 2022 "2441000" λ> decimalAfactoradico 36288000 "A0000000000" λ> map decimalAfactoradico [1..10] ["10","100","110","200","210","1000","1010","1100","1110","1200"] λ> decimalAfactoradico 37199332678990121746799944815083519999999 "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210" |
Comprobar con QuickCheck que, para cualquier entero positivo n,
|
1 |
factoradicoAdecimal (decimalAfactoradico n) == n |
Suma de cadenas
Definir la función
|
1 |
sumaCadenas :: String -> String -> String |
tal que sumaCadenas xs ys es la cadena formada por el número que es la suma de los números enteros cuyas cadenas que lo representan son xs e ys; además, se supone que la cadena vacía representa al cero. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
sumaCadenas "2" "6" == "8" sumaCadenas "14" "2" == "16" sumaCadenas "14" "-5" == "9" sumaCadenas "-14" "-5" == "-19" sumaCadenas "5" "-5" == "0" sumaCadenas "" "5" == "5" sumaCadenas "6" "" == "6" sumaCadenas "" "" == "0" |
Cuadrado más cercano
Definir la función
|
1 |
cuadradoCercano :: Integer -> Integer |
tal que cuadradoCercano n es el número cuadrado más cercano a n, donde n es un entero positivo. Por ejemplo,
|
1 2 3 4 |
cuadradoCercano 2 == 1 cuadradoCercano 6 == 4 cuadradoCercano 8 == 9 cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000 |
Primos cubanos
Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.
Definir la sucesión
|
1 |
cubanos :: [Integer] |
tal que sus elementos son los números cubanos. Por ejemplo,
|
1 2 |
λ> take 15 cubanos [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269] |
Ceros finales del factorial
Definir la función
|
1 |
cerosDelFactorial :: Integer -> Integer |
tal que cerosDelFactorial n es el número de ceros en que termina el factorial de n. Por ejemplo,
|
1 2 3 |
cerosDelFactorial 24 == 4 cerosDelFactorial 25 == 6 length (show (cerosDelFactorial (10^70000))) == 70000 |
La función indicatriz de Euler
La indicatriz de Euler (también 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
|
1 |
phi :: Integer -> Integer |
tal que phi n es igual a φ(n). Por ejemplo,
|
1 2 3 4 |
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 length (show (phi (10^(10^5)))) == 100000 |
Comprobar con QuickCheck que, para todo n > 0, φ(10^n) tiene n dígitos.
Read More «La función indicatriz de Euler»
Huecos maximales entre primos
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
|
1 2 3 4 5 |
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
|
1 2 3 4 5 6 7 8 9 |
Primo Hueco 2 1 3 2 7 4 23 6 89 8 113 14 523 18 887 20 |
Definir la sucesión
|
1 |
primosYhuecosMaximales :: [(Integer,Integer)] |
cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,
|
1 2 3 4 |
λ> take 8 primosYhuecosMaximales [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)] λ> primosYhuecosMaximales !! 20 (2010733,148) |
La sucesión de Thue-Morse
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son
|
1 2 3 4 5 |
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] |
De esta forma se va formando una sucesión
|
1 |
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,... |
que se conoce como la sucesión de Thue-Morse.
Definir la sucesión
|
1 |
sucThueMorse :: [Int] |
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
|
1 2 3 4 5 6 |
λ> take 30 sucThueMorse [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0] λ> map (sucThueMorse4 !!) [1234567..1234596] [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0] λ> map (sucThueMorse4 !!) [4000000..4000030] [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1] |
Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces
|
1 2 |
s(2n) = s(n) s(2n+1) = 1 - s(n) |
La serie de Thue-Morse
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros términos de la serie son
|
1 2 3 4 5 |
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] |
Definir la lista
|
1 |
serieThueMorse :: [[Int]] |
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
|
1 2 |
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]] |