Pull to refresh

Comments 55

Давно мучает вопрос. Гугл не помог. А где кроме криптографии применяются простые числа? Смотрю со стороны и это направление выглядит как развлечение шизофреников))

Вобщем-то если генератор случайных чисел и хеш-функции отнести к криптографии, то наверно нигде. Но эти два явления на самом деле не только криптографические бывают.
У простых чисел тут важное свойство что поделив два таких друг на друга — гарантированно ничего не сократится, не понизит "точность" (не знаю как это назвать по-другому) дроби.

Если одно простое число делится без остатка на другое число, то это другое число либо равно первому, либо 1. В любом другом случае может быть потеря точности, так как число получится дробным.
А как сокращение дроби понижает точность?
Их используют для генерации неповторяющихся паттернов, чтобы убрать вибрации, возникающие при трении в движущихся механизмах, например отношение расстояний между выпуклостями и впадинами в протекторах колес, расстояния между вентиляционными отверстиями в тормозных дисках, и тому подобное.

Есть также связь между простыми числами и квантовой механикой: нетривиальные нули дзета-функции хорошо коррелируют с энергетическими уровнями электронов на орбитах больших ядер, что доказано численными методами. И на основе этого предполагается, что квантовый компьютер докажет гипотезу Римана.
Как бы дело тут скорее даже не в практике, а в математике как таковой. Дело в том, что во множестве (если не вообще во всех !) серьёзных математических проблемах, как правило скрыта (иногда очень тщательно и неочевидно !) некая теоретико-числовая задача. Не зря Гаусс называл арифметику королевой математики. А сама теория чисел практически сводится к изучению свойств простых чисел. Поэтому всё что касается каким-то боком простых чисел, представляет огромный интерес для математики в целом. И вангую что и через тысячу лет будет представлять.
Мне страшно представить как выглядит «недоступное» объяснение
Классическое из учебников математики и физики: «Очевидно, что…… ....»
Очевидно, что бо́льшая часть современных учебников пишутся дилетантами, не разбирающимися в вопросе и пытающимися таким образом срубить бабла.
Даже где-то статья была с разбором некоторых «учебников»

На эту тему есть отличная книга "Простая одержимость" (Джон Дербишир)

А статья слегка напоминает ее пересказ
Читал, книга восхитительная
Спасибо за наводку! Сейчас скачал с рутрекера, читаю. Действительно отлично написано. Единственно уровень немного низковат, хотелось бы побольше математики. Но книга отличная, если кто-то не читал, очень советую.
Вы ведь помните, что такое «простые числа»? Эти числа не делятся ни на какие другие, кроме самих себя и 1.

Фейл на втором же абзаце. 7/2=3.5 Поделил.
С формальной точки зрения Вы правы, но этот абзац все всё-равно поняли.
Комикс smbc
image
Вы правда считаете, что в математической статье допустимы такие ошибки? Стоит ли дальше тратить время на статью, где считаются допустимыми такие ошибки?
В вашем комментарии также есть допущение, которое выглядит странно: "… но этот абзац все всё-равно поняли". Откуда вам это известно? Вы всех опросили перед тем, как написать комментарий?

Помнится, в школьные годы одноклассник приготовил какую-то сложную (для того возраста) тему для доклада перед классом. И его выступление началось со слов «Общеизвестно, всякое сечение шара плоскостью есть круг.» Его тут же прервал учитель, и сказал, что это нужно доказать. Хотя тема доклада была совсем про другое и много сложнее, но уж если взялся за большее, не оплошай и в меньшем. Учитель позволил закончить доклад, не приводя доказательство (кажется, учитель вместо одноклассника привёл это доказательство, чтобы можно было продолжить доклад).
Стоит ли дальше тратить время на статью, где считаются допустимыми такие ошибки?
Докажи что нет. Формально.
Если автор внесёт изменения в статью, я потрачу время на её прочтение.
А вообще, что нужно доказывать? Что в статье есть некорректность? Так я это уже показал. Если все потенциальные читатели знают, что такое простые числа, то статью так и надо было начинать:
Вы ведь помните, что такое «простые числа»? Если нет, то боюсь дальнейшее вы не поймёте, так что считаю своим долгом сэкономить ваше время.

Если же статья рассчитана на домохозяек-блондинок, и автор вынужден опускаться до упрощений, то даже в упрощениях он должен быть точен, чтобы смысл не был искажён.
Многие мои пары в студенчестве по теоремам вышмата были с допущениями и указанием начальных условий…
Как правило, новый материал опирался на уже пройденный. Не могу представить, чтобы я на экзамене, например, по матану не мог объяснить какое-нибудь «допущение», откуда оно взялось и что из этого следует.
Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

https://ru.wikipedia.org/wiki/Делимость
Когда говорят делится, как правило, подразумевают делимость нацело.
Мало того, что число целое, оно ещё должно быть натуральным, о чём в приведённом определении нет ни слова.
А по поводу «подразумевается» у меня есть свежий жизненный пример.
Дочка недавно пробовала свои силы к поступлению в престижную школу. На экзамене по физике на устном ответе оговорилась, хотя мысль была верная. Преподаватель сразу прервал и не стал дослушивать, поставил 0 баллов. Ей не дали второго шанса.

Здесь же у переводчика есть вариант добавить пояснение. Например:
Эти числа не делятся ни на какие другие (без остатка — прим. перев.), кроме самих себя и 1.

Даже в таком виде выглядит существенно лучше.
Объясните дочери, что престижная — необязательно хорошая. И школу, в которой оговорки считаются важнее мысли, лично я бы к хорошим не отнес.
Но стоит ли уподобляться?
Во-первых, почему вы мне даёте совет, ведь я его не просил?
Во-вторых, школа и не обязательно плохая. Ваши личные предпочтения меня не интересуют.
Не знаю, как бы я сам поступил на месте преподавателя. В эту школу стремятся поступить лучшие. Как выявить лучших? Похоже, даже на таких мелочах (оговорился, дал неразвёрнутый ответ и т. п.) и выявляют самых достойных. Наверное, за счёт этого в том числе и держат марку.
О, извините.
Я полагал, что вас могут волновать переживания непоступившей дочери. Еще раз примите извинения за мою ошибку.

И — ни в коем случае не вам, но читающим этот коммент я напомню известный анекдот про Эдисона и Эйнштейна. И — sapienti sat, умолкаю.
Зачем вы на личности перешли? Вам стоило дать совет в чём-нибудь менее значительном, например, как ручку держать.
Всегда так делаю
Помнится, попросили меня с чужим ребёнком посидеть, сидит — играет. И тут он начинает реветь «игрушку потерял, папа придёт — найдёт». Я объясняю, что можно и без папы игрушку найти, и если он не знает как искать, то я могу его научить. Мои попытки разъяснить ни к чему не привели. Как бы вы поступили в данной ситуации?

Как бы вы поступили в данной ситуации?
Спросил бы, любит ли он машинки, и знает ли, чем отличается Мерседес от Жигулей. Это например, естественно: там все по контексту. Мелких детей продуктивнее отвлекать, чем объяснять.

В текущем же обсуждении у меня не было самоцели дать совет ради совета. Ну да ладно, все уже кончилось.
Если Вы комментируете теорему товарища Римана, вы априори разбираетесь в числах и их градациях, а если не разбираетесь и комментируете, то…
Ну, судя по началу статьи, автор и в простых числах ни бельмеса не понимает.
Да и комментирую не теорему, а безграмотное определение простого числа.
Что значит «подразумевается»?
А при извлечении квадратного корня, что подразумевается? Положительное число, пара чисел или модуль?
Математика наука с очень строгой и формальной логикой. Такие допущения обычно означают ошибку ещё на этапе формулировки задачи.
Вот на ноль числа действительно не делятся. А простые — сколько угодно.
Придумайте суждение или формулу, которые (хотя бы с грехом пополам) прогнозируют, каким будет следующее простое число, (в любом заданном ряду чисел), и ваше имя навечно будет связано с одним из величайших достижений человеческого мозга.
Хм...
А вы прочитали что написано по ссылке?
"..No such formula which is efficiently computable is known"
Да. Но автор же согласился даже на «хотя бы с грехом пополам».
кстати, прикол: если пространство-время крутится вокруг большого центра масс, понятно, почему звезды не улетают — и не надо темной материи и энергии — они крутятся вокруг (млечный путь скажем) стрельца-а по закрученному пространству, да и время там другое — чувакам из разных отделов рассказать что в нии как бе проблема одна — кто решил что время на периферии галактики течет так же как у центра, это мы видим давно давно пролеты, а там может уже ничего и нет, ща бах сверхновая, недождались

тролинг: мне Желязны понравился, дворы Хаоса (про разное время) отражения — каждый думает по-своему, импирирует, что на Земле, но квантовую механику — надо его допросить, что-то знает, и (молчит)(звездит
Ошибка в пункте «Величина погрешности». В формуле должны быть не десятичные логарифмы, а натуральные. Для предыдущих двух формул то же самое
Гамма-функция Γ(z) определена для всех комплексных значений z больше нуля.

Поле комплексных чисел не является упорядоченным...

Аа, прям матан в универе вспомнился — хорошо так от прочтения мозги размялись)
Есть и более точные приближения. Напрмер, погрешность не превышает единицы по абсолютному значению у данного приближения:
image, гдеimage
С таблицей и графиком погрешностей можно познакомиться здесь.

Источники:


Одной из функций, серьёзно упрощающих нашу работу, будет 6n ± 1. Эта простая функция выдаёт все простые числа, за исключением 2 и 3, и удаляет все числа, кратные 3, а также все чётные числа.

6n+-1 работает только до 24, дальше картинка другая.


Вообще говоря, это не 6n+-1, это 6n+(1,5)


Первые простые числа 2 и 3, их произведение дает 6. Значит длина периода 6, дальше делимость чисел на 2 и 3 повторяется. Остаток от деления на 6 принимает значения 0, 1, 2, 3, 4, 5. Убираем (0, 2, 4) как кратные 2, и (0, 3) как кратные 3.


0, 1, 2, 3, 4, 5
x, 1, x, x, x, 5

Значит все простые числа больше 3 имеют остаток от деления на 6 равный 1 или 5.


Следующее число после 2 и 3, которое имеет остаток от деления на 6 равный 1 или 5, это число 5. Значит оно простое.


Теперь есть 3 простых числа, их произведение 30. Повторяем паттерн 5 раз, вычеркиваем кратные 5, получаем новый паттерн. Первое число кратное 5 это квадрат, потому что все что меньше было вычеркнуто при проверке меньших множителей.

x, 1, x, x, x, 5,    x, 7, x, x, x, 11,    x, 13, x, x, x, 17,    x, 19, x, x, x, 23,    x, 25, x, x, x, 29
x, 1, x, x, x, x,    x, 7, x, x, x, 11,    x, 13, x, x, x, 17,    x, 19, x, x, x, 23,    x,  x, x, x, x, 29

Теперь получается формула 30n+(1,7,11,13,17,19,23,29). Здесь после вычеркивания все остатки от деления следующих простых чисел на длину периода сами являются простыми числами, но так получается не всегда, поэтому просто так использовать этот подход для поиска простых чисел не получится.


Следующее число после 2, 3 и 5, которое имеет остаток от деления на 30 равный 1, 7 или другим остаткам, это число 7. Дальше то же самое, длина периода 210 (2*3*5*7).
(лучше скопировать в редактор с прокруткой, так нагляднее)


x,   1, x, x, x, x,    x,   7, x, x, x,  11,    x,  13, x, x, x,  17,    x,  19, x, x, x,  23,    x, x, x, x, x,  29,
x,  31, x, x, x, x,    x,  37, x, x, x,  41,    x,  43, x, x, x,  47,    x,  49, x, x, x,  53,    x, x, x, x, x,  59,
x,  61, x, x, x, x,    x,  67, x, x, x,  71,    x,  73, x, x, x,  77,    x,  79, x, x, x,  83,    x, x, x, x, x,  89,
x,  91, x, x, x, x,    x,  97, x, x, x, 101,    x, 103, x, x, x, 107,    x, 109, x, x, x, 113,    x, x, x, x, x, 119,
x, 121, x, x, x, x,    x, 127, x, x, x, 131,    x, 133, x, x, x, 137,    x, 139, x, x, x, 143,    x, x, x, x, x, 149,
x, 151, x, x, x, x,    x, 157, x, x, x, 161,    x, 163, x, x, x, 167,    x, 169, x, x, x, 173,    x, x, x, x, x, 179,
x, 181, x, x, x, x,    x, 187, x, x, x, 191,    x, 193, x, x, x, 197,    x, 199, x, x, x, 203,    x, x, x, x, x, 209

x,   1, x, x, x, x,    x,   x, x, x, x,  11,    x,  13, x, x, x,  17,    x,  19, x, x, x,  23,    x, x, x, x, x,  29,
x,  31, x, x, x, x,    x,  37, x, x, x,  41,    x,  43, x, x, x,  47,    x,   x, x, x, x,  53,    x, x, x, x, x,  59,
x,  61, x, x, x, x,    x,  67, x, x, x,  71,    x,  73, x, x, x,   x,    x,  79, x, x, x,  83,    x, x, x, x, x,  89,
x,   x, x, x, x, x,    x,  97, x, x, x, 101,    x, 103, x, x, x, 107,    x, 109, x, x, x, 113,    x, x, x, x, x,   x,
x, 121, x, x, x, x,    x, 127, x, x, x, 131,    x,   x, x, x, x, 137,    x, 139, x, x, x, 143,    x, x, x, x, x, 149,
x, 151, x, x, x, x,    x, 157, x, x, x,   x,    x, 163, x, x, x, 167,    x, 169, x, x, x, 173,    x, x, x, x, x, 179,
x, 181, x, x, x, x,    x, 187, x, x, x, 191,    x, 193, x, x, x, 197,    x, 199, x, x, x,   x,    x, x, x, x, x, 209

Здесь после вычеркивания чисел кратных 7 присутствуют не только простые числа, например 121 (331 % 210 = 121), хотя всё что меньше квадрата следующего числа (11*11) это простые числа. Чтобы получить только их, надо также вычеркнуть всё что кратно числам меньше корня из 210 (14.49), то есть 11 и 13. Чем длиннее последовательность, тем больше это похоже на решето Эратосфена, хотя вычеркиваний будет меньше, и можно генерировать последовательность динамически, повторяя текущую. По крайней мере, прослеживается некая зависимость, может быть ее можно и как-то по-другому применить.


Основная идея не моя, описана в этом комментарии, я лишь немного структурировал ее.

Очень классное объяснение, я понял лучше чем оригинальную статью. Вы не преподаватель часом?

Нет, просто интересовался этой темой одно время.

Он повторяет этот процесс, далее умножая обе стороны на третий член
Дзета-функция минус 1/2s, умноженное на дзета-функцию, умноженное на 1/3s
А затем вычитает получившееся выражение из дзета-функции

Могу ошибаться, но разве не из дзета-функции минус 1/2^s × дзета-функцию?

Мурашки по коже по мере чтения статьи! И книга «Простая одержимость» очень крута. Все-таки удивительно, что простые числа точно не прогнозируются, то есть нельзя сказать точно, какое следующее число. И вообще, так подумать, что у большого простого числа позади очень большое количество делителей и оно не делится! Офигеть!
Спасибо!
Замечательное по стилю изложение. Звучит как песня.

По сути проблемы. У меня было несколько попыток решение данной задачи. Результаты были никакие и задача откладывалась на следующий раз. (Это как «гантели для мозгов», чтобы «извилины не закисли»). Но, что интересно, критически оценивая свою любительскую работу, я пришел к важному выводу:

1.Данную задачу и ряд других интересных задач, невозможно решить на основе стандартного математического подхода, т.е. на основе формулировки лемм, доказательства теорем и т.д.

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

3.Хорошие алгоритмические решения дадут интервал (n_min, n_max) в котором должен находиться следующее простое число. Лучшим будет тот алгоритм, у которого значение
n_max — n_min будет минимальным.
по идее, достаточно будет, чтобы n_max — n_min < 1
А вот и новости как раз подоспели, вроде как прогресс в доказательстве гипотезы.
Объясните, пожалуйста, кому не сложно, насколько гипотеза Римана упрощает (и упрощает ли) нахождение разложения на простые числа? Насколько я понимаю, криптографические алгоритмы на простых числах работают потому, что у=F(x) считается очень быстро (проверка), а F', такая, что x=F'(y) или не существует, или время её рассчёта растёт экспоненциально от «размера» x и y. Если я правильно понимаю, гипотеза Римана предоставляет функцию F", которая дает не x, а множество x1..xN, одним из членов которого является x. Так ли это, и если да, то насколько велико N? Или, насколько время вычисления F' больше, чем время вычисления F N раз?
Каким это образом ГР предоставляет какую-то функцию? Можете считать что гипотеза Римана верна и разлагать быстрее.
я дятел — допустим есть ну шифровочные алгоритмы — я допустим кому то дам код, есть таблицы, все утеряли, ну есть проверочный код, ну как восстановить? допустим кодовое слово металика — и пишите что они там напридумывали — а все можно сгенерировать нафинг элсе метерса кодом будет акорды
Я когда-то глубоко интересовался гипотезой Римана и комплексными числами.
1) Разобрался как выполняются действия над комплексными числами
2) Разобрался как вычисляется Дзета-Функция для комплексного аргумента.
3) Детально понял смысл гипотезы Римана в геометрическом виде.
4) Написал программу на компьютере, которая строит в различных ракурсах график Дзета функции на комплексной плоскости.
5) Разработал свой алгоритм вычисления нулей Дзета-функции для комплексного аргумента. Написал программу на компьютере вычисляющую 100 тысяч первых нетривиальных нулей дзета функции с точностью до 6 знаков после запятой
6) Сравнил полученные мной результаты со списком нолей Дзета функции, опубликованные Эндрю Одлыжко. Мой список нолей совпал со списком Одлыжко.
7) Нашел много потрясающих закономерностей в расчете Дзета функции и в ее поведении на различных участках комплексной плоскости…
Тема очень сложная и интересная.
Но работу Римана, «О простых числах меньше заданной величины» так и не смог осилить.
Моих знаний математики для этого оказалось недостаточно.
Для этого нужно быть минимум кандидатом математических наук.
Хорошая, подробная статья. Но жаль, что не освещена тема прикладного значения гипотезы Римана, т.е. что именно даст ее доказательство. Допустим, мы сможем уверенно определять точное количество простых чисел <= любого N… Так, и что с этого?
… где {x} = x — |x|

Не, ну вы, конечно, даёте: отняли от числа его модуль, а читатель мучается вопросом: как для действительного положительного числа может остаться не ноль?
Сложно было хотя бы рядом написать, что это не модуль, а целая часть?

Обычно пишут ⌊x⌋ (округление вниз), в Unicode все нужные символы есть. Но для неподготовленного читателя хорошо бы это и текстом упомянуть.

Sign up to leave a comment.

Articles