{"id":2059,"date":"2012-05-30T12:21:54","date_gmt":"2012-05-30T12:21:54","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2059"},"modified":"2014-01-17T18:28:13","modified_gmt":"2014-01-17T17:28:13","slug":"el-algoritmo-de-moessner-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-algoritmo-de-moessner-en-haskell\/","title":{"rendered":"El algoritmo de Moessner en Haskell"},"content":{"rendered":"

La presente relaci\u00f3n de ejercicios est\u00e1 basada en el art\u00edculo El algoritmo de Moessner<\/a> escrito por Antonio Rold\u00e1n Mart\u00ednez en su blog N\u00fameros y hoja de c\u00e1lculo<\/a>.<\/p>\n

El proceso de Moessner de orden n consiste en lo siguiente: De la lista de los n\u00fameros naturales, se tacha los elementos que ocupan las posiciones n, 2*n, … y se forma la sucesi\u00f3n de las sumas parciales de los restantes elementos. De la resultante sucesi\u00f3n se tacha los elementos que ocupan las posiciones n-1, 2*(n-1), … y se forma la sucesi\u00f3n de las sumas parciales de los restantes elementos. El proceso se repite n-1 veces. Por ejemplo, para n=2: <\/p>\n

\r\n1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 ...  [Inicial]\r\n1   3   5    7     9    11    13    15    ...  [Elimina 2]\r\n1   4   9   16    25    36    49    64    ...  [Sumas acumuladas]\r\n<\/pre>\n
Se observa que los elementos de la \u00faltima es la sucesi\u00f3n de los cuadrados. Para n=3, el proceso de Moessner es<\/p>\n
\r\n1 2 3 4  5 6  7  8  9 10 11 12 13 14 15 16 ... [Inicial]\r\n1 2   4  5    7  8    10 11    13 14    16 ... [Elimina 3]\r\n1 3   7 12   19 27    37 48    61 75    91 ... [Sumas acumuladas]\r\n1     7      19       37       61       91 ... [Elimina 2]\r\n1     8      27       64      125      216 ... [Sumas acumuladas]\r\n<\/pre>\n
Se observa que los elementos de la \u00faltima es la sucesi\u00f3n de los cubos. Para n=4, el proceso de Moessner es<\/p>\n
\r\n1 2 3 4  5  6  7  8  9  10 11 12 13  14 15 16 ... [Inicial]\r\n1 2 3    5  6  7     9  10 11    13  14 15    ... [Elimina 4]\r\n1 3 6   11 17 24    33  43 54    67  81 96    ... [Sumas acumuladas]\r\n1 3     11 17       33  43       67  81       ... [Elimina 3]\r\n1 4     15 32       65 108      175 256       ... [Sumas acumuladas]\r\n1       15          65          175           ... [Elimina 2]\r\n1       16          81          256           ... [Sumas acumuladas]\r\n<\/pre>\n
Se observa que los elementos de la \u00faltima es la sucesi\u00f3n de los cuartas potencias. El teorema de Moessner afirma que para cualquier n, la sucesi\u00f3n obtenida mediante el proceso de Moessner es la de las potencias n-\u00e9simas; es decir \"1^n,<\/p>\n
El objetivo de los siguientes ejercicios es definir en Haskell una funci\u00f3n que simule el proceso de Moessner y comprobar el teorema.
\n<\/p>\n
\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1, Definir la funci\u00f3n\r\n--    eliminaPosiciones :: Int -> [Integer] -> [Integer]\r\n-- tal que (eliminaPosiciones n xs) es la lista obtenida eliminando en\r\n-- xs los elementos que ocupan las posiciones n, 2*n, 3*n, .... Por\r\n-- ejemplo, \r\n--    eliminaPosiciones 3 [1..10]  ==  [1,2,4,5,7,8,10]\r\n-- ---------------------------------------------------------------------\r\n\r\neliminaPosiciones :: Int -> [Integer] -> [Integer]\r\neliminaPosiciones _ [] = []\r\neliminaPosiciones n xs =\r\n    take (n-1) xs ++ eliminaPosiciones n (drop n xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n                    \r\n--    sumaAcumulada :: [Integer] -> [Integer]\r\n-- tal que (sumaAcumulada xs) es la lista de las sumas acumuladas de los\r\n-- elementos de xs. Por ejemplo,\r\n--    sumaAcumulada [1,2,4,5,7,8,10]  ==  [1,3,7,12,19,27,37]\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaAcumulada :: [Integer] -> [Integer]\r\nsumaAcumulada = scanl1 (+)\r\n\r\n-- Puede definirse sin usar scanl:\r\nsumaAcumulada1 :: [Integer] -> [Integer]\r\nsumaAcumulada1 [x] = [x]\r\nsumaAcumulada1 ys@(x:xs) = x : zipWith (+) (sumaAcumulada1 ys) xs\r\n\r\n-- Tambi\u00e9n puede definirse sin usar zipWith\r\nsumaAcumulada2 :: [Integer] -> [Integer]\r\nsumaAcumulada2 [x] = [x]\r\nsumaAcumulada2 ys@(x:xs) = \r\n    x : [a+b | (a,b) <- zip (sumaAcumulada2 ys)xs] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    moessner :: Int -> [Integer]\r\n-- tal que (moessner n) es la sucesi\u00f3n obtenida aplicando el proceso de\r\n-- Moessner de orden n. Por ejemplo,\r\n--    take 5 (moessner 4)  ==  [1,16,81,256,625]\r\n-- ---------------------------------------------------------------------\r\n\r\nmoessner :: Int -> [Integer]\r\nmoessner n = aux n [1..] where \r\n    aux 1 xs = xs \r\n    aux k xs = aux (k-1) (sumaAcumulada (eliminaPosiciones k xs))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    prop_moessner :: Int -> Int -> Bool\r\n-- tal que (prop_moessner n m) se verifica si la lista de los m primeros\r\n-- t\u00e9rminos de (moessner n) es [1,2^n,...,m^n].\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_moessner :: Int -> Int -> Bool\r\nprop_moessner n m = \r\n    take m (moessner n) == take m [x^n | x <- [1..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar que para todo n <= 100, la lista de los 5 primeros\r\n-- t\u00e9rminos de (moessner n) es [1,2^n,...,5^n].\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es \r\n--    ghci> and [prop_moessner n 5 | n <- [1..100]]\r\n--    True\r\n<\/pre>\n
Referencias<\/h2>\n
    \n
  1.  J.H. Conway y R.K. Guy Moessner's magic<\/a>. En \"The Book of Numbers\" pp. 63-65\n
  2.  J.H. Conway y T. HsuSome Very interesting sequences<\/a>.\n
  3.  R. Hinze Scans and convolutions. A calculational proof of Moessner\u2019s theorem<\/a>.\n
  4.  D. Kozen y A. Silva On Moessner\u2019s theorem<\/a>.\n
  5.  M.A. Lerma La magia de Moessner<\/a>.\n
  6.  C.T. Long A note on Moessner's process<\/a>\n
  7.  A. Rold\u00e1n El algoritmo de Moessner<\/a>.\n
  8.  E.W. Weisstein Moessner's theorem<\/a>.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    La presente relaci\u00f3n de ejercicios est\u00e1 basada en el art\u00edculo El algoritmo de Moessner escrito por Antonio Rold\u00e1n Mart\u00ednez en su blog N\u00fameros y hoja de c\u00e1lculo. El proceso de Moessner de orden n consiste en lo siguiente: De la lista de los n\u00fameros naturales, se tacha los elementos que ocupan las posiciones n, 2*n,…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[270],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2059"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=2059"}],"version-history":[{"count":9,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2059\/revisions"}],"predecessor-version":[{"id":4015,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2059\/revisions\/4015"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}