Найдено 48-е простое число Мерсенна

    Математики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в июне 2009 года.

    48-е простое число Мерсенна — 257.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате.

    Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 243.112.609-1, имеющему 12.978.189 десятичных разрядов.

    Распределённый проект по поиску простых чисел GIMPS был запущен в 1997 году, и ныне считается самым длительным непрерывным процессом распределённых вычислений в истории человечества: он продолжается уже почти 17 лет. Сейчас в пиковые моменты в GIMPS участвует 360.000 процессоров с суммарной производительностью 150 трлн операций в секунду.

    За время работы GIMPS участники этого проекта нашли 14 простых чисел Мерсенна. Последнее из них 257.885.161-1 было обнаружено 25 января 2013 года в 23:30:26 UTC, после чего его перепроверили несколько раз на разном оборудовании и программном обеспечении. В частности, программа MLucas проверяла 48-е простое число Мерсенна шесть суток на 32-ядерном сервере, и подтвердила его. На Nvidia GPU в программе CUDALucas число проверили за 3,6 суток и тоже подтвердили его.

    Разработчики программного обеспечения GIMPS и участники проекта уже поделили приз $100 000 за прошлое простое число Мерсенна с как минимум 10 миллионами десятичных разрядов. Следующий приз — $150 000 за число с как минимум 100 миллионами десятичных разрядов. За только что найденное число дадут всего лишь $3000.

    В списке самых больших простых чисел, известных на сегодняшний день, десять первых мест занимают числа Мерсенна.

    Топ-100
    -----  ---------------------------- ------- ----- ---- --------------
    Место           Описание           Разрядов  Кто Год  Описание
    -----  ---------------------------- ------- ----- ---- --------------
        1  2^57885161-1                17425170   G13 2013 Мерсенн 48??
        2  2^43112609-1                12978189   G10 2008 Мерсенн 47??
        3  2^42643801-1                12837064   G12 2009 Мерсенн 46??
        4  2^37156667-1                11185272   G11 2008 Мерсенн 45?
        5  2^32582657-1                 9808358    G9 2006 Мерсенн 44?
        6  2^30402457-1                 9152052    G9 2005 Мерсенн 43?
        7  2^25964951-1                 7816230    G8 2005 Мерсенн 42
        8  2^24036583-1                 7235733    G7 2004 Мерсенн 41
        9  2^20996011-1                 6320430    G6 2003 Мерсенн 40
       10  2^13466917-1                 4053946    G5 2001 Мерсенн 39
       11  19249*2^13018586+1           3918990  SB10 2007
       12  475856^524288+1              2976633 L3230 2012 Обобщённое Ферма
       13  356926^524288+1              2911151 L3209 2012 Обобщённое Ферма
       14  341112^524288+1              2900832 L3184 2012 Обобщённое Ферма
       15  27653*2^9167433+1            2759677   SB8 2005
       16  90527*2^9162167+1            2758093 L1460 2010 
       17  75898^524288+1               2558647  p334 2011 Обобщённое Ферма
       18  28433*2^7830457+1            2357207   SB7 2004 
       19  3*2^7033641+1                2117338 L2233 2011 Делит ОФ(7033639,3)
       20  33661*2^7031232+1            2116617  SB11 2007
       21  2^6972593-1                  2098960    G4 1999 Мерсенн 38
       22  6679881*2^6679881+1          2010852  L917 2009 Каллена
       23  1582137*2^6328550+1          1905090  L801 2009 Каллена
       24  3*2^6090515-1                1833429 L1353 2010
       25  7*2^5775996+1                1738749 L3325 2012
       26  252191*2^5497878-1           1655032 L3183 2012
       27  258317*2^5450519+1           1640776  g414 2008 
       28  773620^262144+1              1543643 L3118 2012 Обобщённое Ферма
       29  3*2^5082306+1                1529928  L780 2009 
              Делит ОФ(5082303,3), ОФ (5082305,5)
       30  676754^262144+1              1528413 L2975 2012 Обобщённое Ферма
       31  5359*2^5054502+1             1521561   SB6 2003 
       32  525094^262144+1              1499526  p338 2012 Обобщённое Ферма
       33  265711*2^4858008+1           1462412  g414 2008 
       34  1271*2^4850526-1             1460157 L1828 2012 
       35  361658^262144+1              1457075  p332 2011 Обобщённое Ферма
       36  9*2^4683555-1                1409892 L1828 2012 
       37  121*2^4553899-1              1370863 L3023 2012
       38  145310^262144+1              1353265  p314 2011 Обобщённое Ферма
       39  353159*2^4331116-1           1303802 L2408 2011
       40  141941*2^4299438-1           1294265  L689 2011
       41  3*2^4235414-1                1274988  L606 2008
       42  191*2^4203426-1              1265360 L2484 2012 
       43  40734^262144+1               1208473  p309 2011 Обобщённое Ферма
       44  9*2^4005979-1                1205921 L1828 2012 
       45  27*2^3855094-1               1160501 L3033 2012
       46  24518^262144+1               1150678  g413 2008 Обобщённое Ферма
       47  123547*2^3804809-1           1145367 L2371 2011
       48  415267*2^3771929-1           1135470 L2373 2011
       49  938237*2^3752950-1           1129757  L521 2007 Вудала
       50  65531*2^3629342-1            1092546 L2269 2011
       51  485767*2^3609357-1           1086531  L622 2008 
       52  5*2^3569154-1                1074424  L503 2009 
       53  1019*2^3536312-1             1064539 L1828 2012 
       54  7*2^3511774+1                1057151  p236 2008 Делит ОФ(3511773,6)
       55  428639*2^3506452-1           1055553 L2046 2011
       56  9*2^3497442+1                1052836 L1780 2012 Обобщённое Ферма
       57  1273*2^3448551-1             1038121 L1828 2012 
       58  191249*2^3417696-1           1028835 L1949 2010
       59  59*2^3408416-1               1026038  L426 2010 
       60  81*2^3352924+1               1009333 L1728 2012 Обобщённое Ферма
       61  1087*2^3336385-1             1004355 L1828 2012 
       62  3139*2^3321905-1              999997  L185 2008 
       63  4847*2^3321063+1              999744   SB9 2005 
       64  223*2^3264459-1               982703 L1884 2012 
       65  9*2^3259381-1                 981173 L1828 2011 
       66  113983*2^3201175-1            963655  L613 2008 
       67  1087*2^3164677-1              952666 L1828 2012 
       68  15*2^3162659+1                952057  p286 2012
       69  19*2^3155009-1                949754 L1828 2012 
       70  3*2^3136255-1                 944108  L256 2007 
       71  1019*2^3103680-1              934304 L1828 2012 
       72  5*2^3090860-1                 930443 L1862 2012 
       73  21*2^3065701+1                922870  p286 2012
       74  5*2^3059698-1                 921062  L503 2008 
       75  383731*2^3021377-1            909531  L466 2011 
       76  2^3021377-1                   909526    G3 1998 Мерсенн 37
       77  7*2^3015762+1                 907836  g279 2008
       78  1095*2^2992587-1              900862 L1828 2011 
       79  15*2^2988834+1                899730  p286 2012
       80  4348099*2^2976221-1           895939  L466 2008 
       81  2^2976221-1                   895932    G2 1997 Мерсенн 36
       82  198677*2^2950515+1            888199 L2121 2012 
       83  7*2^2915954+1                 877791  g279 2008 Делит ОФ(2915953,12)
       84  427194*113^427194+1           877069  p310 2012 Обобщённое Каллена
       85  1207*2^2861901-1              861522 L1828 2011 
       86  222361*2^2854840+1            859398  g403 2006 
       87  177*2^2816050+1               847718  L129 2012 
       88  96*10^846519-1                846521 L2425 2011 Почти репдигит
       89  15*2^2785940+1                838653  p286 2012
       90  17*2^2721830-1                819354  p294 2010 
       91  165*2^2717378-1               818015 L2055 2012 
       92  45*2^2711732+1                816315 L1349 2012 
       93  1372930^131072+1              804474  g236 2003 Обобщённое Ферма
       94  1361244^131072+1              803988  g236 2004 Обобщённое Ферма
       95  1176694^131072+1              795695  g236 2003 Обобщённое Ферма
       96  13*2^2642943-1                795607 L1862 2012 
       97  342673*2^2639439-1            794556   L53 2007 
       98  1243*2^2623707-1              789818 L1828 2011 
       99  13*2^2606075-1                784508 L1862 2011 
      100  334310*211^334310-1           777037  p350 2012 Обобщённое Вудала

    Над поиском максимально больших простых чисел в своё время бились Катальди, Декарт, Ферма, Мерсенн, Лейбниц, Эйлер и многие другие математики. По ходу решения этой загадки были разработаны многие разделы теории чисел (например, малая теорема Ферма и квадратичный закон взаимности). В 20-м веке этот поиск привёл к созданию новых быстрых способов перемножения целых чисел: в 1968 году математик Фолкер Штрассен придумал, как использовать для этого быстрое преобразование Фурье. Сейчас этот метод известен как алгоритм Штрассена, его улучшенная версия используется в программном обеспечении GIMPS и повсеместно для быстрого перемножения матриц.

    Загадка простых чисел Мерсенна и поиск новых простых чисел привили любовь к математике многим школьникам, которые в результате выбрали для себя научную и инженерную карьеру.

    Вообще, поиск новых простых чисел, а особенно чисел Мерсенна, можно сравнить с коллекционированием редких вещей.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 140
    • +42
      Можете объяснить, какую выгоду для математики несет нахождение этого числа и других рядомстоящих?
      • +53
        Чье число длиннее :)
        • +16
          В комментарии врывается психоанализ. :]
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              В коментарии врывается ассимитричная криптография.
              • +7
                Скажите, что это была опечатка, или же сюда ворвутся грамматические нацисты!
        • +12
          Можно подарить 10-томник записи 48-го числа какому-нибудь математику, занимающемуся теорией чисел. Оригинальный подарок.
          • НЛО прилетело и опубликовало эту надпись здесь
            • +6
              Ага, а для большей случайности — записать число в двоичной форме :D
              • +3
                «Про генератор случайных чисел ничего нельзя сказать наверняка...»
                • 0
                  9, 9, 9, 9, 9
                  • 0
                    Скорее, FF,FF,FF,FF… Тоже случайная последовательность.
                    • 0
                      Вообще я имел ввиду коммикс про то, как Дилберт идёт по бухгалтерскому аду, а там сидит генератор случайных чисел и долбит: девять, девять, девять… На вопрос, уверены ли они, что числа действительно случайные, отвечают, что никто не может быть уверен.
                      • 0
                        Да, я тоже про него… Вероятно, этот генератор был сделан на десятиричном процессоре.
                        • 0
                          А можно ссылку?
          • +23
            Польза в том, что отдельные люди вообще узнали о числах Мерсенна.
            • +1
              Это прикольно
              • +7
                Если я не ошибаюсь, то существует алгоритм ГПСЧ основанный на числах Мерсенна и можно построить последовательность ПСЧ с периодом равным числу Мерсенна, а последовательность с периодом равным 48 числу Мерсенна в принципе представляет даже комерческий интерес.
                • +2
                  Похожий вопрос наверное задавали и Ньютону в ХVII веке или Ейнштейну в начале ХХ века.

                  Ну а Джордано Бруно вообще сожгли за то, что высказывал ряд догадок, опередивших эпоху и обоснованных лишь последующими астрономическими открытиями: о том, что звёзды далёкие солнца, о существовании неизвестных в его время планет в пределах нашей Солнечной системы, о том, что во Вселенной существует бесчисленное количество тел, подобных Солнцу.

                  • +3
                    Сожгли его в общем-то по вероисповедным соображениям — за то, что он делал еретические выводы из своих научных теорий.
                    • +3
                      Простите, а какая из догадок Бруно опередила эпоху? Та что Иешуа бен Иосиф был магом? Или та что Мариам не могла родить? Или догадка про реинкарнацию?
                      А то сожгли-то его именно за эти догадки.
                    • +36
                      Как, разве не очевидно?
                    • +5
                      «Это отличная идея для футболки» ©
                      • НЛО прилетело и опубликовало эту надпись здесь
                      • 0
                        А, уже ответили… Ох уж эти невзрачные отступы у комментариев.
                        • 0
                          Большие простые числа активно используются в криптографии.
                          • 0
                            Они там в несколько тысяч раз короче
                          • –2
                            Ассимитричная криптография врывается в обсуждение.
                          • +14
                            «Это важное событие для математического сообщества»- както непонятно, каким образом новое 48е число сможет повлиять хоть както на мировую математику? Понятно что соревнование, кто быстрее сорвет куш, но чтото слабо верится что знание 48 а не 47 чисел, хоть както изменит мировую математику.
                            • 0
                              Почитайте книгу «Простая одержимость» и станет всё ясно :)
                              • +1
                                Ну, например, до сих пор не все ясно с распределением простых чисел. В каких-то частях числовой оси они склонны кучковаться, в других огромные числовые промежутки не содержат простых чисел вообще. Это все относится к теории чисел. Зачем она нужна, надеюсь не нужно объяснять.
                                • 0
                                  Нужно ;)

                                  Вообще Риман много интересного сказал про их распределение своей Зета-функцией. Правда, на главный вопрос он всё-таки не ответил.
                            • +12
                              Объясните дураку, не математику, какую это имеет практическую ценность? Зачем находить следующий разряд в числе Пи — вроде ясно, а что с простыми числами?

                              UPD: вот, пока писал, еще двое задали тот же вопрос )
                              • +7
                                Как помне, то польза только в получении опыта при поиске ирасчете. Раз расчет занимает до 6 суток, значит там довольно долгие переборы, или стек нужен неимоверный, а значит приходится писать более сложные программы и мудридь с ядрами. Вот пользя в совершенствовании расчетов и оптимизации железа, я верю, раз смогли вместо 6 суток, довести расчет до 3.6.
                                Но вот когда математики кричат громко, мол очередной переворот в науке найдя очередное эпичное число которое нигде не будет использовано — както смахивает на психов.
                                • +1
                                  Ну это не расчет, а проверка того, что найденное число точно простое.
                                  • +2
                                    Эту журналисты так кричат, а не математики.
                                    • –2
                                      alizar
                                    • +10
                                      На самом деле, примерно такую же, какую ценность имеет, скажем, Формула-1 для рынка серийных авто. Само по себе это число может нафиг никому и не нужно, но для его поиска создали неслабую распределенную вычислительную систему, имеющую рекордный непрерывный срок работы. Из той же статьи следует, что проверить правильность найденного числа — тоже задача нетривиальная. Во всем этом задействована мощная архитектура и куча людей, которые получают опыт в решении больших вычислительных задач. При этом можно смело экспериментировать, возможная ошибка не приведет ни к каким печальным последствиям, в отличии от моделирования какой-нибудь термоядерной реакции, к примеру.
                                      • +2
                                        Да, как раз такая польза понятна и очевидна. Интересовали сами числа — чем может быть полезно число с 17 млн. знаков, куда его можно запихнуть, кроме как в текстовый файл, сопоставимого с числом этих знаков размера?
                                        Есть куча проблем, связанных с тем же Пи или е, решение этих проблем что-то даст науке, тогда как простые числа — просто каждый раз следующее длиннее предыдущего. Вот что не ясно.
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                          • 0
                                            И даже настолько длинные? =)
                                            • +4
                                              Настолько длинные не использовались, потому что их не было известно. Вот найдут ещё хотя бы 2^64 числа такой длины (чтобы метод грубой силы не сработал) — и можно будет строить сверхнадёжную схему, которая чьё-нибудь собрание сочинений сможет закодировать как одну запись :)
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                • +3
                                                  Угадайте, на чём основан самый продинутый генератор псевдослучайных чисел — «Mersenne Twister»?
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                          • +4
                                            Математика примерно на 200 лет опережает промышленность (другими словами, сейчас в промышленности используется аппарат, разработанный 200 лет назад) и примерно на 50 лет запросы физиков. Так что зачем это нужно, мы можем и не узнать.
                                            • +23
                                              Я не разбираюсь, но слышал, что в данный момент теория струн сдерживается именно отсутствием необходимого мат. аппарата.

                                              Лурк, конечно же, надежным источником считать нельзя, но тем не менее:

                                              Уравнения теории струн (и уж тем более её последнего релиза — M-теории) настолько сложны, что физики большей частью оперируют только их приближёнными формами. Что, конечно, не ведёт к повышению точности результатов. Более того, часто складывается такая ситуация, что для решения этих уравнений даже соответствующих математических методов-то не создано, и приходится придумывать всё на лету. Ёбаный стыд. Только этот стыд, собсно, не к самой теории струн, а к нынешнему состоянию математики. Уж пару веков старая добрая ньютоновская небесная механика (никаких вам струн) поставила общую задачу трех тел, а фиг ли толку? Или вот уравнения Навье — Стокса для турбулентных потоков — старая добрая классическая гидродинамика, двести лет отроду. За доказательство существования и гладкости решения (даже не за само решение!) дают миллион американских рублей. Что символизирует.

                                              Практически везде, где физика уперлась в тупик, на самом деле в тупик уперлась математика. И в теории струн — тем более, ибо она там сложнее, чем где бы то ни было. И эта проблема служит источником двух других.
                                              • –24
                                                В математике, кроме полниомов, только что синусы придумали.Все остальные функции покрыты мраком :) Зато научились приближать все остальные функции полнимаи или синусами (ряд Фурье). Всю остальную математику (без геометрии), можно назвать аналитической теория групп, чисел, функциональный анализ, даже тервер… так как выводится из абстрактных понятий.
                                                Правда и теоритическая физика стала черезчур абстрактной.
                                                • +27
                                                  • +1
                                                    Простите. Очень жаль, что вы не прониклись математикой (во всем ее многообразии) и не понимаете, для чего она нужна, и что с ней можно сделать.
                                                    Да и на пальцах сложно объяснить. Вот это как алгоритмы. Вроде бы смотришь, и не понимаешь зачем тебе знать, как массив отсортировать быстрее, клепаешь все сайтики себе на досуге на CMS — ках разных…
                                                    А когда начинаешь изучать (для фана, хотя бы), начинаешь ловить от этого кайф, а потом, когда надо решить нестандартную задачу (~ новую задачу, которую не приходилось решать ранее), понимаешь, что уже думаешь иначе. Вроде бы, явно и не думаешь об алгоритмах, не чертишь кучу матриц, не определяешь сложности… А вот думаешь все равно…
                                                    Кстати, насчет гуманитариев тоже работает — книги читать, историю изучать. Иной раз, вот тоже подумаешь, каков прок от какой-нибудь книги… Ну и так далее…
                                                    • 0
                                                      > В математике, кроме полниомов, только что синусы придумали.Все остальные функции покрыты мраком :)
                                                      Неправда. Есть кучи хорошо изученных функций. Хотя б даже экспонента (и это не полином).
                                                      > Зато научились приближать все остальные функции полнимаи или синусами (ряд Фурье).
                                                      Да. Но это никак не говорит об ограниченности математиков.
                                                      > Всю остальную математику (без геометрии), можно назвать аналитической теория групп, чисел, функциональный анализ, даже тервер… так как выводится из абстрактных понятий.
                                                      Есть очень распространённое мнение (и я являюсь одним из людей, придерживающихся этого мнения), что ВСЯ математика (включая даже упомянутою вами геометрию) выводится из абстрактных понятий. Но в этом нет ничего плохого, наоборот, это хорошо. Абстрактный — это не значит «не имеющий практического применения», «непонятный», «далёкий», «странный», «ненужный». Наоборот, абстрактный значит общий. Выведение математики из абстрактный понятий позволяет сделать математику чётче, строже, логичнее, правильнее.
                                                      > можно назвать аналитической
                                                      Вы так говорите, как будто в этом есть что-то плохое. Слово «аналитический» несёт три смысла:
                                                      1. Непрерывный. Противоположность дискретному. Так говорят о разделах математики, работающих с чем-то непрерывным, т. е. о матане, функане, комплане и т. д. «Синусы» — это как раз анализ, поэтому я не понимаю, почему вы противопоставляете «синусы» «остальным, аналитическим» разделам математики. Эти разделы противопоставляются дискретным разделам, таким как матлог, дискретная математика, алгебра. Естественно, во всех этих разделах нет ничего плохого.
                                                      2. Точный. Противоположность приближённому. Так говорят о вычислениях, сделанных с бесконечно большой точностью, о точных вычислениях. Противопоставляя их приближённым, численным вычислениям, вычислительной математике. Естественно, в таких аналитических вычислениях тоже нет ничего плохого.
                                                      3. Равный своему ряду Тейлора. Полиномы и синусы как раз равны своим рядам Тейлора, поэтому это аналитические функции.
                                                      > Правда и теоритическая физика стала черезчур абстрактной.
                                                      Опять-таки, что в этом плохого?

                                                      Вообще, раньше математика была гораздо проще, чем сейчас. Потом она становилась всё сложнее, и сложнее. Стали появляться всё более сложные задачи, которые требуют сложных методов. Абстрактных, сложных для понимания с точки зрения обычной интуиции. Это есть просто отражение глубокого развития математики. Не нужно делать выводов, что, мол, «математика катится в сраное говно». Нет, просто она растёт, становится сложнее.

                                                      Ответьте мне пожалуйста, moooV. Я тут для вас большой пост написал, если вы не ответите, я буду негодуэ.
                                                      • +1
                                                        А что вы собственно хотите, что бы я ответил? И я не moooV.
                                                        • 0
                                                          Пардон, я имел в виду вас. В общем, уже не надо, спасибо
                                                        • 0
                                                          А я-то тут при чем?

                                                          Вы же цитируете вот этот комментарий (не мой) — просто он серенький и вы промахнулись кнопочкой.
                                                          • 0
                                                            Я не вас имел в виду, извиняюсь
                                                      • +7
                                                        Это и правда, и неправда одновременно.
                                                        Теория струн упёрлась в чудовищную сложность решения собственных уравнений. С одной стороны, да, у математиков нет хорошего аппарата решения таких уравнений. С другой стороны, никто и не обещает, что такой аппарат вообще существует. Ну нет у нелинейных дифференциальных уравнений простых решений.
                                                      • +1
                                                        У этого явления даже есть специальный научный термин

                                                        Непостижимая эффективность математики в естественных науках

                                                        ufn.ru/ru/articles/1968/3/f/
                                                      • +5
                                                        Не все должно иметь практическую ценность. И у нас студенты задавали вопросы на матане — «А какая польза народному хозяйству от того, что есть множество, мощность которого больше множества целых чисел и меньше мощности множества действительных чисел?». Но потом, с опытом, посмотрев назад, понимаешь, что открытия фундаментальной науки далеко не всегда приносят быстрое прикладное применение. И когда-нибудь, вполне возможно, открытия, которые, на первый взгляд, «не имеют практической ценности», станут вполне востребованы.
                                                        Ну кому нужны НА ПРАКТИКЕ Кеплеровские законы движения в момент их открытия? Или расчеты Циолковского? До середины 20-го века практической пользы от них было чуть больше, чем ноль. Так и с этими числами — кому-нибудь да сгодятся.
                                                        P.S. Все, как обычно, IMHO.
                                                        • +7
                                                          Вот такой подход и губит тягу к образованию — я очень благодарен физику в школе, что он не опускал ответы на такие вопросы и не говорил «может и сгодится», если преподаватель не может объяснить нафига его предмет мне нужен, то это печально, очень печально.

                                                          И согласитесь, многие теории и расчеты были сделаны именно, чтобы объяснить уже имеющиеся явления и законы. Тот же расчет траекторий движения планет в древности сколько законов вывел и матаппарат развил, но они знали зачем это делают, а не «может и сгодится».
                                                          • +2
                                                            Вот такой подход и губит тягу к образованию — я очень благодарен физику в школе, что он не опускал ответы на такие вопросы и не говорил «может и сгодится», если преподаватель не может объяснить нафига его предмет мне нужен, то это печально, очень печально.
                                                            Речь идет не о предметах или направлениях (если мы говорим чуть больше, чем о школе), а отдельных открытиях/достижениях/выводах/etc.

                                                            И согласитесь, многие теории и расчеты были сделаны именно, чтобы объяснить уже имеющиеся явления и законы. Тот же расчет траекторий движения планет в древности сколько законов вывел и матаппарат развил, но они знали зачем это делают, а не «может и сгодится».
                                                            А я разве где-то говорил, что кто-то делает для «может и сгодиться»? И в посте, и в комментариях такого нет. Основной вопрос, который обсуждают, какое прикладное значение имеет то или иное открытие. Т.е. если посмотреть чуть выше, то эта ветка растет от поста с вопросом:
                                                            Объясните дураку, не математику, какую это имеет практическую ценность?

                                                            На что я и написал, что не все открытия СРАЗУ имеют ПРИКЛАДНУЮ aka практическую ценность или сразу могут быть поняты и оценены.
                                                          • +2
                                                            Как раз законы Кеплера тогда были очень нужны. В то время не было ни GPS, ни хронометров, а перед путешественниками стояла проблема определения долготы. И астрономические наблюдения были одним из возможных способов узнать точное время. Покрытие звёзд Луной и положение спутников Юпитера — наиболее перспективные на тот момент «небесные часы». А для составления таблиц потребовались бы очень достоверные законы движения планет.
                                                            Но победили, насколько я понимаю, хронометры… Математика тогда проиграла.
                                                          • +2
                                                            Практическую, в смысле — гвоздь забить? Не, гвоздь не забьёшь. Из математики практическую ценность имеет только простейшая арифметика — зарплату считать. Всё остальное — чистая абстракция. Большая часть математики — ни куда не применимая абстракция. На данном этапе. Но иногда, «внезапно» оказывается, что какой-нибудь сугубо абстрактный матаппарат довольно точно описывает или может быть применён к какой-нибудь области физики. Или химии. Или, даже, экономики.

                                                            ЗЫ. А какая практическая польза в нахождении следующего разряда в числе пи? Почти вся практическая ценность пи покрывается его первыми тремя-пятью разрядами.
                                                            • +7
                                                              Любой оверклокер слышал про числа Мерсенна. Дело в том, что их вычисление требует высокой стабильности процессора. Поэтому клиент GIMPS, известный как Prime95, — одна из лучших программ для тестирования стабильности разогнанной системы. Нередка ситуация, когда машина вроде бы стабильна, сутками работает без сбоев, нормально «живёт» в играх. Но стоит лишь запустить Prime95, как через минуту всё обваливается (тем самым дико выбешивая оверклокеров).
                                                            • +2
                                                              Взаимно простые числа тоже могут показаться бесполезной математической абстракцией.
                                                              Однако, они применяются, например в алгоритме шифрования RSA.
                                                              • –19
                                                                Ладно бы телепорт придумали, а то какие-то циферки…
                                                                • +29
                                                                  Циферки это первые шаги к созданию телепорта
                                                                  • +1
                                                                    Это и есть телепорт. Попробуйте записать 48-е простое число Мерсенна на бумаге, и вас сразу телепортирует в любую точку вселенной. Гарантирую.
                                                                    • +4
                                                                      Спасибо, сработало!
                                                                      P.S. Пишу из Малого Магелланова Облака.
                                                                  • 0
                                                                    Число которое в тексте занимает 24 метра, слегка пугает. Попытк аего использования в каких либо расчетах — сравни с безумием. Даже не представляю, что будет, если попытаться загнать это число в переменную и просто умножить х2. Я так думаю, что врядли и 47е число хоть раз дето использовалось.
                                                                    • 0
                                                                      Ну, умножить на два такое число просто, даже на 2^n, где n — любое целое число.При n < 0 погрешность ±1
                                                                      • 0
                                                                        *просто = займет очень мало времени
                                                                        • –3
                                                                          Я имел ввиду программную часть. Вы не сможете просто взять тотже с++, загнать в переменную это число преобразовав его из буфера в число и спокойно умножить. Вот тут и загвоздка, и я понимаю что моего уровня знаний программирования явно нехватит, даже если мне дать доступ к кластеру.
                                                                          • +14
                                                                            В чем сложность? Используйте длинную арифметику. 24мб не так уж и много.
                                                                            • +1
                                                                              Для каждого числа которое участвует в переборе проверяют его простоту, а вот тут числа с сопоставимым размером делят/умножают
                                                                              Вы только представьте: поделить 24мб на 3,5,7,11,13…
                                                                              • +5
                                                                                В исходном комменте человек сказал что его сложно даже умножить на двойку. Что не правда, любой язык, который имеет длинную арифметику справится с такой задачей. Это правда не сложно:)

                                                                                И я не совсем понимаю, причем тут перебор? Для определения простоты числа существуют более подходящие алгоритмы:) Это в школе показывают только перебор как самый простой:)
                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                  • +1
                                                                                    Вообще, для этой задачи используется именно реальная проверка (разработанная для конкретного семейства чисел). Никто не засчитает такой результат, если он был доказан «вероятностно». Конкретных алгоритмов и используемых теорем я, к сожалению, не знаю. Но возможно, что они действительно проверяют цикличность и порядок группы напрямую.
                                                                                    • +1
                                                                                      Первый полиномиальный детерминированный алгоритм для проверки чисел на простоту — http://en.wikipedia.org/wiki/AKS_primality_test.
                                                                                      С тех пор я думаю его существенно улучшили. Но сам по себе алгоритм несложный и мне кажется наглядным примером.
                                                                                      • 0
                                                                                        Интересно. Надо будет разобраться. Как же они так, без факторизации n-1…
                                                                                  • 0
                                                                                    Я привел пример перебором, так как он действительно самый простой. А в данном случае используется специальный тест простоты для чисел Мерсенна
                                                                                    И в этом тесте все равно присутствуют тяжелые для вычислений операции.
                                                                              • +5
                                                                                Даже если не возиться с битами и загнать двоичное представление числа в массив, то умножением или делением на два будет банальный сдвиг влево или вправо соответственно.
                                                                                • +3
                                                                                  Двоичное представление — это много много единиц (число же вида 2^n-1). Осталось лишь сгенерировать 57885161 единичных бит.
                                                                                  • 0
                                                                                    А как его перевести в десятичную запись? Делить двоичное число на 10^9 два миллиона раз — долго. Использовать быстрое умножение чисел в десятичной системе для быстрого возведения в степень? А есть ли такое быстрое умножение вообще?
                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                      • 0
                                                                                        Можно просто умножить «в столбик», если конечно такое число изначально записано в десятичном представлении)
                                                                                        • 0
                                                                                          Умножить в столбик — это O(N^2). Метод Карацубы — O(N^1.6). Но это всё равно под триллион операций. Вопрос — как получить десятичную запись 2^57885161 (я даже не говорю о записи произвольного двоичного числа такой длины) хотя бы за O(N*log(N)*log(log(N)))? И, кстати, как gmplib переводит двоичные числа в десятичные?
                                                                                        • +1
                                                                                          Можно попробовать перемножать быстрым преобразованием Фурье. Система счисления не должна значительно повлиять на алгоритм.
                                                                                          • 0
                                                                                            Хватит ли точности? Если работать по модулю — понадобится простое P>9*10^8 вида N*2^25+1, причём лучше бы ему не выходить за 2^32 (модулярное произведение 64-битных чисел пока делать не очень просто). Если работать в вещественной арифметике, то там вообще всё страшно — никак не проконтролируешь результат.
                                                                                            Но попробовать можно.
                                                                                            • 0
                                                                                              С вещественной арифметикой точно будут проблемы по точности на таких данных. Ну, а работа с 64-битными числами — это все равно О(1), так что почему бы и нет.

                                                                                              Уверен, есть и более продвинутые методы, но и БПФ вроде не испытывает неразрешимых трудностей. Гораздо интереснее будет проверять потом это число на простоту:)
                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                                        • 0
                                                                                          Храните в строке, идёте посимвольно с конца. И как в школе сложение в столбик )
                                                                                          • 0
                                                                                            Лет 10 назад в Петербургском Политехе у друга была лаба — арифметические операции с числами произвольной длины. Алгоритм был действительно аналогичен решению «в столбик».
                                                                                      • +1
                                                                                        Умножил, проверяйте :)
                                                                                        docs.google.com/file/d/0B3EUpqC1CLrLTGhyNVNFYlQtNGc/edit?usp=sharing

                                                                                        Вывод моей маленько программы (я использовал GNU MP Bignum Library из C#)
                                                                                        Parsing
                                                                                        Parsing complete: 00:00:09.7086424
                                                                                        Multiplication complete: 00:00:00.0039770
                                                                                        Converting back to string complete: 00:00:39.7476771
                                                                                        Saving complete: 00:00:00.0601891

                                                                                        P.S. не пытайтесь парсить с помощью встроенного в .Net BigInteger

                                                                                        Использовалось одно ядро core i5-2310 @ 2.9GHz
                                                                                      • +2
                                                                                        Разработчики программного обеспечения GIMPS и участники проекта уже поделили приз $100 000 за прошлое простое число Мерсенна с как минимум 10 миллионами десятичных разрядов. Следующий приз — $150 000 за число с как минимум 100 миллионами десятичных разрядов.

                                                                                        Все, пишу программу на Паскале, ставлю работать ноутбук на ночь и утром еду за деньгами.
                                                                                        • –4
                                                                                          Не думаю, что все будет так просто. Ваш ноутбук и программа на паскале будут работать несколько месяцев, и за это время Вас опередит тот, кто колбасился с оптимизацией и таки достоен этих денег (хотя $150k — ИМХО, многовато за такое).
                                                                                          • +6
                                                                                            Я читал пост :) Это был сарказм
                                                                                        • 0
                                                                                          $150k и затраты, это несоизмеримые размеры. Оно только кажется со стороны что все так просто. Кол-во затрат человеко/часов там видимо просто оргомно, а в денежном эквиваленте идет счет на миллионы. Плюс по железу, с учетом проб и ошибок, заказа нового железа, разработки более мошного. Сидя в инете думаешь что получив доступ к железу можно свернуть горы, но когда реально берешся даже са самый простой проэкт и его внедрение, видишь сколько сжирается времени и денег.
                                                                                          Одно дело когда какойто студент случайно чтото находит, другое дело когда целые команды над этим бьются, вот тогда эти $100-$150к просто капля в море.
                                                                                          • 0
                                                                                            У кого есть сомнения, откройте ссылку с числом из темы и откиньтесь на спинку кресла, попутно рассуждая о смысле жизни.
                                                                                          • +1
                                                                                            << 17.425.170 десятичных знаков
                                                                                            << 22,45 МБ

                                                                                            Я чего-то не понимаю?

                                                                                            upd: видимо, учитывались также запятые.
                                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                                              • +2
                                                                                                На сайте указано Decimal digits American style (ох, уж эти американцы), а значит используется запятая как разделитель групп разрядов (wiki).

                                                                                                Например, запись 1,546 в английской нотации обозначает тысяча пятьсот сорок шесть, а в русской — одна целая пятьсот сорок шесть тысячных.
                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                • +1
                                                                                                  Между разрядами

                                                                                                  ps не обновил комментарии перед отправкой
                                                                                              • +9
                                                                                                Теперь будем с нетерпением ждать 49-е простое число Мерсенна.
                                                                                                • +33
                                                                                                  Да, вот тогда-то мы заживём!
                                                                                                • +1
                                                                                                  на вики написано, что уже найдено 49 чисел
                                                                                                  где-то найоб
                                                                                                  • 0
                                                                                                    да все просто: поиск вероятностными алгоритмами (к которым относится алгоритм Мерсена) занимают сравнительно небольшое время, а вот проверка простоты — годы.
                                                                                                    где-то тут primes.utm.edu/ есть инфа по тому, когда было обнаружено простое и через сколько было таки доказано, что оно простое — до 6 лет доходит
                                                                                                    • +1
                                                                                                      Проверка просторы одного конкретного числа — на такое уж большое дело.
                                                                                                      В статье написано, что проверка простоты данного числа заняла 6 суток на 32-ядерном компьютере и 3,6 на GPU. Годы оно занимало когда компьютеров не было :)
                                                                                                      • 0
                                                                                                        были копьютеры, и гимпс был :)
                                                                                                        компьютеры правда были послабее, но тест на простоту чисел Мерсена более эффективен
                                                                                                        потому самые большие из найденых простых — числа Мерсена
                                                                                                        • 0
                                                                                                          Ну, не только поэтому. Их ещё и перебирать легче :) И с каждым «шагом» количество не подлежащих проверке чисел удваивается :). Для обычных-то чисел нужно идти довольно мелким шагом.
                                                                                                          • 0
                                                                                                            ну да, собственно потому и найдено 49 чисел, а с порядковым номером 47 только сейчас :)
                                                                                                • –1
                                                                                                  В чем вообще суть? Я так понимаю алгоритм поиска таких чисел проработан и теперь вопрос времени, когда «выскочет» еще такое число, но это не случайность, а работа алгоритма, сложного, ресурсоемкого, но абсолютно прозрачного алгоритма — в чем инновация, что алгоритм поиска таких чисел работает и постепенно находит все новые числа. То есть ведь ни для кого не секрет, что поработает система еще какое-то время и будет заголовок про 49-ое число, а потом 50-ое и тд. Это вопрос времени и доступных ресурсов системы.
                                                                                                  • +1
                                                                                                    Это как говорить что отправиться за пределы галактики — дело лишь времени ;)

                                                                                                    Я тоже в школе писал программу по нахождению простых, первые 15 находились быстро, но потом… Думаю проблема в том, что более длинное может быть нерентабельным открывать сегодняшним способом. А раз есть проблема, то и решение найдут возможно быстрее чем 49е Мерсенна, а когда-нибудь обгоним и Вояджер :)
                                                                                                    • 0
                                                                                                      Нахождение больших простых позволяет строить их распределение: подтверждать или опровергать вероятностные алгоритмы поиска простых. Ну и приблизится к выработке формулы простого.
                                                                                                    • 0
                                                                                                      > 1 2^57885161-1 17425170 G13 2013 Мерсенн 48??

                                                                                                      А что означают вопросики в конце?
                                                                                                    • 0
                                                                                                      Всего-то 174251,7 гуголов.
                                                                                                      • 0
                                                                                                        Нет, гугол в степени 174251,7 :(
                                                                                                        • 0
                                                                                                          Это уже какое-то полностью невообразимое число получится…
                                                                                                          • 0
                                                                                                            Ну, как бы, Mrrl прав. :)
                                                                                                            А число и так невообразимое.
                                                                                                      • +2
                                                                                                        У нас есть новое число на место параметра p для генерации криптографического ключа! :-)
                                                                                                        • 0
                                                                                                          По теории криптографии на место параметра p лучше подходит псевдослучайное число, чем известная другим величина.Таким образом увеличивая стойкость криптосистемы.
                                                                                                          • 0
                                                                                                            Это-то да, но оно все равно простое, а то что мы взяли его «специально» об этом мы «врагам» не скажем :-) Зато сами будем довольны тем фактом, что использовали самое большое простое число.
                                                                                                      • 0
                                                                                                        Ну, чтоже ждем лет эдак через >4 следующее простое число, я так понял, время поиcка увеличивается с геометрической прогрессией?
                                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                        • 0
                                                                                                          Очень рростым языком о том зачем криптологам простые числа:

                                                                                                          • 0
                                                                                                            А как проверить, что оно правда простое?
                                                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                              • 0
                                                                                                                Ну это самый примитивный способ. Можно проверить намного быстрее, используя алгоритм AKS или его производные. Эта ветвь теории чисел сейчас как раз активно развивается.

                                                                                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.