{"id":1569,"date":"2015-06-18T06:00:39","date_gmt":"2015-06-18T04:00:39","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1569"},"modified":"2015-10-28T15:16:48","modified_gmt":"2015-10-28T13:16:48","slug":"menor-n-tal-que-el-primo-n-esimo-cumple-una-propiedad","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/menor-n-tal-que-el-primo-n-esimo-cumple-una-propiedad\/","title":{"rendered":"Menor n tal que el primo n-\u00e9simo cumple una propiedad"},"content":{"rendered":"<p>Sea p(n) el n-\u00e9simo primo y sea r el resto de dividir  (p(n)-1)^n + (p(n)+1)^n por p(n)^2. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   si n = 3, entonces p(3) =  5 y r = ( 4^3 +  6^3) mod  (5^2) =   5\n   si n = 7, entonces p(7) = 17 y r = (16^7 + 18^7) mod (17^2) = 238\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   menorPR :: Integer -> Integer \n<\/pre>\n<p>tal que (menorPR x) es el menor n tal que el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2 es mayor que x. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   menorPR 100     == 5\n   menorPR 345     == 9\n   menorPR 1000    == 13\n   menorPR (10^9)  == 7037\n   menorPR (10^10) == 21035\n   menorPR (10^12) == 191041\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmenorPR1 :: Integer -> Integer\nmenorPR1 x = head [n | (n,p) <- zip [1..] primes\n                     , (((p-1)^n + (p+1)^n) `mod` (p^2)) > x]\n\n-- Segunda soluci\u00f3n (usando el binomio de Newton)\n-- ==============================================\n\n-- Desarrollando por el binomio de Newton\n--    (p+1)^n = C(n,0)p^n + C(n,1)p^(n-1) +...+ C(n,n-1)p + 1\n--    (p-1)^n = C(n,0)p^n - C(n,1)p^(n-1) +...+ C(n,n-1)p + (-1)^n\n-- Sumando se obtiene (seg\u00fan n sea par o impar)\n--    2*C(n,0)p^n + 2*C(n,n-2)p^(n-1) +...+ 2*C(n,2)p^2 + 2\n--    2*C(n,0)p^n + 2*C(n,n-2)p^(n-1) +...+ 2*C(n,1)p^1\n-- Al dividir por p^2, el resto es (seg\u00fan n sea par o impar) 2 \u00f3 2*C(n,1)p\n\n-- (restoM n p) es el resto de de dividir (p-1)^n + (p+1)^n por p^2.\nrestoM :: Integer -> Integer -> Integer\nrestoM n p | even n    = 2\n           | otherwise = 2*n*p `mod`(p^2)\n\nmenorPR2 :: Integer -> Integer\nmenorPR2 x = head [n | (n,p) <- zip [1..] primes, restoM n p > x]\n\n-- Comparaci\u00f3n de eficiencia\n--    ghci> menorPR1 (3*10^8)\n--    3987\n--    (2.44 secs, 120291676 bytes)\n--    ghci> menorPR2 (3*10^8)\n--    3987\n--    (0.04 secs, 8073900 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Sea p(n) el n-\u00e9simo primo y sea r el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2. Por ejemplo, si n = 3, entonces p(3) = 5 y r = ( 4^3 + 6^3) mod (5^2) = 5 si n = 7, entonces p(7) = 17 y r = (16^7 + 18^7) mod (17^2) =&#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":[4],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1569"}],"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=1569"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1569\/revisions"}],"predecessor-version":[{"id":1647,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1569\/revisions\/1647"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1569"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1569"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1569"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}