피사노 주기(Pisano Period)

피사노 주기: 피보나치 수를 K로 나눴다고 했을 때, 그 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라 함.

피사노 주기를 P라고 했을 때,

N % M == (N % P) % M

또한 $M = 10^{k}$ 일 때 k>2라면 주기는 항상 $15*10^{k-1}$이라는 공식이 성립함

• pisano period

def pisano_p(x):
    f0, f1 = 0, 1
    f2 = f0+f1

    for i in range(x*x):
        f2 = (f0+f1) % x
        f0 = f1
        f1 = f2
        if f0 == 0 and f1==1:
            return i+1

• 피보나치 수 의 성질
  $F_{n+2}\choose F_{n+1}$ = $1\,1\choose 1\,0$ $F_{n+1}\choose F_{n}$

  $F_{n+1}\,F_{n}\choose F_{n}\,F_{n-1}$ = $1\,1\choose 1\,0$$^{n}$

  $F_{2n-1}$ = $F_{n}$$^{2}$ +$F_{n-1}$$^{2}$

  $F_{2n}$ = ($F_{n-1}$ + $F_{n+1}$)$F_{n}$ = (2$F_{n-1}$ + $F_{n}$)$F_{n}$

  $\sum_{i=0}^{n} F(i) = F_{n+2} -1$
  → 피보나치 수의 합 문제 : https://www.acmicpc.net/problem/2086