Что значит найти наибольшее простое число?

[atlakatl]

Недавно прошло сообщение, что найдено наибольшее простое число. Это по-прежнему одно из чисел Мерсенна: $2^{74 207 281} - 1$
Именно числа Мерсенна легче всего проверяются на простоту. Вот их и проверяют.

В то же время в https://ru.wikipedia.org/wiki/Простое_число читаем, что давно известен многочлен $25$-й степени, все положительные значения которого – простые числа.
Вот у меня и вопрос: что мешает подставить как угодно большое положительное число в качестве коэффициента при $25$-й степени? Значение многочлена в этом случае тоже будет положительным, - а значит именно простым числом?
Предвижу возражение: значение такого многочлена трудно вычислять. Так и от числа Мерсенна никто не требует именно десятичной записи: указали степень – и хватит.
Так в чём в итоге заключается гонка за наибольшим простым числом? – Если вариант с таким многочленом проходит?

[gris]

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

[arseniiv]

atlakatl в сообщении #1095224 писал(а):

Так и от числа Мерсенна никто не требует именно десятичной записи: указали степень – и хватит.

Но ведь абы какую степень не подставишь — надо убедиться, что число простое. С числами Мерсенна проверка получается пока что проще, чем для каких-то других семейств простых (или всех простых вообще) подобной величины.

atlakatl в сообщении #1095224 писал(а):

Вот у меня и вопрос: что мешает подставить как угодно большое положительное число в качестве коэффициента при $25$-й степени?

Вот я взял СКА, рассовал слагаемые многочлена по степеням и нашёл, что, действительно, 25-й степени только одно из них (а могло оказаться несколько!). Только вот оно равно $-256 d^4 k u^{16} y^4$, так что как угодно большие значения $d,k,u,y$ немного не в ту сторону будут работать. Вообще я согласен с gris.

atlakatl в сообщении #1095224 писал(а):

Так в чём в итоге заключается гонка за наибольшим простым числом?

Ну, это как знаки $\pi$. У больших простых есть криптографическое использование, но слишком большие, наверно, уже использовать неудобно.

-- Сб янв 30, 2016 11:43:18 --

Потом, легко, если снова говорить о практических применениях, сгенерировать представление числа Мерсенна $2^a - 1$ по его параметру $a$: просто пишем $a$ двоичных единиц подряд — а вот по тем 26 параметрам считать значение будет довольно утомительно.

-- Сб янв 30, 2016 11:47:18 --

(Оффтоп)

Если кому-то нужна удобоваримая для экспериментов в СКА или где ещё запись того многочлена, вот она:

(2 + k)*(1 - (1 - i + a*i + k - l)^2 - (1 + (-1 + a^2)*l^2 - m^2)^2 - (1 - f^2 + 16*(1 + k)^3*(2 + k)*(1 + n)^2)^2 - (1 + (1 + a)^2*e^3*(2 + e) - o^2)^2 - (-m + l*(-1 + a - n) + b*(-2 + 2*a - 2*n + 2*a*n - n^2) + p)^2 - (l + n + v - y)^2 - (q + (-2 + 2*a - 2*p + 2*a*p - p^2)*s - x + (-1 + a - p)*y)^2 - (1 - x^2 + (-1 + a^2)*y^2)^2 - (1 - u^2 + 16*(-1 + a^2)*r^2*y^4)^2 - (1 - (c*u + x)^2 + (-1 + (a + u^2*(-a + u^2))^2)*(n + 4*d*y)^2)^2 - (h + (h + j)*(1 + 2*g + k + g*k) - z)^2 - (-e + 2*n + p + q + z)^2 - (-(m*p) + l*(a - p)*p + (-1 + 2*a*p - p^2)*t + z)^2 - (h + j - q + w*z)^2)

Переменные, как нетрудно догадаться, все буквы от a до z.

[yk2ru]

atlakatl в сообщении #1095224 писал(а):

что мешает подставить как угодно большое положительное число в качестве коэффициента при $25$-й степени? Значение многочлена в этом случае тоже будет положительным, - а значит именно простым числом?

У какого слагаемого там $25$ степень?

[arseniiv]

arseniiv в сообщении #1095226 писал(а):

$-256 d^4 k u^{16} y^4$

[atlakatl]

arseniiv
Понял в чём фишка. Все $26$ переменных должны быть натуральными числами. Т.е. в бесконечности многочлен сей отрицателен. И надо "поймать волну" на графике, где значение его положительно. - А это может быть или в районе не слишком больших чисел, или вообще проблематично в поиске.
Всем спасибо за ответ.

[gris]

Ну Вы даёте! В какой бесконечности? Если существует шар, вне которого многочлен отрицателен, то это противоречит бесконечности простых чисел.

[arseniiv]

atlakatl в сообщении #1095231 писал(а):

И надо "поймать волну" на графике, где значение его положительно. - А это может быть или в районе не слишком больших чисел, или вообще проблематично в поиске.

Ага. Я его тут погонял со случайными аргументами. По несколько миллионов из 0…999, 0…9, 0…4, 0…2, 0…999 999 999 и ещё некоторых интервалов. Ноль положительных значений. Это показывает просто и прямо, что ничем не приправленный перебор практически бессмыслен.

[grizzly]

arseniiv в сообщении #1095236 писал(а):

Это показывает просто и прямо, что ничем не приправленный перебор практически бессмыслен.

Вы думаете, что направленный перебор будет более осмысленным? Лично я сомневаюсь, что когда-нибудь человечество сможет указать конкретный набор переменных (хотя бы один), при которых полином Джонса примет хоть какое-нибудь положительное значение.

[arseniiv]

grizzly в сообщении #1095242 писал(а):

Вы думаете, что направленный перебор будет более осмысленным?

Направленный перебор может по-разному отличаться от ненаправленного, так что, скорее, я думаю в другом ключе: проще генерировать простые каким-то другим известным способом, чем искать такие ограничения перебора, которые сделают его хотя бы равнополезным этим другим способам. Не сказать чтобы это был какой-то неочевидный ход мысли, конечно…

[Алексей К.]

atlakatl в сообщении #1095224 писал(а):

Недавно прошло сообщение, что найдено наибольшее простое число.

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

-- 30 янв 2016, 11:58:52 --

Или большее всех, до сих пор известных?

[atlakatl]

Алексей К.
Говорилось об этом и на dxdy.ru, и в той же статье Википедии.
Да, из всех до сих пор известных.

[Someone]

The Prime Pages писал(а):

New record prime: $2^{74207281}-1$ with $22338618$ digits by Cooper, Woltman, Kurowski, Blosser & GIMPS (7 Jan 2016).

[venco]

arseniiv в сообщении #1095226 писал(а):

Если кому-то нужна удобоваримая для экспериментов в СКА или где ещё запись того многочлена, вот она:

Будет обидно потратить на поиск значений неправильного полинома. У вас тут несколько ошибок (или это другая версия?).
Я пробовал вот этот:
$ff(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=(k+2)*(1-((w*z + h + j - q)^2 + ((g*k + g + k)*(h + j) + h - z)^2 + (16*(k+1)*k^3*(n+1)^2 + 1 - f^2)^2 + (2*n + p + q + z - e)^2 + (e^3*(e+2)*(a+1)^2 + 1 - o^2)^2 + ((a^2-1)*y^2 + 1 - x^2)^2 + (16*r^2*y^4*(a^2-1) + 1 - u^2)^2 + (((a + u^2*(u^2-a)-1)^2)*(n + 4*d*y)^2 + 1 - (c*u + x)^2)^2 + ((a^2-1)*l^2 + 1 - m^2)^2 + ((a-1)*i + k - l)^2 + (l + n + v - y)^2 + (-m + l*(-1 + a - n) + b*(-2 + 2*a - 2*n + 2*a*n - n^2) + p)^2 + (q + (-2 + 2*a - 2*p + 2*a*p - p^2)*s - x + (-1 + a - p)*y)^2 + (-(m*p) + l*(a - p)*p + (-1 + 2*a*p - p^2)*t + z)^2 ))$
И простое значение:
$ff(20,0,0,0,3,1,0,1,0,0,0,0,1,0,244,1,1,0,0,0,1,0,0,1,0,1)=2$

-- Сб янв 30, 2016 19:33:40 --

И искать положительные значения проще, разложив на систему уравнений.

-- Сб янв 30, 2016 19:41:00 --

А может, мой вариант и неверен...
В любом случае решать надо систему.

[arseniiv]

venco в сообщении #1095429 писал(а):

Будет обидно потратить на поиск значений неправильного полинома. У вас тут несколько ошибок (или это другая версия?).

Брал код формулы из https://ru.wikipedia.org/wiki/Простое_число#Формулы для нахождения простых чисел, позаменял автоматически квадратные скобки круглыми и кое-какие теховские штуки убрал руками, потом сделал CForm в Mathematica, так что место для ошибки остаётся. Сейчас сделаю то же самое ещё раз и сравню результат.

-- Вс янв 31, 2016 10:34:06 --

Сейчас сделал все замены (знаки умножения проставил вручную) в текстовом редакторе без M., потом скопировал туда старый и новый код и убедился в равенстве выражений. Видимо, она просто переставила некоторые подвыражения. Альтернативный новый код, близкий к тому, который в статье:

(k+2)*(1 - (w*z + h + j - q)^2 - ((g*k + 2*g + k + 1)*(h + j) + h - z)^2 - (2*n + p + q + z - e)^2 - (16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 - f^2)^2 - (e^3*(e + 2)*(a + 1)^2 + 1 - o^2)^2 - ((a^2 - 1)*y^2 + 1 - x^2)^2 - (16*r^2*y^4*(a^2 - 1) + 1 - u^2)^2 - (((a + u^2*(u^2 - a))^2 - 1)*(n + 4*d*y)^2 + 1 - (x + c*u)^2)^2 - (n + l + v - y)^2 - ((a^2 - 1)*l^2 + 1 - m^2)^2 - (a*i + k + 1 - l - i)^2 - (p + l*(a - n - 1) + b*(2*a*n + 2*a - n^2 - 2*n - 2) - m)^2 - (q + y*(a - p - 1) + s*(2*a*p + 2*a - p^2 - 2*p - 2) - x)^2 - (z + p*l*(a - p) + t*(2*a*p - p^2 - 1) - p*m)^2)

Надеюсь, нигде не пропустил *.

-- Вс янв 31, 2016 10:37:21 --

А вот на вашем наборе у меня, к сожалению, получается значение $-2050$.