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

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

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

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

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

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

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

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

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

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

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

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

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

29 июня 2008 года подпроект по поиску чисел вида ${\displaystyle 3\cdot 2^{n}-1}$ , проверивший диапазон значений n < 5⋅10 ⁶ , переключён на поиск чисел вида ${\displaystyle 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 простых чисел ${\displaystyle (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 простых чисел ${\displaystyle (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 простых чисел ${\displaystyle (0\leq n\leq 25)}$ :
  • 43142746595714191+23681770×23#×n.
• Арифметические прогрессии из 25 простых чисел ${\displaystyle (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 продолжает набирать все большую и большую вычислительную мощь. На текущий момент новые результаты - простые числа специального вида - появляется каждые несколько дней. Анонсирование этих достижений в реальном времени осуществляется в Дискорд-канале сообщества .

Примечания

Ссылки

См. также

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