2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:14 
Аватара пользователя
В том многочлене целая куча переменных, поэтому вовсе не факт, что удастся так просто получить даже его положительное значение. Впрочем, это мнение простака в простых числах :-(

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:39 
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.

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:53 
atlakatl в сообщении #1095224 писал(а):
что мешает подставить как угодно большое положительное число в качестве коэффициента при $25$-й степени? Значение многочлена в этом случае тоже будет положительным, - а значит именно простым числом?

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

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:59 
arseniiv в сообщении #1095226 писал(а):
$-256 d^4 k u^{16} y^4$

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

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:24 
Аватара пользователя
Ну Вы даёте! В какой бесконечности? Если существует шар, вне которого многочлен отрицателен, то это противоречит бесконечности простых чисел.

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:30 
atlakatl в сообщении #1095231 писал(а):
И надо "поймать волну" на графике, где значение его положительно. - А это может быть или в районе не слишком больших чисел, или вообще проблематично в поиске.
Ага. Я его тут погонял со случайными аргументами. По несколько миллионов из 0…999, 0…9, 0…4, 0…2, 0…999 999 999 и ещё некоторых интервалов. Ноль положительных значений. Это показывает просто и прямо, что ничем не приправленный перебор практически бессмыслен.

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:39 
Аватара пользователя
arseniiv в сообщении #1095236 писал(а):
Это показывает просто и прямо, что ничем не приправленный перебор практически бессмыслен.
Вы думаете, что направленный перебор будет более осмысленным? Лично я сомневаюсь, что когда-нибудь человечество сможет указать конкретный набор переменных (хотя бы один), при которых полином Джонса примет хоть какое-нибудь положительное значение.

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:47 
grizzly в сообщении #1095242 писал(а):
Вы думаете, что направленный перебор будет более осмысленным?
Направленный перебор может по-разному отличаться от ненаправленного, так что, скорее, я думаю в другом ключе: проще генерировать простые каким-то другим известным способом, чем искать такие ограничения перебора, которые сделают его хотя бы равнополезным этим другим способам. Не сказать чтобы это был какой-то неочевидный ход мысли, конечно… :lol:

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:55 
atlakatl в сообщении #1095224 писал(а):
Недавно прошло сообщение, что найдено наибольшее простое число.
Ну, допустим, конкретную ссылку Вы по тем или иным причинам дать не можете. Но тогда напишите хоть что-то вроде "в ноябре, в новостях по такому-то каналу", или "в таком-то парке за шахматным столиком пенсионеры обсуждали", или...

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

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

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 11:06 
Аватара пользователя
Алексей К.
Говорилось об этом и на dxdy.ru, и в той же статье Википедии.
Да, из всех до сих пор известных.

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 14:16 
Аватара пользователя
The Prime Pages писал(а):
New record prime: $2^{74207281}-1$ with $22338618$ digits by Cooper, Woltman, Kurowski, Blosser & GIMPS (7 Jan 2016).

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение31.01.2016, 03:32 
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 --

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

 
 
 
 Re: Что значит найти наибольшее простое число?
Сообщение31.01.2016, 08:24 
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$.

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group