Доказательство (не) пригодности этого N-го простого повторения

18

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

Говоря кратко, мы можем определить разрыв между каждым простым числом как повторение предыдущих простых чисел- кандидатов . Например, для нашей базы п0знак равно2 следующее простое число будет:

п1знак равномин{Икс>п0|-соз(2π(Икс+1)/п0)+1знак равно0)}

Или, как мы видим из графика : .п1знак равно3

Мы можем повторить процесс для простых чисел, оценивая каждого кандидата, повторяющегося вперед. Предположим, мы хотим получить следующее простое число, . Наша функция-кандидат становится:р 2Nп2

п2знак равномин{Икс>п1|еп1(Икс)+((-соз(2π(Икс+1)/п1)+1)(-соз(2π(Икс+2)/п1)+1))знак равно0}

Где:

еп1(Икс)знак равно-соз(2π(Икс+1)/п0)+1 , как указано выше.

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

Повторение становится:

еп0знак равно0п0знак равно2епN(Икс)знак равноепN-1(Икс)+ΠКзнак равно2пN-1(-соз(2π(Икс+К-1)/пN-1)+1)пNзнак равномин{Икс>пN-1|епN(Икс)знак равно0}

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

Рабочий код Python для демонстрации повторения:

from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

Быстрый пример:

>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Беда в том, что я сейчас над головой, и математически, и как ученый. В частности, я не компетентен с анализом Фурье , с определением равномерных покрытий или со сложной плоскостью в целом, и меня беспокоит, что этот подход либо совершенно ошибочен, либо скрывает скрывающийся ужас проблемы 3SAT, которая поднимает ее до NP-полнота.

Таким образом, у меня есть три вопроса здесь:

  1. Учитывая мой краткий рецидив выше, возможно ли детерминистически вычислить или оценить расположение нулей в полиномиальном времени и пространстве?
  2. Если так или нет, то скрывает ли он какие-либо другие подзадачи, которые делали бы решение Polytime или Polyspace неразрешимым?
  3. И если каким-то чудом (1) и (2) выдержать, какие усовершенствования в динамическом программировании вы бы выполнили для удовлетворения этого повторения с высокого уровня? Ясно, что итерации по одним и тем же целым числам через несколько функций неэлегатны и довольно расточительны.
MrGomez
источник
И для тех, кто все еще здесь, несмотря на мою стену текста: я не уверен, сводит ли это себя к дзете Римана, тем самым придавая ему ту же сложность. Я не верю, что это так.
MrGomez
1
ее(пN)
1
Я не слежу за всем в вашем посте. Я думаю, вы имеете в виду NP-полный, а не NP. Вообще, доказать, что теоретико-числовая функция является NP-полной, довольно трудная задача, так как они часто не имеют / скрывают какую-либо комбинаторную структуру, которая позволила бы нам разрабатывать гаджеты для сокращения.
Каве
1
е(Икс)
е

Ответы:

1

Следующая статья показывает, что PRIMES находится в P (он также получил награду Gödel в 2006 году):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

Задавая решение N-й процедуры минимизации простых чисел алгоритму AKS PRIMES (по модулю вычитания), мы можем эффективно получить поддающееся обработке решение для рекуррентного отношения (если вы можете доказать, что простой разрыв задан рекуррентным отношением).

Исходники можно найти в интернете. Я не указываю на них здесь, потому что я не проверял их лично.

N

user13675
источник
1
Страница Rosettacode полностью неверно названа. Это не тест простоты AKS, а переформулировка пробного деления на все целые числа, меньшие n. С другой стороны, стоит отметить, что первичность находится в P, и посмотреть, проливает ли это хоть какой-то свет на исходный вопрос.
DanaJ
Хороший вопрос ... Я исправлю это ...
user13675
1
NЛ.Г.N