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!
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
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.
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
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!
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".
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 :))
@@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.
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 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.
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)
@@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.)
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.
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 😉
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.
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.
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
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 ...
I was actually able to prove this myself (pausing the video) - quite fun My proof was very similar to the shown one but what Neil showed had some ingenious ideas that made the proof shorter and prettier Thank you very much!
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.
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.
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).
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.
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.
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.
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.
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
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
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.
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 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?
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
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.
Yo - I don't follow his argument for step 5 - he says whenever you use q you could use p^10^6 as its smaller than q, but your number also needs to share a common factor with the number two before it, so what if the number two before it has a common factor with q but not with p^10^6 - is there something I'm missing here? Thanks
Also in step 6 I follow his reasoning but I think he's missed out some steps. H could have another factor which is less than p, but as there are infinitely many products of p in the sequence, eventually you will necessarily come to a p where the largest factor of H which hasn't yet been seen will be greater than p
Yeah i got confused too, but it's when you use q as a factor of a new number. So you have a(n-2), a(n-1), q*n where n is a number with shared factors with a(n-2), and that's actually the only way primes can appear. In this case you can use n*p^10^6 instead.
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.
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.
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.
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.
If you consider Randell L Mills cosmology that mass/energy are only half of quanta's game, that all of this is restricted to this, the present r-sphere until particle annihilation, then, how do we get all of this to be fully contained, to neutralize and move on? I think Sloane is onto it.
What I found more interesting than the geyser 35 at 13 is that 12 is the 12th number in the series. How many times is a number itself in this series? I feel this could be another followup discussion.
i.e. the cases where w(m) = m. so far as shown early, it's 1, 2, 3, 4, 12, ... are all cases where w(m) = m. I"m curious as to how often relatively to the sequence does that happen?
We see the sequence plotted out very far @17:49. That the twelfth term is 12 would appear on the red y=x line very early on, but then the blue lines of odds and evens get further from y=x as the sequence proceeds. So if the theory mentioned at the very end can be proven, the one which defines the evens and odds lines based on the pattern break at 101, then you won't get any more results like that after the first terms. This seems like a "strong law of small numbers" thing, where funny things happen with the earlier terms in the sequence because we have relatively few small numbers to work with.
12:01 Neat idea. Every prime-power p^k divides some term, so every prime p divides infinitely many terms. Does it make your proof slicker if you had used the notion of "prime power" instead of "prime" in the first place?
8:17 how can you tell the biggest prime P must be on the list, it is possible W(P) = -1 ( not in the list). It should be a(L(P)), rather than P, it can be very confusing.
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
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.
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.
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
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!
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 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!
This man is a gift.
Professor: It's all done with simple math.
Me: (Lost within 20 seconds)
Always excited when there's a new video out!
Neil's delight is infectious.
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.
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.
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
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.
Great video. Just noting that this should be added to the "Neil Sloane on Numberphile" playlist.
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.
Q.E.D. - "Quod Erat Demonstrandum" - "which was to be demonstrated." Or a small filled box after the written proof.
Neil really is my favorite guest on this channel. Just so many interesting insights and patterns to explore
I like how this guy works in the corner of a circus tent. Awesome video as always! Thank You!
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.
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
Neil Sloane has incredible insight.
I love how he is basically the grandpa of math youtube ❤
11:03 Thank you Brady for trying to keep him honest.
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
...
I like the geyser illustration/animation.
I was actually able to prove this myself (pausing the video) - quite fun
My proof was very similar to the shown one but what Neil showed had some ingenious ideas that made the proof shorter and prettier
Thank you very much!
This is brilliant! No matter how bad my insomnia, that smooth voice never fails..
Love this guy, his voice is very calming
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
As a Texan, this man appears to live at Whataburger
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.
I didn't need to click this video to know that it would be Neil Sloane showing us this bizarre and wonderful sequence
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 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.
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
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.
It’s a brilliant proof. Simple, but not obvious, and completely accessible to anyone once they see it.
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 !!
Neil Sloane is the GOAT
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.
"Five... heh-heh-heh-heh... Yes." - Neil Sloane
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.
*Numberphile drops*
Me: “Cool! Let’s check it out”
*it’s Neil*
Me: *visible happiness mixed with euphoric screaming*
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
20:17 - JAMES BISSONETTE!!!
History Matters AND Numberphile, the man has exquisite taste in Patreon subs.
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.
Neil Sloane: "You can do it with your eyes closed"
CC bot: "Therefore every poem divides infinitely many terms"
I like that this man works inside a Whataburger bag.
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.
*What a beautiful sequence this is! 🌺*
Fascinating!
5.37 If I close my eyes to work it out I'm not waking up!
Fascinating
Hasn't he got a lovely soothing voice?
Find you someone who loves you the way Neil Sloane loves numbers.
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)
202 = 2 x 101
101 = 1 x 101
505 = 5 x 101
and W(101)=215
Just matches up perfectly. It's great.
Triangular relationship between triangles in step1,step2,step3.
"Geezer will appear in a different video..." LOL that was great.
Man, Icleand sure is pretty. Looks a lot like Iceland, really. (0:07)
I'd have thought 7 could never find its way back in the series
Very entertaining and beautiful 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?
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.
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.
This is *not a permutation* - it is *definitely a convolution.*
Series is definite.
I like the idea of recording this inside a Whataburger restaurant with the orange and white stripes, but there aren't any in Wyoming.
Oh, sure, I could totally do this in my head with my eyes closed.
/s
I noticed this time that Neil's ceiling wallpaper looks like the Whataburger stripes!
Love you guys
505 (SOS) being the first disruption to the sequence is divine levels of spook.
Impossible to click play fast enough on a Neil video
Yo - I don't follow his argument for step 5 - he says whenever you use q you could use p^10^6 as its smaller than q, but your number also needs to share a common factor with the number two before it, so what if the number two before it has a common factor with q but not with p^10^6 - is there something I'm missing here? Thanks
Also in step 6 I follow his reasoning but I think he's missed out some steps. H could have another factor which is less than p, but as there are infinitely many products of p in the sequence, eventually you will necessarily come to a p where the largest factor of H which hasn't yet been seen will be greater than p
Yeah i got confused too, but it's when you use q as a factor of a new number. So you have a(n-2), a(n-1), q*n where n is a number with shared factors with a(n-2), and that's actually the only way primes can appear. In this case you can use n*p^10^6 instead.
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.
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.
What if we have different starting terms instead of 1,2,3
up next, the case of the cantankerous old geyser!!
Amazing ! A video about the Yellowstone permutation with Neil in the role of the Old Faithful (to the number sequences) !
(admiring joke, no offence)
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.
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
If you consider Randell L Mills cosmology that mass/energy are only half of quanta's game, that all of this is restricted to this, the present r-sphere until particle annihilation, then, how do we get all of this to be fully contained, to neutralize and move on? I think Sloane is onto it.
6:24 What if the last term is divisible by 5 or 3? Then the assumption that 15 q has no divisors in common with its predecessor is incorrect.
What I found more interesting than the geyser 35 at 13 is that 12 is the 12th number in the series. How many times is a number itself in this series? I feel this could be another followup discussion.
i.e. the cases where w(m) = m. so far as shown early, it's 1, 2, 3, 4, 12, ... are all cases where w(m) = m. I"m curious as to how often relatively to the sequence does that happen?
We see the sequence plotted out very far @17:49. That the twelfth term is 12 would appear on the red y=x line very early on, but then the blue lines of odds and evens get further from y=x as the sequence proceeds. So if the theory mentioned at the very end can be proven, the one which defines the evens and odds lines based on the pattern break at 101, then you won't get any more results like that after the first terms.
This seems like a "strong law of small numbers" thing, where funny things happen with the earlier terms in the sequence because we have relatively few small numbers to work with.
I don't understand much of these numerical videos but it's still super intriguing to watch, thanks 🧮
That Monika Lewinsky as Mona Lisa cover picture... That's a prime number 🤣
12:01 Neat idea. Every prime-power p^k divides some term, so every prime p divides infinitely many terms. Does it make your proof slicker if you had used the notion of "prime power" instead of "prime" in the first place?
What a beautiful proof!
7 steps is not simple.
8:17 how can you tell the biggest prime P must be on the list, it is possible W(P) = -1 ( not in the list). It should be a(L(P)), rather than P, it can be very confusing.
Wow. I totally couldn’t follow this one. I was lost in the weeds before the halfway point.