{"id":6290,"date":"2021-04-21T06:00:28","date_gmt":"2021-04-21T04:00:28","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6290"},"modified":"2021-04-28T07:54:17","modified_gmt":"2021-04-28T05:54:17","slug":"numeros-fibonaccianos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-fibonaccianos\/","title":{"rendered":"N\u00fameros fibonaccianos"},"content":{"rendered":"<p>El enunciado del <a href=\"https:\/\/bit.ly\/3wEcB0h\">segundo problema de este mes de la RSME<\/a> es el siguiente:<\/p>\n<blockquote><p>\n  Un n\u00famero de al menos tres cifras se denomina <strong>fibonacciano<\/strong> si sus cifras, a partir de la tercera, son iguales a la suma de las dos cifras anteriores. Por ejemplo, 5279 es un n\u00famero fibonacciano, pues su tercera cifra, 7, es suma de las dos anteriores (5+2) y su cuarta cifra, 9, tambi\u00e9n (2+7).<\/p>\n<p>  Te daremos el problema por v\u00e1lido si respondes bien a estas dos cuestiones:<br \/>\n  a) \u00bfcu\u00e1ntas cifras como m\u00e1ximo puede tener un n\u00famero fibonacciano?<br \/>\n  b) \u00bfcu\u00e1ntos n\u00fameros fibonaccianos hay?\n<\/p><\/blockquote>\n<p>En la definici\u00f3n de fibonacciano la suma de las cifras tiene que  menor que 10, pero podemos generalizarlo sustituyendo 10 por  n\u00famero n. Dichos n\u00fameros de llaman fibonaccianos generalizados acotados por n. Por ejemplo, 571219315081 es un fibonacciano generalizado acotado por 100 ya que la sucesi\u00f3n de sus d\u00edgitos es 5, 7, 12 (= 5+7), 19 (= 7+12), 31 (= 12+19) 50 (=19+31) y 81 (=31+50).<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   esFibonacciano :: Integer -> Bool\n   fibonaccianos  :: [Integer]\n   fibonaccianosG :: Integer -> [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esFibonacciano n) se verifica si n es un n\u00famero fibonacciano. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     esFibonacciano 5279    ==  True\n     esFibonacciano 527916  ==  False\n<\/pre>\n<ul>\n<li>fibonaccianos es la lista de los n\u00fameros fibonaccianos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 60 fibonaccianos\n     [101,112,123,134,145,156,167,178,189,202,213,224,235,246,257,268,\n      279,303,314,325,336,347,358,369,404,415,426,437,448,459,505,516,\n      527,538,549,606,617,628,639,707,718,729,808,819,909,1011,1123,\n      1235,1347,1459,2022,2134,2246,2358,3033,3145,3257,3369,4044,4156]\n<\/pre>\n<ul>\n<li>(fibonaccianosG n) es la lista de los n\u00fameros fibonaccianos generalizados acotados por n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 60 (fibonaccianosG 100)\n     [101,112,123,134,145,156,167,178,189,202,213,224,235,246,257,268,\n      279,303,314,325,336,347,358,369,404,415,426,437,448,459,505,516,\n      527,538,549,606,617,628,639,707,718,729,808,819,909,1011,1123,\n      1235,1347,1459,1910,2022,2134,2246,2358,2810,2911,3033,3145,3257]\n     \u03bb> take 12 (drop 60 (fibonaccianosG 10))\n     [4268,5055,5167,5279,6066,6178,7077,7189,8088,9099,10112,11235]\n     \u03bb> take 12 (drop 60 (fibonaccianosG 100))\n     [3369,3710,3811,3912,4044,4156,4268,4610,4711,4812,4913,5055]\n     \u03bb> length (fibonaccianosG (10^40))\n     16888\n     \u03bb> length (show (last (fibonaccianosG (10^40))))\n     3943\n<\/pre>\n<p>Usando las funciones anteriores, calcular cu\u00e1ntas cifras como m\u00e1ximo puede tener un n\u00famero fibonacciano y cu\u00e1ntos n\u00fameros fibonaccianos hay.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (inits, isPrefixOf, sort)\n\n-- Definici\u00f3n de esFibonacciano\n-- ============================\n\nesFibonacciano :: Integer -> Bool\nesFibonacciano n =\n  n > 99 && ds `isPrefixOf` drop 2 fs\n  where (a:b:ds) = digitos n\n        fs = a : b : zipWith (+) fs (tail fs)\n\n-- (digitos n) es la lista de los d\u00edgitos de n. Por ejemplo,\n--    digitos 325  ==  [3,2,5]\ndigitos :: Integer -> [Int]\ndigitos n =\n  [read [c] | c <- show n]\n\n-- 1\u00aa definici\u00f3n de fibonaccianos\n-- ==============================\n\nfibonaccianos :: [Integer]\nfibonaccianos =\n  filter esFibonacciano [100..10112358]\n\n-- 2\u00aa definici\u00f3n de fibonaccianos\n-- ==============================\n\nfibonaccianos2 :: [Integer]\nfibonaccianos2 =\n  sort (concat [aux a b | a <- [1..9], b <- [0..9]])\n  where\n    aux a b = [digitosAnumero zs | zs <- drop 3 (inits (takeWhile (<10) (fibs a b)))]\n\n-- (fibs a b) es la sucesi\u00f3n de n\u00fameros de Fibonacci cuyos dos primeros\n-- t\u00e9rminos son a y b. Por ejemplo,\n--    take 9 (fibs 2 4)  ==  [2,4,6,10,16,26,42,68,110]\n--    take 9 (fibs 3 6)  ==  [3,6,9,15,24,39,63,102,165]\nfibs :: Integer -> Integer -> [Integer]\nfibs a b = fs\n  where fs = a : b : zipWith (+) fs (tail fs)\n\n-- (digitosAnumero xs) es el n\u00famero cuya lista de d\u00edgitos es xs. Por\n-- ejemplo,\n--    digitosAnumero [8,1,6,4,9]  ==  81649\ndigitosAnumero :: [Integer] -> Integer\ndigitosAnumero xs =\n  read (concatMap show xs)\n\n-- fibonaccianosG\n-- ==============\n\nfibonaccianosG :: Integer -> [Integer]\nfibonaccianosG n =\n  sort (concat [fibonaccianosGAux n a b | a <- [1..9], b <- [0..9]])\n\nfibonaccianosGAux :: Integer -> Integer -> Integer -> [Integer]\nfibonaccianosGAux n a b =\n  [digitosAnumero zs | zs <- drop 3 (inits (takeWhile (<n) (fibs a b)))]\n\n-- Comprobaci\u00f3n de la generalizaci\u00f3n\n--    \u03bb> fibonaccianos2 == fibonaccianosG 10\n--    True\n\n--    \u03bb> length (fibonaccianosG (10^40))\n--    16888\n--    (2.41 secs, 10,546,873,616 bytes)\n--    \u03bb> length (show (last (fibonaccianosG (10^40))))\n--    3943\n--    (2.41 secs, 10,547,101,856 bytes)\n\n-- C\u00e1lculos\n-- ========\n\n-- El c\u00e1lculo del m\u00e1ximo n\u00famero de cifras de los n\u00fameros fibonaccianos\n-- es\n--      \u03bb> maximum [length (show n) | n <- fibonaccianos2]\n--      8\n--      \u03bb> length (show (last fibonaccianos2))\n--      8\n\n-- El c\u00e1lculo de la cantidad de n\u00fameros fibonaccianos es\n--      \u03bb> length fibonaccianos2\n--      84\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>El enunciado del segundo problema de este mes de la RSME es el siguiente: Un n\u00famero de al menos tres cifras se denomina fibonacciano si sus cifras, a partir de la tercera, son iguales a la suma de las dos cifras anteriores. Por ejemplo, 5279 es un n\u00famero fibonacciano, pues su tercera cifra, 7, es&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6290"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6290"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6290\/revisions"}],"predecessor-version":[{"id":6370,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6290\/revisions\/6370"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}