0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
January 28, 2016 7:07 AM   Subscribe

Fair sharing, the Thue-Morse sequence, infinitely long chess games, and related ideas. [A light, 10 minute video]
posted by Wolfdog (17 comments total) 12 users marked this as a favorite
 
I'm amazed that this works as a binary parity generator.

Also, if AB-AB allows A to get the first pick of every two, and ABBA-ABBA allows A to get the first pick of every four, then ABBABAAB-ABBABAAB allows A to get the first pick of every 8.
(Which, admittedly is better, but still, why stop at 4?)
posted by MtDewd at 8:05 AM on January 28, 2016


MtDewd - which is why it's not ABBA BAAB ABBA BAAB, it's ABBA BAAB BAAB ABBA.

And then ABBA BAAB BAAB ABBA BAAB ABBA ABBA BAAB and so on - each time you append the original sequence, but with all the As and Bs switched to avoid precisely that problem.
posted by parm at 8:13 AM on January 28, 2016


Saw a very nice Larry Moss talk that started in this neighborhood before blasting off into the far reaches of abstraction.
posted by grobstein at 8:38 AM on January 28, 2016


Okay, I was willing to admit the binary parity thing kind of makes sense. The Koch snowflake though, I did not expect. WTF, math.
posted by sfenders at 8:55 AM on January 28, 2016 [3 favorites]


-it's ABBA BAAB BAAB ABBA.
Sorry, that's what I meant (and 16, not 8), but I thought that was repeated.
What I missed was that the sequence (of 16) is then inverted- I thought it was repeated.
So then that sequence of 32 is inverted if you go to 64?

-Okay, I was willing to admit the binary parity thing kind of makes sense.
So how is that related?
posted by MtDewd at 9:24 AM on January 28, 2016


So then that sequence of 32 is inverted if you go to 64?
Right.
posted by Wolfdog at 10:11 AM on January 28, 2016


So how is that related?

Well maybe someone who understands better will come along, this reminds me of that time in high school I thought I could come up with some novel integer factorization method based on representing numbers in different bases, but... you have 0,1 then you add a bit that makes it 1,0 because parity. Then you have the same sequence repeated again, four more numbers in the series, but swapping ones and zeroes because you've added another bit which reverses the polarity. Then you repeat those 8 bits, but swap zero for one because you've added another bit. And so on, it seems to work out.
posted by sfenders at 10:31 AM on January 28, 2016


Omg I've been really into the Thue-Morse sequence since I was a kid (but I never knew Thue was pronounced that way). I still tap it out with my fingers when I'm bored.
posted by gold-in-green at 1:20 PM on January 28, 2016 [2 favorites]


I never knew Thue was pronounced that way
I don't think it is, actually.
posted by Wolfdog at 1:28 PM on January 28, 2016


So how is that related?
I played around with it for a while, and it's recursive, in a fractal sort of way, like he said (sort of).
So I see it's doing the same thing, but I wonder if it's for the same reason, or if that's just coincidence.
posted by MtDewd at 2:07 PM on January 28, 2016


> I don't think it is, actually.

It shouldn't be, at any rate. The guy in the video says "two-way," but the Norwegian name Thue is pronounced [tʉː] -- not exactly like French tu, but close enough for rock and roll, and definitely one syllable.
posted by languagehat at 2:14 PM on January 28, 2016


More like the "2B" morse sequence, amirite?
posted by grog at 5:00 PM on January 28, 2016 [1 favorite]


Or not 2B.
posted by pattern juggler at 6:14 PM on January 28, 2016


That IS the question.
posted by OverlappingElvis at 6:27 PM on January 28, 2016 [1 favorite]


"The Thue-Morse sequence is a list of if there's odd or even numbers of ones in the binary versions of the integers."

*mind blown*
posted by OverlappingElvis at 6:29 PM on January 28, 2016


"a list of if odd or even numbers of ones in the binary versions of the integers"

Having made such a poor effort to understand and explain this earlier, mind clouded by something or other, I'd like to try again. I mean it's pretty obvious once you see it.

First of all, don't think of "binary versions" of anything, just think of counting in binary. You start with 0,1. To get the next two numbers, you tack a 1 on the front of the first two and get 0, 1, 10, 11. The last digit in the second two numbers follows the same pattern as it did in the first two numbers. Then put another 1 in front to get the next four numbers. The last two digits follow the same pattern as they did in the first four numbers. It's just your perfectly normal method of counting. Each time the number goes up to another digit long it's by adding a 1 on the front, which means it repeats the sequence that came before except with odd swapped with even or B with A. Which is the series we were looking for.

If you wanted to split things fairly between three people, a similar series generated by counting in base 3 and taking the sum of digits mod 3 should probably work reasonably well. 0,1,2, 1,2,0,2,0,1, 1,2,0,2,0,1,0,1,2, 2,0,1,0,1,2,1,2,0. You start with 0,1,2 and then append the same sequence shifted by one, and then shifted by two, and then repeat as needed.
posted by sfenders at 7:24 PM on January 28, 2016 [1 favorite]


First of all, don't think of "binary versions" of anything, just think of counting in binary.

*mind blown*
posted by OverlappingElvis at 7:31 PM on January 28, 2016


« Older The Canadian Library Association has been...   |   Crisis on Infinite '90s Childhoods Newer »


This thread has been archived and is closed to new comments