{"id":7138,"date":"2022-07-18T06:00:18","date_gmt":"2022-07-18T04:00:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7138"},"modified":"2022-07-11T13:58:11","modified_gmt":"2022-07-11T11:58:11","slug":"primos-con-cubos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/primos-con-cubos\/","title":{"rendered":"Primos con cubos"},"content":{"rendered":"<p>Un <strong>primo con cubo<\/strong> es un n\u00famero primo p para el que existe alg\u00fan entero positivo n tal que la expresi\u00f3n n^3 + n^2p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que  8^3 + 8^2\u00d719 = 12^3.<\/p>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   primosConCubos :: [Integer]\n<\/pre>\n<p>tal que sus elementos son los primos con cubo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 6 primosConCubos\n   [7,19,37,61,127,271]\n   \u03bb> length (takeWhile (< 1000000) primosConCubos)\n   173\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime)\nimport Test.QuickCheck (NonNegative (NonNegative), maxSize, quickCheckWith, stdArgs) \n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosConCubos1 :: [Integer]\nprimosConCubos1 =\n  [p | x <- [1..],\n       n <- [1..x],\n       (x^3 - n^3) `mod` (n^2) == 0,\n       let p = (x^3 - n^3) `div` (n^2),\n       isPrime p]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Para analizar la respuesta, en esta soluci\u00f3n se calculan los pares\n-- (p,n) tales que p es un primo con cubo y n es un n\u00famero positivo tal\n-- que n^3 + n^2p es un cubo\n\nprimosConCubos2' :: [(Integer,Integer)]\nprimosConCubos2' =\n  [(p,n) | x <- [1..],\n           n <- [1..x],\n           (x^3 - n^3) `mod` (n^2) == 0,\n           let p = (x^3 - n^3) `div` (n^2),\n           isPrime p]\n\n-- El c\u00e1lculo es\n--    \u03bb> take 7 primosConCubos2\n--    [(7,1),(19,8),(37,27),(61,64),(127,216),(271,729),(331,1000)]\n\n-- Se observa que la sucesi\u00f3n de los segundos elementos [1,8,27,64,...]\n-- es la de los cubos y que los primeros elementos se obtienen restando\n-- los segundos elementos consecutivos; es decir,\n--     7 =  8 -  1 = 2^3 - 1^3  \n--    19 = 27 -  8 = 3^3 - 2^3\n--    37 = 64 - 27 = 4^3 - 3^3\n-- Continuando el patr\u00f3n,\n--     61 =  5^3 - 4^3 =  125 -   64\n--     91 =  6^3 - 5^3 =  216 -  125\n--    127 =  7^3 - 6^3 =  343 -  216\n--    271 = 10^3 - 9^3 = 1000 -  729\n--    331 = 11^3 -10^3 = 1331 - 1000\n-- Por tanto, los primos con cubos son diferencias de dos cubos\n-- consecutivos; es decir, coinciden con los n\u00fameros cubanos del\n-- ejercicio anterior. A partir de la conjetura se obtienen las\n-- siguientes definiciones\n\n-- Basado en las anteriores observaciones se obtiene la siguiente\n-- definici\u00f3n \nprimosConCubos2 :: [Integer]\nprimosConCubos2 = \n  filter isPrime [(x+1)^3 - x^3 | x <- [1..]] \n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nprimosConCubos3 :: [Integer]\nprimosConCubos3 =\n  filter isPrime diferenciasCubosConsecutivos\n\ndiferenciasCubosConsecutivos :: [Integer]\ndiferenciasCubosConsecutivos =\n  zipWith (-) (tail cubos) cubos \n\ncubos :: [Integer]\ncubos = map (^3) [0..]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Simplificando la expresi\u00f3n (x+1)^3 - x^3 se obtiene 3*x^2+ 3*x + 1,\n-- con lo que la 3\u00aa definici\u00f3n se reduce a\n\nprimosConCubos4 :: [Integer]\nprimosConCubos4 =\n  [p | x <- [1..],\n       let p = 3*x^2+ 3*x + 1,\n       isPrime p]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosConCubos :: NonNegative Int -> Bool\nprop_primosConCubos (NonNegative n) =\n  all (== primosConCubos1 !! n)\n      [primosConCubos2 !! n,\n       primosConCubos3 !! n,\n       primosConCubos4 !! n]\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_primosConCubos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosConCubos1 !! 6\n--    331\n--    (1.15 secs, 1,105,612,336 bytes)\n--    \u03bb> primosConCubos1 !! 7\n--    397\n--    (1.96 secs, 1,909,369,592 bytes)\n--    \u03bb> primosConCubos2 !! 7\n--    397\n--    \n--    (0.01 secs, 648,840 bytes)\n--    \u03bb> primosConCubos2 !! (10^3)\n--    65580901\n--    (0.53 secs, 1,726,837,688 bytes)\n--    \u03bb> primosConCubos3 !! (10^3)\n--    65580901\n--    (0.49 secs, 1,724,258,632 bytes)\n--    \u03bb> primosConCubos4 !! (10^3)\n--    65580901\n--    (0.47 secs, 1,724,833,992 bytes)\n\n-- Demostraci\u00f3n de la conjetura\n-- ============================\n\n-- Vamos a demostrar que los primos con cubos son diferencias de dos\n-- cubos consecutivos.\n--\n-- Sea p un primo con cubo. Por la definici\u00f3n, existe un entero\n-- positivo n tal que n\u00b3 + n\u00b2p es un cubo. \n--\n-- Lema 1: Los n\u00fameros n y p son coprimos (es decir, mcd(n,p) = 1).\n-- Dem.: En caso contrario, puesto que p es primo, existe un a tal que \n-- n = ap. Luego n\u00b3 + n\u00b2p = (a\u00b3+a\u00b2)p\u00b3 es un cubo y, por tanto,\n-- a\u00b3+a\u00b2 es un cubo lo que es imposible ya que el siguiente cubo de\n-- a\u00b3 es a\u00b3+3a\u00b2+3a+1.\n--\n-- Lema 2: Los n\u00fameros n\u00b2 y n+p son coprimos.\n-- Dem.: Sea k = mcd(n^2,n+p). Por k divide n\u00b2, luego k divide a n;\n-- adem\u00e1s, k divide a n+p y (usando el lema 1 y el ser p primo), se\n-- tiene que k = 1.\n--\n-- Puesto que n\u00b3+n\u00b2p = n\u00b2(n+p) es un cubo, usando el lema 2, se tiene\n-- que n\u00b2 y n+p son cubos y, por serlo n\u00b2, n tambi\u00e9n es un cubo. Es\n-- decir, existen enteros positivos x e y tales que n = x\u00b3 y \n-- n+p = y\u00b3. Por tanto, p = y\u00b3-x\u00b3. Sea k = y-x. Se tiene que k = 1 ya\n-- que \n--    p = y\u00b3-x\u00b3\n--      = (n+k)\u00b3-n\u00b3\n--      = 3k+3k\u00b2+k\u00b3\n-- no es primo para k > 1.\n--\n-- Por consiguiente, p = (x+1)\u00b3-x\u00b3.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Primos_con_cubos.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un primo con cubo es un n\u00famero primo p para el que existe alg\u00fan entero positivo n tal que la expresi\u00f3n n^3 + n^2p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8^3 + 8^2\u00d719 = 12^3. Definir la sucesi\u00f3n primosConCubos :: [Integer] tal que sus elementos son los&#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\/7138"}],"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=7138"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7138\/revisions"}],"predecessor-version":[{"id":7141,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7138\/revisions\/7141"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}