피보나치 수열 심화과정2 - 자연수 n이 피보나치 수인지 바로 알 수 있을까? -

1. 주어진 수가 피보나치 수인지 바로 알 수 있을까?

 

피보나치 수는 $F_{1} = F_{2} = 1$이고 $F_{i} = F_{i-1} + F_{i-2}$을 만족하는 $F_{i}$이다.

 

반대로 어떤 자연수 n이 주어질때 그 수가 피보나치 수열 $F_{i}$의 하나인지 바로 판단할 수 있을까?

 

 

2. 행렬을 이용해 피보나치 수를 만드는 방법

 

일반적으로는 $F_{1} = F_{2} = 1$부터 차근차근 만들어나가는 것이다. 

 

그러면 언젠가 주어진 자연수 n 근처에 도달할 것이고, n에 정확히 도달하면 n은 피보나치 수이고 

 

n을 넘어가면 n은 피보나치 수가 아니다.

 

행렬을 이용한 피보나치 수 생성하는 방법이 O(logN)으로 가장 빠르면서 유의미한데, 이정도만 해도 사실 상당히 빠르다

 

https://deepdata.tistory.com/760

행렬을 이용한 피보나치 수열 문제의 해법

 

3. 연습문제

 

기억 안나니까 연습용으로 하나 가져옴

 

https://www.acmicpc.net/problem/13075

13075번: Fibonacci Sequence

 

4. 풀이

 

matrix_multiplication은 두 행렬 a,b의 곱이고 각 원소를 mod로 나눠준 나머지를 저장하는 행렬을 구하는 함수

 

행렬의 곱 c의 원소 $c_{ij} = \sum_{k = 0}^{n} a_{ik}b_{kj}$를 이용한다면 이해할 수 있을 것이고

 

두번째 matrix_exponentiation은 matrix를 분할정복을 이용해 n거듭제곱하는 함수

 

곱의 초기값이 1이듯이 행렬 곱의 초기값은 항등행렬 [[1,0],[0,1]]이고

 

현재 지수가 홀수면 result에 matrix를 한번 곱해줘서 지수를 짝수로 만들고

 

지수가 짝수면, matrix와 matrix를 곱해 제곱시켜주고 n을 절반으로 나눠준다

 

n = 0이 되면 반복문을 탈출하고 result에 n제곱한 결과가 있다

 

https://deepdata.tistory.com/747

ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 -

 

from sys import stdin

mod = 1000000000

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]
                result[i][j] %= mod
    
    return result

def matrix_exponentiation(matrix,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,matrix,mod)
        
        matrix = matrix_multiplication(matrix,matrix,mod)
        n //= 2
    
    return result

T = int(stdin.readline())

for _ in range(T):

    x = int(stdin.readline())
    
    matrix = [[1,1],[1,0]]

    result = matrix_exponentiation(matrix,x,mod)

    print(result[1][0])

 

아무튼 이렇게 해서 result[1][0]이 n에 가까워질때까지 x를 1부터 증가시켜나가다가...

 

result[1][0]이 n이면 n은 피보나치수일거고 n을 넘어가면 n은 피보나치 수가 아니다

 

근데 이렇게하면 조금 아쉽지

 

n을 넣었을때 이게 바로 피보나치 수인지 아닌지 나왔으면 좋겠는데 

 

처음부터 구해보면서 n을 넘어갈까? 안넘어갈까? 조마조마하게 근사시켜가는데

 

 

5. 완전제곱수(perfect square number)

 

어떤 자연수의 제곱수인 수를 완전제곱수라고 부른다.

 

파이썬으로 어떤 정수 n이 제곱수인지 판단하는 방법?

 

https://deepdata.tistory.com/732

약수의 개수가 짝수인지 홀수인지 바로 알아내는 제곱수 판단하는 방법

 

i의 제곱근 i**(1/2)를 구하고, 이를 int()로 만든 다음에 제곱해서 원래 i랑 같은지 확인하자

 

이러면 i가 매우 커도 문제가 없다

 

n = int(input())

num_list = list(map(int,input().split()))

for i in num_list:
    
    if (int(i**(1/2))**2 == i):
        
        print(1)
    
    else:
        
        print(0)

 

 

6. 피보나치 수의 판별식

 

자연수 n에 대하여 n이 피보나치 수일 필요충분조건은

 

$5n^{2} + 4$ 또는 $5n^{2} - 4$이 완전제곱수(perfect square number)인 것이다.

 

연산 몇번을 하고 완전제곱수인지만 판별하면 n이 바로 피보나치 수인지 알 수 있다는 것이 상당히 놀랍다

 

 

7. 증명을 위한 준비

 

증명하는 방법을 두가지 정도 찾았는데.. 둘 다 상당히 까다롭다 

 

근데 그냥 넘어가면 좀 아쉬우니 뭐 하나라도 따라해보면 좋겠는데

 

https://m.blog.naver.com/kyh941031/221919420503 

어떤 수가 피보나치수인지 판별하는 수학적인 방법 (+ 증명)

 

https://mathstorehouse.com/archives/mathematics/algebra/number-theory/2232/

피보나치 수(Fibonacci number) 판별법 - Math Storehouse

 

근데 왜인지 모르겠지만 아래것이 조금 더 유용할것 같아

 

7-1) 보조정리1 - Binet의 공식

 

임의의 음이 아닌 정수 n에 대하여 피보나치 수열의 일반항 $F_{n}$은 다음과 같다.

 

$$F_{n} = \frac{\varphi^{n} - \psi^{n}}{\varphi - \psi} = \frac{\varphi^{n} - \psi^{n}}{\sqrt{5}}$$

 

여기서 두 실수 $\varphi = \frac{1+\sqrt{5}}{2}$, $\psi = \frac{1-\sqrt{5}}{2}$로 정의

 

증명은 이전에 유도했으니

 

https://deepdata.tistory.com/865

피보나치 수열 심화과정1 - n번째 피보나치 수를 바로 계산할 수 있을까? (피보나치 수열의 일반

 

7-2) 보조정리2 - 인접한 두 피보나치 수인가?

 

$x \leq y$를 만족하는 x,y가 음이 아닌 정수라고 하자. 

 

그러면 x,y가 인접한 두 피보나치 수일 필요충분조건은 $$y^{2} - xy - x^{2} = \pm 1$$이 성립하는 것이다.

 

 

1) 증명1 (=>)

 

x,y가 인접한 두 피보나치 수라고 가정하자.

 

즉, $x = F_{n}$이고 $y = F_{n+1}$인 음이 아닌 정수 n이 존재한다. 

 

두 실수 $\varphi = \frac{1+\sqrt{5}}{2}$와 $\psi = \frac{1-\sqrt{5}}{2}$에 대하여 다음이 성립함은 자명하다.

 

$$\varphi\psi = -1, \varphi + \psi = 1, \varphi^{2} = \varphi + 1, \psi^{2} = \psi + 1$$

 

이제 $y^{2} - xy - x^{2}$을 직접 계산해서 $\pm1$인지 구해본다.

 

먼저 $x = F_{n}$이고 $y = F_{n+1}$을 그대로 대입한다.

 

$$y^{2} - xy - x^{2} = (F_{n+1})^{2} - F_{n}F_{n+1} - (F_{n})^{2}$$

 

다음 비네의 공식 $F_{n} = \frac{\varphi^{n} - \psi^{n}}{\sqrt{5}}$에 의해,

 

$$(F_{n+1})^{2} - F_{n}F_{n+1} - (F_{n})^{2} = \frac{(\varphi^{n+1} - \psi^{n+1})^{2}}{5} - \frac{(\varphi^{n} - \psi^{n})(\varphi^{n+1} - \psi^{n+1})}{5} - \frac{(\varphi^{n} - \psi^{n})^{2}}{5}$$

 

다음 식을 조금 더 정리해보면...

 

$$\frac{1}{5} * ((\varphi^{2n+2} - 2(\varphi\psi)^{n+1} + \psi^{2n+2}) - (\varphi^{2n+1} - \psi(\varphi\psi)^{n} - \varphi(\varphi\psi)^{n} + \psi^{2n+1}) - (\varphi^{2n} - 2(\varphi\psi)^{n} + \psi^{2n}))$$

 

그러면 $\varphi\psi = -1, \varphi + \psi = 1, \varphi^{2} = \varphi + 1, \psi^{2} = \psi + 1$을 이용해서 조금 더 간단하게 할 수 있을 것 같다.

 

$$\frac{1}{5} * ( (\varphi^{2n}(\varphi+1)-2(-1)^{n+1} +\psi^{2n}(\psi+1)) - \varphi^{2n+1} -\psi^{2n+1} + (-1)^{n} - \varphi^{2n} - \psi^{2n} +2(-1)^{n})$$

 

$\varphi$와 $\psi$로 이루어진 부분은 모두 지워진다

 

그러므로 식을 더욱 간단하게 하면..

 

$$\frac{1}{5} ( -2(-1)^{n+1} + (-1)^{n} + 2(-1)^{n} ) = \frac{1}{5} (2(-1)^{n} + 3(-1)^{n}) = (-1)^{n}$$

 

따라서 n에 따라 x,y가 인접한 두 피보나치 수라면 $y^{2} - xy - x^{2}$은 1이거나 -1일 수 있다.

 

 

2) 증명2 (<=)

 

음이 아닌 모든 정수들의 집합 N에 대하여, 집합 A를 다음과 같이 정의한다.

 

$$A = \left\{(x,y) | y^{2} - xy - x^{2} = \pm1, x,y \in N \right\}$$

 

그러면 A의 임의의 두 원소 $(x_{1}, y_{1}), (x_{2}, y_{2})$에 대하여, 관계 R을

 

$$ (x_{1},y_{1}) \leq (x_{2},y_{2}) <=> y_{1} \leq y_{2} $$이라고 정의하자.

 

이는 A에서 반대칭성(antisymmetry), 추이성(transitivity), 완전성(totality)를 모두 만족하는 전순서(total order)이다.

 

**반대칭성(antisymmetry)

 

임의의 두 원소 a,b에 대하여 $(a,b) \in R$이고 $(b,a) \in R$이면 a = b이다

 

실제로 $(x_{1},y_{1}) \leq (x_{2},y_{2}) <=> y_{1} \leq y_{2}$이고

 

바꿔서 $(x_{2}, y_{2}) \leq (x_{1}, y_{1}) <=> y_{2} \leq y_{1}$이면,

 

$(x_{1},y_{1}) = (x_{2},y_{2}) <=> y_{1} = y_{2}$라서 반대칭성도 참인듯

 

$x_{1}, x_{2}$가 서로 같은지는 모르는거 아니냐? 이렇게 생각했는데

 

$(x_{1},y_{1}) = (x_{2},y_{2})$인게 $x_{1} = x_{2}$이고 $y_{1} = y_{2}$인거랑은 무관하지

 

왜냐하면 $(x_{1},y_{1}) = (x_{2},y_{2}) => x_{1} = x_{2} , y_{1} = y_{2}$라고 정의한적이 없기때문이다

 

 

 

---------------------------------------------------------------------------------------------------------

 

**추이성(transitivity)

 

임의의 두 원소 a,b에 대하여 $(a,b) \in R$일때, $(b,c) \in R$이면, $(a,c) \in R$

 

이건 너무 자명하다

 

$(x_{1},y_{1}) \leq (x_{2}, y_{2}) <=> y_{1} \leq y_{2}$이고 

 

$(x_{2},y_{2}) \leq (x_{3}, y_{3}) <=> y_{2} \leq y_{3}$이면...

 

$(x_{1}, y_{1}) \leq (x_{3},y_{3}) <=> y_{1} \leq y_{3}$인건 바로 보인다

 

------------------------------------------------------------------------------------------------------------------

 

**반사성(reflexive)

 

모든 $a \in A$에 대하여 $(a,a) \in R$을 만족한다.

 

즉, $(x_{1},y_{1}) \leq (x_{1},y_{1}) <=> y_{1} \leq y_{1}$으로 자명하므로 관계 R은 항상 반사관계이다.

 

 

**완전성(totality)

 

임의의 $a,b \in A$에 대하여 $(a,b) \in R$이거나 $(b,a) \in R$이다.

 

즉, 관계 R은 다음 2가지 중 하나만 가능하다

 

$(x_{1},y_{1}) \leq (x_{2}, y_{2}) <=> y_{1} \leq y_{2}$

 

$(x_{2}, y_{2}) \leq (x_{1},y_{1}) <=> y_{2} \leq y_{1}$

 

https://ko.wikipedia.org/wiki/%EC%A0%84%EC%88%9C%EC%84%9C_%EC%A7%91%ED%95%A9

전순서 집합 - 위키백과, 우리 모두의 백과사전

 

https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84_%EA%B4%80%EA%B3%84

완전 관계 - 위키백과, 우리 모두의 백과사전

 

 

https://ko.wikipedia.org/wiki/%EB%B0%98%EC%82%AC%EA%B4%80%EA%B3%84

반사관계 - 위키백과, 우리 모두의 백과사전

 

https://jesus-never-fail.tistory.com/22

관계(Relations) / 관계의 특징(Relations and their properties)

 

 

대충 살펴보긴했는데... 맞게 살펴본건지.. 중요한건 아니니까

 

-----------------------------------------------------------------------------------------------------------------------------------

 

 

이제 증명 이어서...

 

집합 A의 임의의 원소 (x,y)에 대하여 x,y가 인접한 두 피보나치 수(x < y)임을 수학적 귀납법으로 보인다.

 

(x,y) = (0,1)인 경우 $y^{2} - xy - x^{2} = 1$이고  $x = F_{0}, y = F_{1}$으로 자명하다.

 

(x,y) = (1,1)인 경우 $y^{2} - xy - x^{2} = -1$이고 $x = F_{1}, y = F_{2}$로 자명하다.

 

이제는 (x,y)가 (0,1), (1,1)이 아니라고 가정하고, (x,y)보다 작은 모든 $(u,v) \in A$에 대하여, 주어진 명제가 성립한다고 가정하자.

 

즉 "$(u,v) \leq (x,y)$이고 $(u,v) \in A$에 대하여 $v^{2} - uv - u^{2} = \pm1$를 만족하면 u,v는 인접한 피보나치 수이다."가 참이다.

 

원소 (y-x, x)를 생각해보면,  x < y이므로 y - x와 x는 음이 아닌 정수 N에 속하는 것은 자명하다.

 

또한, $$y^{2} - xy - x^{2} = x^{2} - (y-x)x - (y-x)^{2} = x^{2} + xy - y^{2} = -(y^{2} - xy - x^{2}) = \pm1$$이다.

 

왜냐하면 $(x,y) \in A$이기 때문에, $y^{2} - xy - x^{2} = \pm1$이다.

 

따라서, $(x,y) \in A$이면, $(y-x,x) \in A$이다.

 

그런데, $x < y$이므로, 관계 R에 따라 $(y-x,x) < (x,y)$이다.

 

그러므로, 가정에 의해 $(y-x,x) < (x,y)$이고 y-x = u, x = v로 치환하면,

 

$v^{2} - uv - u^{2} = \pm1$이므로 $u = y-x, v = x$는 인접한 피보나치 수이다.

 

따라서 $y-x = F_{k}, x = F_{k+1}$인 적당한 k가 존재한다.

 

그런데 두 수의 합 $y = (y-x) + x = F_{k} + F_{k+1} = F_{k+2}$이고, $x = F_{k+1}$, $y = F_{k+2}$이다.

 

그러므로, 수학적 귀납법에 의해 $y^{2} - xy - x^{2} = \pm1$이면, x,y는 인접한 피보나치 수이다.

 

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

8. 본 명제 증명

 

1) 음이 아닌 정수 k가 완전제곱수일 필요충분조건은 $\sqrt{k}$가 정수이다.

 

2) 방정식 $y^{2} - xy - x^{2} = \pm1$을 y에 관해 정리하면, $$y = \frac{x \pm \sqrt{x^{2}+4(x^{2}\pm1)}}{2}$$

 

y는 음이 아닌 정수이므로, 위 y에 대한 해에서 음인 경우를 제외하면,

 

$$y = \frac{1}{2} (x + \sqrt{5x^{2} \pm 4})$$

 

 

8-1) 증명1 (=>)

 

x가 피보나치 수라고 가정하자. 적당한 정수 n이 존재해서 $x = F_{n}$이다.

 

인접한 피보나치 수 $y = F_{n+1}$와 함께 보조정리2에 의해 $y^{2} - xy - x^{2} = \pm1$을 만족한다.

 

이 방정식을 정리하면 y는 음이 아닌 정수이므로,

 

$$y = \frac{1}{2} (x + \sqrt{5x^{2} \pm 4})$$이다.

 

여기서 x,y가 정수이므로 $\sqrt{5x^{2}\pm4}$가 정수여야한다.

 

그러므로, x가 피보나치 수라면, $5x^{2}\pm4$가 완전제곱수여야 $\sqrt{5x^{2}\pm4}$가 정수이다.

 

 

8-2) 증명2(<=)

 

이제 반대로 $5x^{2}\pm4$가 완전제곱수라고 가정하자. 그러므로 $\sqrt{5x^{2}\pm4}$가 정수이다.

 

그런데 x는 정수이므로 언제나 짝수이거나 홀수이다.

 

-------------------------------------------------------------------------------------------------------------------------------

 

**보조정리

 

완전제곱수 n이 짝수이면 $\sqrt{n}$도 짝수이다.

 

반대로 n이 홀수이면 $\sqrt{n}$도 홀수이다.

 

증명) 

 

대우명제 $\sqrt{n}$이 홀수이면, n이 홀수임을 보인다.

 

$\sqrt{n} = (2k+1)^{2} = 4k^{2} + 4k + 1$이므로,  제곱하면 홀수가 된다.

 

반대로 $\sqrt{n}$이 짝수이면, n이 짝수임을 보인다.

 

$\sqrt{n} = (2k)^{2} = 4k^{2}$이므로, 제곱하면 짝수이다.

 

따라서 명제가 참이다

 

-------------------------------------------------------------------------------------------------------------------------------

 

1) x가 짝수라고 가정해보자.

 

$x = 2n$이고, 그래서 $5x^{2}\pm4 = 20n^{2}\pm4$이므로 $5x^{2}\pm4$도 짝수이다. 

 

보조정리에 의해 $\sqrt{5x^{2}\pm4}$도 짝수이다.

 

그래서 두 짝수의 합 $x + \sqrt{5x^{2} \pm 4}$도 짝수이고, 이는 2의 배수이다.

 

그러므로 $y = \frac{1}{2} ( x + \sqrt{5x^{2} \pm 4} )$에서 y가 음이 아닌 정수가 된다.

 

 

2) 이번에는 x가 홀수라고 가정해보자.

 

$x = 2n+1$이고, 그래서 $5x^{2}+4 = 20n^{2} + 20n + 9$ 혹은 $5x^{2} - 4 = 20n^{2} + 20n +1$이다.

 

그러므로 $5x^{2} \pm 4$는 홀수이다.

 

보조정리에 의해 $\sqrt{5x^{2}\pm4}$도 홀수이다.

 

그래서 두 홀수의 합 $x + \sqrt{5x^{2}\pm4}$는 짝수이고, 2의 배수이다.

 

따라서 $y = \frac{1}{2} (x + \sqrt{5x^{2} \pm 4})$에서 y가 음이 아닌 정수가 된다.

 

모든 경우에서 $5x^{2}\pm4$가 완전제곱수인 정수 x에 대해 $y = \frac{1}{2}(x+\sqrt{5x^{2}\pm4})$는 음이 아닌 정수이다.

 

그리고 x,y는 방정식 $y^{2} - xy - x^{2} = \pm1$의 해이다.

 

보조정리2에 의해 x,y는 인접한 두 피보나치 수이다. 

 

따라서 $5x^{2}\pm4$가 완전제곱수이면 x는 피보나치 수이다.

 

 

9. 구현 예시

 

완전제곱수를 판단하는 is_perfect와 이를 이용해 피보나치 수임을 판단하는 is_fib를 작성

 

def is_perfect(n):
    
    if int((n**(1/2)))**2 == n:
        
        return True
    
    return False

def is_fib(n):
    
    x = 5*n*n+4
    y = 5*n*n-4
    
    if is_perfect(x) or is_perfect(y):
        
        return True
    
    return False

 

 

따라가긴 했는데... 이게 맞나