Egyptian Fractions and the Greedy Algorithm - Numberphile
Featuring Sophie Maclean. See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor). More links & stuff in full description below ↓↓↓
Sophie Maclean is based at Kings College, London: sophiethemathmo.wordpress.com
More Sophie on Numberphile: bit.ly/Sophie_Numberphile
Patreon: / numberphile
Numberphile is supported by Jane Street. Learn more about them (and exciting career opportunities) at: bit.ly/numberphile-janestreet
We're also supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
Our thanks also to the Simons Foundation: www.simonsfoundation.org
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor)
1'000'000 == MAX_EGYPTIAN_INT 😂😂😂
Whoever created that "bent finger" heiroglyph was a different kind of numberphile.
Yeah, he was definitely counting to 11.
@@michaelrockwell9691 🤣
It was probably a Microsoft help desk employee
I think credit should be given to the mathematician who devised the greedy algorithm and proved that it terminates. He was Leonardo of Pisa, better known as Fibonacci.
Fibonacci strikes again. But jokes aside now, could you give more on this? When did he use it?
@@Felipe-sw8wp Greedy algorithm was developed by Fibonacci, not the Egyptians who did not use it.
Which proves that the ancient Egyptians had time travel. Which is why they could use the greedy algorythm centuries before the birth of Leonardo.
@@KenFullmanFalse equivalency. 'Akkadians drew circles, therefore Pi.'
@@bobSeigarAkkadians lived in Mess of Potatmia and they drew triangles, which is why we still call the longest side of a triangle the hippopotamus.
Sounds like a promising way to calculate the value of 1 to any number of decimal places!
Not to brag, but I have the value of 1 memorized to over 100 decimal places.
@@vigilantcosmicpenguin8721I've only memorized the first 60, keep up the grind 💪
Poor Sophie ahaha. "It's a finger. A *finger.*"
I respectfully disagree
Yeah that's what I thought. I mean, 'finger' wouldn't be my first guess at what that is supposed to represent... lol.
Sure it is
Maybe it is supposed to be a bent finger but from head on.
look up the actual symbols, they actually look like a bent finger.
This makes PERFECT sense when you think about how this would be used in everyday life. If my taxes from a days milling is 11/12 of a bushel (or proper historic unit) I am going to use 1/n sized scoops to measure out my payment. So 11/12 would be 1 - 1/3 of a 1/4 measure, if the smallest measuring tool I had was a 1/4 (unit) bowl.
I was thinking the practicality comes from the fact that this system means you don't have to have multiple copies of all your fractional measurement things (weights, containers) and can instead do whatever you need with just one of each. Instead of having to measure 7/9 by having seven 1/9th weights, I can do it with the single 1/2, 1/4 and 1/18 weights I already have. (And I can just add precision as needed by buying a new weight just one denominator larger than what I already have.)
The other practical component is it makes dividing things among people easier. Say you need to divide 5 pizzas among 8 people. 5/8 is 1/2 + 1/8, so each person can get half of a pizza plus an eighth, rather than having to divide the pizza into 40 slices and give everyone 5.
The greedy algorithm is a mathematician's algorithm rather than a really practical one. It does terminate but it might use more fractions than the minimum that are enough. And its priority of greed over exploiting factors of the starting fraction's denominator sometimes leads it to overlook simple solutions. The simplest fraction where it is not best is 4/17. The greedy algorithm uses four denoms: 5, 29, 1233, 3039345. But three denoms are enough: 5, 5*6, 5*6*17. One where it overlooks a factor in the starting denom: 4/49. The greedy algorithm uses four denoms: 13, 213, 67841, 9204734721. But two denoms are enough: 14, 98 [edit: typo corrected].
Very nice. Any hint on how you got those better fractions? Just one thing, I believe there is a mistake on the last example, because 1/7 is bigger than 4/49 so it can't be that 4/49=1/7+1/98. (I've checked the others, they all work).
@@Felipe-sw8wp I think it should be 14, 98. That is, 4/49 = 1/14 + 1/98.
Fun fact, the ancient Egyptian thought so too. In fact, deciphering how they got near-minimal representations (and what they considered minimal in the first place) is a whole area of study in and of itself. I remember doing a research paper for a course about this, and some of the sources have very interesting theories.
Nice examples. (But the last one has a typo: 4/49 = 1/14 + 1/98). BTW, Egyptians did not use greedy algorithm. E.g. in Ahmes Papyrus 2/49=1/28+1/196. The greedy algorithm would gave: 1/25+1/1225. Ahmes' answer is much nicer. And it follows immediately from it that 4/49 = 1/14+1/98. So Egyptians were more efficient than the greedy algorithm.
@@papalyosha was wondering why the greedy algorithm wouldn't pick up 1/7, but of course 1/7 is less than 4/49, so should have twigged
The scribe of the Rhind Papyrus, Ahmes, opened this historic works of 84 various problems by asserting he would study 'the knowledge of all secrets'. I prefer to refer to it as the Ahmes Papyrus in honour of its writer! (Henry Rhind was the 19th century buyer of the papyrus.)
nice input
Sometimes a bent finger is just a bent finger.
The Ancient Egyptians felt particularly comfortable with the fraction 2/3. One reason for this that is linked to their desire to express fractions that would be irreducible to us today as the sum of many unit fractions: because 2/3 of any unit fraction 1/n = 1/2n + 1/6n. As a result, even to find 1/3 of a number the Ancient Egyptians would first find 2/3 of it and then halve the result!
isn't 1/2n+1/6n=8n/12n^2=2/3n?
@@proloycodes Sorry, my bad, I meant to say that 2/3 of 1/n = 1/2n + 1/6n. Well spotted. Corrected it now
I don't get it: since ⅔=½+⅙, it *isn't* irreducible to unit fractions, right?
@@landsgevaer it is irreducible to us because there are no common factors of 2 & 3 (except 1). it is reducible to sums of unit fractions though
@@landsgevaer how do you do the fractions in your reply? Is it a LaTex filter? Natural command?
This felt like it ended abruptly. Though I guess no discussion about ancient number systems could be complete with a single KZhead video; especially one less than 10 minutes long.
So in all of a sudden we came to know the origin of Super Mario's Piranha Plant
Yes, yes, yes! That is 1000% (see what I did there?) a piranha plant!
Egyptian fractions was one of my research projects for my final semester. Also my favorite project.
3:43 The exact moment I got _totally_ lost.
Maybe en example will help you. For any [positive] proper fraction with numerator different than 1 (denoted as p/q), there are fractions like 1/something, which are less than this, and we are searching for the biggest of them (so for 3/5 it would be 1/2; 1/3 is smaller than 3/5, too, but 1/2 is the biggest fraction with numerator 1 that is less 3/5, so we choose that one). "Greedy algorithm" means that for whatever is left we repeat this process, so after subtracting 1/2 from 3/5, we are left with 1/10. In this example we are done - the egyptian fraction for 3/5 is: 1/2 + 1/10. (Egyptian fraction for any p/q is 1/a+ 1/b + 1/c + … and so on.) I hope that helps somewhat.
thiis is facinating, bc constructing these numbers in the denominator is reminiscent of how every number can be constructed from prime factors, except in this case it's with addition rather than multiplication
I learned about Egyptian fractions from David Reimer's book "Count like an Egyptian." Highly recommend.
4:42 You don't substitute, you just rearrange the inequality.
Oh thank goodness… I spent minutes trying to figure out what substituted for what until I decided to check the comments. Thanks!
Me, too!! Thank you for clarifying!
I studied this in my history of math course and didn't remember the conclusion, whether or not every rational number was possible. I was thinking about this question this week and this video showed up to answer it! Excellent timing!
Kinda like the 'very large number represents infinity', in a biblical context '40' tends to mean 'quite a while', or 'a significant amount of time', rather than literally 40 years wandering, 40 days and nights of rain, etc. I find that (and the million=infinity) really interesting and perhaps revealing about the culture/context/etc... any other examples?
Yes. It's basically the same in Japanese and, I think, Chinese, where their respective word for 10.000 can also mean "an inconceivable shitload of".
In old Russian 10.000 apparently played that part, and the name for 10 000 -- "t'ma", that literally translates as "darkness", is now used to mean "uncountably many (people)" .😊
@@lonestarr1490 Also Greek. "Myriad" literally means 10,000, but traditionally it could also just mean "a great number," which it still means today in English.
That's just a conjecture by non-Christians. The bible contains *many* larger numbers, and some *much larger* numbers, the largest being two hundred million ("twice ten thousand times ten thousand"). One hundred million ("ten thousand times ten thousand") is also written.
Is there any extra-biblical support that '40' means 'quite a while'?
This is one of the wierdest pen holding style I've ever seen :DD
You ain't seen nothing
Enjoy Sophie's energy and explanations!
and handwriting!
And the accent
halo effect from looks lol
You can split a unit fraction into two unit fractions by the substitution 1/n -> 1/(n + 1) + 1/(n^2 + n). So for example 1/26 = 1/27 + 1/702.
Strange that the symbol for 1/2 looks like the graph of y=x^1/2
Sophie is my absolute favorite ❤
Your handwriting is quite beautiful. Explained really well too! 😊
I do wonder what need the ancient Egyptians had for counting a million things. It's clear they were doing some big-numbers arithmetic at that point. They knew they had a thousand of a thing that was also thousand.
it's a fair question, but at the same time, they were humans, and there's a very human desire to be like, well, what's bigger than a thousand? the overwhelming majority of us have no need for the numbers generated by tetration, pentation, etc, but we do it anyway because big numbers are kind of awesome
The pyramids contain more than a million stones for example. However, an empire like Egypt also needs numbers in that range to handle food distribution and administration in general.
I mean...The Great Pyramid consists of an estimated 2.3 million blocks...
Accounting. The Narmer Macehead records a total plunder of 1,422,000 goats, 400,000 cattle, and 120,000 human captives.
They needed a way to count the money aliens paid them for building the pyramids
That's not a water lily. That is Audrey the man-eating plant from Little Shop of Horrors.
It's pretty similar to writing decimal numbers in binary. .1 = 1/2 .01 = 1/4 etc. So to get 1/3, you need 1/4 + 1/16 + 1/64 + ... and you have .010101...
I think I say this every time, but Sophie has the neatest writing ive ever seen lol
Can we pause for a second and be in awe of the fact we're watching a mathematician flawlessly writing hieroglyphs, and in such clear handwriting? ❤
Yes we can ❤
I remember you from watford girls! Cool to see you on here!
I can only imagine ancient Egyptians using 10 10000 10 as a meme joke. :)
Yeah, like that thing hanging off Orion's Belt. That's not a sword. It's over 9000!!
That’s a bent finger alright! It resembles nothing else that I can think of.
Interesting! I wonder if this relates to Eudoxus theory of proprtions.
40 years wandering, etc? 40 usually meant 'quite a while', or, 'a long dang time', rather than exactly 40 of whatever. Cheers
[me @0:49]: "... Pac-Man exploding out of a hemispherical cake"
I'd love to see the papyrus with pi written down.
2, 3, 7, 43, 1807 ... gets very large very quickly. It's known as Sylvester's sequence (OEIS A000058).
And what about using continued fractions to obtain the" 1/n"s?
"Groundbraking. Its called.. A single stroke." (Chefs kiss for us simple-minded folks.)
The number 1 and a single tally mark -- name a more iconic duo
There are cases where there is more than one way to give an Egyptian fraction. Did they prefer one over another in that case, for example the one coming from the greedy algorithm?
My 4 year old has the same concept for 100. Anything that is a ton of something is simply 100- id assume it’s the same idea for Egyptian 1M
It's still somewhat used in today's English. The word 'miriad' has two meanings, one is 10,000, the other one is 'too many to count'.
So was egyptian maths and numbers more practical than roman or did they use similar ideas with fractions with just different representation for numbers?
My understanding is that the Roman system is a distant descendant of the Egyptian system(s), with various improvements/adaptations made along the way. For example, the subtractive elements of the Roman system make calculation using an abacus or reckoning board faster (in some circumstances). Roman fractions are base 12, which in one way is very awkward, but in another way is very convenient. It's funny that today, we still have that same argument regarding metric versus imperial measurement.
@@glenm99 Yup that is the ONE big advantage of imperial IMO, is that fractions are easier in base 12. I used to work construction and can confirm it DOES make mental math easier. Now when used for larger measurements likes miles........ yeah that is where it gets silly.
Ah, yes... Ancient Egyptian Algebra. I had a nightmare about this once...I think I was in my underwear...
I'll never get back to sleep… _snore_
8:00 what about 1/2+1/3+1/6=1?
That exactly equals one. The expressions in questions are meant to be minimally less than one
Someone invented Egyptian Fractions to avoid getting on the pyramid crew.
Nice video, Sophie! I just posted another video on Egyptian fractions.
7:43 Would you be able to use this to approximate irrational numbers?
I think so, but idk how practical that is.
Woah, hold up, what's that in the thumbnail?💀
bent finger
When not writing in Egyptian, I use the notation R, both for "reciprocal" and for the Egyptian letter. So R2R3R6R43. Does Tweety Bird know the Sylvester sequence?
Modern academic literature uses over-lining, which is nearly the same as how ancient Egyptians did in Hieratic (their preferred non-fancy script that is just as old as Hieroglyphics), so you're not far off.
Sylvester's sequence
Accidentally clicked on this video and i dont regret it
2:55 my best guess is one word. Efficiency.
when you calculated the egyptian fraction for 1, it got me thinking. you get 1/2, 1/2+1/3=5/6, 5/6+1/7=41/42 If you get to a fraction of the form (a-1)/a, then the next fraction you can add is 1/(a+1). (a-1)/a + 1/(a+1) = [(a-1)(a+1) + a]/a(a+1) = [(a-1)(a+1) + (a+1) - 1]/a(a+1) = [a(a+1) - 1]/a(a+1) so you again get a fraction of the form (a'-1)/a', with a' = a(a+1) so to compute this series, you just need to compute the sequence a[n+1] = a[n](a[n] + 1), a[0] = 2 which grows pretty fast, faster than 2^(2^n), which is pretty damn fast 2, 6, 42, 1806, 3263442,...
“that’s a bent finger”
I hardly see it
New wave of Numberphile Mathematicians.
Is it just me, or are mathematicians getting cooler? Doctor Crawford, this amazing person. Even Parker is looking way Cooler than a few years ago. Is there a coolness - time diagram for mathematicians?
I have a conjecture that the rational number p/q will terminate in at most [2^(n-1)
…was that, “one over n is the biggest bull sh1tter’s truth”. Love it.
"i looked into it! dont really know what that does!" hilarious
I wondered if ancient Egyptians had a sense of humor, but I googled the hieroglyph for 10k and it looks more like a bent finger than the one in this video :D
we all giggled, admit it
Ahh the teachers of the Greeks. I love the history of mathematics
That Thumbnail.😮
01:00 - No amount of persuasion will tell me that's a bent finger. In fact I'm worried this vid will be demonitised. 😂😂😂
Oh, bless your heart darling, that right thar is not what one would call a bent finger...
Imagine what they'll think in a few thousand years about our scrawling on paper. What are we missing that they'll see?
1:00 I don't see a bent finger.
Today: _One Million_ Ancient Egyptians: _Soooo much!_ \o/
That bent finger though...
This is interesting way to hold a pen. Very uncomfortable even to look at.
"You want a million of them? ... Heh!"
I normally love numberphile. But I did not follow a single thing in this episode after the introduction of the hieroglyphs and fractions. This one was a swing and a miss for me
We all know that's not a bent finger... It's a lit candle! 🕯️
So, the Egyptians could express numbers in the millions. And Roman numerals only go to Thousands
Making fractions with the Greedo algorithm - Han shot first.
Clean presentation
for anyone wondering 2, 3, 7, 43.... is a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2
I jumped into this video at 7 am before coffee, on the throne, bad idea. Now I have a headache
What am I missing here? Of course there's always a way to write any fraction as a sum of fractions with 1 in the numerator: p/q = 1/q + 1/q + ... + 1/q, and this p times? Is this video rather a statement that it works as well when greedily writing the fraction down? Also why is 1/2 + 1/3 + 1/7 the Egyptian fraction closest to one when we clearly have 1/2 + 1/3 + 1/6 which is closer? Or is the latter not an Egyptian fraction? This video was going a bit too fast... EDIT: Oh, an Egyptian fraction has all different denominators as stated in the video. I suppose this means Egyptian fractions can only be constructed in this greedy manner for fractions less than one, since otherwise one would have lots of 1/1 + 1/1 + ... until getting to the decimal part.
i don't know the details but I'm pretty sure the Egyptians were not interested on repeating the same fraction more than once for some reason. maybe because 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 is way longer than 1/2 + 1/3 + 1/42? or how 20/21 is just 1/2+1/3+1/9+1/126 also I would assume 1/2+1/3+1/7 is the closest to 1 without actually being equal to 1
Yes, you are overlooking something: All denominators in egyptian fractions have to be distinct. So 1/q+1/q wouldn't work for their system. As or the other thing: 1/1 is technically a fraction as well, so I suppose the "without being equal to 1" aioia mentioned is needed here.
@@aioia3885 oh yes the "closest without equaling" was missing in the video, thanks!
Ancient Egyptians were perfectly fine concatenating regular and reciprocal numbers in a form of addition, similar to concatenating digits to build up the number's size and (right of the decimal point) precision amount. They also had tables for how to double odd reciprocals to aid with preserving the unique-denominator property for the result of general addition and multiplication.
Ancient Egyptians had very nice symbol for ten. Personally I would use it in the dozenal system instead of X, but alas! - there is already some kind of tradition in this regard. ;-) P.S. Had any ancient civilization, by chance, a symbol for eleven?
Interesting question, I didn't find any that have a single written symbol for 11. Even in those languages that don't use base 10 numbering system generally break the words and symbols down to a "ten and" style. One I found that doesn't is the Huli language, spoken in Papua New Guinea, which uses a base 15 counting system, with unique words for 1-15. No written symbols that I could find, though. Thanks for the rabbit hole, it was fun.
@@markhubbart8903 You're welcome ;-) And thank you for finding the Huli counting system. I didn't know about it despite Wikipedia mentioning it ;-)
Amazing how smart people on the prairies don't use salt. Salt makes the roads sticky to blowing snow. You end up with stick snow drifting. If you use just sand, it breaks up the snow and ice and the wind blows away. The road is dry and other blowing snow just blows across. This is mostly effective on the open prairies rather than in the cities.
cool🌸
The Infectious enthusiasm almost distracted me from how "Brilliant"ly it was presented, really a fascinating performance of ancientt mathematics
according to something I read a while ago there was one fraction that can't be written like this: (2/3)
It is backwards, but it depends which direction you're writing, because hieroglphyics are read in either direction.
There is a conjecture that if the denominator is 4, the process will stop after four steps or earlier. So I wonder what happens for other denominators.
A conjecture you say? I'd say that's completely obvious... Or am I off the rails here? Which denominator do you mean?
@@lonestarr1490 I looked it up. The conjecture is that for n>2 4/n=1/a+1/b+1/c for some integers a,b,c. So it you do no even need the d. It is called "Erdos-Strauss-Conjecture". Of course, if you allow four summands, it would be trivial. Obviously 4/n=1/n+1/n+1/n+1/n. That was my mistake. With only three summands it is not trivial though. For any n you will find a,b,c that make it work, but it has not been proven for every n. If you can prove it, you will become famous in the maths world.
Ah, not the denominator, but the numerator! Yes, that's another beast completely.
@@lonestarr1490 Haha, I always mix those up, as I know them as dividend and divisor in German. The problem looks so simple, but people have probably spent years on trying to solve it. I wonder if there is a simple solution that nobody has thought of yet.
@@skyscraperfan I also checked trice if I have them the right way around ;) That's usually the gist in number theory: the problems always appear to be trivial and you wonder if there's a clever and short solution nobody thought of thus far. And in fact, there are problems where this was the case. But they're the exception. Usually, number theory problems are freaking hard. That's especially true for every conjecture that comes with the name of Paul Erdös attached ;)
Next let's see the Riemann zeta function in ancient Egyptian.
It’s a bent finger, guys.
Immagine this guys writing the algorithm to know how to translate those in hieroglyphics... Why so fancy with the number skins lol
Deeefinitely a bent finger and not anything else at all nope not anything else why what were you thinking it was?
1:00 ancient Egyptian girls need fun too
Do we count 0-9 or 1-10 ???????
Ancient Egypt did have a concept of nothing, but whether they fully understood it as a quantity of "zero" is unclear, even in later eras where the word was used somewhat more computationally. Counting, therefore, would be 1-10, especially in earlier eras
How did the Egyptians write pi?
My ex called it the "bent finger". :(
So how did they work them out, when they didn't have a more powerful system to do it with? We're supposing that the Egyptian Fractions were all they had.
A000058 in the OEIS.
isnt greedy algorithm just euclidean algorithm but instead of pulling gcd number u pull fraction at each step?
It’s *definitely* a bent finger. 😂
i just came up with a new "socks in the drawer" theorem - could anyone from numberphile team prove it? It is true that when you buy new pair of socks the probability of finding a matching pair in your disorganized sock drawer decreases.
Depends how many colours of socks you have
If there are only 2 colours, the probability is always 100% after three selections, even if you have a thousand of each colour
In the Torah, the number 40 just means "a whole lot."