Infinite Fractions - Numberphile
HTML-код
- Опубликовано: 1 дек 2014
- Matt Parker on Stern-Brocot numbers, fractions and rational numbers.
More links & stuff in full description below ↓↓↓
Matt's book on Amazon US: bit.ly/Matt_4D_US Amazon UK: bit.ly/Matt_4D_UK Signed: bit.ly/Matt_Signed
Poster: bit.ly/NumberPoster
EXTRA FOOTAGE: • Infinite Fractions (ex...
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/stores/numberphile
Other merchandise: store.dftba.com/collections/n... 
Наука
"That's cool." - Brady 2014
That's cool
That’s cool
That's cool
That’s cool
That's cool.
Reading it in a spiral seems like an unnecessarily unusual way of saying that you read it from top to bottom and left to right. Very cool, though.
or if you're in computer science, its a Breadth First search
iamterence77
Yeah, although technically, Breadth first search doesn't imply left to right.
iamterence77 Interesting that BFS comes up. I instantly thought of a level order traversal when he started to read the tree. Queues are involved in both methods, so I suppose that they'll do the same thing under the hood.
If you have the 1/1 in the centre and it's branches come off left and right, then "top to bottom and left to right" doesn't make sense anymore - the advantage of the spiral is that if you move the values around, they're still on the same unbroken line
I read your comment in a spiral.
"Read them like a spiral"
Or regularly. Left to right, top to bottom.
yeah that , uh , not fancy enough I suppose
I read your comment in a spiral.
To generate the Stern-Brocot sequence
Try reading Shakespeare in a spiral: it’ll blow your mind!
That's, like, a Parker spiral.
Fascinating :-)
I totally didn't expect to see you here...
Wait what.
oh hi there haha
xisumavoid I had no idea you were a number guy, Hey there :)
Hey
Man, this seemed so cool that I started plotting it out myself... and the number of patterns that can be found in it are so fantastic. The gaps between each appearance of a 1 give the pattern 1, 3, 7, 15, 31; increasing binary numbers-1, which could also be expressed that the gaps between the numbers in that pattern follow 2, 4, 8, 16. The gaps between each appearance of a 2 follow 2, 5, 11, 23, 47, and the gaps between the numbers of that pattern follow 3, 6, 12, 24.
At that point I predicted that the gaps between appearances of 3 would increase by 4, 8, 16, 32; but instead found they followed the pattern 1, 2, 3, 5, 7, 11, 15, 23 31 - gaps increasing 1, 1, 2, 2, 4, 4, 8, 8.
Haven't worked out the pattern with the gaps between 4s yet. That goes 5, 2, 11, 5, 23, 11. First number that gaps decrease. Would likely need to carry on the sequence further to find the pattern.
But with all of these patterns that show up... it's just awesome :D
Having all 3 of them 'rules', simplified, never repeating, and all fractions... is amazing... I don't understand a lot of the things brought up on this channel, but this specific video gave me chills.
In 3:11, there's a mistake. The phrase 'the (set of) rationals are the same size as the (set of) reals' should be 'the (set of) rationals are the same size as the (set of) natural numbers'. Cantor proved that the reals are not the 'same size' as the rationals, but are uncountably infinite, whereas the rationals are countably infinite (and the sequence of this video is a proof of this fact!).
actually algebraic irrationals are also countable, just like rationals. Only trascendental irrationals are uncountable.
@@radadadadee actually computable transcendentals are also countable, just like algebraics, only noncomputable transcendentals are uncountable... But you missed the point here, Alexander spotted a clear mistake.
I got confused too. Thanks for pointing it out.
If I had known these guys earlier I would have been a math major. Love this stuff.
John Nicolo it's never too late! ;)
+Numberphile I'll need a quarter a Casio and some paper I'm choosing between quantum physics and abstract algebra/ topology
Your thesis will be a calculator unboxing xD
I am in love with the Stern-Brocot sequence.
This method is so much better than the traditional diagonalization approach. Just think how much faster you can reach infinity this way....
"Reach infinity"?
Faster?
Well two people took the bait lol
@@trequor expected many more
His enthusiasm is infectious.
Matt has an amazing cheeky grin that appears when he's enjoying the magic of maths. :-D
Yes, a spiral is much more obvious than just read them top to bottom, left to right :D
Fantastic! Came across this on a wiki-walk a while ago. Still super awesome. Or more awesome. Started fangirling on the inside when I recognised the sequence. Now I understand it a little more, and that's a great feeling. Maybe my favorite sequence. Thanks Brady & Matt for all this goodness.
Wonderful sequence. Keep it up, you are doing a great job.
The title of this video made me think that he was going to talk about infinite continued fractions, and possibly even some Diophantine approximation.
It was still interesting, but you should do a video on that!
This is extremely cool. I'll have to watch this again when I'm not delirious from lack of sleep.
Just spent 10 minutes making graphs with the Stern-Brocot sequence and the associated sequence of fractions. Totally awesome.
Can you do an episode on the Continuum Hypothesis? I was very intrigued by the fact that it cannot be proven false nor correct. Is this true? And how can we make sense of a hypothesis that falls outside of our known truth values?
Computerphile did a series of videos on undecidability.
mindfulmike The Continuum Hypothesis is not undecidable in that same sense.
The Continuum Hypothesis is simply independent of the usual set theoretical axioms that are used for the foundation of maths. A simple analogy: Let the axioms be: A = true, B = true. Then we can prove the theorem that "A and B" is true. But whether C is true of false is independent of the axioms (it's a totally new "variable"). Said otherwise, you have the freedom to arbitrarily decide either way, you'll get a consistent system (supposing that you had a consistent one before).
A famous example for undecidability is the Halting Problem. The task is to decide, given the source code of a program, whether it will run forever of come to a final state (halt). Its undecidability means that there can be no such algorithm that could give the right answer to every possible input source code. It's a theorem that this algorithm cannot exist. It's not a problem of not having enough axioms. It's not that something is up to you to arbitrarily decide.
qorilla But are there other foundations on which to decide whether CH is true or false? Or does the CH have no truth value at all?
Maybe this is more something for philosophy-phile than for numberphile though.. :/
But to answer your question more directly: Look up the Axiom of constructibility. It's something you can add on to the Zermelo-Fraenkel (ZF) axioms and there the CH is true. But whether you want to add this axiom or not, will depend on what you want to do with this theory. You may also choose to just leave it as it is and not care about stuff that would depend on the CH.
qorilla Your explanations are amazing. Thank you very much :)
Comparing the CH to the parallel postulate is very helpful; it makes it immediately clear why its truth is not a matter of 'real truth' but just something we can choose to use or not to use in our models.
As a sidenote, though, I believe a great many philosophers of mathematics (and mathematicians themselves) would not be too pleased by your instrumental approach to mathematics. The exact ontological implications/nature of mathematics is still a subject of vehement disagreement.
Matt says "The video showed that the rationals are the same size as the reals" but then later the paper says "Everyone knows that the rationals are countable".
We know that the reals are uncountable, so I'm guessing Matt misspoke, meaning to say "the rationals are the same size as the naturals" (unless I've got something wrong here)
Well, we didn't need the paper to tell us that the rationals are countable. Good catch. (Yes, unless he's forgotten the basis of mathematics, he should have said "naturals" instead of "reals")
toast_recon if u hear closely , he said that the old video showed irrationals are the same size as reals, so u misheard, he didn't misspoke.
Aryan Arora yeah, no he didn't. Also, the video doesn't show that.
palmomki if u watch the video closely, he is talking about irrational numbers, because an irrational number is a number with decimals numbers going on infinitely, and i know he directly didnt say "that irrationals are the same size as reals" in the video, but this statement is based on the fact that both the reals and irrationals cant be listed in a table (and he explains WHY irrationals cant be listed in a table.)
Aryan Arora
Irrational is a number which can not be written as a the ratio of two integers. 1/3 has decimals going on infinitely, but is is a rational number.
I just got the super pack ( I think that's what it's called) from mathsgear, for Christmas. It was the best present EVER especially as the book was signed! Merry Christmas everyone. And thank you Matt and the rest of the numberphile "gang" merry Christmas! 🎅🎁🎄
wow this was amazing and so was the speaker. want more from him.
I love it. What a nice enumeration!
It has been addressed already in previous comments, but I can't help jumping on--the rationals are the same size as the naturals. The reals are uncountable!
I love how happy talking about this makes you! So fun to watch :)
I like the way that each line on the fraction tree has rotational symmetry.
This was sooo cool a concept, that I just had to configure up an Excel spreadsheet with the maximum columns of the sequence and display the fractions. 16,382 numbers in the sequence. Very fascinating to look at the fractions!!! Especially how the numerators and denominators cycle up and down.
Awesome! I wish I was shown this in first year as well as that grid method.
Matt, you'll be happy to hear that I found an actual use for the Fibonacci sequence. The largest numerator in a given row of the tree representation of the Stern-Brocot numbers is equal to F(n+1), where the top-most row is n=1.
what an amazing sequence!! so funny that math can suprise you when youre not expecting it!
Interesting video, and thank Matt for making his book available on kindle!
To me what makes the fibonacci sequence so fascinating is that it occurs quite a lot in nature.. For instance a nautilus shell. Thanks for uploading this 😃
What occurs is not the Fibonacci sequence, it's the golden ratio. But lots of other ratios also occur in nature.
Lol your ways of writing 5 is really inefficient Matt (4:52)
Parker five
the original comment the first reply and now this reply are all square number of likes
Mind blown. I love this.
There is no need for a spiral. The spiral has to be remembered as clockwise or counter clockwise, which is more information that someone would tend to remember when applying simplified methods. You can just describe the reading of the fraction sequence as the reading of a book. Top to bottom, left to right.
Res Gestae if you move the values around, say, to make 1/1 in the centre and it's branches coming off left and right, "left to right a
I like it more than that diagonal proof, and yeah, it's fun to see the end of the sequence run away 😂
Just watched this again 8 years later. Still astounded by it.
The second method reminds me a lot of pascals triangle. This is super cool, thanks :)
You have a funny way of writing 5 :) Amazing sequence, I knew the second method of generating infinite fractions.
The way you've written out the tree differs from other versions I'm seeing online when looking it up. That version on each line lists out the sequence of numbers from left to right for numerators, right to left for denominators. It ends up with the same numbers but in a quite different order. Took me a while to understand what they were doing.
Now that is *WAY* cool!
The spiral at the end is just the same thing as a breadth-first search right? Might be easier for programmers to comprehend.
Really amazing. Thanks!
This series is EPIC
The part of the sequence that interests me is the mirrored/palindrome groups of numbers that only overlap on the 1s and center on the 2s. I don't really have time to find/read a paper to see if it says anything on that, though.
The more of this link links to this video.
That's cheating.
NNOTM oops
Wish I could give you more likes for that comment, hahaha.
You should write : The "more of this" link, links to this video. Less confusing to understand what you are talking about , :)
sKebess I can not not notice the double spaces before the word "less" in your comment. Also, there's a space between the word "about" and the final comma, and a space between "write" and your colon (no, not that one in your body. I'm referring to the punctuation).
Jaap Zeldenrust In this case, the comma is to mark a "natural" reading pause, nothing more. :)
This guy is the best haha. He's so damn enthusiastic and totally into this sequence.
The book is very interesting and innovative... read the fisrt chapter and am eager to finish reading it soon...
Great video, way above my current knowledge, but I am getting smarter by watching.
I immediatly want to write a program that creates the Stern-Brocot numbers
It's pretty simple actually. Just make that tree and then print it in spiral way. Or do it like Fibonacci sequence using recursion.
AbhiShake Fibonacci sequence style aa lot easier
ala bader
Yeah, tree method will take more time.
That literally only took a minute.
n = input('n = ')
seq = [1,1]
IsEven = (n%2 == 0)
for i in xrange(n//2-1):
seq.append(seq[i+0]+seq[i+1])
seq.append(seq[i+1])
if IsEven == False:
seq.append(seq[n/2-1]+seq[n/2])
print seq
JNCressey Python ?
2:43 That's an understatement...
I never thought this non redundant listing was possible without the grid. AWESOME
Amazing! How have I not seen this video yet?
Numberphile Just bought the book! Looks great!
I want that book! Gonna get it.
That is incredible. I wish my math teachers woul've shown me that back then
I like that the spiraling sequence to "enumerate" the fractions on the tree resembles that produced by the golden ratio phi which is often (even if somewhat erroneously) used to visualize the Fibonacci numbers.
Fantastic!!
One of my fav's. Big fan, but rarely comment. So cool, I'm surprised it didn't show up sooner in the channel. The spiral is silly though, Just read it like a book. (Top to bottom, left to right.)
Great sequence. For anyone watching and reading who's confused the diagonal proof was Cantor.
my new favourite youtube video :)
"That one gets the top, this one gets the bottom, that one gets the top, this one gets the bottom" I wanna make that into a song xD
I love videos where Matt Parker is lecturing an audience, but this video is all close and personal. I feel Matt Parker's eyes staring into where my soul should be whenever he looks at the camera. Lol
That is awesome. I wish maths in school was this interesting.
These two are identical with two different ways of representing the same numbers and the same operations in the same order. The first is being done in serial while the second is being done per series. No spiral is necessary....just read from top to bottom left to right as we always would....
Side note, yes, the sequence is cool.
Cool sequence.
This is wicked cool!
Once again, you guys taught me something that I can brag about around teachers. :D
When we add the ciphers of a number, we obtain what is called the digital root, more properly the rest of Division by 9. For example, when to do to the number 10: 1 + 0 = 1, we are expressing that when we divide 10 by 9 spare one.
Then, if we remove the rest of the number (in our example 10-1 = 9) we will be a value that is always divisible by nine (If by dividing X of nine I left a residue of Y, then X - Y is evenly divisible by nine) . When performing digital root of a number divisible by nine always obtained 9. Expressed in mathematical terms: The result of subtracting a number the module rest 9 is a value which is exactly divisible by 9.
Fantastic!
Being the nerd that I am, as soon as Matt mentioned the graph construction, I immediately went and programmed a small app that uses it, with the breadth-first search required, to print out the first N rational numbers generated that way. I am either a huge nerd or very bored...that's non-exclusive "or" here...
yay cool matt is back! :)
That's really cool!
that was your greatest ever video, my mind is blown
Thanks!
This sequence could be very useful in Dynamic Programing. Gotta find out how.
Probability Trees remind me of my child hood, messing around with numbers :)
Please do more on Permutations!
This is brilliant
Just in case you wondered: The series is indeed called the Stern-Brocot series or Stern's diatomic series, but the tree that Matt presented here (which is related to the Stern-Brocot series in the way Matt described) is not the Stern-Brocot tree. It is called the Calkin-Wilf tree. There also exists a Stern-Brocot tree which also contains all the fractions exactly once, but they are in a slightly different order.
The Stern-Brocot tree has the advantage, that it is arranged as a binary search tree. For example the 3/2 and 2/3 are switched.
Very cool sequence. That "spiral" sequence is known as a "level order traversal" (AKA "breadth-first search" sequence). I've never seen it characterized as a spiral before though (it's usually described using a zig-zag on each subsequent level of the tree).
Great vid! Would he do one about his book?
wow that is so amazing
I love this! : )
You guys and girls and are amazing! Wish I knew what you have forgotten about Math ( or Maths if you prefer ).
As always, this is very cool. But I wish Matt would explain why and how this sequence can/has been used in real life (engineering, computer programming or etc)
Ordered Matt's book the instant I became clear it exised!
Numberphile rules.
Amazing!
I'm buying that book so hard.
TL;DW: This sequence, which lists all fractions in reduced form, starts 1, 1, and has a double recursion: an even-indexed term is equal to the one with half the index, and the next term equals this "halfway back" term plus the next one.
thanks but can you put a TL;DW on their 30 minute long videos?
Mind blown!
The word “bijection” should have been mentioned.
As a computerphile I recognised that the bit at the end is exactly how you map a binary tree to an array :D
My mind was blown 5 times during this video
2:43 I agree Brady. That's cool.
Simple variant: copy the first instead of the last and start with 0 1. You get 0 1 1 0 2 1 1 1 2 0 3 2 2 ... OEIS A281185, except for the first two items in the latter. It's known as a "bow" sequence, opposite of stern, geddit?. It doesn't look promising as a list of whole number ratios, but one interesting feature I've noticed (probably not the first to) is that it seems to contain all the Fibonacci numbers but increasingly spread out at double the distance each time. So from the first 1 to the first 2 is 3, 2 to 3 is 6, 3 to 5 is 12, 5 to 8 is 24, etc. I call it the Fibonacci Dawdle.
I can't like this enough!
I like the fact that you don't immediately add videos to a playlist. It can be very annoying when at the end of a video it just moves on to another one without letting you either share, comment or like.
Also, awesome video, :) I'm amazed I had never heard of this sequence.
What's with the spiral? Why not just say, "read them from left to right, line by line?"
Spirals are KEWL.
+Bloodbath and Beyond Continuous lines are always much neater than broken ones, so I suppose it could be a zigzag or some such, but corners and changes of directions are somewhat more complicated. In essence, it's an arbitrary way to express something that can conceivably be written in any configuration as long as it's in a regular pattern.
For example, rather than arranging it like a tree/triangle like he has on the paper, he could have the branches coming out in exactly opposite directions with 1/1 in the centre. At this point, the spiral becomes necessary as there are no longer any 'straight lines' to read.
tl;dr: spirals are a continuous line that goes in one 'direction' and, as +ginemginem said, they are kewl.
Rovanoid First answer was MUCH better. Second answer was (just like the video) a whole lot of unnecessary explanation just to say something extremely simple: Just read from left to right like a damn paragraph!
+Bloodbath and Beyond once again, you can't do that if the layout is changed - that's the point - the layout does not change the meaning of the set but "read left to right" does change. That's one of the main things we look for in mathematics: patterns independent of semantic configuration.
Not to mention that reading left to right and top to bottom is not a universal convention, whereas a spiral is a shape that is.
Rovanoid THIS layout allows to read from left to right. THAT'S the point. It's on overly complicated step which typifies the isolated world of mathematicians.
If this were a video aimed at other mathematicians, then I could see using a broad, universal convention. For RUclips, there's no need for it.
I saw Matt Parker and I believe another person whom I saw earlier on numberphile on TV the other day! I forget the show, but it was science related. I was like, "I know them!"
I have to say this blows one's mind and Baskington agrees!
Beautiful