페리 수열(farey sequence) 조금 더 깊게3 - 주어진 수의 다음 항을 찾는 방법 -

1. n번째 페리수열의 i번째 항이 주어질 때 i+1번째 항을 찾는 방법

 

n번째 페리 수열의 한 원소 $\frac{a}{b}$가 주어졌다고 하자.

 

이 수보다 크면서 이웃한 바로 다음 항 원소를 구할 수 있을까?

 

예를 들어 $\frac{2}{5}$ 바로 다음 항에 존재하는 분모가 6이하인 기약분수를 찾으라한다면, $\frac{1}{2}$가 답이다.

 

 

 

n번째 페리수열에서 $\frac{a}{b}$와 $\frac{c}{d}$가 서로 이웃하다면, bc - ad = 1이다.

 

이때 b와 a를 알기 때문에 bx - ay = 1을 만족하는 서로소인 정수 x,y를 구하는 문제이다.

 

https://deepdata.tistory.com/576 

확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

 

확장 유클리드 알고리즘을 이용하면 O(logN)에 구할 수 있다.

 

페리수열이므로 a,b는 무조건 서로소이기 때문에 확장 유클리드 알고리즘을 적용하여 x,y의 특수해를 일단 구하기만 하면 된다.

 

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0

    x = 0
    y = 1

    while b != 0:
        
        q,r = a//b, a%b
        a,b = b,r

        before_x,x = x, before_x - x*q
        before_y,y = y, before_y - y*q
    
    return a,before_x, before_y

#ax+by=1을 만족하는 x,y를 구하는 확장 유클리드 알고리즘
#gcd(a,b),x,y가 나온다.
#bc-ad=1을 만족하는 c,d를 구해야하므로 x >> d, y >> c에 대응
gcd,d,c = extended_gcd(a,b)

 

 

이렇게 했을때, ax+by = 1을 만족하는 x,y를 구하는데..

 

bc - ad = 1을 만족하는 c,d를 찾기 위해 x는 d에 대응시키고 y는 c에 대응시킨다.

 

물론 문제는 이 c,d가 $\frac{a}{b}$ 다음의 $\frac{c}{d}$인지는 알수없다.

 

그걸 만족할려면 분모 d가 n 이하여야한다.

 

베주 항등식에서 특수해를 알면 적절한 산술연산으로 일반해를 구할 수 있다.

 

$$ad + bc = 1$$

 

$$ad + bc - ab + ba = 1$$

 

$$a(d-b) + b(c+a) = 1$$

 

d,c가 ax+by  = 1을 만족시킨다면, d - b, c + a도 ax+by = 1을 만족시킨다.

 

이를 k번 반복하면 d - kb, c + ka도 ax + by = 1을 만족시킨다.

 

그래서 d - kb <= n이고 c+ka, d-kb가 서로소를 만족시키는 k를 찾으면 O(k)에 찾을 수 있다.

 

하지만 k 조차도 매우 클 수 있다.

 

이때, d - kb >> -d'에 대응시키고 c + ka >> c'에 대응시키면 bc' - ad' = 1이라는 식이 성립한다.

 

이때, d' <= n이므로 -d + kb <= n이다.

 

부등식을 정리하면 $$ k <= \frac{n + d}{b}$$

 

여기서 d는 확장 유클리드 알고리즘으로 구한 특수해이고, n은 n번째 페리수열의 n이고 b는 $\frac{a}{b}$의 분모 b이다.

 

n,d,b를 알고있으므로 (n+d)//b로 가장 큰 k를 O(1)에 바로 찾을 수 있다.

 

따라서 $$ c' = c + \left \lfloor \frac{n+d}{b} \right \rfloor a, d' = -d +\left \lfloor \frac{n+d}{b} \right \rfloor b$$

 

을 만족하는 c',d'을 찾으면 $\frac{c'}{d'}$이 i+1번째 항이다.

 

#bc-ad=1
gcd,d,c = extended_gcd(a,b)

#b(c+a)+a(d-b) = 1
#general solution (c+ak, d-bk)
#-d+bk <= n
#bk <= n+d
#k <= (n+d)//b

k = (n+d)//b
c += (a*k)
d = -d + b*k

 

 

 

2. n번째 페리수열의 i번째 항, i+1번째 항이 주어질 때, i+2번째 항을 찾는 방법

 

n번째 페리수열의 i번째 항, i+1번째 항이 $\frac{a}{b} < \frac{c}{d}$로 주어진다면..

 

그 다음 항인 i+2번째 항은 어떻게 찾을 수 있을까?

 

 

 

예를 들어 $\frac{1}{2}, \frac{3}{5}$가 주어질 때, 분모가 6이하이면서 0이상 1이하인 기약분수를 찾아야한다면

 

$\frac{2}{3}$이 정답이다.

 

물론 6번째 페리수열의 $\frac{c}{d}$ 다음 항을 찾는 문제이므로 확장 유클리드 알고리즘으로 O(logN)에 해결할 수 있다.

 

그런데 이전의 두 항을 알고있다면 그 다음 항은 산술연산으로 O(1)에 바로 구할 수 있다.

 

$\frac{a}{b}, \frac{c}{d}$ 다음 항인 i+2번째 항이 $\frac{p}{q}$라고 하자.

 

$\frac{a}{b}, \frac{c}{d}, \frac{p}{q}$는 페리수열의 연속된 세 항이다.

 

그러므로 $$\frac{c}{d} = \frac{a+p}{b+q}$$

 

c = a+p, d = b+q일수도 있지만, 어떤 정수 k에 대하여 $$\frac{kc}{kd} = \frac{a+p}{b+q}$$도 가능하다.

 

즉 kc = (a+p), kd = (b+q)이고 $$p = kc - a, q = kd - b$$

 

그런데 분모 q는 n 이하여야하므로, q = kd - b <= n에서 $$k <= \frac{n + b}{d}$$

 

가장 큰 k를 $\frac{n+b}{d}$로 바로 찾을 수 있으므로 

 

$$p = \left \lfloor \frac{n+b}{d} \right \rfloor c - a, q = \left \lfloor \frac{n+b}{d} \right \rfloor d - b$$로 구해지는 $\frac{p}{q}$가 i+2번째 항이다.

 

이를 반복해서 i번째, i+1번째 항을 안다면 a >= 2에서 i+a번째 항을 찾을 수 있다.

 

주의할 점은 페리수열의 끝 항은 $\frac{1}{1}$이다.

 

6번째 페리수열의 2번째, 3번째항 $\frac{1}{6}, \frac{1}{5}$를 알때, 100번째 항을 찾으라고 한다면?

 

100번째 항은 존재하지 않는다.

 

반복을하는데 반복문이 끝나기 전에 p = 1, q = 1이 나온다면 원하는 목표의 항은 존재하지 않는 것이다.

 

#a,b가 i번째
#c,d가 i+1번째
no = False

for k in range(2,j+1):

    x = (n+b)//d

    p,q = x*c-a,x*d-b #p,q가 i+k번째

    if p == 1 and q == 1 and k < j:

        no = True
        break

    a,b = c,d
    c,d = p,q

if no:
    print(-1)

else:
    print(p,q)