{"id":8527,"date":"2024-03-24T06:00:06","date_gmt":"2024-03-24T04:00:06","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8527"},"modified":"2024-03-31T20:25:13","modified_gmt":"2024-03-31T18:25:13","slug":"24-mar-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/24-mar-24\/","title":{"rendered":"Mayor \u00f3rbita de la sucesi\u00f3n de Collatz"},"content":{"rendered":"<p>Se considera la siguiente operaci\u00f3n, aplicable a cualquier n\u00famero entero positivo:<\/p>\n<ul>\n<li>Si el n\u00famero es par, se divide entre 2.<\/li>\n<li>Si el n\u00famero es impar, se multiplica por 3 y se suma 1.<\/li>\n<\/ul>\n<p>Dado un n\u00famero cualquiera, podemos calcular su \u00f3rbita; es decir, las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita de 13 es<\/p>\n<pre lang=\"haskell\">\n   13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...\n<\/pre>\n<p>Si observamos este ejemplo, la \u00f3rbita de 13 es peri\u00f3dica, es decir,<br \/>\nse repite indefinidamente a partir de un momento dado). La conjetura<br \/>\nde Collatz dice que siempre alcanzaremos el 1 para cualquier n\u00famero<br \/>\ncon el que comencemos. Ejemplos:<\/p>\n<ul>\n<li>Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.<\/li>\n<li>Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.<\/li>\n<li>Empezando en n = 27, la sucesi\u00f3n tiene 112 pasos, llegando hasta<br \/>\n9232 antes de descender a 1:  27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   mayoresGeneradores :: Integer -> [Integer]\n<\/pre>\n<p>tal que (mayoresGeneradores n) es la lista de los n\u00fameros menores o iguales que n cuyas \u00f3rbitas de Collatz son las de mayor longitud. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   mayoresGeneradores 20      ==  [18,19]\n   mayoresGeneradores (10^6)  ==  [837799]\n<\/pre>\n<p><!--more--><\/p>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Mayor_orbita_de_la_sucesion_de_Collatz where\n\nimport qualified Data.MemoCombinators as Memo (integral)\nimport Data.List (genericLength, genericTake)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores1 :: Integer -> [Integer]\nmayoresGeneradores1 n =\n  [x | (x,y) <- ps, y == m]\n  where ps = genericTake n longitudesOrbitas\n        m  = maximum (map snd ps)\n\n-- longitudesOrbita es la lista de los n\u00fameros junto a las longitudes de\n-- las \u00f3rbitas de Collatz que generan. Por ejemplo,\n--    \u03bb> take 10 longitudesOrbitas\n--    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]\nlongitudesOrbitas :: [(Integer, Integer)]\nlongitudesOrbitas =\n  [(n, genericLength (collatz n)) | n <- [1..]]\n\n-- (siguiente n) es el siguiente de n en la sucesi\u00f3n de Collatz. Por\n-- ejemplo,\n--    siguiente 13  ==  40\n--    siguiente 40  ==  20\nsiguiente :: Integer -> Integer\nsiguiente n | even n    = n `div` 2\n            | otherwise = 3*n+1\n\n-- (collatz1 n) es la \u00f3rbita de Collatz de n hasta alcanzar el\n-- 1. Por ejemplo,\n--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]\n\n-- 1\u00aa definici\u00f3n de collatz\ncollatz1 :: Integer -> [Integer]\ncollatz1 1 = [1]\ncollatz1 n = n : collatz1 (siguiente n)\n\n-- 2\u00aa definici\u00f3n de collatz\ncollatz2 :: Integer -> [Integer]\ncollatz2 n = takeWhile (\/=1) (iterate siguiente n) ++ [1]\n\n-- Usaremos la 2\u00aa definici\u00f3n de collatz\ncollatz :: Integer -> [Integer]\ncollatz = collatz2\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores2 :: Integer -> [Integer]\nmayoresGeneradores2 n =\n  [x | (x,y) <- ps, y == m]\n  where ps = [(x, longitudOrbita x) | x <- [1..n]]\n        m  = maximum (map snd ps)\n\n-- (longitudOrbita x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n--    longitudOrbita 13  ==  10\nlongitudOrbita :: Integer -> Integer\nlongitudOrbita 1 = 1\nlongitudOrbita x = 1 + longitudOrbita (siguiente x)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores3 :: Integer -> [Integer]\nmayoresGeneradores3 n =\n  [x | (x,y) <- ps, y == m]\n  where ps = [(x, longitudOrbita2 x) | x <- [1..n]]\n        m  = maximum (map snd ps)\n\nlongitudOrbita2 :: Integer -> Integer\nlongitudOrbita2 = Memo.integral longitudOrbita2'\n  where\n    longitudOrbita2' 1 = 1\n    longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> [Integer]) -> Spec\nspecG mayoresGeneradores = do\n  it \"e1\" $\n    mayoresGeneradores 20 `shouldBe` [18,19]\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG mayoresGeneradores1\n  describe \"def. 2\" $ specG mayoresGeneradores2\n  describe \"def. 3\" $ specG mayoresGeneradores3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    3 examples, 0 failures\n\n-- Equivalencia de definiciones\n-- ============================\n\n-- La propiedad es\nprop_mayoresGeneradores :: Positive Integer -> Bool\nprop_mayoresGeneradores (Positive n) =\n  all (== mayoresGeneradores1 n)\n      [mayoresGeneradores2 n,\n       mayoresGeneradores3 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_mayoresGeneradores\n--    +++ OK, passed 100 tests.\n\n-- Comprobaci\u00f3n de eficiencia\n-- ==========================\n\n-- La comprobaci\u00f3n es\n--    \u03bb> mayoresGeneradores (10^5)\n--    [77031]\n--    (5.43 secs, 6,232,320,064 bytes)\n--    \u03bb> mayoresGeneradores2 (10^5)\n--    [77031]\n--    (7.68 secs, 5,238,991,616 bytes)\n--    \u03bb> mayoresGeneradores3 (10^5)\n--    [77031]\n--    (0.88 secs, 571,788,736 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom functools import lru_cache\nfrom itertools import count, islice\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# siguiente(n) es el siguiente de n en la sucesi\u00f3n de Collatz. Por\n# ejemplo,\n#    siguiente(13)  ==  40\n#    siguiente(40)  ==  20\ndef siguiente (n: int) -> int:\n    if n % 2 == 0:\n        return n \/\/ 2\n    return 3*n+1\n\n# collatz1(n) es la \u00f3rbita de Collatz de n hasta alcanzar el\n# 1. Por ejemplo,\n#    collatz1(13)  ==  [13,40,20,10,5,16,8,4,2,1]\ndef collatz1(n: int) -> list[int]:\n    if n == 1:\n        return [1]\n    return [n]+ collatz1(siguiente(n))\n\n# longitudesOrbita() es la lista de los n\u00fameros junto a las longitudes de\n# las \u00f3rbitas de Collatz que generan. Por ejemplo,\n#    >>> list(islice(longitudesOrbitas(), 10))\n#    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]\ndef longitudesOrbitas() -> Iterator[tuple[int, int]]:\n    return ((n, len(collatz1(n))) for n in count(1))\n\ndef mayoresGeneradores1(n: int) -> list[int]:\n    ps = list(islice(longitudesOrbitas(), n))\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef collatz2(n: int) -> list[int]:\n    r = [n]\n    while n != 1:\n        n = siguiente(n)\n        r.append(n)\n    return r\n\ndef longitudesOrbitas2() -> Iterator[tuple[int, int]]:\n    return ((n, len(collatz2(n))) for n in count(1))\n\ndef mayoresGeneradores2(n: int) -> list[int]:\n    ps = list(islice(longitudesOrbitas2(), n))\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# longitudOrbita(x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n#    longitudOrbita(13)  ==  10\ndef longitudOrbita(x: int) -> int:\n    if x == 1:\n        return 1\n    return 1 + longitudOrbita(siguiente(x))\n\ndef mayoresGeneradores3(n: int) -> list[int]:\n    ps = [(x, longitudOrbita(x)) for x in range(1, n+1)]\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\n# longitudOrbita2(x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n#    longitudOrbita2(13)  ==  10\ndef longitudOrbita2(x: int) -> int:\n    r = 0\n    while x != 1:\n        x = siguiente(x)\n        r += 1\n    return r + 1\n\ndef mayoresGeneradores4(n: int) -> list[int]:\n    ps = [(x, longitudOrbita2(x)) for x in range(1, n+1)]\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\n@lru_cache(maxsize=None)\ndef longitudOrbita3(x: int) -> int:\n    if x == 1:\n        return 1\n    return 1 + longitudOrbita3(siguiente(x))\n\ndef mayoresGeneradores5(n: int) -> list[int]:\n    ps = [(x, longitudOrbita3(x)) for x in range(1, n+1)]\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_mayoresGeneradores() -> None:\n    for mayoresGeneradores in [mayoresGeneradores1,\n                               mayoresGeneradores2,\n                               mayoresGeneradores3,\n                               mayoresGeneradores4,\n                               mayoresGeneradores5]:\n        assert mayoresGeneradores(20) == [18,19]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_mayoresGeneradores()\n#    Verificado\n\n# Equivalencia de definiciones\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_mayoresGeneradores_equiv(n: int) -> None:\n    r = mayoresGeneradores1(n)\n    assert mayoresGeneradores2(n) == r\n    assert mayoresGeneradores3(n) == r\n\n# La comprobaci\u00f3n es\n#    >>> test_mayoresGeneradores_equiv()\n#    >>>\n\n# Comprobaci\u00f3n de eficiencia\n# ==========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comprobaci\u00f3n es\n#    >>> tiempo('mayoresGeneradores1(10**5)')\n#    4.08 segundos\n#    >>> tiempo('mayoresGeneradores2(10**5)')\n#    1.95 segundos\n#    >>> tiempo('mayoresGeneradores3(10**5)')\n#    2.16 segundos\n#    >>> tiempo('mayoresGeneradores4(10**5)')\n#    1.71 segundos\n#    >>> tiempo('mayoresGeneradores5(10**5)')\n#    0.14 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Se considera la siguiente operaci\u00f3n, aplicable a cualquier n\u00famero entero positivo: Si el n\u00famero es par, se divide entre 2. Si el n\u00famero es impar, se multiplica por 3 y se suma 1. Dado un n\u00famero cualquiera, podemos calcular su \u00f3rbita; es decir, las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita de&#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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8527"}],"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=8527"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8527\/revisions"}],"predecessor-version":[{"id":8528,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8527\/revisions\/8528"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8527"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8527"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8527"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}