피사노 주기란 피보나치 수열을 어떤 수 m으로 나눈 나머지들의 수열이 반복되는 주기를 말합니다. 피보나치 수열의 각 항을 m으로 나눈 나머지들을 구하다 보면, 이 나머지들이 주기적으로 반복되는 패턴을 갖게 됩니다. 이 패턴이 반복되기 시작하는 주기의 길이를 피사노 주기라고 합니다.
예시
예를 들어, 피보나치 수열을 3으로 나눈 나머지의 피사노 주기를 살펴보겠습니다:
- 피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
- 피보나치 수열을 3으로 나눈 나머지: 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...
여기서 나머지의 수열을 보면 0, 1, 1, 2, 0, 2, 2, 1 이후부터 다시 0, 1, 1, 2, 0, 2, 2, 1이 반복되기 시작합니다. 이 주기는 길이 8의 피사노 주기를 가집니다. 따라서, m=3에 대한 피사노 주기는 8입니다.
피사노 주기의 성질
- 피사노 주기의 길이는 항상 m * 2 이하입니다. 즉, 피사노 주기의 최대 길이는 m * 입니다.
- 피사노 주기를 사용하면 매우 큰 피보나치 수의 나머지를 효율적으로 구할 수 있습니다. 예를 들어 F(n) mod m을 구할 때, n이 매우 큰 경우에도 n mod Pisano period(m)만큼만 계산하면 됩니다.
피사노 주기를 찾는 코드 예시
아래는 특정 m에 대한 피사노 주기를 찾는 파이썬 코드입니다.
def pisano_period(m):
previous, current = 0, 1
for i in range(0, m * m):
previous, current = current, (previous + current) % m
# 피사노 주기의 시작점을 발견 (0, 1이 반복되면 주기가 시작됨)
if previous == 0 and current == 1:
return i + 1
# 예시: 3에 대한 피사노 주기
m = 3
print(pisano_period(m)) # 출력: 8
코드 설명
pisano_period(m): 이 함수는 주어진 에 대해 피사노 주기의 길이를 계산합니다.
- 피사노 주기를 찾기 위해 피보나치 수열의 나머지를 구하다가 (0, 1)이 반복되는 첫 지점을 찾습니다.
대표적인 문제
https://www.acmicpc.net/problem/2749
