2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Что значит найти наибольшее простое число?
Сообщение30.01.2016, 08:46 
Аватара пользователя


21/09/12

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

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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:14 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:39 
Заслуженный участник
Аватара пользователя


27/04/09
27252
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 


03/10/06
799
atlakatl в сообщении #1095224 писал(а):
что мешает подставить как угодно большое положительное число в качестве коэффициента при $25$-й степени? Значение многочлена в этом случае тоже будет положительным, - а значит именно простым числом?

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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 09:59 
Заслуженный участник
Аватара пользователя


27/04/09
27252
arseniiv в сообщении #1095226 писал(а):
$-256 d^4 k u^{16} y^4$

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:09 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:39 
Заслуженный участник
Аватара пользователя


09/09/14
6238
arseniiv в сообщении #1095236 писал(а):
Это показывает просто и прямо, что ничем не приправленный перебор практически бессмыслен.
Вы думаете, что направленный перебор будет более осмысленным? Лично я сомневаюсь, что когда-нибудь человечество сможет указать конкретный набор переменных (хотя бы один), при которых полином Джонса примет хоть какое-нибудь положительное значение.

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:47 
Заслуженный участник
Аватара пользователя


27/04/09
27252
grizzly в сообщении #1095242 писал(а):
Вы думаете, что направленный перебор будет более осмысленным?
Направленный перебор может по-разному отличаться от ненаправленного, так что, скорее, я думаю в другом ключе: проще генерировать простые каким-то другим известным способом, чем искать такие ограничения перебора, которые сделают его хотя бы равнополезным этим другим способам. Не сказать чтобы это был какой-то неочевидный ход мысли, конечно… :lol:

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 10:55 


29/09/06
4552
atlakatl в сообщении #1095224 писал(а):
Недавно прошло сообщение, что найдено наибольшее простое число.
Ну, допустим, конкретную ссылку Вы по тем или иным причинам дать не можете. Но тогда напишите хоть что-то вроде "в ноябре, в новостях по такому-то каналу", или "в таком-то парке за шахматным столиком пенсионеры обсуждали", или...

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

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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 11:06 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Что значит найти наибольшее простое число?
Сообщение30.01.2016, 14:16 
Заслуженный участник
Аватара пользователя


23/07/05
17303
Москва
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 
Заслуженный участник


04/05/09
4526
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 
Заслуженный участник
Аватара пользователя


27/04/09
27252
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