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

1. 페리 수열의 대칭성(symmetry)

 

n번째 페리 수열의 분수 $\frac{a}{b}$에 대해 생각해보자.

 

먼저 기약분수이므로 a,b가 서로소이고 0과 1 사이에 있으므로 a < b이다.

 

https://deepdata.tistory.com/1104 

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

 

 

이전에 관찰했던 것처럼 n번째 페리 수열에는 분모가 n 이하인 정수 b에 대하여 b보다 작은 서로소인 모든 정수 a에 대해

 

$\frac{a}{b}$가 있다고 했다.

 

즉 $\frac{a}{b}$가 있다면, b와 서로소인 a가 아닌 어떤 정수 c에 대하여 $\frac{c}{b}$가 있다.

 

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

 

그런데 a < b라 가정하고 a,b가 서로소이면 b-a와 b도 서로소이다.

 

대우를 생각하면 "b-a와 b가 서로소가 아니면, a,b도 서로소가 아니다"

 

b-a와 b가 서로소가 아니라면, 어떤 소수 p에 대하여 b-a = pq, b = pr, q,r은 서로소이다.

 

여기서 a < b이므로 b-a < b이고 그러므로 r > q이다.

 

b - a = pr - a = pq이므로 a = pr - pq = p(r-q)

 

그러므로 a도 p를 소인수로 가진다.

 

즉, a,b가 모두 p를 소인수로 가지므로 a,b는 서로소가 아니다.

 

따라서 b-a와 b가 서로소가 아니면, a,b도 서로소가 아니다.

 

이것의 대우인 "a,b가 서로소이면 b-a와 b도 서로소이다."

 

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

 

이 말은 무슨 뜻인가?

 

n번째 페리수열에 $\frac{a}{b}$가 존재한다면, $\frac{b-a}{b}$가 존재한다.

 

그런데 $\frac{b-a}{b} = 1 - \frac{a}{b}$이다.

 

즉 $\frac{a}{b}$가 존재한다면, $1 - \frac{a}{b}$도 n번째 페리수열에 존재한다. 

 

따라서 n번째 페리수열은 $\frac{1}{2}$를 중심으로 왼쪽, 오른쪽에 $\frac{a}{b}$와 $1 - \frac{a}{b}$가 대칭으로 있는 형태이다.

 

 

 

실제로 6에 대하여 서로소인 1로부터 $\frac{1}{6}$이 있고 이에 대칭인 $\frac{5}{6}$이 있다.

 

5도 마찬가지로 서로소인 1로부터 $\frac{1}{5}$가 있고 이에 대칭인 $\frac{4}{5}$가 있다.

 

서로소인 2로부터 $\frac{2}{5}$가 있고 이에 대칭인 $\frac{3}{5}$가 있다.

 

4도 마찬가지로 서로소인 1로부터 $\frac{1}{4}$가 있고 이에 대칭인 $\frac{3}{4}$가 있다.

 

3도 마찬가지로 서로소인 1로부터 $\frac{1}{3}$이 있고 이에 대칭인 $\frac{2}{3}$이 있다.

 

 

2. 페리 수열의 합

 

n번째 페리수열에 $a_{1}, a_{2}, ... , a_{|F_{n}|}$이 있다고 가정하자.

 

여기서 $|F_{n}|$은 n번째 페리수열의 길이이다.

 

위에서 보인 페리수열의 대칭성으로부터 $1 - a_{1}, 1 - a_{2}, ... 1 - a_{|F_{n}|}$도 n번째 페리수열에 존재한다.

 

즉 두 집합이 서로 동치이다.

 

$$a_{1}, a_{2}, ... , a_{|F_{n}|} = 1 - a_{1}, 1 - a_{2}, ... , 1 - a_{|F_{n}|}$$

 

두 집합이 동치이므로 왼쪽 집합의 모든 원소 합과 오른쪽 집합의 모든 원소 합이 동일하다.

 

S가 n번째 페리수열의 원소 합이라고 한다면,

 

$$S = a_{1} + a_{2} + ... + a_{|F_{n}|} = |F_{n}| - (a_{1} + a_{2} + ... + a_{|F_{n}|})$$

 

그러므로 다음과 같이 정리할 수 있다.

 

$$2 * (a_{1} + a_{2} + ... + a_{|F_{n}|}) = 2S = |F_{n}|$$

 

따라서 $$S = \frac{1}{2}|F_{n}|$$

 

놀랍게도 페리 수열 길이의 절반이 페리 수열 원소의 합과 동일하다.

 

 

 

6번째 페리수열의 길이는 13이다.

 

이들의 합은 대칭끼리 짝지어서 6 + 1/2 = 13/2로 실제로 공식이 맞다.

 

 

3. 분모의 합과 분자의 합의 관계

 

n번째 페리 수열에서 모든 분모 b의 합은 모든 분자 a의 합의 2배이다.

 

$$\sum_{F_{n}}^{} b = 2\sum_{F_{n}}^{} a$$

 

 

증명은 쉽지 않은데 간단하게만 생각해보자.

 

먼저 n 이하의 n과 서로소인 모든 정수의 합은 오일러의 phi함수를 이용해 다음과 같이 구할 수 있다.

 

$$S = \frac{n\varphi(n)}{2}$$

 

귀납법으로 증명할 수 있다는데 언젠가 증명할 수 있다면 해보기로 하고 머리 아프니까 넘어가자

 

https://forthright48.com/sum-of-coprime-numbers-of-integer/

Sum of Co-prime Numbers of an Integer | forthright48

 

 

그러면 n번째 페리수열에는 $\frac{a}{b}$에 대하여 b와 서로소인 모든 a가 있다.

 

그러므로 b의 합은 (b와 서로소인 a의 개수) * b만큼 즉 $\varphi(b)b$이다.

 

$$\sum_{F_{n}}^{} b = \sum_{F_{n}}^{} \varphi(b)b$$

 

이때 b에 대응하는 분자는 b와 서로소인 모든 a이고 이들의 합은 $$\sum_{F_{n}}^{} a = \sum_{F_{n}}^{} \frac{\varphi(b)b}{2}$$

 

위 식에서 양변을 2로 나누고 대입하면 $\sum_{F_{n}}^{} \frac{b}{2} = \sum_{F_{n}}^{} a$

 

따라서, $$\sum_{F_{n}}^{} b = 2\sum_{F_{n}}^{} a$$

 

 

4. 기타

 

n번째 페리수열의 i번째 항의 분모를 $b_{i}$라고 하자.

 

$$\sum_{i=1}^{|F_{n}|} \frac{b_{i}}{b_{i+1}} = \frac{3|F_{n}|-4}{2}$$

 

$$\sum_{i=1}^{|F_{n}|} \frac{1}{b_{i}b_{i+1}} = 1$$

 

증명은 논문하나짜리인데 너무 어려우니 생략

 

 

 

예를 들어만 생각해보자.

 

6번째 페리수열의 길이는 13이다.

 

이때 첫번째 합은 $\frac{1}{6} + \frac{6}{5} + \frac{5}{4} + \frac{4}{3} + \frac{3}{5} + \frac{5}{2} + \frac{2}{5} + \frac{5}{3} + \frac{3}{4} + \frac{4}{5} + \frac{5}{6} + \frac{6}{1} = \frac{35}{2}$

 

실제로 3*13 - 4 = 35이므로 맞다.

 

두번째 합은... $\frac{1}{6} + \frac{1}{30} + \frac{1}{20} + \frac{1}{12} + \frac{1}{15} + \frac{1}{10} + \frac{1}{10} + \frac{1}{15} + \frac{1}{12} + \frac{1}{20} + \frac{1}{30} + \frac{1}{6} = 1$이다.

 

 

10438번: 페리 수열의 합 (acmicpc.net)

10438번: 페리 수열의 합