El algoritmo de Moessner en Haskell
La presente relación de ejercicios está basada en el artículo El algoritmo de Moessner escrito por Antonio Roldán Martínez en su blog Números y hoja de cálculo.
El proceso de Moessner de orden n consiste en lo siguiente: De la lista de los números naturales, se tacha los elementos que ocupan las posiciones n, 2*n, … y se forma la sucesión de las sumas parciales de los restantes elementos. De la resultante sucesión se tacha los elementos que ocupan las posiciones n-1, 2*(n-1), … y se forma la sucesión de las sumas parciales de los restantes elementos. El proceso se repite n-1 veces. Por ejemplo, para n=2:
|
1 2 3 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... [Inicial] 1 3 5 7 9 11 13 15 ... [Elimina 2] 1 4 9 16 25 36 49 64 ... [Sumas acumuladas] |
Se observa que los elementos de la última es la sucesión de los cuadrados. Para n=3, el proceso de Moessner es
|
1 2 3 4 5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... [Inicial] 1 2 4 5 7 8 10 11 13 14 16 ... [Elimina 3] 1 3 7 12 19 27 37 48 61 75 91 ... [Sumas acumuladas] 1 7 19 37 61 91 ... [Elimina 2] 1 8 27 64 125 216 ... [Sumas acumuladas] |
Se observa que los elementos de la última es la sucesión de los cubos. Para n=4, el proceso de Moessner es
|
1 2 3 4 5 6 7 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... [Inicial] 1 2 3 5 6 7 9 10 11 13 14 15 ... [Elimina 4] 1 3 6 11 17 24 33 43 54 67 81 96 ... [Sumas acumuladas] 1 3 11 17 33 43 67 81 ... [Elimina 3] 1 4 15 32 65 108 175 256 ... [Sumas acumuladas] 1 15 65 175 ... [Elimina 2] 1 16 81 256 ... [Sumas acumuladas] |
Se observa que los elementos de la última es la sucesión de los cuartas potencias. El teorema de Moessner afirma que para cualquier n, la sucesión obtenida mediante el proceso de Moessner es la de las potencias n-ésimas; es decir
El objetivo de los siguientes ejercicios es definir en Haskell una función que simule el proceso de Moessner y comprobar el teorema.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
-- --------------------------------------------------------------------- -- Ejercicio 1, Definir la función -- eliminaPosiciones :: Int -> [Integer] -> [Integer] -- tal que (eliminaPosiciones n xs) es la lista obtenida eliminando en -- xs los elementos que ocupan las posiciones n, 2*n, 3*n, .... Por -- ejemplo, -- eliminaPosiciones 3 [1..10] == [1,2,4,5,7,8,10] -- --------------------------------------------------------------------- eliminaPosiciones :: Int -> [Integer] -> [Integer] eliminaPosiciones _ [] = [] eliminaPosiciones n xs = take (n-1) xs ++ eliminaPosiciones n (drop n xs) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- sumaAcumulada :: [Integer] -> [Integer] -- tal que (sumaAcumulada xs) es la lista de las sumas acumuladas de los -- elementos de xs. Por ejemplo, -- sumaAcumulada [1,2,4,5,7,8,10] == [1,3,7,12,19,27,37] -- --------------------------------------------------------------------- sumaAcumulada :: [Integer] -> [Integer] sumaAcumulada = scanl1 (+) -- Puede definirse sin usar scanl: sumaAcumulada1 :: [Integer] -> [Integer] sumaAcumulada1 [x] = [x] sumaAcumulada1 ys@(x:xs) = x : zipWith (+) (sumaAcumulada1 ys) xs -- También puede definirse sin usar zipWith sumaAcumulada2 :: [Integer] -> [Integer] sumaAcumulada2 [x] = [x] sumaAcumulada2 ys@(x:xs) = x : [a+b | (a,b) <- zip (sumaAcumulada2 ys)xs] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- moessner :: Int -> [Integer] -- tal que (moessner n) es la sucesión obtenida aplicando el proceso de -- Moessner de orden n. Por ejemplo, -- take 5 (moessner 4) == [1,16,81,256,625] -- --------------------------------------------------------------------- moessner :: Int -> [Integer] moessner n = aux n [1..] where aux 1 xs = xs aux k xs = aux (k-1) (sumaAcumulada (eliminaPosiciones k xs)) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- prop_moessner :: Int -> Int -> Bool -- tal que (prop_moessner n m) se verifica si la lista de los m primeros -- términos de (moessner n) es [1,2^n,...,m^n]. -- --------------------------------------------------------------------- prop_moessner :: Int -> Int -> Bool prop_moessner n m = take m (moessner n) == take m [x^n | x <- [1..]] -- --------------------------------------------------------------------- -- Ejercicio 5. Comprobar que para todo n <= 100, la lista de los 5 primeros -- términos de (moessner n) es [1,2^n,...,5^n]. -- --------------------------------------------------------------------- -- La comprobación es -- ghci> and [prop_moessner n 5 | n <- [1..100]] -- True |
Referencias
- J.H. Conway y R.K. Guy Moessner’s magic. En “The Book of Numbers” pp. 63-65
- J.H. Conway y T. HsuSome Very interesting sequences.
- R. Hinze Scans and convolutions. A calculational proof of Moessner’s theorem.
- D. Kozen y A. Silva On Moessner’s theorem.
- M.A. Lerma La magia de Moessner.
- C.T. Long A note on Moessner’s process
- A. Roldán El algoritmo de Moessner.
- E.W. Weisstein Moessner’s theorem.