Prouhet Thue Morse Suite

published: 29 April 2024 / updated 29 April 2024

Lire cette page en français

article: 14 septembre 2019

Preamble

In a video of Numberphile, it's about the number of times the number 3 appears in the numbers. Link to the video:
https://www.youtube.com/watch?v=UfEiJJGv4CE

In binary, we have only the choice between the numbers 0 and 1.

The question is: what can be analyzed in the binary sequences?

An amazing sequence

The numbers from 0 to n, in binary are thus represented:

0   0
1   1
2   10
3   11
4   100
5   101 ....

Let's count the bits that are at 1:

0   0   0
1   1   1
2   10  1   
3   11  2   
4   100 1
5   101 2 ....

Let's see how to automate the counting of these bits to 1:

: binDigitCount ( d --- nb )
    0 >r                \ count of digits "1"
    begin
        over            \ duplicate low signifiant byte
        1 and           \ test lower byte
        if
            r> 1+ >r    \ increment count of digits "1"
        then
        2dup d0>        \ test if not null
    while
        d2/             \ Arithmetic shift right by 1
    repeat
    2drop
    r>  ;

The word binDigitCount processes a double precision number. It runs as follows:

3. bindigitCount . 2  ok
4. binDigitCount . 1  ok

Here is a loop for counting the bits of a sequence of integers from 0 to n:

: countLoop ( n ---)
    0 do
        i . 3 spaces
        i s>d binDigitCount . cr
    loop ;

Execution of countLoop:

16 countLoop 0    0
1    1
2    1
3    2
4    1
5    2
6    2
7    3
8    1
9    2
10    2
11    3
12    2
13    3
14    3
15    4
 ok

s there a hidden pattern in the sequence of bit counts at 1?

The answer is: YES!

I will help you. We must not focus on the future itself, but on numbers that are even or odd:

  0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4....

The Prouhet-Thue-Morse Suite

We will resume the loop, but showing:

• 0 if the number of bits at 1 is even
• 1 if the number of bits at 1 is odd

: PTMloop
    cr
    0 do
        i s>d binDigitCount
        2 mod
        if
            s" 1" type
        else
            s" 0" type
        then
    loop ;

Execution of word PTMloop:

16 PTMloop
0110100110010110 ok
32 PTMloop
01101001100101101001011001101001 ok
64 PTMloop
0110100110010110100101100110100110010110011010010110100110010110 ok

This sequence has a particularity: the non-repetition of the sequences. Let's start from the sequence:

16 PTMloop
0110100110010110

It is found at the beginning of the following sequence:

32 PTMloop
01101001100101101001011001101001

Let's bring back to the next line the other half of the sequence:

32 PTMloop
0110100110010110
1001011001101001

The second half of the sequence is the binary opposite of the first half!

And it's the same for the third sequence:

64 PTMloop
01101001100101101001011001101001
10010110011010010110100110010110

This is how this Prouhet Thue Morse Suite is built:

The size of the footage is growing very, very fast.

This continuation has no periodicity:

• it is aperiodic and even ... random;
• there are never more than 2 identical adjacent terms;
• does not contain groups of three times the same digit;
• does not contain any XYXYX pattern with X = {0 or 1} and Y = {all following 0 and 1).

Reference: https://oeis.org/A010060

The PTM suite in decimal

This suite is written in decimal:

  0.412 454 033 640....

Its development is infinite. It has been shown to be a transcendent number, at the same title as PI.