WikiSort.ru - Не сортированное

Период Пизано ${\displaystyle \pi (m)}$  — это длина периода последовательности Фибоначчи по модулю заданного натурального числа m.

Периодичность

Последовательность Фибоначчи по модулю любого натурального числа m периодична, так как среди первых ${\displaystyle m^{2}+1}$ пар чисел найдутся две равные пары ${\displaystyle (x_{i},x_{i+1})\equiv (x_{j},x_{j+1}){\pmod {m}}}$ для некоторых ${\displaystyle i\leq j}$ . Поэтому для всех натуральных k выполняется ${\displaystyle x_{i+k}\equiv x_{j+k}{\pmod {m}}}$ , то есть, последовательность периодична.

Примеры

Например, по модулю ${\displaystyle 4}$ последовательность Фибоначчи выглядит как

0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1 ...

и поэтому ${\displaystyle \pi (4)=6}$ .

Последовательность периодов Пизано начинается так (последовательность A001175 в OEIS):

${\displaystyle m}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle \pi (m)}$	1	3	8	6	20	24	16	12	24	60	10	24	28	48	40	24

Свойства

• Если a и b взаимно просты, то ${\displaystyle \pi (ab)=\mathrm {HOK} \left(\pi (a),\pi (b)\right)}$ . Или если ${\displaystyle m=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}}$ , то ${\displaystyle \pi (m)=\mathrm {HOK} (\pi (p_{1}^{\alpha _{1}}),\pi (p_{2}^{\alpha _{2}}),\ldots ,\pi (p_{k}^{\alpha _{k}}))}$ (следствие китайской теоремы об остатках).

• ${\displaystyle \pi (m)=\sigma (m)\cdot \sigma _{0}(m)}$ , где за ${\displaystyle \sigma (m)\;}$ обозначено количество нулей в периоде, а за ${\displaystyle \sigma _{0}(m)\;}$ обозначен индекс первого нуля (не считая ${\displaystyle F_{0}}$ ). Более того, известно что ${\displaystyle \sigma (m)\in \{1,2,4\}}$ .

• Для простого числа p и целого числа k ≥ 1 выполняется ${\displaystyle \pi (p^{k})|p^{k-1}\cdot \pi (p)}$ . Более того, для всех точных степеней простых чисел от 1 до миллиона выполнено равенство ${\displaystyle \pi (p^{k})=p^{k-1}\cdot \pi (p)}$ . Но до сих пор неизвестно, на всегда ли выполнено это равенство, и существуют ли такое p, что ${\displaystyle \pi (p^{2})=\pi (p)}$ .

• Если ${\displaystyle p}$  — простое число, то справедливы следующие утверждения:
  • при ${\displaystyle p\equiv \pm 1{\pmod {5}}}$ число ${\displaystyle \pi (p)}$ является делителем ${\displaystyle p-1}$ ,
  • при ${\displaystyle p\equiv \pm 2{\pmod {5}}}$ число ${\displaystyle \pi (p)}$ является делителем ${\displaystyle 2p+2}$ .

• Для всех положительных целых чисел m справедливо неравенство ${\displaystyle \pi (m)\leq 6m}$ , причём равенство в нём достигается только на числах вида ${\displaystyle m=2\cdot 5^{k}}$ .

Ссылки

• Charles W. Campbell II, «The Period of the Fibonacci Sequence Modulo j», Math 399 Spring 2007
• Marc Renault, «The Fibonacci sequence modulo m»
• Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).

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