{"id":245,"date":"2008-10-13T09:15:02","date_gmt":"2008-10-13T08:15:02","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=245"},"modified":"2008-10-13T09:15:02","modified_gmt":"2008-10-13T08:15:02","slug":"lowy-na-merseny","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2008\/10\/13\/lowy-na-merseny\/","title":{"rendered":"\u0141owy na „merseny”"},"content":{"rendered":"

Jak zapewne wi\u0119kszo\u015b\u0107 z Pa\u0144stwa wie, stwory zwane „mersenami”\u00a0to z regu\u0142y bardzo d\u0142ugie w\u0119\u017ce o wzorze M=<\/font>2n<\/sup>-1<\/span><\/span>, gdzie n jest liczb\u0105 naturaln\u0105. Francuski mnich i uczony Merin Mersenne hodowa\u0142 je przed blisko 400 laty\u00a0 i\u00a0zauwa\u017cy\u0142, \u017ce tylko wtedy, gdy wyk\u0142adnik n jest liczb\u0105 pierwsz\u0105 (p), „mersen” (M), tak\u017ce mo\u017ce<\/strong> by\u0107 liczb\u0105 pierwsz\u0105 (Mp). Mo\u017ce, ale nie musi<\/strong>. Na starcie ci\u0105gu liczb M=2p<\/sup>-1<\/span>\u00a0dominuj\u0105 Mp, ale bardzo szybko staj\u0105 sie unikatami w g\u0105szczu z\u0142o\u017conych liczb Mersenne’a (Mz) dla n=p. Czo\u0142\u00f3wka ci\u0105gu wygl\u0105da tak:<\/p>\n

3, 7, 31, 127, 2047<\/strong>, 8191, 131071, 524287, 8388607<\/strong>,
\n536870911<\/strong>, 2147483647, 137438953471<\/strong>, 2199023255551<\/strong>,
\n8796093022207<\/strong>, 140737488355327<\/strong>, 9007199254740991<\/strong>,
\n576460752303423487<\/strong>, 2305843009213693951, …<\/p>\n

Mz wyr\u00f3\u017cnione s\u0105 t\u0142ustym drukiem. Kto nie ma nic lepszego do roboty, mo\u017ce spr\u00f3bowa\u0107 roz\u0142o\u017cy\u0107 je na czynniki pierwsze;).
\nW miar\u0119 w\u0119drowania wzd\u0142u\u017c tego ci\u0105gu na\u00a0Mp trafia si\u0119 coraz rzadziej. Permanentnie potykamy si\u0119 natomiast o Mz, czyli „odpady”,\u00a0kt\u00f3re ma\u0142o kogo interesuj\u0105. W\u00f3wczas zaczyna si\u0119 polowanie na Mp i jest to,\u00a0co ju\u017c dawno zauwa\u017cono,\u00a0bardzo efektywny\u00a0spos\u00f3b polowania na najwi\u0119ksze liczby pierwsze. Te drugie \u0142owy trwaj\u0105 przynajmniej od kilkuset lat, a zdecydowanie przybra\u0142y na sile wraz z pojawieniem si\u0119 „m\u00f3zg\u00f3w elektronowych” w latach 50.<\/p>\n

Od 1996 roku funkcjonuje projekt oblicze\u0144 rozproszonych GIMPS, czyli og\u00f3lno\u015bwiatowa nagonka na Mp. Kto ma ochot\u0119, mo\u017ce si\u0119 przy\u0142\u0105czy\u0107 do ob\u0142awy, zatrudniaj\u0105c sw\u00f3j komputer, cho\u0107 popularne komputery domowe maj\u0105 mniejsze\u00a0szanse na schwytanie delikwenta ni\u017c giganty zainstalowane w niekt\u00f3rych instytucjach, a od 23 sierpnia br. nadzieje ich w\u0142a\u015bcicieli na zgarni\u0119cie 100 000 dolar\u00f3w ostatecznie prys\u0142y. Tak\u0105 kwot\u0119 wyznaczy\u0142 szeryf, czyli Electronic Frontier Foundation, za g\u0142ow\u0119 i reszt\u0119 cielska w\u0119\u017ca Mp z\u0142o\u017conego z ponad 10 milion\u00f3w cyfr. W\u0142a\u015bnie 23 sierpnia jeden z \u0142owc\u00f3w nagr\u00f3d przekroczy\u0142\u00a0ten limit, czyli znalaz\u0142 45. liczb\u0119 pierwsz\u0105 Mersenne’a z\u0142o\u017con\u0105 z 12 978 189 cyfr,\u00a0o czym mo\u017cna przeczyta\u0107 na stronie projektu GIMPS<\/a>. Dla tych, kt\u00f3rym si\u0119 nie powiod\u0142o, pocieszeniem\u00a0s\u0105 dwie informacje. Po pierwsze, nagroda jest dzielona mi\u0119dzy najaktywniejszych my\u015bliwych, czyli mniej wi\u0119cej tak,\u00a0jak pula nagr\u00f3d w turnieju tenisowym. Po drugie: szeryf ustanowi\u0142 jeszcze dwie nagrody\u00a0– 150 000 dolar\u00f3w\u00a0za przekroczenie 100 milion\u00f3w cyfr i \u0107wier\u0107 miliona po zaliczeniu miliardcyfrowej Mp. Warto doda\u0107, \u017ce z wyp\u0142at\u0105 nie jest tak hop-siup. Najpierw trzeba dok\u0142adnie sprawdzi\u0107, czy z liczb\u0105 wszystko gra, a to troch\u0119 trwa.<\/p>\n

Jaki po\u017cytek ma ludzko\u015b\u0107 z takich i wielu podobnych, nierzadko kosztownych \u0142ow\u00f3w matematycznych? Niestety, to dobre pytanie. Nie ulega w\u0105tpliwo\u015bci, \u017ce praktyczne korzy\u015bci z odkrycia z\u0142\u00f3\u017c\u00a0gazu ziemnego\u00a0s\u0105 nieco wi\u0119ksze, ni\u017c z odkrycia kolejnego liczbowego giganta. „Linia obrony” mniejszych korzy\u015bci oparta jest na stwierdzeniu, kt\u00f3re przypomina sprzeciw mojej \u017cony, gdy chc\u0119 si\u0119 czego\u015b pozby\u0107 przy robieniu domowych porz\u0105dk\u00f3w: „zostaw, to si\u0119 mo\u017ce przyda\u0107”. I rzeczywi\u015bcie, czasem okazuje si\u0119 przydatne.<\/p>\n

Nie znam zada\u0144 do gimnastykowania szarych kom\u00f3rek, w kt\u00f3rych wyst\u0119puj\u0105 liczby Mersenne’a, ale nie odbiegn\u0119 daleko od tematu, je\u015bli zaproponuj\u0119 Pa\u0144stwu zastanowienie si\u0119 nad kolejn\u0105 pot\u0119gow\u0105 \u0142amig\u0142\u00f3wk\u0105.<\/p>\n

Od ponad 150 lat znana jest hipoteza, \u017ce iloczyn n kolejnych liczb naturalnych nie mo\u017ce by\u0107 pot\u0119g\u0105. \u0141atwo dowie\u015b\u0107, \u017ce to prawda, dla n=2, 3, a nawet 4. Dalej zaczynaj\u0105 si\u0119 dowodowe schodki, a potem schody, na szczyt kt\u00f3rych wspi\u0105\u0142 si\u0119 dopiero w 1975 roku genialny Paul Erd\u00f6s. P\u00f3\u017aniej wysz\u0142a na jaw pewna ciekawostka.
\n1*2*3*4=24, czyli do kwadratu (25) brakuje 1.
\n8*9*10*11=7920\u00a0– je\u015bli dodamy 1, pojawi si\u0119 kwadrat (7921= 89^2)
\n37*38*39*40=2193360, a wi\u0119c o 1 mniej od kwadratu (2193361=1481^2)
\nCzy kto\u015b odwa\u017cy si\u0119 udowodni\u0107, \u017ce iloczyn czterech kolejnych liczb naturalnych zawsze b\u0119dzie o jeden mniejszy od kwadratu?<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Jak zapewne wi\u0119kszo\u015b\u0107 z Pa\u0144stwa wie, stwory zwane „mersenami”\u00a0to z regu\u0142y bardzo d\u0142ugie w\u0119\u017ce o wzorze M=2n-1, gdzie n jest liczb\u0105 naturaln\u0105. Francuski mnich i uczony Merin Mersenne hodowa\u0142 je przed blisko 400 laty\u00a0 i\u00a0zauwa\u017cy\u0142, \u017ce tylko wtedy, gdy wyk\u0142adnik n jest liczb\u0105 pierwsz\u0105 (p), „mersen” (M), tak\u017ce mo\u017ce by\u0107 liczb\u0105 pierwsz\u0105 (Mp). Mo\u017ce, ale […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/245"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=245"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/245\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=245"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=245"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=245"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}