Egyptian fractions
Tonight's idea
A unit fraction has a 1 on top: \(\tfrac12, \tfrac13, \tfrac1{24}\). Egyptian scribes, more than 3,500 years ago, wrote fractions as sums of different unit fractions. Not \(\tfrac27 = \tfrac17 + \tfrac17\), but \(\tfrac27 = \tfrac14 + \tfrac1{28}\). It is a good way to share: to split 5 loaves among 6 people, \(\tfrac56 = \tfrac12 + \tfrac13\) says give everyone half a loaf, then a third.
Fibonacci, in 1202, gave a method that always works. Greedy: take the largest unit fraction that fits, subtract it, and repeat on what is left. For \(\tfrac4{13}\): since \(13 \div 4 = 3.25\), \(\tfrac13\) is too big and \(\tfrac14\) fits. In general, the first denominator is \(b \div a\) rounded up.
Why must it stop? Watch the numerators. Suppose \(\tfrac1d\) is the biggest unit fraction that fits under \(\tfrac ab\). Then \(\tfrac1{d-1}\) was too big: \(\tfrac ab \lt \tfrac1{d-1}\), so \(a(d-1) \lt b\), so \(ad - b \lt a\). The remainder is
\(\dfrac ab - \dfrac1d = \dfrac{ad - b}{bd}\), and its numerator \(ad - b\) is smaller than \(a\).
Each step makes the numerator a smaller whole number, so after at most \(a\) steps it reaches 1 and the process ends. The denominators never repeat: each remainder is smaller than the unit fraction just removed, so the next denominator is larger.
Watch one: \(\tfrac{4}{13}\)
\(13 \div 4 = 3.25\), round up to 4. Subtract: \(\tfrac4{13} - \tfrac14 = \tfrac{16 - 13}{52} = \tfrac3{52}\). Now \(52 \div 3 = 17.3\), round up to 18. Subtract: \(\tfrac3{52} - \tfrac1{18} = \tfrac{54 - 52}{936} = \tfrac{2}{936} = \tfrac1{468}\). That is a unit fraction, so stop:
\[\tfrac{4}{13} = \tfrac14 + \tfrac1{18} + \tfrac1{468}.\]
The numerators ran \(4, 3, 1\): falling, as promised. Check by putting everything over 468: \(117 + 26 + 1 = 144\), and \(\tfrac{144}{468} = \tfrac{4}{13}\).
Your turn
- Run the greedy method on \(\tfrac23\), \(\tfrac34\) and \(\tfrac56\).
- Run it on \(\tfrac{9}{20}\) and on \(\tfrac37\). Write down the numerator at each step and check that it falls.
- (a) Check that \(\tfrac16 = \tfrac17 + \tfrac1{42}\), then show that \(\tfrac1n = \tfrac1{n+1} + \tfrac1{n(n+1)}\) for every \(n\) by adding the right-hand side. (b) Use it to write \(\tfrac27 = \tfrac17 + \tfrac17\) as a sum of three different unit fractions. (c) Why does this show every fraction has infinitely many Egyptian forms?
- Greedy is not always shortest. For \(\tfrac4{17}\) it gives \(\tfrac15 + \tfrac1{29} + \tfrac1{1233} + \tfrac1{3039345}\). (a) Explain why \(\tfrac15\) is the first term. (b) After it, \(\tfrac4{17} - \tfrac15 = \tfrac3{85}\). Find two different unit fractions that add to \(\tfrac3{85}\), giving a three-term answer. Hint: write \(\tfrac{3}{85}\) with a bigger denominator so that the numerator is one more than a divisor of the denominator.
Stretch: beating the greedy method badly
Greedy turns \(\tfrac5{121}\) into five unit fractions, and the last denominator has 25 digits. Find three different unit fractions that add to \(\tfrac5{121}\). Hint: \(363 = 3 \times 121\), and 363 has small divisors that add up nicely.
Answers
- \(\tfrac23 = \tfrac12 + \tfrac16\). \(\tfrac34 = \tfrac12 + \tfrac14\). \(\tfrac56 = \tfrac12 + \tfrac13\).
- \(\tfrac9{20}\): \(20 \div 9 = 2.2\), so \(\tfrac13\); remainder \(\tfrac{7}{60}\); \(60 \div 7 = 8.6\), so \(\tfrac19\); remainder \(\tfrac{1}{180}\). So \(\tfrac9{20} = \tfrac13 + \tfrac19 + \tfrac1{180}\), numerators \(9, 7, 1\). \(\tfrac37\): \(\tfrac13\), remainder \(\tfrac2{21}\); \(\tfrac1{11}\), remainder \(\tfrac1{231}\). So \(\tfrac37 = \tfrac13 + \tfrac1{11} + \tfrac1{231}\), numerators \(3, 2, 1\).
- (a) \(\tfrac17 + \tfrac1{42} = \tfrac{6 + 1}{42} = \tfrac16\). In general \(\tfrac1{n+1} + \tfrac1{n(n+1)} = \tfrac{n + 1}{n(n+1)} = \tfrac1n\). (b) Split one of the sevenths: \(\tfrac27 = \tfrac17 + \tfrac18 + \tfrac1{56}\). (c) Any unit fraction in an answer can be split into two new ones, so you can always make a longer answer; there is no end to them.
- (a) \(17 \div 4 = 4.25\), rounded up is 5; \(\tfrac14\) would be more than \(\tfrac4{17}\) since \(4 \times 4 = 16 \lt 17\). (b) \(\tfrac3{85} = \tfrac6{170} = \tfrac5{170} + \tfrac1{170} = \tfrac1{34} + \tfrac1{170}\). So \(\tfrac4{17} = \tfrac15 + \tfrac1{34} + \tfrac1{170}\). (Another: \(\tfrac3{85} = \tfrac{18}{510} = \tfrac1{30} + \tfrac1{510}\).)
Stretch. \(\tfrac5{121} = \tfrac{15}{363}\), and \(15 = 11 + 3 + 1\), all divisors of 363. So \(\tfrac5{121} = \tfrac{11}{363} + \tfrac{3}{363} + \tfrac{1}{363} = \tfrac1{33} + \tfrac1{121} + \tfrac1{363}\). Greedy always finishes, but it is not always clever.