Egyptian Fractions and the Greedy Algorithm - Numberphile
Вставка
- Опубліковано 18 тра 2024
- 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
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 💪
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.
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
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 UA-cam video; especially one less than 10 minutes long.
Sometimes a bent finger is just a bent finger.
Egyptian fractions was one of my research projects for my final semester. Also my favorite project.
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!
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!
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.
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'?
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!
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.
Enjoy Sophie's energy and explanations!
and handwriting!
And the accent
halo effect from looks lol
Sophie is my absolute favorite ❤
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
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...
Strange that the symbol for 1/2 looks like the graph of y=x^1/2
That's not a water lily. That is Audrey the man-eating plant from Little Shop of Horrors.
This is one of the wierdest pen holding style I've ever seen :DD
You ain't seen nothing
Your handwriting is quite beautiful.
Explained really well too! 😊
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
2, 3, 7, 43, 1807 ... gets very large very quickly. It's known as Sylvester's sequence (OEIS A000058).
I'd love to see the papyrus with pi written down.
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 ❤
That’s a bent finger alright! It resembles nothing else that I can think of.
I think I say this every time, but Sophie has the neatest writing ive ever seen lol
I remember you from watford girls! Cool to see you on here!
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?
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.
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'.
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!!
Woah, hold up, what's that in the thumbnail?💀
bent finger
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,...
And what about using continued fractions to obtain the" 1/n"s?
“that’s a bent finger”
I hardly see it
"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
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
Sylvester's sequence
Accidentally clicked on this video and i dont regret it
2:55 my best guess is one word. Efficiency.
Nice video, Sophie! I just posted another video on Egyptian fractions.
Someone invented Egyptian Fractions to avoid getting on the pyramid crew.
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.
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_
This is interesting way to hold a pen. Very uncomfortable even to look at.
[me @0:49]: "... Pac-Man exploding out of a hemispherical cake"
New wave of Numberphile Mathematicians.
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
7:43 Would you be able to use this to approximate irrational numbers?
I think so, but idk how practical that is.
for anyone wondering 2, 3, 7, 43.... is a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2
I have a conjecture that the rational number p/q will terminate in at most [2^(n-1)
Oh, bless your heart darling, that right thar is not what one would call a bent finger...
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?
It is backwards, but it depends which direction you're writing, because hieroglphyics are read in either direction.
Ahh the teachers of the Greeks. I love the history of mathematics
So, the Egyptians could express numbers in the millions. And Roman numerals only go to Thousands
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.
1:00 I don't see a bent finger.
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 ;)
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 ;-)
I jumped into this video at 7 am before coffee, on the throne, bad idea. Now I have a headache
We all know that's not a bent finger... It's a lit candle! 🕯️
Imagine what they'll think in a few thousand years about our scrawling on paper. What are we missing that they'll see?
Making fractions with the Greedo algorithm - Han shot first.
cool🌸
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.
Today: _One Million_
Ancient Egyptians: _Soooo much!_ \o/
That Thumbnail.😮
It’s a bent finger, guys.
That bent finger though...
…was that, “one over n is the biggest bull sh1tter’s truth”. Love it.
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
Next let's see the Riemann zeta function in ancient Egyptian.
Deeefinitely a bent finger and not anything else at all nope not anything else why what were you thinking it was?
according to something I read a while ago there was one fraction that can't be written like this: (2/3)
01:00 - No amount of persuasion will tell me that's a bent finger. In fact I'm worried this vid will be demonitised. 😂😂😂
"i looked into it! dont really know what that does!" hilarious
"You want a million of them? ... Heh!"
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.
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
My ex called it the "bent finger". :(
isnt greedy algorithm just euclidean algorithm but instead of pulling gcd number u pull fraction at each step?
A000058 in the OEIS.
Immagine this guys writing the algorithm to know how to translate those in hieroglyphics... Why so fancy with the number skins lol
The Infectious enthusiasm almost distracted me from how "Brilliant"ly it was presented, really a fascinating performance of ancientt mathematics
Love the Math although its Over my Head. I work on Systems for Dummies. They have No Name But I Call it Star System Math as the Stars as the Math... Change all the Numbers in Pi. to the 3rd House.
Here is How it Goes
1 2 3 Multiplied by 3, then added to a Single Digit
4 5 6
7 8 9
3x
3x 1= 3
3x 4= 12/1+2=3 3 6 9 ONLY 3 Answers
3x 7= 21/2+1=3 3 6 9
3 6 9
3x 2=6
3x 5=15/6
3x8=24/6
3x3=9
3x6=18/9
3x9=27/9
Why on earth haven't you mentioned the notorious odd Egyptian fractions conjecture? Does the greedy algorithm work for odd denominators?
The greedy algorithm works for ALL denominators but isnt optimized.
@@alanhersch4617 Of course. What I mean is: Does the greedy algorithm work if we always take the smallest odd reciprocal? As far as I know this is an open question.
@@rainerausdemspring3584 Oh oop, totally misunderstood.
Was expecting to see the actual USES of fractions, add, multiply, subtract, etc... using the symbols, akin to Roman numeral math. Got none of that, just more recent math terms that don't explain HOW or WHY they used or made these symbols. Only dissertation of modern algebra breakdown.
The title was "Egyptian Fractions and the Greedy Algorithm". How come that led you not to expect what Sophie gave us? or to expect "add, multiply, subtract, etc... using the symbols, akin to Roman numeral math"? That might be an interesting field of study but it would be a very different video.
That is because general fractional addition/subtraction in this system is a whole other beast (what is shown is integer division). Meanwhile, general multiplication and division is both about distribution of multiplication coupled with a lot of simplification by addition, which can get very hard to understand (yet the ancient scribes somehow omitted more than what they included, some say by way of scratchwork on separate mediums).
That is not a bent finger.
In the Torah, the number 40 just means "a whole lot."
Clean presentation