Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 34
Ну вот!!! 270 — это вам не 70 миллионов и 2-й пункт отступления сразу становится очевидным.
Но когда же всё-таки мы получим простую функцию, позволяющую найти pn для любого n?..
А что вы называете простой функцией?
Если под простой функцией вы имеете ввиду полином, то никогда.
Т.е. вы утверждаете, что P != NP… смело.
Не понял.
Теорема о несуществовании многочлена P от одной переменной n, такого, что для всех целых P(n) простое и P(n)=P(m)=>n=m не имеет никакого отношения ни к P ?= NP, ни к теории вычислительной сложности вообще.
Теорема о несуществовании многочлена P от одной переменной n, такого, что для всех целых P(n) простое и P(n)=P(m)=>n=m не имеет никакого отношения ни к P ?= NP, ни к теории вычислительной сложности вообще.
Собственно:
en.wikipedia.org/wiki/Formula_for_primes
It is known that no non-constant polynomial function P(n) with integer coefficients exists that evaluates to a prime number for all integers n.
en.wikipedia.org/wiki/Formula_for_primes
С другой стороны, есть старый результат Матиясевича, утверждающий существование такого многочлена с целыми коэффициентами от десяти переменных, что множество его неотрицательных значений на положительных целых числах есть в точности множество всех простых чисел.
А кто-нибудь можно объяснить, чем это полезно помимо математического любопытства?
Когда Буль в середине 19 века создавал свою алгебру им тоже двигало только математическое любопытство. Компьютеры (которые немыслимы без использования математической логики) начали создавать только через 100 лет.
Как вспомнил Андрей Коняев, обсуждая эту же тему, именно при вычислении простых чисел-близнецов обнаружили баг в процедуре деления чисел на процессорах Pentium, в результате чего компания Intel потеряла полмиллиарда долларов на замене дефектных процессоров. Вот такая вот польза.
— Эта запись не совсем корректна.Правильно будет что-то вроде:
Если быть еще более точным, то вместо inf даже можно написать min, поскольку мы имеем дело с целыми числами.
Спасибо. Насчёт inf я не уверен, придерживался той записи, которая используется в исходных работах.
Корректна. «lim inf» как единый символ — стандартное обозначение, например, mathworld.wolfram.com/InfimumLimit.html.
Думаю, что имелся в виду нижний предел (который lim, подчеркнутый снизу).
Спасибо за новость! Краем глаза слежу за этой темой (хотя сам, по большему счету, понимаю только формулировку задачи). В последний раз, когда я заглядывал на их страничку — они скукожили оценку до ~5000. А тут такой прорыв)
Термин «коллективный разум» тоже немного запутывает. Общепринятый термин немного про другое. Тут скорее сотрудничество, что для науки не новость начиная где-то со времен Гаусса. Идеальным названием было бы «простые числа становятся ближе».
Это не значит, что все простые числа отстоят друг от друга на расстоянии меньше 70 000 000
Даже больше — очень просто доказывается, что есть сколь угодно большой зазор между соседними простыми (взять промежуток от k!+2 до k!+k для произвольного k)
Числа 4680, 600, 270 появляются следующим образом. Доказывают утверждение в такой формулировке: если k достаточно большое, то для любого набора h1, ..., hk из k чисел, удовлетворяющего свойству А (admissible set), существует бесконечно много чисел n таких, что хотя бы два из чисел n+h1, ..., n+hk простые. Если доказать такое утверждение, остаётся только предъявить один конкретный набор со свойством А, тогда получится граница (максимальное число набора) — (минимальное число набора).
Для гипотезы простых-близнецов достаточно доказать формулировку с k=2; тогда можно взять набор из двух чисел 0 и 2. Но получается доказать только с большими значениями k. Результат с k=632 соответствует границе 4680, вот набор из 632 чисел от 0 до 4680, удовлетворяющий свойству A: http://math.mit.edu/~primegaps/tuples/admissible_632_4680.txt. Граница 600 соответствует k=105, граница 270 — k=54. Вообще, вот ссылка, взятая из черновика polymath8a: http://math.mit.edu/~primegaps/.
Свойство А набора означает, что для каждого простого числа p множество различных остатков набора по модулю p не содержит хотя бы одного из возможных. На примере http://math.mit.edu/~primegaps/tuples/admissible_54_270.txt для границы 270:
Уже предвижу следующий вопрос: откуда берутся значения k? А вот тут начинается хардкор. Например, для черновика polymath8a финальное значение получается оптимизацией k (там оно называется k0) в рамках ограничений следующих двух теорем:
Для гипотезы простых-близнецов достаточно доказать формулировку с k=2; тогда можно взять набор из двух чисел 0 и 2. Но получается доказать только с большими значениями k. Результат с k=632 соответствует границе 4680, вот набор из 632 чисел от 0 до 4680, удовлетворяющий свойству A: http://math.mit.edu/~primegaps/tuples/admissible_632_4680.txt. Граница 600 соответствует k=105, граница 270 — k=54. Вообще, вот ссылка, взятая из черновика polymath8a: http://math.mit.edu/~primegaps/.
Свойство А набора означает, что для каждого простого числа p множество различных остатков набора по модулю p не содержит хотя бы одного из возможных. На примере http://math.mit.edu/~primegaps/tuples/admissible_54_270.txt для границы 270:
- модуль 2: все числа набора чётные, нет остатка 1;
- модуль 3: каждое из чисел набора имеет вид либо 3m, либо 3m+1, нет остатка 2;
- модуль 5: последняя цифра каждого числа набора — одна из 0, 2, 4, 8, нет остатка 1 (он же 6);
- и так для бесконечного количества простых.
Уже предвижу следующий вопрос: откуда берутся значения k? А вот тут начинается хардкор. Например, для черновика polymath8a финальное значение получается оптимизацией k (там оно называется k0) в рамках ограничений следующих двух теорем:
кто смог представить доказатательство того, что существет конечная величина, обозначающая верхнюю границу величины интервала для бесконечного кол-ва пар простых чисел.
Нижнюю же вроде?
и наверное «обозначающая» не вполне корректно использовать. «существует конечная нижняя граница величины интервала» или как то так.
Нет, всё правильно, верхняя граница. «Верхняя граница величины интервала для бесконечного кол-ва пар простых чисел равна n» значит «существует бесконечное кол-во пар простых чисел, где они (числа в паре) находятся на расстоянии не более n».
кто смог представить доказатательство того, что существет конечная оценка величины интервала
тоже не то ведь? lim inf же указано даже
Скажите, а что Вам мешает писать имена собственные кириллицей? Тем более, что про Чжана Итана есть даже статья в Википедии.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Коллективный разум в теории чисел