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

Формула, значениями которой являются простые числа

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

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

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

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

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

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

${\displaystyle 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 }$

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

В статьях «Что такое ответ?» Герберта Вилфа (1982) ^[5] и «Формулы для простых чисел» Андервуда Дадли (1983) ^[6] более подробно обсуждается бесполезность таких формул.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

То есть,

${\displaystyle {\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 переменными. ^[8] Следовательно, существует неравенство полинома, порождающего простые числа, как указано выше, только с 10 переменными. Однако его степень велика (порядка 10 ⁴⁵ ). С другой стороны, существует также такой набор уравнений степени только 4, но с 58 переменными. ^[9]

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

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

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

затем

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

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

В формуле нет ничего особенного в функции пола . Тот доказал, что существует также константа, такая что ${\displaystyle B}$

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

также является простым числом, представляющим . ^[12] ${\displaystyle r>2.106\ldots }$

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

${\displaystyle 2,7,337,38272739,56062005704198360319209,}$

${\displaystyle 176199995814327287356671209104585864397055039072110696028654438846269,\ldots }$

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

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

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

${\displaystyle g_{0}=\alpha }$и

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

затем

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

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

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

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

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

Точное значение, которое генерирует все простые числа , дается быстро сходящимся рядом ${\displaystyle f_{1}}$

${\displaystyle 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 ,}$

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

${\displaystyle f_{1}\simeq 2.920050977316134712092562917112019.}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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 ( n ). Кроме того, поскольку P ( n ) можно записать как n ( n + 1) + 41, если 41 делит n + 1, оно также делит P ( n ). Это явление связано со спиралью Улама , которая также неявно квадратична, и числом класса ; этот многочлен связан с числом Хегнера . Существуют аналогичные многочлены для ( счастливых чисел Эйлера ), соответствующие другим числам Хегнера. ${\displaystyle 163=4\cdot 41-1}$ ${\displaystyle p=2,3,5,11{\text{ and }}17}$

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

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

${\displaystyle 224584605939537911+18135696597948930n}$

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

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

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

${\displaystyle 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, 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, 1, 47, 3, 1, 5, 3, ... (последовательность A132199 в OEIS ). Роуленд (2008) доказал, что эта последовательность содержит только единицы и простые числа. Однако он не содержит все простые числа, поскольку члены gcd( n + 1, an ₎ всегда нечетны и, таким образом, никогда не равны 2. 587 — наименьшее простое число (кроме 2), не встречающееся в первых 10 000 результатах, отличных от 1. Тем не менее, в той же статье было высказано предположение, что оно содержит все нечетные простые числа, хотя это довольно неэффективно. ^[20]

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

Смотрите также

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

Ссылки

1. Mackinnon, Nick (июнь 1987), «Формулы простых чисел», The Mathematical Gazette , 71 (456): 113–114, doi :10.2307/3616496, JSTOR  3616496, S2CID  171537609.
2. Willans, CP (декабрь 1964 г.), «О формулах для th-го простого числа», The Mathematical Gazette , 48 (366): 413–415, doi :10.2307/3611701, JSTOR  3611701, S2CID  126149459 ${\displaystyle n}$.
3. Neill, TBM; Singer, M. (октябрь 1965 г.), «Редактору, The Mathematical Gazette », The Mathematical Gazette , 49 (369): 303–303, doi :10.2307/3612863, JSTOR  3612863
4. Гудштейн, РЛ; Уормелл, CP (февраль 1967 г.), «Формулы для простых чисел», The Mathematical Gazette , 51 (375): 35–38, doi : 10.2307/3613607, JSTOR  3613607
5. Уилф, Герберт С. (1982), «Что такое ответ?», The American Mathematical Monthly , 89 (5): 289–292, doi :10.2307/2321713, JSTOR  2321713, MR  0653502
6. Дадли, Андервуд (1983), «Формулы для простых чисел», Mathematics Magazine , 56 (1): 17–22, doi :10.2307/2690261, JSTOR  2690261, MR  0692169
7. Джонс, Джеймс П.; Сато, Дайхатиро; Вада, Хидео; Винс, Дуглас (1976), «Диофантово представление множества простых чисел», American Mathematical Monthly , 83 (6), Математическая ассоциация Америки: 449–464, doi :10.2307/2318339, JSTOR  2318339, архивировано из оригинала 24.02.2012.
8. Матиясевич, Юрий В. (1999), «Формулы для простых чисел», в Табачников, Серж (ред.), Квант Selecta: Алгебра и анализ , том. II, Американское математическое общество , стр. 13–24, ISBN. 978-0-8218-1915-9.
9. Джонс, Джеймс П. (1982), «Универсальное диофантово уравнение», Журнал символической логики , 47 (3): 549–571, ​​doi : 10.2307/2273588, JSTOR  2273588, S2CID  11148823.
10. Миллс, WH (1947), "Функция, представляющая простые числа" (PDF) , Бюллетень Американского математического общества , 53 (6): 604, doi : 10.1090/S0002-9904-1947-08849-2.
11. Колдуэлл, Крис К.; Ченг, Юанью (2005), «Определение постоянной Миллса и заметка о проблеме Хонакера», Журнал целочисленных последовательностей , 8 , статья 05.4.1.
12. Тот, Ласло (2017), «Вариация функций, представляющих простые числа, подобных функциям Миллса» (PDF) , Журнал целочисленных последовательностей , 20 (17.9.8), arXiv : 1801.08014.
13. Элсхольц, Кристиан (2020), «Безусловные функции, представляющие простые числа, следуя Миллсу», American Mathematical Monthly , 127 (7), Вашингтон, округ Колумбия: Математическая ассоциация Америки : 639–642, arXiv : 2004.01285 , doi : 10.1080/00029890.2020.1751560, S2CID  214795216
14. EM Wright (1951), «Функция, представляющая простые числа», American Mathematical Monthly , 58 (9): 616–618, doi :10.2307/2306356, JSTOR  2306356
15. Бейли, Роберт (5 июня 2017 г.), «Четвертый премьер Райта», arXiv : 1705.09741v3 [math.NT]
16. Фридман, Дилан; Гарбульский, Джули; Глецер, Бруно; Грайм, Джеймс; Трон Флорентин, Масси (2019), «Константа, представляющая простое число», American Mathematical Monthly , 126 (1), Вашингтон, округ Колумбия: Математическая ассоциация Америки : 70–73, arXiv : 2010.15882 , doi : 10.1080/00029890.2019.1530554, S2CID  127727922
17. Стеклес, Кэти (26 января 2019 г.), «Рекордная формула математика может генерировать 50 простых чисел», New Scientist
18. Саймон Плуфф (2019), «Набор формул для простых чисел», arXiv : 1901.01849 [math.NT]По состоянию на январь 2019 года число, которое он приводит в приложении для 50-го сгенерированного числа, на самом деле является 48-м.
19. Поиск AP27 PrimeGrid, официальное объявление от PrimeGrid . AP27 указан на странице "Jens Kruse Andersen's Primes in Arithmetic Progression Records".
20. Роуленд, Эрик С. (2008), "Естественная повторяемость, генерирующая простые числа", Журнал целочисленных последовательностей , 11 (2): 08.2.8, arXiv : 0710.3217 , Bibcode : 2008JIntS..11...28R.

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

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

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

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