이집트 분수 계산기

남은 분수보다 크지 않은 가장 큰 단위분수를 계속 떼어 내면 됩니다. n/d에서 떼어 낼 것은 1/⌈d/n⌉이고, 남는 것은 (n·⌈d/n⌉ − d)/(d·⌈d/n⌉)입니다. 이것을 남는 분수가 0이 될 때까지 되풀이합니다. 피보나치가 1202년에 쓴 방법이라 피보나치–실베스터 알고리즘이라고 합니다.

반드시 끝납니다. 한 항을 뗄 때마다 남은 분수의 «분자»가 반드시 줄어들기 때문입니다(n·⌈d/n⌉ − d < n). 자연수는 계속 줄어들 수 없으니 언젠가 분자가 1이 되고, 그때 단위분수 하나로 마무리됩니다.

한 항을 뗄 때마다 남은 분수의 분모가 곱해지기 때문입니다. 자릿수가 거의 두 배씩 늘어, 5/121은 네 번째 항의 분모가 이미 8,739억을 넘고 다섯 번째는 25자리입니다. 그래서 이 계산기는 BigInt로 계산합니다 — 배정밀도 실수로는 몇 항 만에 값이 어긋납니다.

아닙니다. 5/121은 탐욕으로 다섯 항이 되지만 1/33 + 1/121 + 1/363처럼 세 항짜리 답이 있습니다. 탐욕은 «지금 뗄 수 있는 가장 큰 것»만 보므로 뒤를 내다보지 못합니다. 가장 짧은 분해를 빠르게 찾는 방법은 알려져 있지 않아, 이 계산기는 작은 범위만 훑어 더 짧은 것이 있으면 보여 줍니다.

분명한 이유는 알려져 있지 않지만, 실제로 나누기 좋았다는 설명이 있습니다. 빵 n개를 m명이 나눌 때 «각자 1/2씩 받고 남은 것을 1/6씩»처럼 자르면 실제 분배가 쉬워집니다. 2/3을 빼면 모든 분수를 단위분수의 합으로 적었고, 같은 단위분수를 두 번 쓰지 않았습니다.

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