In mathematics, the Thue–Morse sequence is the infinite sequence of 0s and 1s (or any other ordered pair of symbols) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings

0 then

01,

0110,

01101001,

0110100110010110 [after

Wikipedia].

This sequence has several interesting applications.

Here is one of them:

Say there are 8 tasty cookies, all of different sizes. Both

**A**lice and

**B**ob want to take the biggest available cookie at any moment. For an allegedly fair procedure, normally they would toss a coin in order to determine who may start, and then they would alternate with taking a cookie. When Alice starts, the sequence looks like this:

**AB AB AB AB**But this is far apart from being fair!

The only fair thing here is tossing the coin. Then, simple alternation means a constant disadvantage of the second one. In each round, the one who selects first gets a bigger cookie than the other one. And when constantly alternating, this is unfairly always the same person!

In contrast, using the first 8 elements of the Thue-Morse sequence will lead to a much fairer procedure:

**AB BA BA AB**Considerations like these play a role in various tournament competitions, such as the kicking sequence of a penalty shoot-out in soccer, the serving order in tennis, and the rotation of color of pieces in a chess match.

The Thue-Morse sequence appears in many other contexts.

For instance, it can also be used for controlling a

Turtle graphics program in order to draw a

Koch snowflake.

For more details and additional interesting information about the Thue-Morse sequence see e.g.

http://blog.zacharyabel.com/tag/thue-morse-sequence/.

//edit:See

below for a fast ASM version of ThueMorse() by wilbert.

**Code:**

; PB 5.31

CompilerIf #PB_Compiler_OS = #PB_OS_Linux

Procedure.l PopCount32 (k.l)

; -- Population count:

; return number of bits that are set to 1 in 'k'

; (after code posted by idle, 2015-05-14:

; http://www.purebasic.fr/english/viewtopic.php?p=465096#p465096

; Thank you!)

;x - (x >> 1) & $55555555

!mov eax, [p.v_k]

!mov edx, eax

!shr edx, 1

!and edx, 0x55555555

!sub eax, edx

;x = (x & $33333333) + ((x >> 2) & $33333333)

!mov edx, eax

!and eax, 0x33333333

!shr edx, 2

!and edx, 0x33333333

!add eax, edx

;x = (x + (x >> 4)) & $0f0f0f0f0f

!mov edx, eax

!shr edx, 4

!add eax, edx

!and eax, 0x0f0f0f0f

;x * 0x01010101 >> 24

!imul eax, 0x01010101

!shr eax, 24

ProcedureReturn ; return the value of eax

EndProcedure

CompilerElse

Procedure.l PopCount32 (k.l)

; -- Population count:

; return number of bits that are set to 1 in 'k'

; (processor and used assembler must support the SSE 4.2 instruction set)

! popcnt eax, [p.v_k]

ProcedureReturn ; return the value of eax

EndProcedure

CompilerEndIf

Procedure.i ThueMorse (k.i)

; -- return value of the Thue-Morse sequence at place 'k' (0 or 1)

; [<http://mathworld.wolfram.com/Thue-MorseSequence.html>, 2015-05-01]

If k < 0

ProcedureReturn -1 ; error

EndIf

ProcedureReturn PopCount32(k) % 2

EndProcedure

Structure CharArray

char.c[0]

EndStructure

Procedure.s ThueMorse_Sequence (n.i, symbols$="01")

; -- return a Thue-Morse sequence of lenght 'n'

Protected last.i, k.i, ret$

Protected *p.Character, *s.CharArray=@symbols$

If n < 1 Or Len(symbols$) <> 2

ProcedureReturn "" ; error

EndIf

ret$ = Space(n)

*p = @ret$

last = n - 1

For k = 0 To last

*p\c = *s\char[PopCount32(k) % 2]

*p + SizeOf(Character)

Next

ProcedureReturn ret$

EndProcedure

; -- Demo

Debug ThueMorse(15)

Debug ThueMorse_Sequence(16)

; The Thue-Morse sequence even has a relationship to music: :D

Debug ThueMorse_Sequence(4, "AB")