Паттерн в ряду простых чисел

[welder]

Здравствуйте. Не так давно, обнаружил (возможно это уже известный, но не для меня) паттерн в распределении простых чисел.

Воспользуемся формулировкой теста простоты Агравала-Каяла-Саксены:

$\forall{n}\in\mathbb{N},\ ((x + 1)^n - (x^n + 1) = 0\mod n) \Rightarrow n\in P,$

где $P$ - множество простых чисел.
Это записано не совсем корректно (оригинальная формула недоступна для моего понимания, поэтому воспользовался тем, что узнал на канале Numberphile в переводе Mad Astronomer'а), но так я хотел сказать: если каждый биномиальный коэффициент (за исключением двух единиц) разложения $(x + 1)^n$ делится на $n$, то $n$ - простое.
Вычисление $n$-ой строки треугольника Паскаля (содержащей необходимые биномиальные коэффициенты) обладает алгоритмической сложностью порядка $O(n^2)$ операций сложения или $O(n)$ операций нахождения факториала и их отношений. Факториалы можно вычислять быстрее если использовать дерево умножений. Можно еще быстрее, определяя сколько в факториале простых множителей используя деление аргумента на простые числа меньшие либо равные аргументу факториала, записывать в память целое от такого деления как степени простых чисел. Если степень какого-либо простого в факториале числителя равна сумме степеней того же числа в факториалах знаменателя то, этот коэффициент не поделится на $n$, так как все степени этого числа были исчерпаны при делении факториалов, а не постое $n$ содержит степень именно такого простого числа. На мой взгляд, это как-то связано с теоремой Люка о делимости биномиальных коэффициентов на простые числа, описание в Википедии оказалось для меня слишком сложным. В последнем случае нужно знать простое ли $n$ - следует ли добавить 1 в новый элемент списка степеней, или добавить некотрые числа к степеням уже известных простых чисел. Сложность порядка $O(\pi(n))$ операций деления и сложения\вычитания.
Это очень медленно! А битовая сложность еще больше.

Нельзя ли как-то добыть информацию о делимости каждого биномиального коэффициента на $n$ без его вычисления? Предположим, что в некоторых, особо удачных случаях можно. Но догадка оказалась неверна, однако приводит к неплохим результатам. В чем суть, сумма чисел в $n$-ой строке триугольника Паскаля равна $2^n$. отбросим единицы как заведомо не делимые на $n$. Если такую сумму можно равномерно распределить между $n-1$ слогаемым (всего коэффициентов в строке $n+1$, убрали две единицы, стало $n-1$ слагаемых), и она делится на $n$, то $n$ - простое. Сформулируем критерий:

$\forall{n}\in\mathbb{N}, (0=2^n-2\mod n)\wedge(0=2^n-2\mod (n-1)) \Rightarrow n\in P$

Но, возможна ситуация, когда $n$ - составное и коэффициенты $n$-ой строки не только в сумме делятся на $n$, но и при распределении на равные слогаемые, так же делятся на $n$. Если сумма делится, к примеру на 7 , но отдельные слагаемые - нет и количество слагаемых при этом уменьшается:
$7a_1+7a_2+23+19=7a_1+7a_2+42=7(a_1+a_2+6)$ - не строка из треугольника Паскаля, просто иллюстрация.
Кажется, что можно отсеять такие строки, если распределить по слагаемым сумму строки равномерно, т.е. взять среднее значение.
В том случае, если некоторые коэффициенты не делятся на $n$, существование целочисленного среднего значения, также не дает нам точной информации, о делимости каждого коэффициента на $n$. Пример:

$7\times 5+7\times 5+25+45=7\times 5+7\times 5+70$

Кажется, что количество слагаемых уменьшилось и такая сумма не распределится на 4 одинаковых слагаемых (т.е. не поделится на 4 - число слагаемых), но не тут-то было:

$7\times 5+7\times 5+70=7\times 5+7\times 5+35+35=7\times 5+7\times 5+7\times 5+7\times 5$

Но к моему удивлению такая ситуация для строк триугольника Паскаля весьма редка, при $n < 2000000$ ложно-положительные результаты отсутствуют. Ложно-отрицательных результатов много. Нашел контрпример $n = 2^{43}-1$ - явно принадлежит множеству чисел Мерсена исходя из его вида, и такого числа нет в списке всех известных чисел Мерсена (в этом списке нет пропусков), следовательно $n = 2^{43}-1$ - не простое. Так же, замечено, что общий вид критерия поиска

$\forall{n}\in\mathbb{N}, (0=2^n-2\mod n)\wedge(0=2^n-2\mod (n-k)) \Rightarrow n\in P$

чуть менее эффективен, но число ложно-положительных результатов для $n$ сопоставимых порядков быстро убывает с ростом порядка величины проверяемых чисел. К примеру для $k=2$ - 14-ое возвращенное значение функции (код приведу ниже) составное, а следующее составное не 28-ое как может показатся, а 43-е. Исследовал все $k<64$ - возвращаемые значения совпадают с множеством простых чисел Мерсена, только в начале. Наибольшее совпадение - $M_{127}$ - 9-ое простое число Мерсена.

Используется синтаксис Python

def Agrawal_Kayal_Saxena_primality_test(natural_number):
    """There is primality test based on AKS primality test. For all "n", if
    (x + 1) ** n - (x ** n - 1) is divisible by "n", then "n" is prime. But it's
    so slow working.

    I've made a hypotesis:
    (1) {n for n in range(N) if ((2 ** n) % n == 2) and
         ((2 ** n) % (n - 1) == 2)
         }.issubset(P) == True,
    where N - set of natural numbers; P - set of prime numbers, "%" - module
    operator.
    There have a lot of false negative and a bit of false positive returns.

    For example n = 2 ** 43 - 1 is not prime, but test return True. How did I
    find this minimal counterexample where "n" is very large? I used the fast
    implementation of 2 ** Mn by module Mn, where Mn - is n-th Mersene number.
    (2) 2 ** Mn % Mn == 2 ** (2 ** n - 1) % (2 ** n - 1) ==
        2 ** ((2 ** n - 1) % n) == 2 ** (Mn % n)
    By the diffinition of (2) we can make fast implementation of 2 ** Mn %
    (Mn - k), where k in N.
    (3) 2 ** Mn % (Mn - k) == 2 ** (2 ** n - 1) % (2 ** n - 1 - k) ==
        2 ** ((2 ** n - 1) % (n - k)) == 2 ** (Mn % (n - k))
    For example:
        2 ** M19 % (M19 - 1) == 2 ** ((2 ** 19 - 1) % (19 - 1)) ==
     == 2 ** ((2 ** 19 - 1) % 18) == 2
    If we divide 2 ** (2 ** n - 1) by 2 ** n we got a 2 ** ((2 ** n - 1) - n) of
    1-s, wich compliting every single 2 ** n - 1. (included in the decomposition
    of 2 ** Mn to an addendums) to 2 ** n. Divide the resulting number by 2 ** n
    and so on, until possible it to devide. When number could't to divided, then
    it's an remainder of 2 ** (2 ** n - 1) by module of (2 ** n - 1),
    i.e. 2 ** Mn % Mn.
    Q.E.D.

    Suppose, bit lengths of numbers Mersene numbers b1 and b2:
        b1 = math.log2(2 ** (2 ** n - 1) - 1),
        b2 = math.log2(2 ** (2 ** n - 1) - 1).
    Then be able to explain why the FMMM algorithmis faster then all other. It's
    faster then anythin else algoritm for powering by module, because this
    imlementation reduce complexity of problem to
    O(math.log2(b1) * math.log2(log(b1))) from O(b1 * math.log2(b1))
    for fast powering by module. Logarithmic complexity simplification!

    """



    def AKS_rowsum(row_index):
        """Sum an addendums in a n-th row of Pascal's Triangle (except are 0-th
        and n-th of addendums).

        It is a special representation of core condition of
        Agrawal-Kayal-Saxena primality test.

        """
        return (1 << row_index) - 2
        # Is equivalen of 2 ** power - 2 in terms bit-magic. I used bit-magic
        # because that is faster than naive method.

    def AKS_extension(applicant):
        specrep = AKS_rowsum(applicant)
        divisibilty = specrep % applicant
        distribytility = specrep % (applicant - 1)
        # A sum is able distribyted on equal summands in type like "a * c",
        # where "a" is applicant to a prime number; c - is some multiplier.
        # (applicant - 1) is quantity of summands in special representation
        # of AKS core condition.
        return False if divisibilty or distribytility else True

    return AKS_extension(natural_number)
 

Для

Используется синтаксис Python

range(100000)

критерию соответствуют 33 простых числа:

7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367, 42463, 71443, 77659, 95923, 99079, 113779, 117307, 143263, 174763, 175447, 184843

Почему это работает? Почему так мало контрпримеров?

[arseniiv]

welder в сообщении #1407350 писал(а):

но так я хотел сказать: если каждый биномиальный коэффициент (за исключением двух единиц) разложения $(x + 1)^n$ делится на $n$, то $n$ - простое

А в чём была проблема так и записать: $\left(\forall m\in 1..(n-1).\; n|\binom nm\right)\Rightarrow n\in\mathbb P$?

-- Сб июл 27, 2019 16:19:21 --

(Оффтоп)

welder в сообщении #1407350 писал(а):

оригинальная формула недоступна для моего понимания

welder в сообщении #1407350 писал(а):

описание в Википедии оказалось для меня слишком сложным

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

[welder]

arseniiv в сообщении #1407368 писал(а):

welder в сообщении #1407350 писал(а):

но так я хотел сказать: если каждый биномиальный коэффициент (за исключением двух единиц) разложения $(x + 1)^n$ делится на $n$, то $n$ - простое

А в чём была проблема так и записать: $\left(\forall m\in 1..(n-1).\; n|\binom nm\right)\Rightarrow n\in\mathbb P$?

-- Сб июл 27, 2019 16:19:21 --

(Оффтоп)

welder в сообщении #1407350 писал(а):

оригинальная формула недоступна для моего понимания

welder в сообщении #1407350 писал(а):

описание в Википедии оказалось для меня слишком сложным

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

Тест Агравала-Каяла-Саксены
Извините за вставку с английской Вики, но неполучается вставить ссылку на русскоязычную, где есть моменты которые не освящены в англоязычной. В разделе "Формулировка", я уже путаюсь - там сравнивают по модулю сразу двух чисел $(x^r-1)$ и $n$? Какой смысл у целой части $\sqrt{\varphi(r)}\log n$? Почему необходимо выполнение $o_r(n)>\log^2 n$? $o_r(n)$ - это $o$-малое, нижняя ассимптотика роста? Но роста чего, при исследовании сложности алгоритмов, это очевидно, нижняя граница сложности вычисления на машине Тьюринга от размера входа, но как это "привинчено" к самому тесту, а не к его сложности - не ясно.

-- 27.07.2019, 22:25 --

Думаю формулировка теорем на словах как в древнем Вавилоне поможет мне понять, но на Вики, все очень сжато, доказательсва уложены в короткие формулы, которые легко понять, когда ты пользуешься Вики как справочником, но не для изучения кого-то вопроса почти с нуля.

-- 27.07.2019, 22:29 --

Хотел было поделится сим фактом с господином Числофилом с одноименного канала (Numberphile, Этот эпизод в переводе Mad Astronomer'а), но у них нет формы обратной связи - видимо психи-паттернисты их утомили, своими безумными паттернами и доказательствами гипотезы Римана.

Небольшое уточнение, на вход подавал нечетные числа вида $2n+1$, поэтому при входе:

Используется синтаксис Python

range(100000)

на выходе есть числа близкие к 200000.

[welder]

Странно, контрпримеры 184369 и 4369 (можно найти при $k=4$) по модулям 4, 6, 12 равны 1. Согласно теореме которая используется в решете Аткина, все простые числа лежат в арифметических последовательностях $4n+1,\ 6n+1,\ 12n+1$. Может ли число лежать сразу во всех таких последовательностях? Может быть, стоит все такие числа отсеивать, даже если там попадаются простые, число ложно-отрицательных результатов возрастет, но, возможно, число ложно-положительных уменьшится? Вдруг все ложно-положительные результаты по модулю 4, 6, 12 равны 1?

[arseniiv]

welder в сообщении #1407374 писал(а):

там сравнивают по модулю сразу двух чисел $(x^r-1)$ и $n$?

И на английской странице, и на русской объясняется, что это значит: «Сравнение по двум модулям вида $a(x)\equiv b(x)\pmod{h(x),n}}$ для многочленов $a(x),b(x)\in\mathbb Z[x]$ означает…». На английской притом это записано более общо ($a\equiv b\pmod{m_1,m_2}$, если $a-b = c_1m_1 + c_2m_2$ для некоторых $c_1, c_2$; всё в соответствующем кольце). Не забудьте также обратить внимание, что тут не по модулю двух чисел, а по модулю двух многочленов.

welder в сообщении #1407374 писал(а):

Какой смысл у целой части $\sqrt{\varphi(r)}\log n$? Почему необходимо выполнение $o_r(n)>\log^2 n$?

Ну, там вот есть раздел «Обоснование», плюс саму исходную статью можно бы почитать, если его недостаточно.

А $o_r$ — это вроде https://en.wikipedia.org/wiki/Multiplicative_order.

[welder]

Занялся изучением статьи https://primes.utm.edu/prove/prove4_3.html.

Цитата:

Their idea was to look at the simpler condition:

$(x-a)^p=(x^p-a)\mod{(x^r-1,\ p)}$

This must hold if $p$ is prime and it is conjectured that if $r >1$ does not divide $p$ and the above congruence holds, then either $p$ is prime or $p^2$ is 1 modulo $r$.

Давайте проверим число 7 на простоту. Пусть $x=2;\ a=1$. Замечу, $a$ следует перебирать от 1 до $2\sqrt{r}\log{n}$, если найдется $a$, которое нарушит выше приведенное условие, то $p$ - составное. Подберем такое $r$, чтобы $1\ne p^2\mod(r)$, перебирая все простые, $1\ne 7^2\mod(5)$. Значит $r=5$. Отсюда,

$(2-1)^7=(2^7-1)\mod{(2^5-1,\ p)}$

7 - не простое чило! Но это не так. Где я ошибся?

-- 30.07.2019, 21:16 --

Там же:

Цитата:

Theorem: Suppose that a and p are relatively prime integers with p > 1. p is prime if and only if...

(и приводится вышеуказанное сравнение по модулям. Тестируемое число $p$ и число $a$ - должны быть взаимно просты, т.е. 1 для $a$ неподходит, т.к. на 1 делится любое число.

-- 30.07.2019, 21:26 --

Хотя, нет. Неверно, $a$ и $p$, должны быть просты в вероятностном тесте Агравалы-Бисваса. И там необходимо проверить кучу биномиальных коэффициентов.

-- 30.07.2019, 21:34 --

И так, идея которую я описал в самом начале, и которая является темой топика совсем не похожа на тест АКС. В обоих случаях есть проверка по модулю тестируемого числа. Но только в моейм случае, берем по модулю $p-1$. Т.е. представленный мной паттерн весьма примечателен. Но никак не получается понять АКС, я пробовал проверять числа, но как видите для числа 7 ничего не вышло.