Комментарии 34
Ну вот!!! 270 — это вам не 70 миллионов и 2-й пункт отступления сразу становится очевидным.
+2
Но когда же всё-таки мы получим простую функцию, позволяющую найти pn для любого n?..
0
А что вы называете простой функцией?
+3
Если под простой функцией вы имеете ввиду полином, то никогда.
+2
Т.е. вы утверждаете, что P != NP… смело.
0
Не понял.
Теорема о несуществовании многочлена P от одной переменной n, такого, что для всех целых P(n) простое и P(n)=P(m)=>n=m не имеет никакого отношения ни к P ?= NP, ни к теории вычислительной сложности вообще.
Теорема о несуществовании многочлена P от одной переменной n, такого, что для всех целых P(n) простое и P(n)=P(m)=>n=m не имеет никакого отношения ни к P ?= NP, ни к теории вычислительной сложности вообще.
+1
Собственно:
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
0
С другой стороны, есть старый результат Матиясевича, утверждающий существование такого многочлена с целыми коэффициентами от десяти переменных, что множество его неотрицательных значений на положительных целых числах есть в точности множество всех простых чисел.
0
А кто-нибудь можно объяснить, чем это полезно помимо математического любопытства?
0
Когда Буль в середине 19 века создавал свою алгебру им тоже двигало только математическое любопытство. Компьютеры (которые немыслимы без использования математической логики) начали создавать только через 100 лет.
+13
Как вспомнил Андрей Коняев, обсуждая эту же тему, именно при вычислении простых чисел-близнецов обнаружили баг в процедуре деления чисел на процессорах Pentium, в результате чего компания Intel потеряла полмиллиарда долларов на замене дефектных процессоров. Вот такая вот польза.
+16
— Эта запись не совсем корректна.
Правильно будет что-то вроде:
Если быть еще более точным, то вместо inf даже можно написать min, поскольку мы имеем дело с целыми числами.
Правильно будет что-то вроде:
Если быть еще более точным, то вместо inf даже можно написать min, поскольку мы имеем дело с целыми числами.
+5
Спасибо. Насчёт inf я не уверен, придерживался той записи, которая используется в исходных работах.
+2
Корректна. «lim inf» как единый символ — стандартное обозначение, например, mathworld.wolfram.com/InfimumLimit.html.
+6
Думаю, что имелся в виду нижний предел (который lim, подчеркнутый снизу).
+3
Спасибо за новость! Краем глаза слежу за этой темой (хотя сам, по большему счету, понимаю только формулировку задачи). В последний раз, когда я заглядывал на их страничку — они скукожили оценку до ~5000. А тут такой прорыв)
+2
НЛО прилетело и опубликовало эту надпись здесь
Термин «коллективный разум» тоже немного запутывает. Общепринятый термин немного про другое. Тут скорее сотрудничество, что для науки не новость начиная где-то со времен Гаусса. Идеальным названием было бы «простые числа становятся ближе».
0
Это не значит, что все простые числа отстоят друг от друга на расстоянии меньше 70 000 000
Даже больше — очень просто доказывается, что есть сколь угодно большой зазор между соседними простыми (взять промежуток от k!+2 до k!+k для произвольного k)
+1
НЛО прилетело и опубликовало эту надпись здесь
Числа 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) в рамках ограничений следующих двух теорем:
+24
кто смог представить доказатательство того, что существет конечная величина, обозначающая верхнюю границу величины интервала для бесконечного кол-ва пар простых чисел.
Нижнюю же вроде?
и наверное «обозначающая» не вполне корректно использовать. «существует конечная нижняя граница величины интервала» или как то так.
0
Нет, всё правильно, верхняя граница. «Верхняя граница величины интервала для бесконечного кол-ва пар простых чисел равна n» значит «существует бесконечное кол-во пар простых чисел, где они (числа в паре) находятся на расстоянии не более n».
0
кто смог представить доказатательство того, что существет конечная оценка величины интервала
тоже не то ведь? lim inf же указано даже
0
Скажите, а что Вам мешает писать имена собственные кириллицей? Тем более, что про Чжана Итана есть даже статья в Википедии.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Коллективный разум в теории чисел