#slides 페리 수열 (Farey Sequence) - 바보 셈(freshman sum)을 한 원소가 다음에 등장하는 재미있는 수열

less than 1 minute read

프로젝트 오일러(Project Euler) 문제를 풀다가 알게 됐다. 바보 셈(freshman sum)을 한 원소가 다음에 등장하는 재미있는 수열.

페리 수열 길이를 바로 구할 때, 사용하는 Euler’s totient function. 증명을 공부하다 보니 Chinese Remainder Theorem (중국인의 나머지 정리)를 알아야 해. 이걸 또 증명하다보니 Extended Euclidean algorithm (확장된 유클리드 호제법)을 공부해야 한다. 휴 더 깊어졌으면 위험할 뻔했어. 이해하느라 꽤 시간을 썼다. 하나씩 블로그에 올릴 예정.