The Thue-Morse Sequence (with visualizations)

Рет қаралды 4,754

Күн бұрын

In this video, we introduce the Prouhet-Thue-Morse sequence, which is a binary sequence. We discuss three methods to construct the sequence and then investigate some of the sequence's properties (including why it is the "fair sharing" sequence, the overlap-free property, its connection to a square-free sequence, how to use the sequence to build the Koch curve, it's connection to the Prouhet-Tarry-Escott problem, and an intriguing related infinite product representation of the square root of 2).
If you like this video, please consider subscribing to my channel and let me know in the comments if you'd like to see more like this.
The content for this video was taken from the amazing survey paper "The ubiquitous Prouhet-Thue-Morse sequence" by Jean-Paul Allouche and Jeffrey Shallit: cs.uwaterloo.ca/~shallit/Pape... . The paper includes many more facts of this truly remarkable sequence.
Here is a wonderful video from ‪@standupmaths‬ describing many of the same properties: • The Fairest Sharing Se...
#math #manim #sequence #integersequence #binary #thuemorse #thue #morse #fractal #kochcurve #roottwo #fairsharing
To learn more about animating with manim, check out:
manim.community
_______________________________________
Background Music:
Undercover Vampire Policeman by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. creativecommons.org/licenses/...
Source: chriszabriskie.com/uvp/
Artist: chriszabriskie.com/

Пікірлер: 59

@magicdatabase Жыл бұрын

You had me saying "W H A T?" about every other minute watching this video. This stuff is incredible.

@MathVisualProofs Жыл бұрын

Super cool sequence right?

@benjaminlum5894 Жыл бұрын

Good to know I'm not the only one XD

@mostly_mental Жыл бұрын

Thue-Morse is definitely my favorite sequence, and I learn something new every time I run across it. Great to see it illustrated so well.

@MathVisualProofs Жыл бұрын

Thank you. It is definitely an amazing one.

@theemeraldprogamer731 2 ай бұрын

This will make me cry and NOT tears of joy

@EtienneGracque Жыл бұрын

I first heard about the Thue-Morse sequence in a Numberphile video, but it barely scratched the surface. You took that to a whole new level! You should do a follow-up video called "more amazing marvels on the Thue-Morse sequence", I want to learn more!

@MathVisualProofs Жыл бұрын

I haven’t seen the numberphile one. I’ll check it out. @standupmaths has a great video about it. I’ll see if I can follow up with more stuff. Check the linked paper too :)

@EtienneGracque Жыл бұрын

@@MathVisualProofs My bad, it was Good Old Matt Parker indeed. Sorry about the confusion.

@MathVisualProofs Жыл бұрын

@@EtienneGracque no worries. That is a great video (like all of his).

@Adityarm.08 5 ай бұрын

Very insightful, thank you! Nothing could be more intellectually satisfying for me. I've always been obsessed with symmetry & developed this habit of chewing food according to this sequence when I was very young - trying to keep the load balanced on my left vs right molars. Just typed the first 16 terms on OEIS today & landed here. Glad to have found your channel along the way :)

@MathVisualProofs 5 ай бұрын

Thanks for checking it out!

@benjaminlum5894 Жыл бұрын

The most mindboggling thing to me is the end, where people have discovered the limit of P but not Q. Feels like a half proof waiting to be fully solved. Exciting times!

@MathVisualProofs Жыл бұрын

So cool right?

@MathPhysicsEngineering Жыл бұрын

I came back to watch this for the second time! You have done an incredible job! This video truley deserves to get over a million views! The fact that this video got only 3.2k views over 7 month only shows how unfair youtube's algorithm. It promotes only channels that are already big! Though I have to say that with your quality contenet you mannaged to get nearly 70k subscribers. You should get more views from subscribers. Good luck, I will be following your channel.

@MathVisualProofs Жыл бұрын

Thanks for the comment! I don't know how the algorithm works - I suppose I really need to improve my thumbnails and title game :) The subscriber growth seems to have come from KZfaq Shorts, but those don't translate to views on the wider, high definition videos. Anyway, thank you for your comment and hope you keep up with your content as well!

@searge123searge 9 ай бұрын

Was working on mathematical stuff for over a year but couldn't find anything similar to it. Today someone told me about the thue-morse sequence and it really is just the same thing. This makes me very happy.

@MathVisualProofs 9 ай бұрын

Such cool math right? Have you followed the linked paper then from Shallit and Allouche?

@searge123searge 9 ай бұрын

@@MathVisualProofs Yes, cool math indeed! And yes, I read the paper after watching the video. In addition, there are some weird things going on, specifically when doing operations with numbers inside of the fraction, that I haven't been able to find described by somebody else. Cheers!

@youngcwel Жыл бұрын

can't believe you are so unpopular, you're really underrated, I hope you succeed

@MathVisualProofs Жыл бұрын

Thanks!

@bahachicken89 Жыл бұрын

wow, I used to this and still do this ever since I was 13-14, I do taps with my left and right hands. firs I do LRRL then I imagine L=LRRL and R=RLLR, so what I had done isn't LRRL but is actually just L so I complete the LRRL sequence which is now LRRLRLLRRLLRLRRL so the sequence is now complete, but actually not because now I imagine that L=LRRLRLLRRLLRLRR and R=RLLRLRRLLRRLRLLR so I didn't complete the sequence of LRRL, I only completed step 1. and I go as far as I can before messing up. just realized now that this is actually a thing. wow. I also used to constantly double in my head starting from 1 before I learned about powers, this moment really reminds me that moment.

@Bob_the_Jedi Жыл бұрын

Found you from my recommendations, perhaps the algorithm has discovered you. Very interesting video.

@MathVisualProofs Жыл бұрын

Thanks for clicking and checking it out !

@horlickminton6534 Жыл бұрын

I don’t know how this guy does it but he has the best math videos on KZfaq. And I love his voice. I would marry this guy 🧠😍

@MathVisualProofs Жыл бұрын

thanks!

@Adityarm.08 4 ай бұрын

Thanks!

@MathVisualProofs 4 ай бұрын

Wow! Glad you liked the video. Thanks for the visit and support!

@jakobthomsen1595 11 ай бұрын

Amazing!

@MathVisualProofs 11 ай бұрын

Thanks!

@user-cz4ou7ve6x 4 ай бұрын

To add to your cool list of properties of the Thue-Morse sequence, I've just come across another one: "An Un-mixable Packet of Playing Cards" (relative to virtually every systematic shuffling procedure used today)! While studying the properties of "Cyclic, Mirrored, and AMP structures," Kent Bessey (a professor at BYU, I believe) discovered an infinite number of portions (i.e., sections) of the Thue-Morse sequence that give rise to packet structures of playing cards that are invariant under nearly all of the common systematic shuffling procedures people use to mix cards. In fact, here is a link to the playlist of video presentations that discuss this discovery and some of the applications to mathematical card magic: kzfaq.info/sun/PLz_0A1YUkZzhfz3LV7hRjQ96yuTpr6EyL

@columbus8myhw Жыл бұрын

I'm curious about playing "Thue-Morse chess": the player to move is determined by a Thue-Morse sequence (white, then black, then black, then white, then black…) For extra fun, shift the Thue-Morse sequence by a random offset and don't declare whose move it will be in advance.

@MathVisualProofs Жыл бұрын

Check these slides: cs.uwaterloo.ca/~shallit/Talks/green3.pdf. Infinite chess with tm is a thing.

@youngcwel Жыл бұрын

7:53 I literally cried there LMAOO😭😭

@MathVisualProofs Жыл бұрын

😀👍

@fawzibriedj4441 5 ай бұрын

When I saw the Koch curve, I thought "This must be a joke..."

@wieneryron Жыл бұрын

Interesting! Re the Koch Snowflake: What happens when if you let that sequence go out to infinity? I am guessing the turtle plot eventually loops back around so that the full snowflake is outlined (although maybe not! maybe we are just looking at an infinitesimally small portion of the curve(??)). But if it does loop back around and since there's no repetition (and thus no overlap of the turtle path), then does each loop around add to the chaotic "roughness" of the snowflake? And if so, does this path actually converge to the true snowflake in the limit? Ie, does it become the fractal?

@MathVisualProofs Жыл бұрын

Good questions. I haven't spent a lot of time looking at the details of the results, but the short answer to your questions is "yes". Here is a paper that surveys some of the ideas: arxiv.org/pdf/math/0610791.pdf (I can't find the cited Holdner/Ma paper not behind a paywall, but that would be a good one to check out too).

@columbus8myhw Жыл бұрын

I'm fairly certain it doesn't loop around, it just keeps on growing

@MathVisualProofs Жыл бұрын

@@columbus8myhw yes. I am not sure as well. I haven’t read the papers I mentioned well enough to know why they mention the snowflake (and Parker’s video, linked, mentions same thing)… maybe one day I’ll spend more time. Here I just wanted to see it drawn :)

@dayhill9855 9 ай бұрын

Ultimately we can only discern/perceive a pattern based on the current perspective of zooming out, ultimately infinity means the pattern we see could actually be just a small part of the true repeating pattern that could be completely different than the snowflake currently seen, or it could not even have a repeating pattern at all.

@dayhill9855 9 ай бұрын

So just so I know for the combinatorial property of 0w0w0 or 1w1w1 can w be as simple as just 0 or just 1 or does a binary word have to have so many digits to be a binary word?

@MathVisualProofs 9 ай бұрын

Even just 0 or 1 works (even empty word). Pretty cool right?

@dayhill9855 9 ай бұрын

@@MathVisualProofs so even 111 or 000 will never be there? Interestingly I've always been intrinsically fascinated with this sequence pattern and have severe OCD disorders and upon finding out it actually has a name I notice many people with OCD say the same that this pattern is intrinsically in them, I think there's a link with it and OCD.

@MathVisualProofs 9 ай бұрын

@@dayhill9855 Right, those strings don't appear. If one of them did, it wouldn't be the fair sharing sequence anymore because the one person involved would get an extra item at one point and would have more 2 more than the other person for a short moment (whereas the idea is that each person has either the same number of choices at any given point or just one more than the other; and they each spend similar time with the lead of one).

@muqtarjamaegal6071 Жыл бұрын

I watched 3blue 1brown but I understand here you are hero please calculus

@MathVisualProofs Жыл бұрын

What kinds of calculus would you like to see? Not as easy to work visual proofs in

@strictmec4139 2 ай бұрын

Not me thinking of using this in gambling 😂

@matteoaldegani228 Жыл бұрын

Q=1/P=(2)^(1/2)

@MathVisualProofs Жыл бұрын

This doesn’t follow. Q is unknown still as far as I can tell.

@phiarchitect Жыл бұрын

I wonder if Fibonacci is hiding in there somewhere?

@MathVisualProofs Жыл бұрын

I don't think so. Though there is a related Fibonacci word.

@ibrahim_raven1701 Жыл бұрын

200mg of Modafinil lead me here.

@MathVisualProofs Жыл бұрын

Thanks for checking it out

@ibrahim_raven1701 Жыл бұрын

@@MathVisualProofs .-- . .-.. -.-. --- -- .

@kafkaontheshore9102 Жыл бұрын

How is this useful? Can't you just make player 2 take 2 on their turn and then 1 therefore?

@MathVisualProofs Жыл бұрын

This shows how you should do multiple rounds. So yes, player 1 goes then player 2 goes twice. Then player 1 goes once, then player 2 goes once, then player 1 goes twice and player 2 goes 1, etc.