рекуррентная функция

[alisa-lebovski]

По моим расчетам, при $\alpha=\frac{5-\sqrt{5}}{10}$ получается шаг 20, т.е. $f(n+20)=f(n)$. Это перебором долго будет.

[svv]

alisa-lebovski в сообщении #1476421 писал(а):

Тут интереснее поставить вопрос, при каких еще $\alpha$ (например, вида $(a+b\sqrt{m})/c$, где $a, b, c, m$ - целые) и соответственно величинах шага наблюдается подобный эффект?

В матричной форме эффект выражается в том, что при некоторых $\alpha$ и $n$ матрица
$A=\begin{bmatrix}1&-\alpha\\1&0\end{bmatrix}\;,$
возведённая в степень $n$, внезапно пропорциональна единичной матрице.
Пусть $\alpha>\frac 1 4$, тогда собственные значения $A$ равны $\frac 1 2\pm i\sqrt{\alpha-\frac 1 4}$. Их аргумент равен $\pm\arctg\sqrt{4\alpha-1}$ и после умножения на $n$ должен быть кратен $\pi$. Отсюда
$\alpha=\dfrac{1+\tg^2 \frac{\pi k}n }4=\dfrac 1{4\cos^2\frac{\pi k}n }$

Значение $\alpha=\frac{3+\sqrt{5}}2$ получается при $k=2, n=5$.
Значение $\alpha=\frac{5-\sqrt{5}}{10}$ получается при $k=1, n=10$.
При каких $k$ и $n$ формула даёт числа вида $(a+b\sqrt{m})/c$ — этого я не знаю. Вопрос сводится к тому, когда такой вид имеет $\cos^2\frac{\pi k}n$ или $\cos\frac{2\pi k}n$.

[nnosipov]

svv в сообщении #1476435 писал(а):

Вопрос сводится к тому, когда такой вид имеет $\cos^2\frac{\pi k}n$ или $\cos\frac{2\pi k}n$.

Т.е. при каких $k$ и $n$ число $\cos\frac{2\pi k}n$ будет квадратичной иррациональностью? На самом деле это несложный вопрос, поскольку число $\cos\frac{2\pi k}n$ (при $\gcd{(k,n)}=1$) будет алгебраической иррациональностью степени $\varphi(n)/2$, где $\varphi$ --- функция Эйлера.

[alisa-lebovski]

Спасибо, отлично! Значит, $\varphi(n)=4$, что дает: $n=5,8,10,12$. Подробнее,
$n=5$: $k=1,2,3$.
$n=8$: $k=1,3,5,7$.
$n=10$: $k=1,3,7,9$.
$n=12$: $k=1,5,7$.
Итого 13 случаев.
При четных $k$ получаем шаг $n$, при нечетных - шаг $2n$.
Максимально возможный шаг - 24.

[alisa-lebovski]

Ошиблась.
$n=5:$ $k=1,2,3,4$.
$n=12:$ $k=1,5,7,11$.
И всего 16 случаев.

[svv]

alisa-lebovski и nnosipov, спасибо!

[svv]

Реально случаев ещё меньше, потому что $\cos\frac{2\pi k}{n}=\cos\frac{2\pi (n-k)}{n}$, и такие случаи, как $n=10, k=1$ и $n=10, k=9$, дают одно и то же значение $\alpha$.
Приведу табличку:
$\begin{array}{cc} \dfrac k n & \alpha \\ [2ex] \dfrac 1 5 & \dfrac{3-\sqrt{5}}{2}\\ [2ex] \dfrac 2 5 & \dfrac{3+\sqrt{5}}{2}\\ [2ex] \dfrac 1 8 & \dfrac{2-\sqrt{2}}{2}\\ [2ex] \dfrac 3 8 & \dfrac{2+\sqrt{2}}{2}\\ [2ex] \dfrac 1{10} & \dfrac{5-\sqrt{5}}{10}\\ [2ex] \dfrac 3{10} & \dfrac{5+\sqrt{5}}{10}\\ [2ex] \dfrac 1{12} & 2-\sqrt{3}\\ [2ex] \dfrac 5{12} & 2+\sqrt{3}\end{array}$

[alisa-lebovski]

Да, это я не учла. Спасибо, отлично!