{"id":7162,"date":"2022-08-01T06:00:48","date_gmt":"2022-08-01T04:00:48","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7162"},"modified":"2022-07-23T13:08:34","modified_gmt":"2022-07-23T11:08:34","slug":"numeros-primos-de-hilbert-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-primos-de-hilbert-2\/","title":{"rendered":"N\u00fameros primos de Hilbert"},"content":{"rendered":"<p>Un <a href=\"http:\/\/bit.ly\/204SW1p\"><strong>n\u00famero de Hilbert<\/strong><\/a> es un  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  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<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime, primeFactors) \nimport Test.QuickCheck (NonNegative (NonNegative), quickCheck)\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-- 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>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numeros_primos_de_Hilbert.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un n\u00famero de Hilbert es un 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 no&#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":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7162"}],"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=7162"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7162\/revisions"}],"predecessor-version":[{"id":7163,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7162\/revisions\/7163"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}