피보나치 수의 주기 timer 1s memory 64MB

1960년 IBM의 Donald Wall은 피보나치 수열이 양의 정수 m으로 나눈 나머지에 대하여 주기를 갖는다는 것을 증명하였다.

예를 들어 m이 11인 경우 아래와 같은 주기를 갖는다.

피보나치 수열이 모듈로 m에 대하여 주기를 갖는 길이를 K(m)이라고 하자. 위 표를 예로 들자면 K(11) = 10 이 된다.

Donald Wall은 몇 가지 다른 특성들에 대한 것도 알아내었는데 그것은 다음과 같다.

• m > 2라면 K(m)은 짝수이다.

• n > 2 인 모든 짝수에 대하여 K(m) = n인 m이 존재한다.

• K(m) ≤ m*m - 1

• K(2ⁿ) = 3 * 2^(n-1)

• K(5ⁿ) = 4 * 5ⁿ

• K(2 * 5ⁿ) = 6m

• n > 2 이라면 K(10ⁿ) = 15 * 10^(n-1)

여러분이 해결해야할 문제는 양의 정수 m이 주어질 때 K(m)을 구하는 것이다.