Комментарии 46
Во-первых, нигде не нашёл математическую формулу расчёта простых чисел.
Если исследование начать с википедии, то можно сразу увидеть пример формулы в виде полинома.
Но та же википедия даёт ссылку на https://oeis.org/A000040 где, как мне кажется, формул вычисления последовательности довольно много.
В чем принципиальная разница между вашей "математической формулой" и алгоритмом?
(не по формальному определению, а по свойствам)
Чем соответствие карри-ховарда не устраивает?
Прекрасное соответствие! Только речь в нём о доказательствах, а не о формулах. Впрочем, его можно расширить и на математические формулы, включающие логические элементы. Вкратце об этом написано в начале поста.
Но доказательство можно представить в виде формулы.
Я по прежнему не понимаю почему было важно написать правило $P_n = P_(n-1)+$… на языке TeX, а не P n = P (n-1)+… на хаскеле или любом другом языке.
Нельзя. Это разные понятия. Может быть только схожая символическая запись.
X = 1 и X = 1
В чем разница?
Доказательство может включать в себя формулу. Формула может сама доказать что-то. Формула в отсутствии доказательства также будет иметь своё соответствие. Таким образом, принцип можно расширить как минимум на два "класса объектов": доказательства и формулы.
А может и не включать?
Если доказательство без формулы будет переписано с формулой то означает ли это что исходно доказательство без формулы содержит формулу? Можно ли считать это одно и то же доказательство?
И ещё — расшифруйте пожалуйста «класс объектов» и опишите процедуру отнесения к ним на моем последнем примере — $X=1$ и X=1
Формулы, возвращающей n-ое простое число не существует.
Задание функции формулой и алгоритмом эквивалентны. Можно ещё таблицей функцию задавать.
Улучшения заключаются в исключении из рассмотрения чётных чисел и проверке делимости только на простые числа, меньшие кв. корней чисел-кандидатов.
Эту идею конечно давно придумали (может никто не публиковал на Хабре подобные статьи). Создать массив простых чисел до p <= N1/2.
Для создания этого массива делителей наверное нужно проверять делимость на 2 и дальше на непарные числа 3 < n <= N1/2.
Мне кажется, что в данном случае представление алгоритма в виде формулы лишь запутывает читателя. Здесь уместно заметить, что языки программирования не зря получились именно такие, какими мы их знаем, и что важно — там нет возможностей для представления алгоритмов в виде подобных формул. Почему там нет таких возможностей? Наверное ваша статья даёт ответ — с формулами выходит ужасно сложно.
Хотя, возможно, я чего-то не понял. Тогда автор мог бы пояснить, в чём он видит преимущество представления выбранного алгоритма в виде формулы. Кроме того в заключении есть указания на оценку сложности алгоритма. Но неужели автор думает, что сложность переборного алгоритма до сих пор никто не оценил? Или в его алгоритме всё же есть какие-то отличия? Мне не хватило настойчивости на дешифрование алгоритма из предложенной формулы, а потому оставляю надежду на возможность выявления каких-то преимуществ предложенного подхода. И для этого надеюсь на комментарии автора.
1. составления более-менее лаконичной математической формулы вычисления простых чисел. В ней заложен известный алгоритм перебора делителей с известными улучшениями.
2. оптимизации данного алгоритма (в формуле не представлена).
Формулу можете пропустить, если интересует только моя оптимизация алгоритма перебора делителей. Можно читать с «Однако, есть ещё более эффективный способ...»
2. Обозначение оператора обнаружения Dt (сокращённо от detection) я ввёл таким образом, что в подписи снизу указывается искомое число, сверху- индекс членов последовательности, по которому ведётся поиск. Помимо этого индекса члены последовательности могут включать в себя другие индексы или переменные. В нашем случае члены последовательности по j включают в себя индекс i. Чтобы было понятно, по которому индексу работает оператор, я ввёл верхнюю подпись.
3. На входе оператора обнаружения последовательность, на выходе- число. Оператор- это отображение одного множества в другое. Их размерности могут быть разными. Оператор обнаружения обрабатывает только те члены последовательности, номера которых меньше либо равны номера искомого числа. Потом он заканчивает работу согласно его внутренней логике. В этом его преимущество над функцией поиска минимального значения, например. Последняя работает во всём заданном диапазоне.
4. В приведённом Вами «контрпримере» по моей формуле получится именно 3. Верхний индекс оператора нужно было написать m, других индексов члены указанной последовательности в себя не включают. Почему m? Используйте другую букву, сути это не изменит.
5. Я не претендую на математическую строгость обозначений, могут быть и более удачные.
6. Возможно, подобная формула уже где-то написана. Можете поискать. Я не нашёл.
Оператор обнаружения обрабатывает только те члены последовательности, номера которых меньше либо равны номера искомого числа. Потом он заканчивает работу согласно его внутренней логике.
… так чем же это отличается от алгоритма?
Нет, я говорю, что x_m — это последовательность чисел
x_m- это член последовательности с номером m, последовательность обозначается (x_m)
Боюсь, тут Вы заблуждаетесь...
Вы сами придумали новую формулу и сами её опровергли… Формула в посте имеет совсем другой вид.
никто не пишет интервалы целых чисел как [a, b)
Запись корректна, т. к. множество натуральных чисел входит во множество вещественных. Ваше обозначение- это набор, а не интервал.
Вы размышляете о квантификаторах, как программист.
Ни о каких квантификаторах я не размышлял.
Не имеет смысла говорить о временной сложности формулы, поскольку формулы не обладают временной сложностью.
Я не писал о временной сложности формулы. Речь была о преимуществе оператора обнаружения над функцией поиска минимального значения в заданном интервале. Приведённая формула с операторами позволяет более-менее кратко описать известный алгоритм перебора делителей на языке математики.
… И формула будет верна, но не существует алгоритма, который мог бы ее вычислить.
Алгоритмы, на мой взгляд, можно придумать и для т. н. «невычислимых функций». Пока их изучают люди, но ИИ активно разрабатывается.
Я Вам могу сразу сказать, что такой формулы не существует, потому что она просто неверна
Специально или нет, но Вы исказили мою формулу и доказываете неверность своего искаженного варианта.
Так вот, даже не видя Вашей реализации или какой-нибудь реализации min, я могу смело утверждать, что их временная сложность одинаковая — линейная,
Вы смело рассуждаете о том, чего не поняли. Алгоритм для оператора обнаружения заключается в переборе чисел из последовательности до первого искомого. Потом он останавливается (оставшаяся часть последовательности не обрабатывается). Алгоритм для функции минимума же будет перебирать все члены последовательности, в нём нет доп. логики остановки.
Ввиду того, что конструктив в вашем «писании» отсутствует, разъяснение Вам поста заканчиваю. Спасибо, до свидания.
Сложность алгоритма в общем смысле (объём работы)
Это как?
Согласно общему определению вычислительной сложности. В первом приближении это суммарное количество элементарных арифметических операций, необходимых для выполнения задания. Они могут быть распределены по времени (одна рекуррентная формула) и в пространстве (сито).
Спасибо за книгу. Одержимость задачей поиска простых чисел ни к чему хорошему не приведёт. В меру же занятие полезно. Гипотеза Римана, о которой речь в книге, к моему посту имеет слабое отношение. Пи-функции нужно знать точно, они получаются измерением длины массива найденных простых чисел до заданного корня. Аппроксимация данных на графиках логарифмами, вероятно, не лучшая, но в первом приближении этого достаточно.
Всем, кто не видит разницы между "математической формулой" и "алгоритмом" могу привести несколько аналогий: техническое задание- алгоритм, алгоритм- код, код на языке высокого уровня- код на ассемблере. Везде может содержаться одна и та же информация, но её представление разное! Более того, многие закономерности и алгоритмы существуют в природе, социальной сфере. Не стоит превышать значимость информатики, это всего лишь одна из областей знаний. Взгляд на известные алгоритмы под другим углом может быть полезен!
github.com/Alexander-IK/Prime-number-generators-with-residues-caching/blob/main/Prime_number_generators.ipynb
Оценка вычислительной сложности — O(N*loglog(N^0.5))
По использованию памяти — θ(N^0.5)
Публикации
Формула расчёта простых чисел и оптимизация перебора делителей