Sea \(\{b_i \mid i \geq 1\}\) una sucesión infinita de números enteros mayores que 1. Entonces, todo entero \(x\) mayor que cero se puede escribir de forma única como \[ x = x_0 + x_1 b_1 + x_2 b_1 b_2 + \dots + x_n b_1 b_2 \dotsm b_n, \] donde cada \(x_i\) satisface la condición \(0 \leq x_i < b_{i+1}\). Se dice que \([x_n, x_{n-1}, \dots, x_2, x_1, x_0]\) es la representación de \(x\) en la base \((b_i).

Por ejemplo, la representación de 377 en la base \((2i)_{i \geq 1}\) es \([7,5,0,1]\), ya que \[ 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6, \] y además: \[ 0 \leq 1 < 2, \quad 0 \leq 0 < 4, \quad 0 \leq 5 < 6, \quad 0 \leq 7 < 8. \]

Definir las funciones

decimalAmultiple :: [Int] -> Int -> [Int]
multipleAdecimal :: [Int] -> [Int] -> Int

tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,

decimalAmultiple [2,4..] 377                      ==  [7,5,0,1]
multipleAdecimal [2,4..] [7,5,0,1]                ==  377
decimalAmultiple [2,5..] 377                      ==  [4,5,3,1]
multipleAdecimal [2,5..] [4,5,3,1]                ==  377
decimalAmultiple [2^n | n <- [1..]] 2015          ==  [1,15,3,3,1]
multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1]  ==  2015
decimalAmultiple (repeat 10) 2015                 ==  [2,0,1,5]
multipleAdecimal (repeat 10) [2,0,1,5]            ==  2015

Comprobar con QuickCheck que se verifican las siguientes propiedades

prop_inversas :: [Int] -> Int -> Property
prop_inversas bs x =
    x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x

prop_coeficientes :: [Int] -> Int -> Property
prop_coeficientes bs x =
    x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs]
    where cs = reverse (decimalAmultiple bs x)

para distintas bases dadas. Por ejemplo,

λ> quickCheck (prop_inversas [2,4..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_inversas [3,5..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_coeficientes [2,4..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_coeficientes [3,5..])
+++ OK, passed 100 tests.

Leer más…

La diferencia progresiva entre dos elementos de una lista es la resta entre el que ocupa la mayor posición y la menor. Por ejemplo, en la lista [1,5,8,2,9] la diferencia entre los elementos 5 y 8 es 3 y entre 5 y 2 es -3.

Definir la función

mayorDiferencia :: [Int] -> Int

tal que (mayorDiferencia xs) es la mayor diferencia progresiva entre los elementos de xs. Por ejemplo,

mayorDiferencia [1,5,8,2,9]  ==  8
mayorDiferencia [9,5,8,2,1]  ==  3
mayorDiferencia [3,2,1]      ==  0
mayorDiferencia [1..10^7]    ==  9999999

Leer más…

Los conjuntos de polinomios se pueden representar por listas de listas de la misma longitud. Por ejemplo, los polinomios 3x²+5x+9, 10x³+9 y 8x³+5x²+x-1 se pueden representar por las listas [0,3,5,9], [10,0,0,9] y [8,5,1,-1].

Definir la función

sumaPolinomios :: Num a => [[a]] -> [a]

tal que (sumaPolinomios ps) es la suma de los polinomios ps. Por ejemplo,

λ> sumaPolinomios1 [[0,3,5,9],[10,0,0,9],[8,5,1,-1]]
[18,8,6,17]
λ> sumaPolinomios6 (replicate 1000000 (replicate 3 1))
[1000000,1000000,1000000]

Leer más…

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

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…

Definir la función

nMinimoCambios :: Ord a => [a] -> Int

tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,

nMinimoCambios [3,5,3,7,9,6]      ==  4
nMinimoCambios [3,5,3,7,3,3]      ==  2
nMinimoCambios "Salamanca"        ==  5
nMinimoCambios (4 : [1..500000])  ==  499999

En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.

Leer más…

Definir la función

diagonalesSecundarias :: Matriz a -> [[a]]

tal que (diagonalesSecundarias p) es la lista de las diagonales secundarias de p. Por ejemplo, para la matriz

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

la lista de sus diagonales secundarias es

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

En Haskell,

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

Leer más…

La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.

Definir las funciones

densidades :: Int -> (Double,Double,Double)
graficas   :: Imt -> IO ()

tales que

• (densidades n) es la terna formada por la n-ésima densidad de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,

densidades 100     ==  (0.22,    2.0e-2, 0.76)
densidades 1000    ==  (0.246,   3.0e-3, 0.751)
densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)
densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)

• (graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

y (graficas 400) dibuja

Leer más…

Definir la función

sumaDivisoresHasta :: Integer -> [(Integer,Integer)]

tal que (sumaDivisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 1 y n y b es la suma de los divisores propios de a. Por ejemplo,

λ> sumaDivisoresHasta 12
[(1,0),(2,1),(3,1),(4,3),(5,1),(6,6),(7,1),(8,7),(9,4),(10,8),(11,1),(12,16)]
λ> maximum (map snd (sumaDivisoresHasta 123456))
368640

Leer más…

Definir la función

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

tal que (divisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 2 y n y b es un divisor propio de a. Por ejemplo,

λ> divisoresHasta 6
[(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)]
λ> divisoresHasta 8
[(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)]
λ> length (divisoresHasta 1234567)
16272448

Leer más…

La conjetura de Waring sobre los números primos establece que todo número impar es primo o la suma de tres primos. La conjetura de Goldbach afirma que todo número par mayor que 2 es la suma de dos números primos. Ambos problemas siguen abiertos después de más de 200 años. En este problema no se propone su solución, sino una tarea más simple: buscar una manera de expresar los enteros mayores que 7 como suma de exactamente cuatro números primos; es decir, definir la función

suma4primos :: Integer -> (Integer,Integer,Integer,Integer)

tal que (suma4primos n) es una cuádrupla (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,

suma4primos 24             ==  (2,2,3,17)
suma4primos 1234567890123  ==  (2,3,29,1234567890089)

Comprobar con QuickCheck que suma4primos es correcta; es decir si (suma4primos n) es (a,b,c,d) entonces los números a, b c y d son primos y su suma es n.

Nota: Para cada n pueden existir distintas cuádruplas que cumplan la especificación. Por ejemplo, para el 16 hay tres: (2,2,5,7), (3,3,3,7) y (3,3,5,5). Cualquiera de ellas se admite como solución.

Leer más…