{"id":8361,"date":"2023-12-19T06:00:40","date_gmt":"2023-12-19T04:00:40","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8361"},"modified":"2024-02-02T17:08:40","modified_gmt":"2024-02-02T15:08:40","slug":"19-dic-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-dic-23\/","title":{"rendered":"N\u00fameros primos de Hilbert"},"content":{"rendered":"<p>Un <a href=\"http:\/\/bit.ly\/204SW1p\">n\u00famero de Hilbert<\/a> es un entero positivo de la forma 4n+1. Los primeros n\u00fameros de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, &#8230;<\/p>\n<p>Un <strong>primo de Hilbert<\/strong> es un n\u00famero de Hilbert n que no es divisible por ning\u00fan n\u00famero de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, &#8230;<\/p>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   primosH :: [Integer]\n<\/pre>\n<p>tal que sus elementos son los primos de Hilbert. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   take 15 primosH     == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]\n   primosH !! (3*10^4) == 313661\n<\/pre>\n<p><!--more--><\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Numeros_primos_de_Hilbert where\n\nimport Data.Numbers.Primes (isPrime, primeFactors)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheck)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosH1 :: [Integer]\nprimosH1 = [n | n <- tail numerosH,\n                divisoresH n == [1,n]]\n\n-- numerosH es la sucesi\u00f3n de los n\u00fameros de Hilbert. Por ejemplo,\n--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]\nnumerosH :: [Integer]\nnumerosH = [1,5..]\n\n-- (divisoresH n) es la lista de los n\u00fameros de Hilbert que dividen a\n-- n. Por ejemplo,\n--   divisoresH 117  ==  [1,9,13,117]\n--   divisoresH  21  ==  [1,21]\ndivisoresH :: Integer -> [Integer]\ndivisoresH n = [x | x <- takeWhile (<=n) numerosH,\n                    n `mod` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosH2 :: [Integer]\nprimosH2 = filter esPrimoH (tail numerosH)\n  where esPrimoH n = all noDivideAn [5,9..m]\n          where noDivideAn x = n `mod` x \/= 0\n                m            = ceiling (sqrt (fromIntegral n))\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\n-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo\n-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) \u00d7 (4b + 3)\n-- (ver en https:\/\/bit.ly\/3zq7h4e ).\n\nprimosH3 :: [Integer]\nprimosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]\n  where semiPrimoH n = length xs == 2 &#038;&#038; all (\\x -> (x-3) `mod` 4 == 0) xs\n          where xs = primeFactors n\n\n-- Verificaci\u00f3n                                                     --\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    take 15 primosH1 `shouldBe` [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]\n  it \"e2\" $\n    take 15 primosH2 `shouldBe` [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]\n  it \"e3\" $\n    take 15 primosH3 `shouldBe` [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    3 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosH :: NonNegative Int -> Bool\nprop_primosH (NonNegative n) =\n  all (== primosH1 !! n)\n      [primosH2 !! n,\n       primosH3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_primosH\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosH1 !! 2000\n--    16957\n--    (2.16 secs, 752,085,752 bytes)\n--    \u03bb> primosH2 !! 2000\n--    16957\n--    (0.03 secs, 19,771,008 bytes)\n--    \u03bb> primosH3 !! 2000\n--    16957\n--    (0.07 secs, 152,029,168 bytes)\n--\n--    \u03bb> primosH2 !! (3*10^4)\n--    313661\n--    (1.44 secs, 989,761,888 bytes)\n--    \u03bb> primosH3 !! (3*10^4)\n--    313661\n--    (2.06 secs, 6,554,068,992 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import count, islice, takewhile\nfrom math import ceil, sqrt\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# numerosH es la sucesi\u00f3n de los n\u00fameros de Hilbert. Por ejemplo,\n#    >>> list(islice(numerosH(), 15))\n#    [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57]\ndef numerosH() -> Iterator[int]:\n    return count(1, 4)\n\n# (divisoresH n) es la lista de los n\u00fameros de Hilbert que dividen a\n# n. Por ejemplo,\n#   divisoresH(117)  ==  [1,9,13,117]\n#   divisoresH(21)   ==  [1,21]\ndef divisoresH(n: int) -> list[int]:\n    return [x for x in takewhile(lambda x: x <= n, numerosH())\n            if n % x == 0]\n\ndef primosH1() -> Iterator[int]:\n    return (n for n in islice(numerosH(), 1, None)\n            if divisoresH(n) == [1, n])\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef primosH2() -> Iterator[int]:\n    def esPrimoH(n: int) -> bool:\n        m = ceil(sqrt(n))\n        def noDivideAn(x: int) -> bool:\n            return n % x != 0\n        return all(noDivideAn(x) for x in range(5, m+1, 4))\n    return filter(esPrimoH, islice(numerosH(), 1, None))\n\n# Verificaci\u00f3n                                                     --\n# ============\n\ndef test_primosH() -> None:\n    assert list(islice(primosH1(), 15)) == \\\n        [5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73]\n    assert list(islice(primosH2(), 15)) == \\\n        [5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73]\n    print (\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_primosH()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# nth(i, n) es el n-\u00e9simo elemento del iterador i. Por ejemplo,\n#    nth(primos(), 4) == 11\ndef nth(i: Iterator[int], n: int) -> int:\n    return list(islice(i, n, n+1))[0]\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_primosH_equiv(n: int) -> None:\n    assert nth(primosH1(), n) == nth(primosH2(), n)\n\n# La comprobaci\u00f3n es\n#    >>> test_primosH_equiv()\n#    >>>\n\n# Comparaci\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 comparaci\u00f3n es\n#    >>> tiempo('nth(primosH1(), 3000)')\n#    2.51 segundos\n#    >>> tiempo('nth(primosH2(), 3000)')\n#    0.05 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Un n\u00famero de Hilbert es un entero positivo de la forma 4n+1. Los primeros n\u00fameros de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, &#8230; Un primo de Hilbert es un n\u00famero de Hilbert n que&#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\/8361"}],"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=8361"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8361\/revisions"}],"predecessor-version":[{"id":8408,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8361\/revisions\/8408"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}