Русская Википедия:Период Пизано
Период Пизано <math>\pi(m)</math> — это длина периода последовательности Фибоначчи по модулю заданного натурального числа m.
Примеры
Например, определим период Пизано при <math>m = 4</math>. Пусть <math>F_i</math> — <math>i</math>-е число Фибоначчи. <math>F_i \mod m</math> — остаток от деления <math>i</math>-го числа Фибоначчи на число <math>m</math>. Заполнив следующую таблицу,
| <math> i </math> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | … |
| <math> F_i </math> | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | … |
| <math> F_i \mod m </math> | 0 | 1 | 1 | 2 | 3 | 1 | 0 | 1 | 1 | 2 | 3 | 1 | 0 | 1 | 1 | 2 | 3 | 1 | 0 | … |
заметим, что первые шесть чисел (0, 1, 1, 2, 3, 1) последовательности <math>\{ F_i \mod m \} </math> повторяются бесконечно, значит для <math>m = 4</math> период Пизано равен шести: <math>\pi(4)=6</math>.
Последовательность, составленная из периодов Пизано, получила номер Шаблон:OEIS2C, и начало её показано в следующей таблице.
| <math>m</math> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| <math>\pi(m)</math> | 1 | 3 | 8 | 6 | 20 | 24 | 16 | 12 | 24 | 60 | 10 | 24 | 28 | 48 | 40 | 24 |
Периодичность
Последовательность Фибоначчи по модулю любого натурального числа <math>m</math> периодична, так как среди первых <math>m^{2}+1</math> пар чисел найдутся две равные пары <math>(x_{i}, x_{i+1}) \equiv (x_{j}, x_{j+1}) \pmod m</math> для некоторых <math>i \leqslant j</math>. Поэтому для всех натуральных k выполняется <math>x_{i+k} \equiv x_{j+k} \pmod m</math>, то есть, последовательность периодична.
Свойства
- Если a и b взаимно просты, то <math>\pi(ab) = \mathrm{HOK} \left( \pi(a), \pi(b) \right) </math>. Или, если разложить <math>m</math> на простые множители: <math>m = p_{1}^{ \alpha_{1} } \cdot p_{2}^{ \alpha_{2} } \cdot \ldots \cdot p_{k}^{ \alpha_{k} }</math>, то <math>\pi(m) = \mathrm{HOK} \left( \pi(p_{1}^{\alpha_{1}}), \pi(p_{2}^{\alpha_{2}} \right) , \ldots , \pi( p_{k}^{ \alpha_{k} } ) )</math> (следствие китайской теоремы об остатках).
- <math>\pi(m) = \sigma(m) \cdot \sigma_0(m) </math>, где за <math>\sigma(m)\;</math> обозначено количество нулей в периоде, а за <math>\sigma_0(m)\;</math> обозначен индекс первого нуля (не считая <math>F_0</math>). Более того, известно что <math>\sigma(m) \in \{ 1, 2, 4 \}</math>.
- Для простого числа <math>p</math> и целого числа <math>k \geqslant 1</math> выполняется <math>\pi(p^k) | p^{k-1} \cdot \pi(p)</math>. Более того, для всех точных степеней простых чисел от 1 до миллиона выполнено равенство <math>\pi(p^k) = p^{k-1} \cdot \pi(p)</math>. Но до сих пор неизвестно (см. открытые математические проблемы), для всех ли чисел справедливо это равенство, и существуют ли такое p, что <math>\pi(p^2) = \pi(p)</math>.
- Если <math>p</math> — простое число, то справедливы следующие утверждения:
- при <math>p \equiv \pm 1 \pmod 5 </math> число <math>\pi(p)</math> является делителем <math> p - 1 </math>;
- при <math> p \equiv \pm 2 \pmod 5 </math> число <math>\pi(p)</math> является делителем <math> 2 \cdot p + 2 </math>.
- Для всех положительных целых чисел <math>m</math> справедливо неравенство <math>\pi(m) \leqslant 6\cdot m</math>, причём равенство в нём достигается только на числах вида <math>m = 2 \cdot 5^{k} </math>.
Ссылки
- Charles W. Campbell II, «The Period of the Fibonacci Sequence Modulo j», Math 399 Spring 2007
- Marc Renault, «The Fibonacci sequence modulo m»
- Шаблон:Книга
