Numeración con múltiples bases
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.
Soluciones
import Test.QuickCheck decimalAmultiple :: [Int] -> Int -> [Int] decimalAmultiple bs n = reverse (aux bs n) where aux _ 0 = [] aux (b:bs) n = r : aux bs q where (q,r) = quotRem n b multipleAdecimal :: [Int] -> [Int] -> Int multipleAdecimal bs xs = sum (zipWith (*) (reverse xs) (1 : scanl1 (*) bs)) 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)