Период трибоначчи по модулю

[slavav]

Числа трибоначчи: $t_0 = 0, t_1 = 0, t_2 = 1, t_{n + 3} = t_{n + 2} + t_{n + 1} + t_n$. Требуется отыскать период последовательности $a_n = t_n \bmod 10^9 + 7$.

[lel0lel]

$n=10^9+7$ простое, тогда $\pi\mid n^3-1$ (это не всегда работает, возможно что-то типа $\pi\mid n(n^2-1)$. Разложение $n^3-1=2\times 6067\times 500000003\times 164826110927971$. То есть период равен некоторому значению из

\{1, 2, 6067, 12134, 500000003, 1000000006, 3033500018201,
6067000036402, 164826110927971, 329652221855942, 1000000015000000057,
2000000030000000114, 82413055958463832783913,
164826111916927665567826, 500000010500000073500000171,
1000000021000000147000000342\}

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

Сейчас проверил численно, верно следующее: $\pi\mid n^2-1$, то есть множество выше не подходит.
Действительно, вот машина нашла $\pi=20833333625000001$

[maxal]

slavav в сообщении #1559658 писал(а):

Числа трибоначчи: $t_0 = 0, t_1 = 0, t_2 = 1, t_{n + 3} = t_{n + 2} + t_{n + 1} + t_n$. Требуется отыскать период последовательности $a_n = t_n \bmod 10^9 + 7$.

С учётом простоты модуля, в PARI/GP вычисляется так:

? p = 10^9+7
%1 = 1000000007

? f = factormod(x^3-x^2-x-1, p)
%2 = 
[                                 Mod(1, 1000000007)*x + Mod(512913426, 1000000007) 1]
[Mod(1, 1000000007)*x^2 + Mod(487086580, 1000000007)*x + Mod(242409634, 1000000007) 1]

? lcm( fforder(ffgen(f[1,1])), fforder(ffgen(f[2,1])) )
%3 = 20833333625000001

[lel0lel]

Небольшой оффтоп.
maxal
Интересно, как быстро PARI/GP умеет вычислять, к примеру, $t_n \bmod n$, где $n=11^{10245}$. У меня время порядка $40$ секунд, но это собственный код в Wolfram.

[slavav]

lel0lel, откуда берутся гипотезы про делимость?

[lel0lel]

Так понимаю, что из анализа группы единиц, по аналогии с https://en.wikipedia.org/wiki/Pisano_period

[maxal]

lel0lel в сообщении #1559677 писал(а):

Интересно, как быстро PARI/GP умеет вычислять, к примеру, $t_n \bmod n$, где $n=11^{10245}$. У меня время порядка $40$ секунд, но это собственный код в Wolfram.

Такой код:

n=11^10245; M = matcompanion(x^3-x^2-x-1)*Mod(1,n); M^n;

у меня в GP выполнился за полторы минуты. Но надо понимать, что это в интерпретаторе. Если скомпилировать, то должно ускориться в разы.

-- Thu Jul 07, 2022 12:15:36 --

slavav в сообщении #1559678 писал(а):

lel0lel, откуда берутся гипотезы про делимость?

Это не гипотезы, а нечетко сформулированные утверждения. Строгое изложение теории можно найти в учебнике
Глухов М. M., Елизаров В. П., Нечаев А. А. Алгебра.
См. глава 25 § 9. Вычисление периода и длины подхода ЛРП над конечным полем

[lel0lel]

maxal в сообщении #1559683 писал(а):

у меня в GP выполнился за полторы минуты. Но надо понимать, что это в интерпретаторе. Если скомпилировать, то должно ускориться в разы.

Удивительно, что в разы, если правильно понимаю, то интерпретатор занимается "промежуточным анализом исходного кода и планированием его выполнения", но ведь ваш код не громоздкий. Это я всё к тому, что очень удивительно, что в большинстве пакетов не реализован алгоритм Fiduccia, с его помощью можно многие операции выполнять быстрее. Я проверял ускорение только в Wolfram и Maple, всюду это разы, а на больших степенях десятки и сотни.

[maxal]

lel0lel в сообщении #1559686 писал(а):

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

С этим кодом может не будет большого ускорения. Изначально у меня был цикл с возведениями в степень 11 - вот там ускорении более реально.

lel0lel в сообщении #1559686 писал(а):

Это я всё к тому, что очень удивительно, что в большинстве пакетов не реализован алгоритм Fiduccia, с его помощью можно многие операции выполнять быстрее.

В лоб Fiduccia реализуется как

n=11^10245; Mod(x,(x^3-x^2-x-1)*Mod(1,n))^n;

что дает ускорение ~10% по сравнению с предыдущим вариантом.