페리 수열(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) 구현해..