This sequence has several interesting applications.
Here is one of them:
Say there are 8 tasty cookies, all of different sizes. Both Alice and Bob 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:
Replaced "% 2" wth "& 1".
See below for a fast ASM version of ThueMorse() by wilbert.
Code: Select all
; 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) & 1
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) & 1]
*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")