Формула простых чисел

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

Формулы, основанные на теореме Вильсона

Простая формула

$f(n)=\left\lfloor {\frac {n!{\bmod {(}}n+1)}{n}}\right\rfloor (n-1)+2$

для положительного целого числа $n$, где $\lfloor \ \rfloor$ — это функция пола , которая округляет до ближайшего целого числа.По теореме Вильсона , $n+1$ является простым тогда и только тогда, когда $n!\equiv n{\pmod {n+1}}$. Таким образом, когда $n+1$ является простым, первый делитель произведения становится единицей, и формула дает простое число $n+1$. Но когда $n+1$ не является простым, первый множитель становится нулевым, и формула дает простое число 2. Эта формула не является эффективным способом генерации простых чисел, поскольку вычисление $n!{\bmod {(}}n+1)$ требуется около $n-1$ умножения и сокращения по модулю $n+1$.

В 1964 году Уилланс дал формулу

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

для $n$-е простое число $p_{n}$. Эта формула сводится к $p_{n}=1+\sum _{i=1}^{2^{n}}[\pi (i)<n]$; то есть оно тавтологически определяет $p_{n}$ как наименьшее целое число m, для которого функция подсчета простых чисел $\pi (m)$ это как минимум n . Эта формула также неэффективна. Помимо внешнего вида $(j-1)!$, он вычисляет $p_{n}$ путем сложения $p_{n}$ копии $1$; например, $p_{5}=1+1+1+1+1+1+1+1+1+1+1+0+0+\dots +0=11$.

Статьи Что такое ответ? Герберта Уилфа (1982) и формулы для простых чисел Андервуда Дадли (1983). продолжить дискуссию о бесполезности таких формул.

Формула, основанная на системе диофантовых уравнений

Поскольку множество простых чисел является вычислимо перечислимым , по теореме Матиясевича его можно получить из системы диофантовых уравнений . Джонс и др. (1976) нашел явный набор из 14 диофантовых уравнений с 26 переменными, такой, что данное число k + 2 является простым тогда и только тогда, когда эта система имеет решение в неотрицательных целых числах:

$\alpha _{0}=wz+h+j-q=0$

$\alpha _{1}=(gk+2g+k+1)(h+j)+h-z=0$

$\alpha _{2}=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}=0$

$\alpha _{3}=2n+p+q+z-e=0$

$\alpha _{4}=e^{3}(e+2)(a+1)^{2}+1-o^{2}=0$

$\alpha _{5}=(a^{2}-1)y^{2}+1-x^{2}=0$

$\alpha _{6}=16r^{2}y^{4}(a^{2}-1)+1-u^{2}=0$

$\alpha _{7}=n+\ell +v-y=0$

$\alpha _{8}=(a^{2}-1)\ell ^{2}+1-m^{2}=0$

$\alpha _{9}=ai+k+1-\ell -i=0$

$\alpha _{10}=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0$

$\alpha _{11}=p+\ell (a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0$

$\alpha _{12}=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x=0$

$\alpha _{13}=z+p\ell (a-p)+t(2ap-p^{2}-1)-pm=0$

14 уравнений α ₀ , …, α ₁₃ можно использовать для получения полиномиального неравенства, порождающего простые числа, с 26 переменными:

$(k+2)(1-\alpha _{0}^{2}-\alpha _{1}^{2}-\cdots -\alpha _{13}^{2})>0.$

То есть,

${\begin{aligned}&(k+2)(1-{}\\[6pt]&[wz+h+j-q]^{2}-{}\\[6pt]&[(gk+2g+k+1)(h+j)+h-z]^{2}-{}\\[6pt]&[16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}]^{2}-{}\\[6pt]&[2n+p+q+z-e]^{2}-{}\\[6pt]&[e^{3}(e+2)(a+1)^{2}+1-o^{2}]^{2}-{}\\[6pt]&[(a^{2}-1)y^{2}+1-x^{2}]^{2}-{}\\[6pt]&[16r^{2}y^{4}(a^{2}-1)+1-u^{2}]^{2}-{}\\[6pt]&[n+\ell +v-y]^{2}-{}\\[6pt]&[(a^{2}-1)\ell ^{2}+1-m^{2}]^{2}-{}\\[6pt]&[ai+k+1-\ell -i]^{2}-{}\\[6pt]&[((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}]^{2}-{}\\[6pt]&[p+\ell (a-n-1)+b(2an+2a-n^{2}-2n-2)-m]^{2}-{}\\[6pt]&[q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x]^{2}-{}\\[6pt]&[z+p\ell (a-p)+t(2ap-p^{2}-1)-pm]^{2})\\[6pt]&>0\end{aligned}}$

представляет собой полиномиальное неравенство с 26 переменными, а набор простых чисел идентичен набору положительных значений, принимаемых левой частью, поскольку переменные a , b ,…, z варьируются в пределах неотрицательных целых чисел.

Общая теорема Матиясевича гласит, что если множество определяется системой диофантовых уравнений, то оно также может быть определено системой диофантовых уравнений всего с 9 переменными. Следовательно, существует полином, порождающий простые числа, как указано выше, только с 10 переменными. Однако ее степень велика (порядка 10 ⁴⁵ ). С другой стороны, существует и такая система уравнений только 4-й степени, но с 58 переменными.

Формула Миллса

Первая известная такая формула была установлена ​​У. Миллсом ( 1947 ), который доказал, что существует действительное число А такое, что если

$d_{n}=A^{3^{n}}$

затем

$\left\lfloor d_{n}\right\rfloor =\left\lfloor A^{3^{n}}\right\rfloor$

является простым числом для всех положительных целых чисел n . Если гипотеза Римана верна, то наименьшее такое A имеет значение около 1,3063778838630806904686144926... (последовательность A051021 в OEIS ) и известно как константа Миллса . Это значение порождает простые числа $\left\lfloor d_{1}\right\rfloor =2$, $\left\lfloor d_{2}\right\rfloor =11$, $\left\lfloor d_{3}\right\rfloor =1361$, ... (последовательность A051254 в OEIS ). известно очень мало О константе А (даже о том, рациональна ли она ). Эта формула не имеет практической ценности, поскольку не существует известного способа вычисления константы без нахождения простых чисел.

нет ничего особенного в функции пола Обратите внимание, что в формуле . Тот доказал, что существует также константа $B$ такой, что

$\lceil B^{r^{n}}\rceil$

также является основным представителем для $r>2.106\ldots$.

В случае $r=3$, значение константы $B$ начинается с 1,24055470525201424067... Первые несколько сгенерированных простых чисел:

$2,7,337,38272739,56062005704198360319209,$

$176199995814327287356671209104585864397055039072110696028654438846269,\ldots$

Не принимая гипотезу Римана, Эльшольц разработал несколько функций, представляющих простые числа , аналогичных функциям Миллса. Например, если $A=1.00536773279814724017\ldots$, затем $\left\lfloor A^{10^{10n}}\right\rfloor$ является простым для всех положительных целых чисел $n$. Аналогично, если $A=3.8249998073439146171615551375\ldots$, затем $\left\lfloor A^{3^{13n}}\right\rfloor$ является простым для всех положительных целых чисел $n$.

Формула Райта

Другая тетрационно растущая формула образования простых чисел, подобная формуле Миллса, основана на теореме Э. М. Райта . Он доказал, что существует такое действительное число α , что если

$g_{0}=\alpha$ и

$g_{n+1}=2^{g_{n}}$ для $n\geq 0$,

затем

$\left\lfloor g_{n}\right\rfloor =\left\lfloor 2^{\dots ^{2^{2^{\alpha }}}}\right\rfloor$

является главным для всех $n\geq 1$. Райт приводит первые семь десятичных знаков такой константы: $\alpha =1.9287800$. Это значение порождает простые числа $\left\lfloor g_{1}\right\rfloor =\left\lfloor 2^{\alpha }\right\rfloor =3$, $\left\lfloor g_{2}\right\rfloor =13$, и $\left\lfloor g_{3}\right\rfloor =16381$. $\left\lfloor g_{4}\right\rfloor$ четно . и поэтому не является простым Однако с $\alpha =1.9287800+8.2843\cdot 10^{-4933}$, $\left\lfloor g_{1}\right\rfloor$, $\left\lfloor g_{2}\right\rfloor$, и $\left\lfloor g_{3}\right\rfloor$ остаются неизменными, в то время как $\left\lfloor g_{4}\right\rfloor$ простое число, состоящее из 4932 цифр. Эта последовательность простых чисел не может быть расширена за пределы $\left\lfloor g_{4}\right\rfloor$ не зная больше цифр $\alpha$. Как и формула Миллса, формула Райта по тем же причинам не может быть использована для нахождения простых чисел.

Функция, представляющая все простые числа

Учитывая константу $f_{1}=2.920050977316\ldots$ (последовательность A249270 в OEIS ), для $n\geq 2$, определим последовательность

$f_{n}=\left\lfloor f_{n-1}\right\rfloor (f_{n-1}-\left\lfloor f_{n-1}\right\rfloor +1)$ ( 1 )

где $\left\lfloor \ \right\rfloor$ это функция пола .Тогда для $n\geq 1$, $\left\lfloor f_{n}\right\rfloor$ равно $n$й простой: $\left\lfloor f_{1}\right\rfloor =2$, $\left\lfloor f_{2}\right\rfloor =3$, $\left\lfloor f_{3}\right\rfloor =5$, и т. д. Начальная константа $f_{1}=2.920050977316$ приведенное в статье, достаточно точно для того, чтобы уравнение ( 1 ) генерировало простые числа до 37, $12$й премьер.

Точная ​ стоимость $f_{1}$ порождающий все простые числа, задается быстро сходящимся рядом

$f_{1}=\sum _{n=1}^{\infty }{\frac {p_{n}-1}{P_{n}}}={\frac {2-1}{1}}+{\frac {3-1}{2}}+{\frac {5-1}{2\cdot 3}}+{\frac {7-1}{2\cdot 3\cdot 5}}+\cdots ,$

где $p_{n}$ это $n$-е простое число, и $P_{n}$ является произведением всех простых чисел, меньших $p_{n}$. Чем больше цифр $f_{1}$ насколько мы знаем, тем больше простых чисел уравнение ( 1 будет генерировать ). Например, мы можем использовать 25 членов ряда, используя 25 простых чисел меньше 100, чтобы вычислить следующее более точное приближение:

$f_{1}\simeq 2.920050977316134712092562917112019.$

) достаточно цифр, В этом уравнении ( 1 чтобы снова получить 25 простых чисел меньше 100.

Как и в случае с формулой Миллса и формулой Райта, приведенной выше, чтобы сгенерировать более длинный список простых чисел, нам нужно начать с знания большего количества цифр исходной константы: $f_{1}$, что в данном случае требует более длинного списка простых чисел при вычислении.

Формулы Плуффа

В 2018 году Саймон Плуфф выдвинул гипотезу о наборе формул для простых чисел. Аналогично формуле Миллса они имеют вид

$\left\{a_{0}^{r^{n}}\right\}$

где $\{\ \}$ — функция округления до ближайшего целого числа. Например, с $a_{0}\approx 43.80468771580293481$ и $r=5/4$, это дает 113, 367, 1607, 10177, 102217... (последовательность A323176 в OEIS ). С использованием $a_{0}=10^{500}+961+\varepsilon$ и $r=1.01$ с $\varepsilon$ определенное число от 0 до половины, Плуфф обнаружил, что может сгенерировать последовательность из 50 возможных простых чисел (с высокой вероятностью того, что они будут простыми). Предположительно существует такое ε, что эта формула даст бесконечную последовательность реальных простых чисел. Количество цифр начинается с 501 и каждый раз увеличивается примерно на 1%.

Простые формулы и полиномиальные функции

Известно, что не существует непостоянной полиномиальной функции P ( n ) с целыми коэффициентами, которая дает простое число для всех целых чисел n . Доказательство состоит в следующем: предположим, что такой многочлен существует. Тогда P (1) будет иметь простое число p , поэтому $P(1)\equiv 0{\pmod {p}}$. Но для любого целого k числа $P(1+kp)\equiv 0{\pmod {p}}$ также, так $P(1+kp)$ также не может быть простым (поскольку оно делилось бы на p ), если бы оно не было p само . Но единственный способ $P(1+kp)=P(1)=p$ для всех k , если полиномиальная функция постоянна.Те же рассуждения показывают еще более сильный результат: не существует непостоянной полиномиальной функции P ( n ), которая дает простое число почти для всех целых чисел n .

Эйлер впервые заметил (в 1772 г.), что квадратичный многочлен

$P(n)=n^{2}+n+41$

является простым для 40 целых чисел n = 0, 1, 2, ..., 39 с соответствующими простыми числами 41, 43, 47, 53, 61, 71, ..., 1601. Различия между терминами составляют 2, 4. , 6, 8, 10... Для n = 40 получается квадратное число 1681, которое равно 41 × 41, наименьшему составному числу для этой формулы для n ≥ 0. Если 41 делит n , оно делит P ( н ) тоже. Более того, поскольку P ( n ) можно записать как n ( n + 1) + 41, если вместо этого 41 делит n + 1, оно также делит P ( n ). Явление связано со спиралью Улама , которая также неявно квадратична, и номером класса ; этот многочлен связан с числом Хегнера $163=4\cdot 41-1$. Существуют аналогичные полиномы для $p=2,3,5,11{\text{ and }}17$ ( счастливые числа Эйлера ), соответствующие другим числам Хигнера.

Учитывая целое положительное число S , может быть бесконечно много c таких, что выражение n ² + n + c всегда взаимно прост с S . Целое число c может быть отрицательным, и в этом случае перед созданием простых чисел происходит задержка.

Известно, исходя из теоремы Дирихле об арифметических прогрессиях , что линейные полиномиальные функции $L(n)=an+b$ производят бесконечное количество простых чисел, пока a и b являются относительно простыми (хотя ни одна такая функция не будет принимать простые значения для всех значений n ). Более того, теорема Грина-Тао утверждает, что для любого k существует пара a и b со свойством, что $L(n)=an+b$ является простым для любого n от 0 до k - 1. Однако с 2020 года наиболее известный результат такого типа получен для k = 27:

$224584605939537911+18135696597948930n$

является простым для всех n от 0 до 26. Неизвестно даже, существует ли одномерный многочлен степени не ниже 2, принимающий бесконечное число простых значений; см . гипотезу Буняковского .

Возможная формула с использованием рекуррентного соотношения

Другой простой генератор определяется рекуррентным соотношением

$a_{n}=a_{n-1}+\gcd(n,a_{n-1}),\quad a_{1}=7,$

где gcd( x , y обозначает наибольший общий делитель x ) и y . Последовательность разностей a _{n +1} − a _n начинается с 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1. , 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 47, 3, 1, 5, 3, ... (последовательность A132199 в OEIS ). Роуленд (2008) доказал, что эта последовательность содержит только единицы и простые числа. Однако он не содержит все простые числа, поскольку члены НОД( n + 1, an _n ) всегда нечетны и поэтому никогда не равны 2. 587 - это наименьшее простое число (кроме 2), не встречающееся в первых 10 000 результатов. которые отличны от 1. Тем не менее, в той же статье было высказано предположение, что оно содержит все нечетные простые числа, хотя это довольно неэффективно.

Обратите внимание, что существует тривиальная программа, пересчитывающая все и только простые числа, а также более эффективные , поэтому такие рекуррентные отношения представляют собой скорее предмет любопытства, чем какой-либо практической пользы.

См. также

• Теорема о простых числах

Дальнейшее чтение

• Регимбал, Стивен (1975), «Явная формула для k-го простого числа», Mathematics Magazine , 48 (4), Mathematical Association of America: 230–232, doi : 10.2307/2690354 , JSTOR   2690354 .
• Венугопалан. Формула для простых чисел, простых чисел-близнецов, количества простых чисел и количества простых чисел-близнецов . Труды Индийской академии наук - математические науки, Vol. 92, № 1, сентябрь 1983 г., стр. 49–52, исправления.

Внешние ссылки

• Вайсштейн, Эрик В. , « Формулы простых чисел » (« Порождающий многочлен простых чисел ») в MathWorld .