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

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

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

• 321-числа: простые числа вида ;
• числа Софи Жермен: такое простое , что также является простым;
• обобщенные простые числа Ферма: простые числа вида ;
• факториальные простые числа (англ.): простые вида (последовательность A088054 в OEIS);
• праймориальные простые числа (англ.): простые числа вида (последовательности A014545 и A014545 в OEIS);
• простые числа Прота: простые числа вида ,  — нечетно, (последовательность A080076 в OEIS);
• простые числа Каллена (англ.): простые числа вида (последовательность A005849 в OEIS);
• простые числа Вудалла (англ.): простые числа вида (последовательность A002234 в OEIS);
• обобщенные простые числа Вудалла: простые числа вида ;
• простые числа Виферича (англ.): такие простые , что делится на (последовательность A001220 в OEIS);
• предположительно простые числа (англ.);
• простые числа-близнецы: пара простых чисел, отличающихся на 2 (последовательности A006512 и A001359 в OEIS).

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

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

• проблемы Ризеля: поиск такого минимального нечётного , что число является составным для всех натуральных ;
• проблемы Серпинского: поиск такого минимального нечетного натурального , что число является составным для всех натуральных (совместно с проектом Seventeen or Bust).

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

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

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

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

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

5 декабря 2007 года добавлен подпроект для поиска чисел вида с использованием программного обеспечения LLR^[5].

29 июня 2008 года подпроект по поиску чисел вида , проверивший диапазон значений n < 5·10⁶, переключен на поиск чисел вида ^[6].

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

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

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

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

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

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

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

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

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

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

Научные достижения

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

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 простых чисел :
  • 12353443596260323+23793841×23#×n;
  • 46176957093163301+1109121×23#×n;
  • 18162964758258289+3755664×23#×n;
  • 20919497549238289+3155495×23#×n;
  • 2960886048458003+2346233×23#×n.
• Арифметические прогрессии из 24 простых чисел :
  • 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 простых чисел :
  • 43142746595714191+23681770×23#×n.
• Арифметические прогрессии из 25 простых чисел :
  • 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 год

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

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

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

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

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

Примечания