PrimeGrid (PrimeGrid)

PrimeGrid — проект добровольных распределенных вычислений на платформе BOINC, целью которого является поиск различных простых чисел специального вида. Проект стартовал 12 июня 2005 года. По состоянию на 25 марта 2012 года в нём приняли участие более 49 000 пользователей (156 565 компьютеров) из 188 стран, в совокупности обеспечивая производительность 3,3 петафлопс.

Список подпроектов

В проекте производится поиск простых чисел специального вида следующих типов:

• 321-числа: простые числа вида $3\cdot 2^{n}\pm 1$;
• числа Софи Жермен: такое простое $p$, что $2p+1$ также является простым;
• обобщенные простые числа Ферма: простые числа вида $a^{2^{n}}+b^{2^{n}}$ (частный случай, $k^{2^{n}}+1$);
• факториальные простые числа: простые вида $n!\pm 1$ (последовательность A088054 в OEIS);
• праймориальные простые числа: простые числа вида $n\#\pm 1$ (последовательности A014545 и A014545 в OEIS);
• простые числа Прота: простые числа вида $k\cdot 2^{n}+1$, $k$ — нечетно, $2^{n}>k$ (последовательность A080076 в OEIS);
• простые числа Каллена: простые числа вида $n\cdot 2^{n}+1$ (последовательность A005849 в OEIS);
• простые числа Вудала: простые числа вида $n\cdot 2^{n}-1$ (последовательность A002234 в OEIS);
• обобщённые простые числа Вудалла: простые числа вида $n\cdot k^{n}-1$;
• простые числа Вифериха: такие простые $p$, что $2^{p-1}-1$ делится на $p^{2}$ (последовательность A001220 в OEIS);
• предположительно простые числа;
• простые числа-близнецы: пара простых чисел, отличающихся на 2 (последовательности A006512 и A001359 в OEIS).

Поиск простых чисел Каллена, Вудалла, Прота и обобщённых простых чисел Ферма эффективно реализуется с использованием вычислительных возможностей современных видеокарт Nvidia (технология CUDA).

Часть вычислительных мощностей проекта используется для решения открытых математических проблем:

• проблемы Ризеля: поиск такого минимального нечётного $k$, что число $k\cdot 2^{n}-1$ является составным для всех натуральных $n$;
• проблемы Серпинского: поиск такого минимального нечётного натурального $k$, что число $k\cdot 2^{n}+1$ является составным для всех натуральных $n$ (поглотив проект Seventeen or Bust);
• проблемы Серпинского — Ризеля по основанию 5: поиск такого минимального нечётного $k$, что число $k\cdot 5^{n}-1$ является составным для всех натуральных $n$.

В 2010 году была найдена первая известная арифметическая прогрессия из 26 простых чисел (подпроект AP26). В 2019 году была найдена первая известная арифметическая прогрессия из 27 простых чисел (подпроект AP26/AP27).

Для тестов простоты используются алгоритмы Люка-Лемера-Ризеля и решета.

История проекта

3 июля 2007 года добавлен подпроект, направленный на поиск простых чисел Каллена/Вудалла. Уже 8 августа 2007 года было открыто первое новое простое число Вудалла 2013992×2^2013992−1, содержащее 606 279 цифр.

13 октября 2007 года добавлен подпроект, целью которого является решение проблемы Серпинского.

5 декабря 2007 года добавлен подпроект для поиска чисел вида $3\cdot 2^{n}-1$ с использованием программного обеспечения LLR.

29 июня 2008 года подпроект по поиску чисел вида $3\cdot 2^{n}-1$, проверивший диапазон значений n < 5⋅10⁶, переключён на поиск чисел вида $3\cdot 2^{n}+1$.

26 декабря 2008 года добавлен подпроект, направленный на поиск праймориальных простых чисел.

27 декабря 2008 года добавлен подпроект AP26, целью которого является поиск арифметической прогрессии из 26 простых чисел.

16 августа 2009 года добавлен подпроект, направленный на поиск простых чисел Софи Жермен.

10 ноября 2009 года добавлен подпроект по поиску обобщённых чисел Ферма.

10 декабря 2009 года для подпроекта AP26 добавлен расчётный клиент с поддержкой технологии CUDA.

31 января 2010 года начато сотрудничество с проектом Seventeen or Bust, направленное на решение проблемы Серпинского.

1 декабря 2010 года анонсирован новый расчётный модуль для поиска простых чисел Прота методом решета с поддержкой технологий CUDA и OpenCL.

7 января 2011 года добавлен подпроект для решения проблемы Серпинского/Ризеля по основанию 5.

9 января 2012 года в модуле LLR реализована поддержка векторных расширений системы команд процессора AVX, что обеспечивает 20—50 % прибавку в производительности в зависимости от приложения.

4 февраля 2012 года реализован расчётный модуль genefer для поиска обобщённых чисел Ферма с поддержкой технологии CUDA.

Достижения

В результате выполняемых расчётов был открыт ряд простых чисел специального вида и арифметических прогрессий из простых чисел.

2007 год

• Числа Вудалла:
  • 3752948×2^3752948−1 (1 129 757 цифр) — самое большое известное простое число Вудалла;
  • 2367906×2^2367906−1 (712 818 цифр);
  • 2013992×2^2013992−1 (606 279 цифр).

2008 год

• 321-числа:
  • 3×2^4235414−1 (1 274 988 цифр).
• Числа Прота:
  • 258317×2^5450519+1 (1 640 776 цифр);
  • 265711×2^4858008+1 (1 462 412 цифры);
  • 651×2⁴⁷⁶⁶³²+1 (143 484 цифры);
  • 825×2³⁷³³³¹+1 (112 387 цифр).

2009 год

• Арифметические прогрессии из 25 простых чисел $(0\leq n\leq 24)$:
  • 12353443596260323+23793841×23#×n;
  • 46176957093163301+1109121×23#×n;
  • 18162964758258289+3755664×23#×n;
  • 20919497549238289+3155495×23#×n;
  • 2960886048458003+2346233×23#×n.
• Арифметические прогрессии из 24 простых чисел $(0\leq n\leq 23)$:
  • 4891686128805269+19453568×23#×n;
  • 4687877159107031+18203167×23#×n;
  • 1948053460212667+17745794×23#×n;
  • 3634080452156039+16981607×23#×n;
  • 10307159737232191+14120563×23#×n;
  • 13678065943093049+13223804×23#×n;
  • 10317962076055027+10241601×23#×n;
  • 7979661543967237+9936237×23#×n;
  • 39421708111691+9740894×23#×n;
  • 5531900872160491+9383796×23#×n;
  • 13432401425380607+9219580×23#×n;
  • 14992521666441877+8832442×23#×n;
  • 167806194923077+4935146×23#×n;
  • 6274259724784693+2522655×23#×n;
  • 7960592659339799+2326495×23#×n;
  • 6872932294461509+2042703×23#×n;
  • 20187352211709911+1799216×23#×n;
  • 2725131905640097+1342336×23#×n;
  • 25545151920212759+1140241×23#×n;
  • 13785500104035967+1004314×23#×n;
  • 19471368812966089+410682×23#×n;
  • 19516186145019209+313705×23#×n;
  • 20909681071069667+234797×23#×n.
• 321-числа:
  • 3×2^5082306+1 (1 529 928 цифр).
• Числа Каллена:
  • 6679881×2^6679881+1 (2 010 852 цифры) — самое большое известное простое число Каллена;
  • 6328548×2^6328548+1 (1 905 090 цифр).
• Числа Прота:
  • 27×2^2218064+1 (667 706 цифр);
  • 659×2⁶¹⁷⁸¹⁵+1 (185 984 цифры);
  • 519×2⁵⁶⁷²³⁵+1 (170 758 цифр);
  • 15×2⁴⁸³⁰⁹⁸+1 (145 429 цифр).
• Обобщённые простые числа Вудалла:
  • 563528×13⁵⁶³⁵²⁸−1 (627 745 цифр).
• Предположительно простые числа:
  • 2^4583176+2131 (1 379 674 цифры).
• Другие:
  • 27×2^1902689−1 (572 768 цифр).

2010 год

• Арифметическая прогрессия из 26 простых чисел $(0\leq n\leq 25)$:
  • 43142746595714191+23681770×23#×n.
• Арифметические прогрессии из 25 простых чисел $(0\leq n\leq 24)$:
  • 18626565939034793+30821486×23#×n;
  • 25300381597038677+28603610×23#×n;
  • 42592855872841649+19093314×23#×n;
  • 24715375237181843+19071018×23#×n;
  • 46428033558097831+12893265×23#×n;
  • 58555890166091939+10416756×23#×n;
  • 49644063847333931+7851809×23#×n.
• 321-числа:
  • 3×2^6090515−1 (1 833 429 цифр).
• Числа Прота:
  • 90527×2^9162167+1 (2 758 093 цифры).
• Факториальные простые числа:
  • 103040!−1 (471 794 цифры);
  • 94550!−1 (429 390 цифр).
• Праймориальные простые числа:
  • 843301#−1 (365 851 цифра) — самое большое известное праймориальное простое число на момент открытия;
  • 392113#+1 (169 966 цифр).
• Проблема Серпинского — Ризеля по основанию 5:
  • 151026×5⁵⁵⁹⁶⁷⁰−1 (391 198 цифр);
  • 3938×5⁵⁵⁸⁰³²−1 (390 052 цифры);
  • 105782×5⁵⁵¹⁷⁶⁶−1 (385 673 цифры);
  • 183916×5⁵¹⁹⁵⁹⁷−1 (363 188 цифр);
  • 53542×5⁵¹⁵¹⁵⁵−1 (360 083 цифры).
• Проблема Ризеля: найдено простое число 191249×2^3417696−1 (1 028 835 цифр), основание 191249 исключено из рассмотрения.

2011 год

• Простые-близнецы:
  • 3756801695685×2⁶⁶⁶⁶⁶⁹±1 (200 700 цифр) — самая большая известная пара простых-близнецов.
• Обобщённые простые числа Ферма:
  • 75898⁵²⁴²⁸⁸+1 (2 558 647 цифр);
  • 361658²⁶²¹⁴⁴+1 (1 457 075 цифр);
  • 145310²⁶²¹⁴⁴+1 (1 353 265 цифр);
  • 40734²⁶²¹⁴⁴+1 (1 208 473 цифр).
• Числа Прота:
  • 9×2^2543551+1 (765 687 цифр);
  • 25×2^2141884+1 (644 773 цифры);
  • 4479×2²²⁶⁶¹⁸+1 (68 223 цифры);
  • 3771×2²²¹⁶⁷⁶+1 (66 736 цифр);
  • 7333×2¹³⁸⁵⁶⁰+1 (41 716 цифр).
• Факториальные простые числа:
  • 110059!-1 (507 082 цифр).
• 321-числа:
  • 3×2^7033641+1 (2 117 338 цифр).
• Обобщённые числа Вудалла:
  • 404882×43⁴⁰⁴⁸⁸²-1 (661 368 цифр).
• Проблема Ризеля: в результате нахождения простых чисел
  • 353159×2^4331116-1 (1 303 802 цифр),
  • 141941×2^4299438-1 (1 294 265 цифр),
  • 123547×2^3804809-1 (1 145 367 цифр),
  • 415267×2^3771929-1 (1 135 470 цифр),
  • 65531×2^3629342-1 (1 092 546 цифр),
  • 428639×2^3506452-1 (1 055 553 цифры)

исключены из рассмотрения основания 428639, 415267, 353159, 141941, 123547, 65531. Непроверенными на тот момент оставались ещё 57 оснований.

2012 год

• Числа Прота:
  • 7×2^5775996+1 (1 738 749 цифр);
  • 9×2^3497442+1 (1 052 836 цифр);
  • 81×2^3352924+1 (1 009 333 цифры);
  • 131×2^1494099+1 (449 771 цифра);
  • 329×2^1246017+1 (375 092 цифры);
  • 1705×2⁹⁰⁶¹¹⁰+1 (272 770 цифр);
  • 7905×2³⁵²²⁸¹+1 (106 052 цифры).
• Обобщённые простые числа Ферма:
  • 475856⁵²⁴²⁸⁸+1 (2 976 633 цифры) — самое большое известное обобщённое простое число Ферма;
  • 341112⁵²⁴²⁸⁸+1 (2 900 832 цифры);
  • 773620²⁶²¹⁴⁴+1 (1 543 643 цифры)
  • 676754²⁶²¹⁴⁴+1 (1 528 413 цифр)
  • 525094²⁶²¹⁴⁴+1 (1 499 526 цифр).
• Обобщённые простые числа Каллена:
  • 427194×113⁴²⁷¹⁹⁴+1 (877 069 цифр) — самое большое известное обобщённое простое число Каллена.
• Праймориальные простые числа:
  • 1098133#−1 (476 311 цифр) — самое большое праймориальное простое число среди известных.
• Проблема Ризеля: в результате нахождения простых чисел
  • 252191×2^5497878−1 (1 655 032 цифры)
  • 162941×2⁹⁹³⁷¹⁸−1 (299 145 цифр)

исключены из рассмотрения основания 162941 и 252191. Непроверенными остаются ещё 55 оснований.

• Проблема Серпинского: в результате нахождения простых чисел
  • 147559×2^2562218+1 (771 310 цифр),
  • 123287×2^2538167+1 (764 070 цифр)

исключены из рассмотрения основания 123287 и 147559. Непроверенными остаются ещё 15 оснований.

• Простые Софи Жермен:
  • 18543637900515×2⁶⁶⁶⁶⁶⁷−1 (200 701 цифра) — самое большое известное простое Софи Жермен.
• Другие:
  • 27×2^3855094−1 (1 160 501 цифра).

2013 год

• Числа Прота:
  • 57×2^2747499+1 (827 082 цифры)
  • 183×2^1747660+1 (526 101 цифра)
  • 2145×2^1099064+1 (330 855 цифр)
• Проблема Ризеля: в результате нахождения простых чисел
  • 40597×2^6808509–1 (2 049 571 цифра);
  • 304207×2^6643565−1 (1 999 918 цифр)
  • 398023×2^6418059−1 (1 932 034 цифры)

исключены из рассмотрения основания 40597, 304207 и 398023. Непроверенными остаются ещё 52 основания.

• Факториальные простые числа:
  • 147855!−1 (700 177 цифр)
• Проблема Серпинского — Ризеля по основанию 5:
  • 37292×5^1487989+1 (1 040 065 цифр)
  • 173198×5^1457792−1 (1 018 959 цифр)

2014 год

• Проблема Серпинского — Ризеля по основанию 5:
  • 325918×5^1803339−1 (1 260 486 цифр);
  • 138172×5^1714207−1 (1 198 185 цифр);
  • 22478×5^1675150−1 (1 170 884 цифры);
  • 326834×5^1634978−1 (1 142 807 цифр);
  • 207394×5^1612573−1 (1 127 146 цифр);
  • 104944×5^1610735−1 (1 125 861 цифра);
  • 330286×5^1584399−1 (1 107 453 цифры);
  • 22934×5^1536762−1 (1 074 155 цифр);
  • 178658×5^1525224−1 (1 066 092 цифры);
  • 59912×5^1500861+1 (1 049 062 цифр).
• 321-числа:
  • 3×2^11484018−1 (3 457 035 цифр);
  • 3×2^10829346+1 (3 259 959 цифр).
• Числа Прота:
  • 35×2^3587843+1 (1 080 050 цифр);
  • 35×2^3570777+1 (1 074 913 цифр);
  • 33×2^3570132+1 (1 074 719 цифр);
  • 93×2^3544744+1 (1 067 077 цифр);
  • 87×2^3496188+1 (1 052 460 цифр);
  • 51×2^3490971+1 (1 050 889 цифр);
  • 255×2^3395661+1 (1 022 199 цифр).
• Проблема Ризеля: в результате нахождения простых чисел
  • 502573×2^7181987−1 (2 162 000 цифр) — самое большое известное число Ризеля;
  • 402539×2^7173024−1 (2 159 301 цифра)

исключены из рассмотрения основания 402539 и 502573. Непроверенными остаются ещё 50 оснований.

2015 год

• Числа Прота:
  • 27×2^5213635+1 (1 569 463 цифры);
  • 191×2^3548117+1 (1 068 092 цифры);
  • 141×2^3529287+1 (1 062 424 цифры);
  • 249×2^3486411+1 (1 049 517 цифр);
  • 195×2^3486379+1 (1 049 507 цифр);
  • 197×2^3477399+1 (1 046 804 цифры);
  • 113×2^3437145+1 (1 034 686 цифр);
  • 159×2^3425766+1 (1 031 261 цифра);
  • 177×2^3411847+1 (1 027 071 цифра);
  • 267×2^2662090+1 (801 372 цифры).
• 321-числа:
  • 3×2^11895718−1 (3 580 969 цифр) — самое большое известное 321-число, самое большое простое число, открытое в проекте PrimeGrid;
  • 3×2^11731850−1 (3 531 640 цифр).
• Проблема Серпинского — Ризеля по основанию 5:
  • 100186×5^2079747−1 (1 453 686 цифр);
  • 144052×5^2018290+1 (1 410 730 цифр).
• Обобщённые числа Ферма:
  • 42654182¹³¹⁰⁷²+1 (1 000 075 цифр).

2016 год

• Числа Прота:
  • 189×2^3596375+1 (1 082 620 цифр)
  • 275×2^3585539+1 (1 079 358 цифр)
  • 309×2^3577339+1 (1 076 889 цифр)
  • 251×2^3574535+1 (1 076 045 цифр) .
  • 381×2^3563676+1 (1 072 776 цифр)
  • 351×2^3545752+1 (1 067 381 цифра)
  • 345×2^3532957+1 (1 063 529 цифр)
  • 329×2^3518451+1 (1 059 162 цифры)
  • 495×2^3484656+1 (1 048 989 цифр)
  • 323×2^3482789+1 (1 048 427 цифр)
  • 491×2^3473837+1 (1 045 732 цифры)
  • 453×2^3461688+1 (1 042 075 цифр)
  • 479×2^3411975+1 (1 027 110 цифр) ;
  • 373×2^3404702+1 (1 024 921 цифра) ;
  • 303×2^3391977+1 (1 021 090 цифр) ;
  • 453×2^3387048+1 (1 019 606 цифр) ;
  • 369×2^3365614+1 (1 013 154 цифры) ;
  • 393×2^3349525+1 (1 008 311 цифра) ;
  • 403×2^3334410+1 (1 003 716 цифр) ;
  • 387×2^3322763+1 (1 000 254 цифры) .
• Проблема Серпинского — Ризеля по основанию 5:
  • 180062×5^2249192−1 (1 572 123 цифры) ;
  • 53546×5^2216664−1 (1 549 387 цифр) ;
  • 296024×5^2185270−1 (1 527 444 цифры) ;
  • 92158×5^2145024+1 (1 499 313 цифры) ;
  • 77072×5^2139921+1 (1 495 746 цифр) ;
  • 306398×5^2112410−1 (1 476 517 цифр) ;
  • 154222×5^2091432+1 (1 461 854 цифры) .
• Обобщённые простые числа Ферма:
  • 1828858²⁶²¹⁴⁴+1 (1 641 593 цифры) ;
  • 1615588²⁶²¹⁴⁴+1 (1 627 477 цифр) ;
  • 1488256²⁶²¹⁴⁴+1 (1 618 131 цифра) ;
  • 1415198²⁶²¹⁴⁴+1 (1 612 400 цифр) ;
  • 43165206¹³¹⁰⁷²+1 (1 000 753 цифры) ;
  • 43163894¹³¹⁰⁷²+1 (1 000 751 цифра) .
• Простые Софи Жермен:
  • 2618163402417×2^1290000−1 (388 342 цифры) — самое большое известное простое Софи Жермен.

Последующие годы

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

Ссылки

• Официальный сайт проекта
• PrimeGrid Mega Primes

См. также

• Арифметические прогрессии из простых чисел
• Добровольные вычисления
• Открытые проблемы в теории чисел
• Простые числа
• BOINC
• GIMPS
• Seventeen or Bust