Тест простоты

[nnosipov]

Dmitriy40
Если $n$ простое число, то указанное в гипотезе сравнение заведомо верно --- это банальный факт, и многочлены Фибоначчи здесь ни при чем (верно для любого нормированного многочлена степени $n-1$). Так что контрпример --- это составное $n$, для которого сравнение также было бы верно. Т.е. вычислять неприятную сумму нужно только для составных $n$.

Еще один упрощающий момент: сумму можно сократить вдвое, поскольку при нечетном $n$ многочлен $F_n(x)$ является четной функцией.

[Dmitriy40]

nnosipov в сообщении #1437781 писал(а):

Т.е. вычислять неприятную сумму нужно только для составных $n$.

Ну собственно я и не гнался за скоростью. А это почти и не ускоряет, до $n<3000$ всего 430 простых, т.е. проверять надо более 85% чисел. Дальше простых ещё меньше. Так что потеря менее 15% скорости даёт зато и проверку простых тоже.

nnosipov в сообщении #1437781 писал(а):

Еще один упрощающий момент: сумму можно сократить вдвое, поскольку при нечетном $n$ многочлен $F_n(x)$ является четной функцией.

И тоже, ускорение навскидку примерно 25%. Если б гнаться за скоростью, то да, но для первого подхода сойдёт и так.

С практической точки зрения данный тест простоты интереса не вызывает из-за своей медлительности (перебор делителей и то на порядки быстрее), а с точки зрения поиска контрпримера ... Может кому и интересно будет.

[nnosipov]

Dmitriy40 в сообщении #1437789 писал(а):

с точки зрения поиска контрпримера ...

По-моему, только это здесь и интересно.

[Sonic86]

Пусть $f(x)=\sum\limits_{k=0}^{n-1}a_kx^k$ - произвольный, upd: fix: $a_0=1$.
Тогда $S=\sum\limits_{x=0}^{n-1}f(x)=\sum\limits_{x=0}^{n-1}\sum\limits_{k=0}^{n-1}a_kx^k=\sum\limits_{k=0}^{n-1}a_k\sum\limits_{x=0}^{n-1}x^k=n+\sum\limits_{k=1}^{n-1}a_k\sum\limits_{x=0}^{n-1}x^k$. (upd: fix: здесь для $k=0$ получается слагаемое $na_0$ - исправил здесь и далее)
Тогда $S\equiv -1\pmod n \Leftrightarrow \sum\limits_{k=1}^{n-1}a_k\sum\limits_{x=0}^{n-1}x^k \equiv -1 \pmod n$.
Пусть $n$ - свободно от квадратов, $p\mid n$ - любой простой делитель $n$. Тогда $S\equiv -1\pmod n \Leftrightarrow (\forall p) \sum\limits_{k=1}^{n-1}a_k\sum\limits_{x=0}^{n-1}x^k \equiv -1 \pmod p$
Имеем: $\sum\limits_{x=0}^{n-1}x^k \equiv \sum\limits_{0\leqslant x < n, p\nmid n}x^k \equiv \frac{n}{p}\sum\limits_{x=1}^{p-1}x^k \equiv -\frac{n}{p}[p-1|k] \pmod p$.
(Здесь использована нотация Айверсона: $|P(t)|=1 \Leftrightarrow P(t), |P(t)|=0 \Leftrightarrow \neg P(t)$).
Тогда $S\equiv -1\pmod n \Leftrightarrow (\forall p \mid n) \frac{n}{p}\sum\limits_{k=1}^{n-1}a_k[p-1|k]\equiv \frac{n}{p}\sum\limits_{l=1}^{\left[\frac{n-1}{p-1}\right]}a_{(p-1)l}\equiv 1\pmod p$.
Получили общий критерий для произвольного многочлена $f(x)$.
Для многочленов Фибоначчи $a_k=\binom{\frac{n+k-1}{2}}{k}[k\not\equiv n\pmod 2]$.
Возьмем нечетные $n$, тогда $a_{(p-1)l}=\binom{\frac{n+(p-1)l-1}{2}}{(p-1)l}$. Нам остается исследовать выполнимость сравнения $\sum\limits_{l=1}^{\left[\frac{n-1}{p-1}\right]}\binom{\frac{n+(p-1)l-1}{2}}{(p-1)l} \equiv 1\pmod p (\forall p\mid n)$.

Здесь скорее всего почти все слагаемые $a_{(p-1)l}\equiv 0\pmod p$, ненулевыми могут быть только несколько слагаемых сначала или с конца, м.б. даже только с конца. Но здесь у меня руки несколько опустились из-за довольно корявой структуры суммы и нехватки ресурсов. Здесь можно дальше ковырять, или расчехлить железку в поиска контрпримера - расчеты здесь будут сильно быстрее, чем вышеприведенная проверка в лоб. Если кто может и хочет - попробуйте.
Ну и выкладки нужно проверить - я легко мог наврать.
(очень жаль, что нет автоматических средств выполнения подобных преобразований - хорошо было бы поручить проверку ему, да и все)

[nnosipov]

Sonic86 в сообщении #1437920 писал(а):

Пусть $f(x)=\sum\limits_{k=0}^{n-1}a_kx^k$ - произвольный.

Обнаружил у себя в одном из файлов критерий для случая $f(x)=x^{n-1}$. А именно, пусть $n \geqslant 2$. Сравнение

$$1^{n-1}+2^{n-1}+\ldots+(n-1)^{n-1} \equiv -1 \pmod{n}$$

имеет место тогда и только тогда, когда $n$ --- простое число или $n$ --- число Кармайкла со свойством: $n/p-1$ делится на $p$ для любого простого делителя $p$ числа $n$. Таким образом, вопрос о контрпримере в данном случае сводится к поиску специальных чисел Кармайкла (существуют ли они, мне неизвестно).

Вообще, хотелось бы послушать начальника транспортного цеха ТС, почему все это может быть интересно.

[Soul Friend]

Вычислил некоторое количество полиномов Фибоначчи, для наглядности. $0 \leqslant n, x \leqslant13$

(Картинки)

Всё ещё не до конца понял структуру сумм $f(n)=a \cdot f(n-1)+f(n-2)$ , а именно то - как накапливаются остатки по модулю $n$ .

nnosipov в сообщении #1437781 писал(а):

поскольку при нечетном $n$ многочлен $F_n(x)$ является четной функцией.

Как показала практика, при чётном $x$ и чётном $n$ - функция чётная. При $x$ чётное и $n$ нечётное - функция нечётная.
При $x$ нечётная - значения функции чередуются как для $n$ - чётная, так и для $n$ - нечётная. (через два нечётных одна чётная)

[maxal]

Pedja в сообщении #1437583 писал(а):

Dmitriy40 в сообщении #1437578 писал(а):

Обычно ищут более быстрые тесты

Это правда. Посмотрите тест с временем выполнения $O (\log ^ 3 n)$, описанным в гипотезе 5.

По поводу гипотезы 5 я уже высказал сомнения на MO.