Menu Close

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 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 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  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 1^n, 2^n, 3^n, 4^n, \dots

El objetivo de los siguientes ejercicios es definir en Haskell una función que simule el proceso de Moessner y comprobar el teorema.

-- ---------------------------------------------------------------------
-- 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

  1. J.H. Conway y R.K. Guy Moessner’s magic. En “The Book of Numbers” pp. 63-65
  2. J.H. Conway y T. HsuSome Very interesting sequences.
  3. R. Hinze Scans and convolutions. A calculational proof of Moessner’s theorem.
  4. D. Kozen y A. Silva On Moessner’s theorem.
  5. M.A. Lerma La magia de Moessner.
  6. C.T. Long A note on Moessner’s process
  7. A. Roldán El algoritmo de Moessner.
  8. E.W. Weisstein Moessner’s theorem.
Haskell