#unit fractions

[mathwithicecream]

Ancient Egyptian Fractions

Note:  This post uses \(\LaTeX\), so it will likely look nicer viewed on my blog in browser.

Last time, we learned how the ancient Egyptians divided using as an example 351 divided by 13.  This was a somewhat convenient choice because 13 divides neatly into 351.  However, what if we had chosen numbers that were not nice, 358 divided by 13, for instance?

Knowing that \(351/13 = 27\), it isn’t difficult to see that \(358/13 = 27\frac{7}{13}\), but at this point an ancient Egyptian scribe would become confused.

You see, the ancient Egyptians viewed fractions as each having their own indivisible form or identity.  For example, there was the half, the third, the fourth, etc.  There was not, however, \(\frac{2}{3}\), because that would be two of the third, and how could the third be in the same place twice?

Instead of grappling with the existential terror of the parts suddenly gaining doppelgangers, the ancient Egyptians only represented fractions as the sum of unequal unit fractions (i.e. fractions with 1 in the numerator).  For example, $$\frac{3}{4} = \frac{1}{2} + \frac{1}{4}$$ $$\frac{2}{3} = \frac{1}{2} + \frac{1}{6}$$ $$\frac{7}{11} = \frac{1}{2} + \frac{1}{11} + \frac{1}{22}$$

Note that it is easy to show that this representation is not unique for any fraction (even for a fraction that is already unit!).  Another note is that what we’re doing is somewhat cheating, because we’re just taking modern notation and translating it into a form that an ancient Egyptian scribe might understand.  Let’s not think about that, too much, okay?  Instead, let’s look at some general algorithms of finding unit fraction representations!

Method 1:  The “Greedy” Algorithm

In this method, we find the largest unit fraction less than our given fraction and subtract it from the given fraction.  If the result is a unit fraction, stop.  Otherwise, that result becomes the next unit fraction.

Example 1.1:  \(\frac{3}{4}\).

The largest unit fraction less that \(\frac{3}{4}\) is \(\frac{1}{2}\), so we write $$\frac{3}{4} = \frac{1}{2} + \left(\frac{3}{4} - \frac{1}{2}\right) = \frac{1}{2} + \frac{1}{4}.$$

Example 1.2:  \(\frac{3}{7}\)

The largest unit fraction less than \(\frac{3}{7}\) is \(\frac{1}{3}\), so we write $$\frac{3}{7} = \frac{1}{3} + \left(\frac{3}{7} - \frac{1}{3}\right) = \frac{1}{3} + \frac{2}{21}.$$  The largest unit fraction less than \(\frac{2}{21}\) is \(\frac{1}{11}\), so we write $$\frac{2}{21} = \frac{1}{11} + \left(\frac{2}{21} - \frac{1}{11}\right) = \frac{1}{11} + \frac{1}{231}.$$  Then, $$\frac{3}{7} = \frac{1}{3} + \frac{1}{11} + \frac{1}{231}.$$

This algorithm seems to work relatively well, but as we saw in Example 1.2, the denominator can become somewhat unwieldy for relatively simple non-unit fractions.  Another potential issue would occur if there was a fraction such that the “Greedy” Algorithm didn’t terminate (i.e. returned an infinite series of unit fractions).

Exercise 1:

Does the “Greedy” Algorithm always terminate?  If not, give an example.  If so, prove it.  (Answer under the cut)

Method 2:  The “Splitting” Algorithm

Wouldn’t it be nice to not need to worry about whether our algorithm terminated or not?  Let me introduce you to the “Splitting” Algorithm, which makes use of the fact that for any positive integer \(n\), $$\frac{1}{n} = \frac{1}{n+1} + \frac{1}{n(n+1)}.$$  Let’s illustrate this method with an example!

Example 2.1:  \(\frac{2}{3}\)

$$\frac{2}{3} = \frac{1}{3} + \frac{1}{3} = \frac{1}{3} + \frac{1}{3+1} + \frac{1}{3(3+1)} = \frac{1}{3} + \frac{1}{4} + \frac{1}{12}.$$

Wasn’t that fast an easy?  It’s simple to see that this algorithm will always terminate, and we didn’t need to go to all the trouble of finding largest unit fractions or subtracting fractions or any of the other headaches from the “Greedy” Algorithm.  Don’t get too excited, though.  Let’s try one more example first.

Example 2.2:  \(\frac{4}{7}\)

We write out $$\frac{4}{7} = \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} = \frac{1}{7} + \frac{1}{8} + \frac{1}{56} + \frac{1}{8} + \frac{1}{56} + \frac{1}{8} + \frac{1}{56},$$

and Yikes.  If you would like to go through the process of finding this expansion using only the splitting algorithm, be my guest.  If you’re sane, the answer is $$\frac{1}{7} + \frac{1}{8} + \frac{1}{56} + \frac{1}{9} + \frac{1}{72} + \frac{1}{57} + \frac{1}{3192} + \frac{1}{10} + \frac{1}{90} + \frac{1}{73} + \frac{1}{5256} + \frac{1}{58} + \frac{1}{3306} + \frac{1}{3193} + \frac{1}{10192056}.$$  Meanwhile, using the “Greedy” Algorithm, $$\frac{4}{7} = \frac{1}{2} + \frac{1}{14}.$$

In fact, if you don’t take advantage of obvious reductions, it isn’t difficult to show that given a fraction with numerator \(m\), the “Splitting” Algorithm would return the sum of \(2^{m}-1\) distinct unit fractions.

So, which method is better?  Depends on the situation.  In fact, in most cases the best method is probably some combination involving simplification.

A better question:  What does this have to do with modern mathematics?  I have no idea--it’s just interesting!  It leads to a lot of wild questions like “Given any fraction, how can it be represented by the sum of the fewest number of unit fractions?” or “How many ways are there to write a given fraction as the sum of \(n\) distinct unit fractions?”

Anyway, I hope you enjoyed.  This will probably be the last post in my Ancient Egyptian Mathematics series, and I want to thank everyone who read and gave feedback along the way.  Until next time!

Answer to Exercise 1

In fact, the “Greedy” Algorithm will always terminate!  Here is a proof:

Take any fraction \(\frac{a}{b},\,(a,b\in\mathbb{Z}_{>0},\,a<b,\,a\neq1)\), and let \(\frac{1}{c}\) be the largest unit fraction such that \(\frac{1}{c} < \frac{a}{b}\).  If this is true, we must have \(\frac{1}{c-1} > \frac{a}{b}\).  Taking the reciprocals, we have \(c > \frac{b}{a}\) and \(c < \frac{a + b}{a}\).

Now, when we take $$\frac{a}{b} = \frac{1}{c} + \left(\frac{a}{b} - \frac{1}{c}\right) = \frac{1}{c} + \frac{ac-b}{bc},$$ we want to show that $$ac-b < a.$$

This is routine, as $$ac-b < a\frac{a+b}{a}-b = a.$$

Then, since \(a\) is finite and the numerator of the next fraction is strictly less than \(a\), the “Greedy” Algorithm must terminate.

Other Posts in this Series:

[Multiplication][Division][Fractions][ref]

[eduusa]

Unit Fractions: Definition, Examples

According to Merriam-Webster, a unit fraction is a fraction whose numerator is unity and whose denominator is an integer. The look-up popularity for this word is in the top 26% of words. The word unit fraction is placed near the words unit factor and unit heater. 

Unit fractions are rational numbers. 1/25, 1/100, 1/200, and many others are all rational numbers. However, the numbers 7/33, 9/10, 67/96, and many others are rational numbers, too, but they are not unit fractions. 

[paulspuzzles-blog]

Solution #2a

As noted in the original Solution #2, there are many different solutions to this one.  You’ll find some of them below the line.

First let’s start with what I’ll call the five “orthodox” solutions that I found last time.  Credit for finding these is shared between Demerine, Viscardius, crow and myself:

These solutions all have certain things in common: the top three rows are all the same, and use the fact that 6 and 28 are perfect numbers - if you add up the factors of a perfect number other than the number itself, you get the number out.  So if you add up the *reciprocals* of those factors, you get 1.  The bottom row is then the row we play around with to find different ways of filling it up.

From here you can choose to mix things up to find other solutions - so for instance, you can shuffle things around a bit to get results like these:

Though so far we haven’t been super adventurous yet.  So far every solution has left us with five blocks left over.  Can we get a solution that leaves fewer blocks left over?  Or perhaps doesn’t use some of the bigger fraction blocks?  These are actually the same question, since the bigger the leftover fraction blocks, the fewer left over we’ll have.

If you add up all the fractions we have here, you get 71/30, or 2 and 11/30.  Which means we’re going to end up with 11/30 left over no matter what.  But hold on.  11/30 = 1/3 + 1/30, so there should be a solution using all but those pieces...

Yay, it’s thirdless!  You know what else equals 11/30?  1/5 + 1/6... so here’s a solution that doesn’t use the 1/5 block or the 1/6 block. Though the bottom row is a little crammed with small fractions!

Finally, here’s a solution that doesn’t use the quarter block, since we seem to have quite a few ways to make 1/4:

I never noticed any of these back with the original puzzle, because why would I think to try adding up every fraction not in use there?  There were two many of them and adding up 1/19 + 1/23 + 1/29 or whatever just sounds like a headache.  But by restricting myself to just these fractions, it helped me churn out more answers!  Constraints breed creativity, I guess.

See what other solutions you can find!

[paulspuzzles-blog]

Puzzle #2a

Yes, yes it’s been far too long.  And I can’t even promise a new puzzle with this one!  This is, in fact, a rehash of Puzzle #2 (which IMO is easily the best puzzle I’ve ever designed) but with the twist that I've now created a version you can play with yourself! 

I have two versions of the puzzle available: a GIMP .xcf file that you can play around with if you have GIMP or any other art package that can handle .xcf files, or I have a .rar file of all the individual blocks saved as .png files, so you can Open As Layers the whole thing into your art package of choice:

.xcf: https://www.dropbox.com/s/ldwd8gw04yjii54/egyptian%20fractions%20template.xcf?dl=0

.rar with .pngs: https://www.dropbox.com/s/9tb94a9aka5k0db/egyptian%20fractions%20pieces.rar?dl=0

From here you can move each piece around as its own layer and slot them into position (you have to be pixel perfect about it, but hey, that’s part of the fun that exact solutions do exist).

Extra notes below the line:

So you may have noticed there’s been a few changes to the format.  The first obvious one is that our unit fraction pieces are now bars rather than arcs of circles.  I went for bars for a simple reason - I could use it to make each bar length a pixel-perfect size for the fraction I wanted.  Pretty much I found the LCM of the reciprocals of all these fractions, which comes out to 2520, and that became my unit - I made each bar a fraction of that, so the ½ bar is 1280 pixels wide, the 1/3 bar is 840 pixels wide and so on.

It’s an effective system, but it means that the puzzle has been streamlined a lot (which may not be a bad thing, depending on your viewpoint).  Firstly, we’re trying to make four lots of ½ rather than two lots of 1.  This is mostly because I’d’ve had to make the whole thing twice as wide and let’s face it, 1280 pixels fits better on a standard modern monitor than 2520 pixels.

I’ve also left out all the “red herring” fractions - things like the prime unit fractions 1/11 or smaller, or the smaller power of two unit fractions 1/16 and 1/32.  Again, the mechanical reason for this is that for pixel precision they would have made the whole thing larger - 1/16 would have made it twice as big, 1/32 four times as big, and the prime ones even crazier (ah yes, let me make this 31 times bigger to include 1/31).  But at the end of the day, perhaps no red herrings makes for a cleaner puzzle - every fraction you’re presented with is used in at least one solution, and the puzzle still retains the charming aspect that there are many different solutions.  You’ve seen some solutions in action from Puzzle #2 already, but I’ll post some solutions tomorrow anyway.

One last thing - the system I’ve used to label the bars - /2 for 1/2, /3 for 1/3, /4 for 1/4 and so on - is a convention that Robins and Shute (1987) use to denote Egpytian/unit fractions so that a bunch of extra 1s aren’t constantly needed to write them down.  Hope that’s okay.