Exercitium 2024
Ejercicios en Haskell y Python
Índice
- 1. Representaciones de un número como suma de dos cuadrados
- 2. La serie de Thue-Morse
- 3. La sucesión de Thue-Morse
- 4. Huecos maximales entre primos
- 5. La función indicatriz de Euler
- 6. Ceros finales del factorial
- 7. Primos cubanos
- 8. Cuadrado más cercano
- 9. Suma de cadenas
- 10. Sistema factorádico de numeración
- 11. Duplicación de cada elemento
- 12. Suma fila del triángulo de los impares
- 13. Reiteración de suma de consecutivos
- 14. Producto de los elementos de la diagonal principal
- 15. Reconocimiento de potencias de 4
- 16. Exponente en la factorización
- 17. Mayor órbita de la sucesión de Collatz
- 18. Máximos locales
- 19. Caminos en un triángulo
1. Representaciones de un número como suma de dos cuadrados
Definir la función
representaciones :: Integer -> [(Integer,Integer)]
tal que representaciones n es la lista de pares de números naturales (x,y) tales que n = x² + y². Por ejemplo.
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] length (representaciones (10^14)) == 8
Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.
2. 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 <pre lang="text"> [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] </pre>
Definir la lista
serieThueMorse :: [[Int]]
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]
3. 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
[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
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
sucThueMorse :: [Int]
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
λ> 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
s(2n) = s(n) s(2n+1) = 1 - s(n)
4. 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
| 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)
5. La función indicatriz de Euler
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 length (show (phi (10^(10^5)))) == 100000
Comprobar con QuickCheck que, para todo n > 0, φ(10n) tiene n dígitos.
6. Ceros finales del factorial
Definir la función
cerosDelFactorial :: Integer -> Integer
tal que cerosDelFactorial n es el número de ceros en que termina el
factorial de n. Por ejemplo,
cerosDelFactorial 24 == 4 cerosDelFactorial 25 == 6 length (show (cerosDelFactorial (10^70000))) == 70000
7. 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
cubanos :: [Integer]
tal que sus elementos son los números cubanos. Por ejemplo,
λ> take 15 cubanos [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]
8. Cuadrado más cercano
Definir la función
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,
cuadradoCercano 2 == 1 cuadradoCercano 6 == 4 cuadradoCercano 8 == 9 cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000
9. Suma de cadenas
Definir la función
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,
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"
10. 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
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
factoradicoAdecimal :: String -> Integer decimalAfactoradico :: Integer -> String
tales que
- (factoradicoAdecimal cs) es el número decimal correspondiente al número factorádico cs. Por ejemplo,
λ> 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,
λ> 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,
factoradicoAdecimal (decimalAfactoradico n) == n
11. Duplicación de cada elemento
Definir la función
duplicaElementos :: [a] -> [a]
tal que (duplicaElementos xs) es la lista obtenida duplicando cada elemento de xs. Por ejemplo,
duplicaElementos [3,2,5] == [3,3,2,2,5,5] duplicaElementos "Haskell" == "HHaasskkeellll"
12. Suma fila del triángulo de los impares
Se condidera el siguiente triángulo de números impares
1
3 5
7 9 11
13 15 17 19
21 23 25 27 29
...
Definir la función
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,
sumaFilaTrianguloImpares 1 == 1 sumaFilaTrianguloImpares 2 == 8 length (show (sumaFilaTrianguloImpares (10^500))) == 1501 length (show (sumaFilaTrianguloImpares (10^5000))) == 15001 length (show (sumaFilaTrianguloImpares (10^50000))) == 150001
13. 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 + 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 + 5 = 6
\
==> 14
/ \
5 + 3 = 8 ==> 29
\ /
==> 15
/
3 + 4 = 7
Definir la función
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,
sumaReiterada [1,5,3] == 14 sumaReiterada [1,5,3,4] == 29
14. 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
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,
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
15. Reconocimiento de potencias de 4
Definir la función
esPotenciaDe4 :: Integral a => a -> Bool
tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,
esPotenciaDe4 16 == True esPotenciaDe4 17 == False esPotenciaDe4 (4^(4*10^5)) == True esPotenciaDe4 (1 + 4^(4*10^5)) == False
16. Exponente en la factorización
Definir la función
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,
exponente 2 24 == 3 exponente 3 24 == 1 exponente 6 24 == 0 exponente 7 24 == 0
17. 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
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
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,
mayoresGeneradores 20 == [18,19] mayoresGeneradores (10^6) == [837799]
18. 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
maximosLocales :: Ord a => [a] -> [a]
tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,
maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6] maximosLocales [1..100] == [] maximosLocales "adbpmqexyz" == "dpq"
19. Caminos en un triángulo
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
3 7 4 2 4 6 8 5 9 3
se representa por
[[3],[7,4],[2,4,6],[8,5,9,3]]
Definir la función
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,
λ> 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]]