파레이 수열·스턴–브로코 계산기

분모가 n 이하인 0~1 사이의 기약분수를 크기순으로 모두 늘어놓은 것입니다. F(4)라면 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1의 일곱 항입니다. 분모가 커질수록 새 분수가 사이사이에 끼어들며 촘촘해집니다.

이웃한 a/b < c/d는 언제나 bc − ad = 1을 만족합니다. 1/3과 1/2이라면 3×1 − 1×2 = 1입니다. 이 성질 덕분에 다음 항을 나눗셈 한 번으로 바로 낼 수 있어, 분수를 전부 만들어 정렬할 필요가 없습니다.

두 분수의 분자끼리, 분모끼리 더한 (a+c)/(b+d)입니다. 분수 덧셈으로는 틀린 계산이지만, 그 값이 언제나 두 분수 사이에 들어옵니다. 이웃한 두 항의 중항은 F(b+d)에서 정확히 그 자리에 새로 나타나고, 이웃 규칙 덕분에 언제나 기약분수입니다.

1 + φ(1) + φ(2) + … + φ(n)입니다. 분모가 정확히 k인 기약분수가 오일러 φ(k)개이기 때문입니다(0/1은 분모 1로 셉니다). 그래서 n을 하나 늘릴 때마다 정확히 φ(n)개가 새로 끼어들고, 전체 개수는 대략 3n²/π²에 가깝습니다.

그 소수를 파레이 수열 안에 끼워 넣어 양옆 이웃 중 가까운 쪽을 고르면 됩니다. 스턴–브로코 트리를 타고 내려가는 것이 바로 그 절차로, 지금 구간의 중항을 만들어 목표보다 크면 왼쪽, 작으면 오른쪽으로 갑니다. π를 분모 7 이하로 재면 22/7, 113 이하로 재면 355/113이 나옵니다.

겹치지만 같지는 않습니다. 연분수를 잘라 만든 수렴분수는 모두 최적 근사이지만, 최적 근사가 전부 수렴분수인 것은 아닙니다. π를 분모 100 이하로 재면 311/99가 나오는데 이것은 수렴분수가 아니라 22/7과 355/113 사이에 낀 반수렴분수입니다. 분모 상한이 정해져 있을 때는 파레이 쪽이 곧바로 답합니다.

π와의 차이가 약 2.7×10⁻⁷로, 소수점 여섯째 자리까지 맞습니다. 분모가 113밖에 안 되는데 이만큼 정확한 것은 π의 연분수에 292라는 큰 항이 이어지기 때문입니다 — 큰 항 앞의 근사는 유난히 잘 맞습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.