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

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

페리 수열(farey sequence) 조금 더 깊게2 - 페리 수열의 대칭성과 페리 수열의 합 -

1. 페리 수열의 대칭성(symmetry) n번째 페리 수열의 분수 $\frac{a}{b}$에 대해 생각해보자. 먼저 기약분수이므로 a,b가 서로소이고 0과 1 사이에 있으므로 a < b이다. https://deepdata.tistory.com/1104 페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 - 1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. deepdata.tistory.com 이전에 관찰했던 것처럼 n번째 페리 수열에는 분모가 n 이하인 정수 b에 대하여 b보다 작은 서로소인 모든 정수 a에 대해 $\..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 -

1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. 이때, 0과 1 사이에 존재하는 기약분수이므로 a < b이다. 그러므로 n번째 페리수열에 존재하는 기약분수들은 다음과 같이 만들수도 있다. "양 끝에는 $\frac{0}{1}, \frac{1}{1}$이 있고, 분모가 b = 2,3,4,5,..,n에 대하여 분자는 k보다 작으면서 서로소인 모든 정수 a에 대해 $\frac{a}{b}$를 나열한 것이다." 예를 들어, 5번째 페리 수열을 보자. 분모가 2이면 2와 서로소인 1에 대해 $\frac{1}{2}$ 분모가 3이면 3과 서로소인 1,2에 대해..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

페리 수열(Farey sequence) 문제를 해결하기 위해 알아야 할 기본 성질 간단하게

1. n번째 페리 수열 0부터 1사이의 분모가 n이하인 모든 기약분수를 오름차순으로 나열한 수열 n = 1부터 8까지의 경우를 나열하면 다음과 같다. 2. 두 분수 사이에 있는 분수 theorem1) 0과 1 사이의 두 분수 $\frac{a}{b}$와 $\frac{c}{d}$에 대하여 $\frac{a}{b} 0$이다. 그런데 $$\frac{a+c}..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms