A fact from Thue–Morse sequence appeared on Wikipedia's Main Page in the Did you know column on 28 February 2004. The text of the entry was as follows:
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
To me, the pseudocode was not very clear, especially considering indexOfHighestOneBit was neither implemented nor explained.
Here is my implementation in Python, which uses the "When counting in binary, the digit sum modulo 2 is the Thue–Morse sequence" fact. itertools.count() just counts 0, 1, 2, 3... forever (this could also be written as a while loop to make it into pseudocode). bit_count() calculates the Hamming weight, and & 1 is like taking "modulo 2"/parity.
import itertools
def thue_morse():
for n in itertools.count():
yield n.bit_count() & 1
for b in thue_morse():
print(b, end=", ")
(That's my 1st wikipedia entry so - my apologies if something is wrong...)
In the 'History' section, user 'colosimo' states:
'Also, the sequence was rediscovered in 2000 by 8th grade student John Colosimo, who used it as the perfect order in which participants in turn-taking games could most fairly take turns. It especially applies in games where the players move along a path to reach a desired goal, eliminating any advantage potentially gained by either player by taking the first turn.'
An interesting application for the Thue-Morse Sequence. Congratulations.
However, I searched the web for an evidence of this statement without finding one. There are may other examples of people who 'happened' to re-discovered the Thue-Morse Sequence, so I suggest either to give an evidence (publication) that John Colosimo indeed re-discovered the Thue-Morse Sequence, or to delete the section.
is indeed balanced, though one must concede that most games consist of finite turns, and of those, most are predisposed to granting an unfair advantage to one side or the other, even when attempting to offset that advantage with Thue-Morse, due to the fact that the number of turns tends to most often fall in a fairly narrow band (which can be trivially proven by observing that in a game which typically finishes in a single turn, the first player will have a significant advantage!).
Even in situations where the number of turns is distributed in such a way that it offsets this advantage, many games still give undue benefit to the first player (for example, in Monopoly, if the best properties in the game were the light-blue properties—they aren't—which are available within a single move of the starting point, the first player would have the opportunity to land on such a property and claim it, whereas the second player would have a reduced chance to claim a light-blue property because one of the properties on which he might land has already been claimed). Nonetheless, the described reasoning is much the same as I employed when I discovered Thue-Morse at a very young age. It's worth noting that the first term of Thue-Morse must be discarded when you are attempting to use it to "balance" in this manner. Jouster (whisper) 18:56, 28 November 2007 (UTC)[reply]
I believe this sequence is well known to very many people having the slightest degree of Obsessive Compulsive Disorder. That is because it seems like the most "fair" sequence of things. For a person with OCD, it is often important that if he first turns his head to the right, then he must also turn it to the left. But because having the head turned first is more valuable than last, he must then turn the head to the left again. Then to the right, since the number must be equal. And then the generalization is easy to find.
"It especially applies in games where the players move along a path to reach a desired goal, eliminating any advantage potentially gained by either player by taking the first turn." - Provided that advantages are equally distributed throughout the game, and that the path is infinite... In most games, none of these premises apply, but certainly, in many games these can be taken as approximations. Then the Thue-Morse sequence may balance out most of the advantage. And even when the premises do not apply, the sequence may reduce the unfairness. Consider the situation in which the children are to divide into teams for an informal soccer match. First, the two top players are appointed for choosing. Then they choose one player at at time, following the Thue-Morse sequence. This will balance out part of the advantage of choosing first.
Elias Hasle —Preceding unsigned comment added by 77.40.128.194 (talk) 09:47, 19 October 2009 (UTC)[reply]
I think my addition addresses several of the points made above. It basically provides the mathematical underpinning for the observations of "8th grade student John Colosimo." And it dates to my own OCD behavior governing the order in which I stepped over sidewalk cracks starting around age 9 (in 1959). Robert Richman 01:36, 16 January 2012 (UTC) — Preceding unsigned comment added by Rmrichman (talk • contribs)
BTW: "Since Thue published in German, his work was ignored at first" is nonsense, Einstein also published in German. At that time, you could not just ignore Hilbert's publications because they were in German, or Poincaré's because they were French. (Actually, there is still quite a lot of mathematics being published in French.)--80.136.184.22409:09, 9 July 2007 (UTC)[reply]
This article contains the worst explanation of a sequence I have ever seen.
The beginning of the article shows the first few terms of the sequence with spaces in between some of the bits, making it seem like the first element is 0, the next is 10, etc. when in fact each element of the sequence is just one bit. I have no clue why someone thought this would make the definition comprehensible. I had to read the article several times to figure out what was meant. I demand this be rewritten.— Preceding unsigned comment added by 76.183.88.237 (talk) 04:36, 5 April 2012 (UTC)[reply]
The clue is in the words "binary sequence" in the first sentence, which links to bitstream. However, since using spaces to divide up the sequence into blocks seems to have confused you, I have removed them. Gandalf61 (talk) 08:18, 5 April 2012 (UTC)[reply]
The article uses the term "Thue-Morse sequence" to mean at least three distinct things:
a) the sequence of finite strings 0, 01, 0110, 01101001, 0110100110010110, . . .
b) the successive overlaying of each of those finite strings on the first half of the next, to make one (semi-)infinite string 0110100110010110 . . .
c) the sequence of binary digits occurring in b).
It would be a very good idea if these were disambiguated by being very clear in the article just which one of these is being referred to in any given statement.
The article with its current confusion is very sloppy and hence inappropriate for an encyclopedia article.
acoustic representation of the Thue-Morse sequence as a series of square waves
i added this audio to the article which was removed with the comment "can't see that as being very useful, and it's somewhat unclear how the sequence was being converted to sound anyway". as for the usefulness, i personally wondered what it sounded like and i think it has some musical potential (though, maybe in a less raw form..). as for the second point: 0 is represented by silence, 1 by a square wave. the commons-description shows the method i used. --sofias. (talk) 21:22, 8 April 2019 (UTC)[reply]
From Wikipedia:Image use policy#Adding images to articles, "The purpose of an image is to increase readers' understanding of the article's subject matter, usually by directly depicting people, things, activities, and concepts described in the article. ...". First, I realize this is talking about images and not audio clips, but there doesn't seem to be the same level of policy/guideline detail set out for audio, maybe because it tends to serve a different purpose in articles. But this case isn't about adding a clip of a song to an article about a song, or something like that, so I think the point that the above quote is making is still worth applying. On a side note, without bothering to import this thing and actually look at the waveform, I can't be sure, but there should be periods of sound of equal length with those of silence, and to me, the tones sound longer than the silences. I could be wrong, but there's zero documentation for the utility you pointed to, and that's kind of a problem if it can't be verified. Anyway, that's all kind of beside the point, because even if it were correct, I can't see that it's useful to include. –Deacon Vorbis (carbon • videos) 22:04, 8 April 2019 (UTC)[reply]
Off-topic, but if you want to discuss here, please please have the common courtesy to use capitalization. This isn't just an informal chat room or something, and it does make reading a lot easier. Thanks, –Deacon Vorbis (carbon • videos) 22:11, 8 April 2019 (UTC)[reply]
slower version
I think it gives an impression about what an aperiodic yet highly regular sequence "feels" like, it's a sonification. The periods representing an isolated "1" are as long as the periods representing an isolated "0, the periods representing "11" and "00" are twice as long, accordingly. Perhaps the speed is too fast to pick this up clearly, i made a slower version. I think you are the first person who expressed this preference for capitalization to me. For me it is visual noise, but i try to remember your preference and hope i do it decently. --sofias. (talk) 23:43, 8 April 2019 (UTC)[reply]
article might have original research, and I am actually concerned that the writing might be contrived to direct credit to particular researchers.Rich (talk) 21:46, 27 April 2022 (UTC)[reply]
We can construct the sequence in forward rather than reverse order.
defthue_morse_bits(n):"""Return a string of the first 2**n bits of the Thue-Morse sequence."""bits=0foriinrange(n):bits=((bits+1)<<(1<<i))-(bits+1)returnf"{bits:0{1<<n}b}"[thue_morse_bits(n)forninrange(6)]
We should have at most one implementation and I lean towards having zero, especially as without sources it appears to be WP:OR. I think the other order is more natural so I would prefer not to replace it with this one. —David Eppstein (talk) 18:05, 25 September 2024 (UTC)[reply]
I think of it as WP:CALC rather than WP:OR, but without a good source we haven't verified that it is noteworthy, so we get to the same answer if we don't have consensus: don't do it. Let's see if I can find some worthy source. —Quantling (talk | contribs) 18:13, 25 September 2024 (UTC)[reply]
First source I would search is Arndt's Matters Computational, already used for the other code. If a bit-hacking trick isn't in that source, it probably doesn't have a published source. —David Eppstein (talk) 19:56, 25 September 2024 (UTC)[reply]
Thank you, Arndt is a great addition to my knowledge base. I'll look through it.
Although not justifying our thue_morse_bits program itself, but addressing the reverse vs. forward list of bits: there's something called the parity number, which is a decimal point ("bit point"??) in front of the Thue–Morse sequence of bits, with sequence bits appearing left to right. So, a forward result returned by thue_morse_bits divided by an appropriate power of 2 is a rational approximation of that parity number. That's a small argument in favor of returning the forward pattern. —Quantling (talk | contribs) 21:41, 25 September 2024 (UTC)[reply]
Okay, I admit that this is WP:OR or fails WP:NOTE, until we find some sort of source, but I have it down to four simple operations per iteration for the forward order.
defthue_morse_bits(n):"""Return an int of the first 2**n bits of the Thue-Morse sequence."""bits=0foriinrange(n):bits=~bitsbits=bits-(bits<<(1<<i))returnbits[f"{thue_morse_bits(n):0{1<<n}b}"forninrange(6)]
I did not find a source. :-( Do we have consensus that this forward-string-producing approach is nonetheless okay under WP:CALC? @David Eppstein: Based upon the above conversation, I am thinking that we do not have consensus, but I don't want to go home without first double checking. —Quantling (talk | contribs) 14:58, 4 October 2024 (UTC)[reply]
I think the code is interesting but that it is original research. WP:CALC is for simple numerical calculations like converting pounds to kilograms. It could reasonably apply to producing simple examples of the output of an algorithm. For instance, if we had a source for this algorithm, we could use CALC to justify saying what its output is for n=1,2,3,4. I do not think CALC applies to the description of algorithms themselves. —David Eppstein (talk) 20:54, 4 October 2024 (UTC)[reply]
The WP:CALC section includes 'Mathematical literacy may be necessary to follow a "routine" calculation, particularly for articles on mathematics or in the hard sciences.' which I take to mean that items that are easy for folks with some literacy to understand and verify qualify for this exception. If somehow that changes your "no" to a "yes", please let me know. But having already double checked, I will interpret your silence as a "no". Thank you —Quantling (talk | contribs) 21:08, 4 October 2024 (UTC)[reply]
As far as I can tell, the given "fast" implementation isn't notably fast. The correct measure of the length of a binary sequence is the number of bits of that sequence. By this metric, the given implementation produces a sequence of length in time: the traversal implied by (written as (n ^ (n - 1)) in the code) is , not constant. The "doubling" Python implementation given later is also , I think, so is no slower.
If you are measuring things in bit complexity, the "fast" implementation takes time Theta(n log n) while the "doubling" implementation takes time Theta(n^2). The point you are missing is that to generate the first n items in the sequence, the fast implementation uses numbers whose value is at most n while the doubling implementation uses numbers with n bits (value more like 2^n). —David Eppstein (talk) 17:18, 31 March 2025 (UTC)[reply]
Sorry, misunderstood the "fast" code. The given function computes only a single bit of the sequence, so it looks like to generate a sequence of length using this method.
1M is in the range where the difference between log n word size for the "fast" method and n word size for the "doubling" method is insignificant. —David Eppstein (talk) 17:51, 31 March 2025 (UTC)[reply]
To produce the n-th bit requires a computation on lg(n) bits because that is how many bits it takes to represent the number n. I compute that the cumulative runtime to compute the first n bits is therefore ∑ O(lg n) = O(n lg n). —Quantling (talk | contribs) 17:59, 31 March 2025 (UTC)[reply]
I think I missed something in my previous analysis. The "fast" method performs O(n) bit operations on words of O(log n) bits each, and the "doubling" method performs O(log n) bit operations on words of O(n) bits each. But the doubling method is actually only O(n) in bit complexity, not O(n log n), because the word size it needs increases in a geometric series and it only does O(1) bit operations on the largest word size.
Where these methods really differ is in space usage. The "fast" method also uses only a bounded number of machine words for space. The "doubling" method uses enough words to store n bits. My expectation would be that in a language where performance comparisons are meaningful (not Python) and for big enough n for memory hierarchy issues to matter, the "fast" method will be much faster because it does not need to access main memory to store all those bits. Try n=2^40 or so, implemented in C? It should be possible with the fast method but start bogging down with the doubling method —David Eppstein (talk) 18:29, 31 March 2025 (UTC)[reply]
The slow method — mod-2 counting the number of set bits in the binary expansion of n, for each n independently — is O(n lg n) time and O(lg n) space (to hold n), which is the same as the fast method (except for the multiplicative constant). I guess this just shows that big-O analysis can hide a lot. —Quantling (talk | contribs) 18:59, 31 March 2025 (UTC)[reply]
This suggests that there is an O(n) bit complexity O(log n) space method: just do the naive binary increment algorithm and keep track of the parity of how many bits there are. But of course we would need published sources. —David Eppstein (talk) 19:06, 31 March 2025 (UTC)[reply]
In the discussion of complexity, it is important to keep in mind that is conventionally the size of an integer in bits. So it is not possible to compute the -element sequence in less space than by any offline method.
An online method (that returns a single specified bit of the sequence) could conceivably return a single bit of the sequence in less space. The "fast" algorithm given is online, but I don't think it is especially space-efficient: computing bit of the sequence requires space for its intermediate computation as far as I can tell. It also seems to require time due to the for loop and exclusive-or.
The "fast" algorithm could be modified to be a time space offline algorithm for computing a whole sequence of length by replacing the yield with an adjustment of the value variable: I don't see how to do better.
The "doubling" method uses at most "extra" space and time: one computes to the next power of 2 and then truncates. Thus, doubling appears after some thought to be a time space offline algorithm: each doubling requires linear time in the size of the sequence to be doubled.
Let me check this reasoning with a colleague and get back to you all. Do take a look at my benchmark if you want to see how this plays out in Python.
@Bart Massey I am having trouble following your logic; it could be me or it could be your logic. I don't see any quadratic (or worse) runtime or space requirements.
If we have to have space to store all n output bits then storage will be Ω(n) bits. If we don't have to store them all simultaneously, but do have to store the input variable n then storage will be Ω(lg n) bits. If we don't have to pay to store the input, we might have to store a pointer into the input bit array as a loop variable, which would require Ω(lg lg n) bits — but maybe we can avoid the looping variable by simply marching along a Turing Machine tape.
Runtime for the computation of any one output bit (without relying on having computed others) is going to be Ω(lg n) operations on bits because every bit of the binary representation of n needs to be examined. However, if we are storing all outputs simultaneously then we can reuse what we have already computed, and double the length of the output in time O(n); this results in a total runtime of O(n) + O(n/2) + O(n/4) + O(n/8) + ... = O(n). —Quantling (talk | contribs) 21:23, 31 March 2025 (UTC)[reply]
You are right that any offline algorithm must use bits to store the output. Your analysis of the online problem also looks good. However, the given algorithm for that problem (the "fast" algorithm) does seem to me to use bits and time to compute the -th bit.
You are also right that I botched the runtime analysis of the "doubling" algorithm: your bound of time is correct (and I think tight). Thanks much for the more careful analysis. Bart Massey (talk) 04:46, 1 April 2025 (UTC)[reply]
