Первая формула Вилланса

Первая формула Вилланса или просто формула Вилланса — аналитическое выражение для вычисления $n$ -го простого числа^[1], полученное на основе теоремы Вильсона и опубликованное математиком К. П. Виллансом в 1964 году^[2].

Формула имеет следующий вид^[1]:

$p_{n}=1+\sum _{i=1}^{2^{n}}\left\lfloor \left\lfloor n\left(\sum _{j=1}^{i}\left\lfloor \cos ^{2}\pi \left({\frac {(j-1)!+1}{j}}\right)\right\rfloor \right)^{-1}\right\rfloor ^{1/n}\right\rfloor$

Считается, что формула Вилланса не может быть использована для выполнения эффективной вычислительной работы на практике, так как она представляет из себя производный вариант решета Эратосфена^[3].

Примечания

↑ ¹ ² Уоррен. Г.-мл. 18.2 Формулы Вилланса // Алгоритмические трюки для программистов. — 2-е. — М.: ООО «И. Д. Вильямс», 2014. — С. 421. — ISBN 978-5-8459-1838-3.
↑ Willans C. P. On formulae for the nth prime number (англ.) // Mathematical Gazette. — 1964. — Vol. 48, № 366. — С. 413–415. Архивировано 21 июня 2021 года.
↑ Rowland E. S. A Natural Prime-Generating Recurrence (англ.) // Journal of Integer Sequences. — 2008. — Vol. 11. — С. 1—13. Архивировано 8 августа 2017 года.

Ссылки

Prime Formulas Архивная копия от 14 мая 2011 на Wayback Machine на сайте wolfram.com

Похожие исследовательские статьи

В математике, целая часть вещественного числа $\text{[math]}$ — округление $\text{[math]}$ до ближайшего целого в меньшую сторону. Целая часть числа также называется антье, или пол. Наряду с полом существует парная функция — потолок — округление $\text{[math]}$ до ближайшего целого в большую сторону.

Многочле́ны Чебышёва — две последовательности ортогональных многочленов $\text{[math]}$ и $\text{[math]}$ названные в честь Пафнутия Львовича Чебышёва:

Многочлен Чебышёва первого рода $\text{[math]}$ характеризуется как многочлен степени $\text{[math]}$ со старшим коэффициентом $\text{[math]}$ , который меньше всего отклоняется от нуля на отрезке $\text{[math]}$ . Впервые рассмотрены самим Чебышёвым.

Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что для любого натурального $\text{[math]}$ найдётся простое число $\text{[math]}$ в интервале $\text{[math]}$

Биномиа́льный коэффицие́нт — коэффициент перед членом разложения бинома Ньютона $\text{[math]}$ по степеням $\text{[math]}$ . Коэффициент при $\text{[math]}$ обозначается $\text{[math]}$ или $\text{[math]}$ и читается «биномиальный коэффициент из $\text{[math]}$ по $\text{[math]}$ » :

\text{[math]}

Постоянная Э́йлера — Маскеро́ни или постоянная Эйлера — математическая константа, определяемая как предел разности между частичной суммой гармонического ряда и натуральным логарифмом числа:

\text{[math]}

Юлиа́нская да́та (JD) — астрономический способ измерения времени, при котором считается число суток, прошедших начиная с полудня понедельника, 1 января 4713 года до н. э. пролептического юлианского календаря или, что то же самое, 24 ноября 4714 года до н. э. пролептического григорианского календаря. Первый день имел номер 0. С тех пор по настоящее время прошло немногим менее 2,5 миллиона дней. Даты сменяются в полдень UT или TT. Для точного обозначения времени применяют дробную часть, например, JD = 2451545,25 соответствует 18 часам 1 января 2000 года; 3 часа дня 2 августа 1942 года — JD 2430574,125; 13,5 июня 1944 года — JD 2431255,0.

Биномиа́льное распределе́ние с параметрами $\text{[math]}$ и $\text{[math]}$ в теории вероятностей — распределение количества «успехов» в последовательности из $\text{[math]}$ независимых случайных экспериментов, таких, что вероятность «успеха» в каждом из них постоянна и равна $\text{[math]}$ .

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

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\text{[math]}$ вершинами имеет $\text{[math]}$ рёбер и обозначается $\text{[math]}$ . Является регулярным графом степени $\text{[math]}$ .

В теории кодирования грани́ца Хэ́мминга определяет пределы возможных значений параметров произвольного блокового кода. Также известна как граница сферической упаковки. Коды, достигающие границы Хэмминга, называют совершенными или плотноупакованными.

Алгоритм Лемана детерминировано раскладывает данное натуральное число $\text{[math]}$ на множители за $\text{[math]}$ арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году. Данный алгоритм был первым детерминированным алгоритмом факторизации целых чисел, имеющим оценку меньшую, чем $\text{[math]}$ . В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.

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

<span class="mw-page-title-main">Функция распределения простых чисел</span>

В математике функция распределения простых чисел, или пи-функция $\text{[math]}$ , — это функция, равная числу простых чисел, меньших либо равных действительному числу x. Она обозначается $\text{[math]}$ .

Формула суммирования Абеля, введённая норвежским математиком Нильсом Хенриком Абелем, часто применяется в теории чисел для оценки сумм конечных и бесконечных рядов.

<span class="mw-page-title-main">Суммирующая функция делителей</span>

Суммирующая функция делителей в теории чисел — функция, являющаяся суммой функции делителей. Функция часто используется для исследования асимптотического поведения дзета-функции Римана. Различные исследования асимптотического поведения функции делителей иногда называют проблемами делителей.

Константа Миллса A — действительное число, одна из констант в теории чисел. Константа Миллса определяется как минимальное действительное число $\text{[math]}$ такое, что для всех целых положительных $\text{[math]}$ числа

\text{[math]}

Теорема Евклида — основной элемент теории чисел. Она утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список.

Качающийся факториал — функция, определённая на множестве неотрицательных целых чисел $\text{[math]}$ . Обозначается $\text{[math]}$ , произносится эн качающийся факториа́л.

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

В информатике метод Акра–Баззи, или теорема Акра–Баззи, используется для анализа асимптотического поведения математических рекуррент, которые появляются при анализе алгоритмов «разделяй и властвуй», где подзадачи имеют существенно разные размеры. Это обобщение основной теоремы для рекуррентных уравнений «разделяй и властвуй», которая предполагает, что подзадачи имеют одинаковый размер. Он наназван в честь математиков Мохамада Акры и Луая Баззи.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.