The Yellowstone Permutation - Numberphile
HTML-код
- Опубликовано: 25 июн 2024
- Featuring Neil Sloane. See brilliant.org/numberphile for Brilliant and get 20% off their premium service (episode sponsor)
More links & stuff in full description below ↓↓↓
Correction at 4:08… Neil says “then we get twice 61" instead of “about twice 61". The actual result is 120, not 122 as labelled.
Neil Sloane is founder of the legendary OEIS: oeis.org/
Yellowstone Permutation and its wonderful geysers: oeis.org/A098550
More Neil Sloane videos: bit.ly/Sloane_Numberphile
Brady in Iceland: www.bradyharanblog.com/icelan...
Numberphile is supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Video by Brady Haran and Pete McPartlan
Thanks to the Numberphile Society for fact checking, especially Paul
Patreon: / numberphile
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
Shout out to these Patreon supporters:
Ben Delo
Jeff Straathof
Ken Baron
Yana Chernobilsky
Juan Benet
Andy B
James Bissonette
Jubal John
Jeremy Buchanan
Steve Crutchfield
Ben White
Andrei M Burke
Tracy Parry
Ian George Walker
RAD Donato
Arnas
Bernd Sing
Valentin
Matthew Schuster
Nat Tyce
Alfred Wallace
Ron Hochsprung
Ubiquity Ventures
John Zelinka
Gnare
Alex Khein
Michael Dunworth
Mirik Gogri
Kannan Stanz
Heather Liu
Doug Hoffman
Xavier F. G.
John Loach 
Наука
![[DEBUT STREAM] It's wind-up time!! #hololiveEnglish #holoJustice](http://i.ytimg.com/vi/p_ZQs-kgUKI/mqdefault.jpg)
Correction at 4:08… Neil says “then we get twice 61" instead of “about twice 61". The actual result is 120, not 122 as labelled.
If his eyes were closed, he could make that correction without making a fuss about it.
@@yoram_snir he was showing off by doing it with his eyes open.
... obviously... ?! ...
Also, it's Iceland and not Icleand like mentioned at 0:10 ;)
As explained at 18:25, you (most typically) COME from twice the prime whenever you hit a prime.
I.e. the sequence being 2*61, some odd 160-ish number, 61, some even number around 2*61 that happens to be divisible by 3 and 5 (call this X), 61 times the smallest number that is coprime to X (61*7).
Or you could come from 3 times the prime, with the sequence being 3*67, some even number just under 2*67, 67, some even number below or just above 2*67 (call this X) which happens to be divisible by 3, the smallest number that is coprime to X times 67 (5*67).
man, "always choose the smallest option" is both the only sensible way to make it a unique sequence and also does so much work in the proof. I love how beautiful and intuitive this makes this proof.
It's also the most convenient for if you want to write a Python script to find you the permutation of length n, where a while loop can always start at 4 and iterate by 1 each time it checks for a compliant number. The FIRST number it finds each time will always be the smallest. Run this same loop inside a for loop that iterates for n-3 times, et voila!
N-3 because we get for free that for n < 4, a(n)= n?
I love that you are mostly actually showing his writing instead of just showing the animation of it in this one. It fits.
The best part is Neil’s evil laugh after “Step five…yes…” 11:21
Seeing him smile when you ask if it's predictable, or if its non-predictable, was so heart warming, made me smile, I love the fact that numbers and rules can be real once explained why it's great.
This is how we should teach math, explaining why its cool first, then get into details. Shame math growing up is quite lame. At least the teachers/experiments that could be done like science.
Man, watching videos with Neil in them is like listening to a math lesson narrated by Bob Ross. It's super interesting and I feel all warm and fuzzy just by listening to him
His voice and talking style do seem to have an ASMR-ready kind of appeal for sure. But only when talking about math!
Leo?
@@simongran5611 Hallå där, Simon! Det var länge sedan! Vilket sammanträffande att stöta på dig här! :D
He's among my favourite Numberphile contributors. Also, I think it's adorable how he drops some details because of sheer excitement :3
Imagine Neil with a Bob Ross wig.
I really like the way this proof keeps building into successively stronger results at each step. "smallest legal term" is the simple and obvious way to define the sequence, but magically makes proving its properties easy
TIL the British pronunciation of geyser is "geezer" (which also means an old man). The American pronunciation is with a long I, so "gizer" or "guy-zer".
And American geezers are old men, but usually emphasize like "You Old Geezer"
I [and this is a personal pedantic thing, being an íslandophile] feel it should be pronounced in English "Gayseer" - as the root of the English word is the icelandic "Geysir" - pronounced in icelandic as [almost] "Cayseer" [ˈceiːsɪr̥] , the name given to the Icelandic one of that name - from the verb for "gush" - [ís: gusa], which used to errupt near to Strokkur [the geysir shown in the video of iceland] before becoming unstable and now very rare to errupt.
But I am quite picky, so :))
I wonder if that is like Caesar vs Kaiser
@@terencetsang9518 Yes. The original Latin was something like "GAEH-sarr" (using "g" instead of "c/k" to indicate that it's not an aspirated plosive like "c/k" would be in English, but sounds much more like a "g"). The "ae" represents two separate and pure vowels spoken together, not a diphthong. The "rr" represents a trilled, tip-of-the-tongue "r" sound, like in Spanish. The modern "SEE-sur" is wildly different from Classical Latin.
@@mytube001 And the two words are not etymologically related. "Geyser" is related to "gush" (thank you, Ingie!), but "Caesar" is related to "scissors" and other words meaning "to cut". Leading to the legend (probably not true) that Caesar was born by Caesarian section, i.e., cut from his mother's womb.
hell yeah more neil sloane
Seriously a treasure. Anytime I see him, Hannah Fry, or Ed Copeland, instant watch
I am really glad there are people who enjoy math and can perform such feats, but there is no way that I could ever put the effort into creating such a sequence. Bravo to you!
Professor: It's all done with simple math.
Me: (Lost within 20 seconds)
See brilliant.org/numberphile for Brilliant and get 20% off their premium service (episode sponsor)
More Neil Sloane videos: bit.ly/Sloane_Numberphile
I'm not sure if you realized, but the video contains multiple errors (in editing) that make it, in my humble opinion, worth revisiting for a "director's cut". I made a comment explaining just some of the issues.
3708.g
Always excited when there's a new video out!
I had a lot of fun stopping the video each time Neil revealed a step to try and prove it myself! 😊 thanks for the video Brady!
I wish they'd colored the terms that are inputs vs the outputs differently. Then it'd be easier to follow for me. I'll definitely have to rewatch this a few times to full grasp the proof.
I have some points of confusion about the proof. I tried giving my own interpretations below, but hopefully, someone can explain these points.
6:20 Why 15 times q? I feel like whatever the second-to-last term is should replace "15" here.
8:09 Do the visuals match what Sloane said? I think the visuals are saying "p appears in the sequence, and every term after is composite," which I don't think relates to anything. I feel like it might make more sense if Sloane is saying "no primes greater than or equal to p divide any term in the entire sequence."
9:10 Why must the GCD be a prime number? It might make more sense if the GCD could be composite, and q is just any prime number that divides the GCD. In that case, it is still true to say that qp is not in the sequence, but it satisfies the requirements for being in position n, so a(n)
Thanks, 6:20 confused me as well, didn't understand the choice for 15., using the second to last makes much more sense.
@@eithan Yes, I guess second-to-last * q works for this part of the proof. It might not be legal, in the sense that it might not be the smallest possible value, but the same is true for 15! And if the second last term doesn't have a 3 or 5 as a factor, 15 is invalid anyway.
@@silver6054 Yeah, the claim is not that it's the smallest possible. We are just showing that at least one value works, and therefore there must be a minimum working value.
At 12:55, a(k+2) could be smaller than p, but it can't be any bigger, and this can only happen p times before you run out of numbers smaller than p.
(I agree it's a missing link but I enjoyed puzzling it out.)
9:10 Yes, and in fact saying gcd here is a mistake. He should've said "a prime factor" instead - then it works.
He says it's easy, but it might be the hardest proof on this channel. Following subtle logic and actually understanding why every step is correct is much, _much_ harder than even a very difficult calculation. It's the difference between creative insights and cranking an algorithmic handle.
I think some of the proofs that Professor Stankova has demonstrated may be more difficult (especially that famous IMO problem), since they have the same level of creative insight with some tougher math. But I also agree that Sloane might be underestimating how tricky this one is!
He goes a bit fast, but if you stop the video and think about each step, it's actually pretty easy. Which is a lot of fun! Several very simple steps in a row - each one of which is obvious when you stop and think about it - combine into something that is not obvious at all.
@@PhilBagels I think it was Alexander Grothendieck who once said: Don't try to prove anything that isn't almost obvious.
@@PhilBagels True, and the right up on OEID is a lot easier to follow (the W and L function are confusing IMO). But, all that being the case, saying that something is obvious _if and only if you stop to think about its explanation_ is just the same as saying that it isn't obvious! Which is just another form of that old truism that all questions are easy when you know the answer.
There's one about circles presented by the curly-haired Aussie guy which I absolutely could not wrap my head around after multiple viewings.
Q.E.D. - "Quod Erat Demonstrandum" - "which was to be demonstrated." Or a small filled box after the written proof.
This man is a gift.
I have to admit I couldn't follow this proof - although I'm sure I could if I were reading it from a paper. This is unusual, though! Most of Neil's videos are easy to follow along with. The sequences he parades before us are like circus acts, and he is the ringmaster... he even has Big Top wallpaper 😉
That makes two of us.
What I didn't follow from the video is how a(n) > p^2 > qp for n-2 > L(p^2) was a contradiction.
Just because we prove that a(n) is larger than a smaller thing doesn't mean that it's not still larger than the larger thing.
I'll think on it more and probably figure it out, but he could've elaborated better there. I do usually understand his explanations.
@@DreamprismHe starts by looking at some a(n) bigger than p^2. Under the assumption that no prime p or bigger appears as a factor of any number in the sequence, a(n) has some prime factor q < p (which it shares with a(n-2)).
So let a(n)=Mq for some integer M. We have Mq > p^2.
However, by assumption, pq never appears in the sequence (since no term is divisible by the prime p or bigger). But pq < p^2 which means pq < Mq.
Now, remember one of the defining properties of the sequence: pick the SMALLEST POSSIBLE number that fits the other rules. pq certainly fits the other rules - it shares a factor of q with a(n-2) and it has no factors in common with a(n-1).
Therefore, we should have that a(n)=qp. But we assumed p didn't appear as a factor of any number in the sequence. Contradiction. And since p was arbitrary, we contradicted the assumption there was a largest prime that appears as a factor.
Try starting with the final two steps, taking for granted the assumptions that are proven in the previous ones, and then go back.
Yeah. Sometimes Neil is too quick for even himself and makes some mistakes or misses some important detail. The OEIS has a clean proof.
Predictable in the same sense that the primes are predictable, so not predictable, but in away predictable... LOVE IT !
You say "geezer", I say "guyzer". I love these videos, and the extra nuggets like the differences between British and American English.
At 4:08, doesn’t 61 followed by 122 break the relatively prime rule?
Yes it will break. They got the value wrong in the video. I checked it in the sequence wiki. It's not 122, it's 120
...
131 159
*132 61*
*133 120*
*134 427*
135 124
...
As a Texan, this man appears to live at Whataburger
Neil's delight is infectious.
I like how this guy works in the corner of a circus tent. Awesome video as always! Thank You!
Neil really is my favorite guest on this channel. Just so many interesting insights and patterns to explore
6:23 how can you be sure that the term one back won't have 3 and/or 5 as factors?
that also buffles me ..
Yeah I think there are a couple of flaws in the proof as he laid it out. When he was talking about the gcd he didn't actually show that the gcd was a prime number, for instance, he just assumed it.
I looked at the OEIS page and actually it was a(n-2)*q rather than 15*q.
Yeah I thought the same. My assumption is that something went wrong in the editing, and he's actually talking about some particular example where 15 actually works. But that's just a guess though - it absolutely can't work in general (after 15 itself, for example).
@@LaytonBehelit Thanks, that makes a lot more sense!
I love how he is basically the grandpa of math youtube ❤
Love this guy, his voice is very calming
I like the geyser illustration/animation.
Great video. Just noting that this should be added to the "Neil Sloane on Numberphile" playlist.
Neil Sloane has incredible insight.
Very entertaining and beautiful video.
2:15 the way he said “nine” was really really funny lol
Lovely sequence but got to say i have to re watch this when I'm not on the train to work
"Five... heh-heh-heh-heh... Yes." - Neil Sloane
Fascinating!
Fascinating
Could you please do a video about OEIS A068869 "smallest number k such that n! + k is a square" and explain why for n = 1,4,5,6,7,8,9,10,11,13,14,15 & 16, k itself is also a square. And while you're there, can you explain why for when n = 12, k is not a square? I think it's pretty curious and would love to know what's going on there. Thanks!
I guess that among all the ways to express n! as the product of two integer factors, the way where the factors are closest is likely to be two even numbers, just because powers of 2 are so abundant in n!. And (x-k)(x+k)+k^2=x^2.
@@rosiefay7283 I'm not sure I know what you mean
11:03 Thank you Brady for trying to keep him honest.
Love you guys
7 steps is not simple.
This is brilliant! No matter how bad my insomnia, that smooth voice never fails..
Neil is a gem. Shiny bright bro, you light up the world!
I didn't need to click this video to know that it would be Neil Sloane showing us this bizarre and wonderful sequence
I have fallen asleep many times watching these videos. (No offense, I love the videos lol) Today i'm gonna put these on autoplay so I can fall asleep faster to wake up early for school.
It may seem strange for Neil to have said that this proof can be done with your eyes closed, but it actually makes perfect sense. The proof has 7 steps, but as long as you have a decent memory, you can remember the outcome of each step, to then complete the next, and each individual step is really just elementary logic and algebra, so it can be done in your head. The only reason it looks complicated in the video is because Neil has to actually explain the intuition to the viewers, and this is obviously more complicated than the proof itself.
*What a beautiful sequence this is! 🌺*
Neil Sloane is the GOAT
At 8:10 he says that "from prime p on, all primes are missing". It's important to the argument that p is *not* in the sequence. But the visuals imply that p is the last prime in the sequence. Confused me for a while, because I thought p was in the sequence and I didn't think his argument made sense.
15:50 I definitely thought for certain that Neil was going to say " I will try to say "Guy-zer", because I am the "gee-zer" here !!
I like, rather obviovus but IMO interesting, conclusion from the fact that all natural numbers appear in the sequence. This is a fancy procedure to shuffle natural numbers.
Hopefully, in 2023, I'd like to dig deeper into the quantitative relationship between the ulam spiral and giant primes, and watch a video of your best team independently observing and measuring and discussing these coordinates and at the moment.
I like that this man works inside a Whataburger bag.
Series is definite.
What a beautiful proof!
I really enjoy the OEIS videos. I got a sequence accepted a few years ago (A328225) after one of these videos. This just reminded me that I never figured out why my sequence looked the way it did when it was plotted. I would love to hear some thoughts. I am not a mathematician in any form, so it could be absolutely nothing.
How did you generate the sequence?
@@spaceyote7174 I was just playing around with some code I was working on and I stumbled across the sequence.
I think your graphics for step 3 are wrong. At 8:10 you show _p_ as being in the sequence, but the proof's assumption (explained correctly in the voiceover) is that _p_ *doesn't* appear in the sequence.
To be more exact, the assumption is: for any number that appears in the sequence _a(n),_ the prime factorization of _a(n)_ includes only primes that are strictly smaller than _p_ .
In particular, _p_ itself doesn't appear in the sequence, because its prime factorization is just _p_ meaning that it includes the primes we forbade.
I think you phrased the assumption as: suppose p is the first prime that doesn't appear. But I think Sloane is phrasing it as: suppose p is the largest prime that *does* appear.
@@jacemandt The exact phrasing is, emphasis mine:
> Proof: suppose not. Suppose *[from] prime p on, all primes are missing.* [... Something lost in editing ...] and from then on, all the terms are *products of primes less than p.*
"p on" (inclusive) are missing
"terms are products of primes less than p" (less than p, not including p)
The rest of the proof also seems to work only if p does not appear in the sequence.
Yes, thank you! It is quite important that p itself not appear in the first place. This caused me much confusion.
@@NeatNit I don't understand the step where he says that gcd(a(n),a(n-2)) has to be a prime.
@@thephysicistcuber175 At what point does he say or assume that? I think he just says that it has to be >1.
5.37 If I close my eyes to work it out I'm not waking up!
Impossible to click play fast enough on a Neil video
I presume starting with 1,2,3 rather than 1,2 is required because of the special nature of 1 having no non-unit factors.
That means I could start the sequence with any two seeds that are non-unit and coprime.
Will the sequence eventually evolve into the same sequence as the one that starts with 1,2,3?
If so, can you predict how long it will take to do so based on the values of the two seed numbers?
I'd have thought 7 could never find its way back in the series
Hasn't he got a lovely soothing voice?
It’s a brilliant proof. Simple, but not obvious, and completely accessible to anyone once they see it.
btw this video isnt in your guys' neil sloane playlist! i recently went through the whole playlist and was sad there wasnt more, but then i found out there was
Thank
How do people find these sequences? Do they just write down random rules until something interesting appears?
4:11 isn't that wrong? After 61 we can't have 122, because obviously gcd(61,122) = 2. According to the OEIS the next term is 120.
True. Quoting from another comment by Arun S R:
Yes it will break. They got the value wrong in the video. I checked it in the sequence wiki. It's not 122, it's 120
128 110
129 177
130 122
131 159
132 61
133 120
134 427
135 124
136 183
gcd(61,122) = 61
But your point stands
@@Gna-rn7zx Of course, thanks.
20:17 - JAMES BISSONETTE!!!
History Matters AND Numberphile, the man has exquisite taste in Patreon subs.
Is there a mistake here or am I missing something?
0:55 Two numbers next to each other must be "relatively prime" (gcd = 1)
4:08 you have the prime 61 next to a 122. That would mean they have a gcd of 61, not only 1
Edit: I see someone else's comment found that it was supposed to be 120, not 122. ty internet stranger
"Geezer will appear in a different video..." LOL that was great.
This is *not a permutation* - it is *definitely a convolution.*
Triangular relationship between triangles in step1,step2,step3.
At 6:22 it feels like something got edited out, since what he says doesn't make sense in general. Maybe he was talking about an example where the second to last term was specifically 15? (Always multiplying the second to last term by some big prime should work in general for what he's doing in that step)
I noticed this time that Neil's ceiling wallpaper looks like the Whataburger stripes!
Step 1 of the proof seems incomplete. Consider a(6): 15·q, for some large prime q, is not a candidate for n=6, because it shares a factor with a(5)=9, and also because it *doesn't* share a factor with a(4)=4.
Am I missing something here?
Edit: the 15 is the error, see comment below
Yeah what he said is just wrong, but easily fixable. We can generate a possible value for a(n) by picking a large prime q and using a(n-2)·q.
Ah, I see. That candidate clearly shares a factor with a(n-2), and so the only factor it might share with a(n-1) is q, but we can pick q large enough so that doesn't happen.
1:44 As a computer scientist, the easier way to frame this is that the penultimate term generates an ascending list of viable candidates (thus terminating at first success), and the ultimate term acts as a filter, accepting only a subset.
More specifically, the unique factors of the penultimate term each generate a simple multiplicative sequence, and you need to perform an efficient online merge sort. This can be accomplished by maintaining a heap (data structure) containing the next term for each unique factor, then you pick the smallest of these replacing it in the heap by the next term for that factor. You can do pop/push (replacement) in a single logarithmic rebalance.
Adding more sophistication, you can process several small factors in parallel more efficiently with bit vectors. But the actual runtime in the hybrid model would depend on the distribution of primes (modulo this strange sequence generation process). I suspect the distribution of primes has been studied, but I'm a computer scientist, so what do I know?
Edit: I wasn't clear on this, but you also have to filter on numbers previously used.
Anything with primes has ths tension between predictable and unpredictable!
This is the craziest permutation of the integers I have seen - going to work through that proof on my own sheet of paper.
He's like a magician producing a rabbit, you don't know how they came up with the proof and he's justifiably smug about it.
What if we have different starting terms instead of 1,2,3
Amazing ! A video about the Yellowstone permutation with Neil in the role of the Old Faithful (to the number sequences) !
(admiring joke, no offence)
*Numberphile drops*
Me: “Cool! Let’s check it out”
*it’s Neil*
Me: *visible happiness mixed with euphoric screaming*
Find you someone who loves you the way Neil Sloane loves numbers.
Brilliant.
That must be interesting
Really cool sequence, but the proof of permutation moved far too quickly for a numberphile video. I plan to come back to this again later.
Neil Sloane: "You can do it with your eyes closed"
CC bot: "Therefore every poem divides infinitely many terms"
You should make a video about 52!, the number of ways a deck of cards can be arranged, and talk about Scott Czepiels representation of the size of it. It’s very interesting. Vsause has a clip from a video about it. It would be a great topic for the channel.
They've definitely done a video on it
I don't understand much of these numerical videos but it's still super intriguing to watch, thanks 🧮
I like the idea of recording this inside a Whataburger restaurant with the orange and white stripes, but there aren't any in Wyoming.
202 = 2 x 101
101 = 1 x 101
505 = 5 x 101
and W(101)=215
Just matches up perfectly. It's great.
Man, Icleand sure is pretty. Looks a lot like Iceland, really. (0:07)
They are never going to run out of math problems
Why did they interrupt the Theorem part for a commercial??
Could you use the fundamental theorem of arithmetic to prove this as well? Since every positive whole number can be written as a product of primes
If all prime's 'cause' geysers, can one not work back from geysers to find primes?
Wow. I totally couldn’t follow this one. I was lost in the weeds before the halfway point.
Oh, sure, I could totally do this in my head with my eyes closed.
/s
4:10 I am not quite understand, doesn't the next term must be co-prime with previous term, but 122 and 61 have common factor of 61? Am I missing something?
Edit: I saw numberphile's comment, thanks for the clarification.
after all this i'm just wondering what happens if you put different starting configurations, like maybe 1, 1, 1 could be interesting
1, 1, 1, can't work, because the next step has to be relatively prime with 1 and also have a common factor with 1. Something's gotta give there. But you could try starting with 1, 3, 2, or 1, 2, 5, or 1, 3, 5, etc. Since you're always adding on the lowest number that works, you'll still always get every number. Let's see now, 1, 3, 2, would continue with 9, 4, 15, 8, 5, 6, 25, 12, 35, 16, 7, ...
@@PhilBagels yeah i didn't think of that, i do still think those other ones would be interesting though
Endofprimes