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

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

Формула, основанная на теореме Вильсона [ править ]

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

${\ 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 п! \ эквив п {\ pmod {п + 1}}}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ Displaystyle п! {\ bmod {(}} п + 1)}$${\ displaystyle n-1}$${\ Displaystyle {\ bmod {(}} п + 1)}$

Формула на основе системы диофантовых уравнений [ править ]

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

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

Формула Миллса [ править ]

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

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

потом

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

является простым числом для всех натуральных чисел n . ^[5] Если гипотеза Римана верна, то наименьшее из таких A имеет значение около 1,3063778838630806904686144926 ... (последовательность A051021 в OEIS ) и известно как константа Миллса . Это значение приводит к простым числам , , , ... (последовательность 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}$). Эта формула не имеет практического значения, потому что не существует известного способа вычисления константы без поиска простых чисел.

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

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

также является простым представителем для ( Tóth, 2017 ).${\displaystyle r>2.106\ldots }$

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

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

Не принимая гипотезу Римана, Эльшольц разработал несколько функций, представляющих простые числа, аналогичные функциям Миллса. Например, если , то является простым для всех положительных целых чисел . Аналогично, если , то является простым для всех натуральных чисел .^[7]${\displaystyle A\approx 1.00536773279814724017}$${\displaystyle \left\lfloor A^{10^{10n}}\right\rfloor }$${\displaystyle n}$${\displaystyle A\approx 3.8249998073439146171615551375}$${\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 }$

первично для всех . ^[8] Райт дает первые семь знаков после запятой такой константы: . Это значение приводит к простым числам , и . это даже и так не простое. Тем не менее, с , , и остаются неизменными, в то время как это простое с 4932 цифр. ^[9] Эта последовательность простых чисел не может быть расширена без знания дополнительных цифр . Подобно формуле Миллса и по тем же причинам формулу Райта нельзя использовать для поиска простых чисел.${\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 }$

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

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

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

( 1 )

где - функция пола . Тогда для , равняется е простой: , , и т.д. ^[10] Исходная константа дан в статье, достаточно точная для уравнения ( 1 ) , чтобы генерировать простые числа через 37, то е простой.${\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 ,}$

где - это простое число- е, и является произведением всех простых чисел меньше . Чем больше цифр мы знаем, тем больше простых чисел сгенерирует уравнение ( 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 ... Используя и с определенным числом от 0 до половины, Плуфф обнаружил, что он может сгенерировать последовательность из 50 вероятных простых чисел (с высокой вероятностью основной). Предположительно существует такое ε, что эта формула даст бесконечную последовательность реальных простых чисел. Количество цифр начинается с 501 и каждый раз увеличивается примерно на 1%. ^{[11] [12]}${\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 - если полиномиальная функция постоянна. Те же рассуждения показывают еще более сильный результат: нет непостоянной полиномиальной функции${\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}$Существует P ( n ), который оценивается как простое число почти для всех целых n .

Эйлер впервые заметил (в 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 ( п ) тоже. Кроме того, поскольку 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 , может быть бесконечно много с таким образом, что выражение п ² + п + с , всегда взаимно прост с S . Целое число c может быть отрицательным, и в этом случае существует задержка перед созданием простых чисел.

Известно, основанный на теореме Дирихле об арифметических прогрессиях , что линейные полиномиальные функции производят бесконечное множество простых чисел до тех пор, и б являются взаимно простыми (хотя нет такой функции не будет считать , простые значения для всех значений п ). Более того, теорема Грина – Тао гласит, что для любого 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. ^[13] Неизвестно даже, существует ли одномерный многочлен степени не менее 2, который принимает бесконечное число простых значений; см. гипотезу Буняковского .

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

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

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

где НОД ( х , у ) обозначает наибольший общий делитель из й и у . Последовательность разностей 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) доказал, что эта последовательность содержит только единицы и простые числа. Однако он не содержит всех простых чисел, так как члены gcd ( n + 1, a _n ) всегданечетным и, следовательно, никогда не равным 2. 587 - наименьшее простое число (кроме 2), не появляющееся в первых 10 000 исходов, отличных от 1. Тем не менее в той же статье предполагалось, что оно содержит все нечетные простые числа, даже если оно довольно неэффективно. ^[14]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Regimbal, Стивен (1975), "Явная формула для к-го простого числа", Математика Журнал , Математическая ассоциация Америки, 48 (4): 230-232, DOI : 10,2307 / 2690354 , JSTOR  2690354.
• Венугопалан. Формула для простых чисел, простых чисел-близнецов, числа простых чисел и числа простых чисел-близнецов . Труды Индийской академии наук - математические науки, Vol. 92, № 1, сентябрь 1983 г., стр. 49–52 исправления.

Внешние ссылки [ править ]

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