Krdytkyu

The Thue-Morse sequence is defined as a binary sequence and can be generated like

  0, 01, 01 10, 01 10 10 01, 01 10 10 01 10 01 01 10, ... . 

So the second half of the series is always the binary complement of the first half of the series.

But is there a way to generate an analogous ternary sequence?
Intuitively my first guess for a ternary Thue-Morse sequence was like

  0, 01, 012, 012 120, 012 120 120 201, 012 120 120 201 120 201 201 012, ...

So here the second half of the series is the "ternary complement" (rotation $0 to 1, 1 to 2, 2 to 0 $ instead of $0 to 1, 1 to 0 $) of the first half.

But it could also be

  0, 01, 012, 012 120 201, 012 120 201 120 201 012 201 012 120, ... 

Here the second third is the "ternary complement" of the first third and the third third is the "ternary complement" of the second third.

Does any of my constructions for a ternary Thue-Morse series make sense?

Is there maybe a unique way to generate an analogous ternary sequence?

And how to construct n-ary versions of the Thue-Morse series in general?

It's $0, 012, 012 120 201, 012 120 201 120 201 012 201 012 120, ...$

To easily construct the Thue-Morse sequence, you can do the following:

Start with $0$;
Replace $(0to01)$ and $(1to10)$.
So you get: $$0, 0 1, 01 10, 0110 1001, 01101001 10010110,...$$

To easily construct the ternary version of Thue-Morse sequence, you can do the following:

Start with $0$;
Replace $(0to012), (1to120), (2to201).$
So you get: $$0, 0 1 2, 012 120 201, 012120201 120201012 201012120$$

To easily construct the $4$-ary version of Thue-Morse sequence, you can do the following:

Start with $0$;
Replace $(0to 0123), (1to 1230), (2to2301), (3to3012).$
So you get: $$0, 0 1 2 3, 0123 1230 2301 3012, 0123123023013012 1230230130120123 2301301201231230 3012012312302301$$

To easily construct the $n$-ary version of Thue-Morse sequence, you can do the following:

Start with $0$;
Replace

$$(0to012cdots[n-2][n-1]n),
(1to123cdots[n-1]n0),$$

$$(2to234cdots n01),$$

$$dots$$

$$(nto n01cdots[n-3][n-2][n-1]).$$

To find out a particular number n for b symbols, convert the number to base b, sum the digits, and then modulo by b.

For example, you have two symbols, 0 and 1, and you want to find out what the fifteenth place in this sequence would be. Convert 14 (14 is the fifteenth number since this sequence starts with 0) to base two (the number of symbols), it's 1110. Sum the digits, it's 3. Take 3 modulo two (again, the number of symbols). It's 1. So the fifteenth place in the binary Thue-Morse sequence is 1.

If you have four symbols, 0 and 1 and 2 and 3, and you want to find out the twelfth place in the sequence. Convert 11 to base four, it's 23. Sum the digits, it's 5. Five modulo four is 1, so the twelfth place in the quaternary Thue-Morse sequence is also 1.

I figured that out today. Maybe it was already well-known, I don't know. Hopefully I figured out something new.

Here's how I went about figuring out why it works (and, just as importantly, that it works):

I first heard of the Thue-Morse sequence today. (I was looking for turn-order sequences for card games.)

I read about the "amount of ones being odd or even" thing in the case of two symbols. I.e. 14 in binary is 1110, it has three ones, three is odd, so it's the second symbol ("1").

I searched for whether or not there was a version that worked with more symbols (I figured I wanted to know for games with more players). I found this page, saw MLE's answer and thought that I'd convert the numbers to base three and four respectively, and take a look at the digits, and see if I could find some correspondence. Putting "count the ones" aside for a moment, thinking "is there some digit I can count, some other thing that seems to match with the sequences MLE posted?" and I saw that the sum of the digits modulo the base seemed to match up. I thought about that and saw that that's also another way of expressing Conway's "count the ones". Counting ones and ignoring zeroes is the same as summing the ones and the zeroes. So I was feeling good about it, but I wanted to test.

I wrote a little computer program to do it quickly for me, to convert to a particular base, then sum the digits and then mod the sum. It matched up with everything I threw at it, but I didn't think that was particularly convincing since I only had bases 2, 3 and 4, and numbers up to like 32 or so to work with. I wanted to compare with higher numbers and compare more automatically (which still wouldn't be a proof, but would convince me that it was an approach to explore further).
But instead of doing the "substitute 0 for 012" etc approach, I wanted to program some algorithm to quickly find a particular Thue-Morse number.
I knew about

T(2n) = T(n)

T(2n+1) = not T(n)

I saw that

T(2n+1) = not T(n) = (T(n)+1) modulo 2.

and thought that one possible generalization for other numbers of symbols could be:

T(bn) = T(n)

T(bn+y) = (T(n)+y) modulo b

where y is lower than b.
I don't know if that was already known or not, that was something I came up with.

I implemented this is Scheme as:

(define (thumo n b)

  (if (> b n)

      n

      (modulo

       (+

    (thumo (quotient n b) b)

    (remainder n b))

       b)))

I immediately saw that that was pretty much the same as my sum the digits and mod approach:

(define (enarize n b)

  ;; the word "enarize" I made up but it's a sort

  ;; of decimal representation of another base.

  (if (> b n)

      n

      (+ ( * 10 (enarize (quotient n b) b)) (remainder n b))))



(define (sum-of-digits n)

  (if (> 10 n) n

      (+ (sum-of-digits (quotient n 10)) (remainder n 10))))



(define (thumo n b)

  (modulo (sum-of-digits (enarize n b)) b))

Because it can be refactored into the same thing. First, I see that I
can combine enarize and sum-of-digits because they're so similar
(though inversed); I don't need to multiply by ten only to divide by
ten again (at least as long as I work in the same "mod") :

(define (sum-of-enarized-digits n b)

  (if (> b n)

      n

      (+ (sum-of-enarized-digits (quotient n b) b) (remainder n b))))

That makes it so that (sum-of-enarized-digits n b) matches up with
(sum-of-digits (enarize n b)), and I can wrap it all with a big modulo
b to make it match up with the sum-the-digits version of thumo.

But, I also know that when you're planning to mod a sum, it's harmless
to mod the operands beforehand (as long as you don't skimp on the
final modulo operation). I don't know how to express that formally...
it's just something I've figured out when programming. But
hopefully it's well known among you math folks. That means I can have the
modulo within the recursing function without harm to the final sum:

(define (thumo n b)

  (if (> b n)

      n

      (modulo

       (+

    (thumo (quotient n b) b)

    (remainder n b))

       b)))

And, that matches up symbol to symbol with the other algorithm from earlier so QED♥!

PS. I'm new to writing about math, I've got more of a CS background. I'm pretty thin-skinned, I want to do more math stuff so please don't be too harsh on me.

There is another road to arrive at such a generalization using polynomials in $x$ arriving at formal power series in the limit.

Consider the geometric series $f_0(x)=1+x+x^2+x^3 + ... $. That series can be rewritten as an infinite product
$$ f_0(x) = (1+x)(1+x^2)(1+x^4)(1+x^8)... = prod_{k=0}^infty (1+x^{2^k}) tag {1.1}
$$
If we consider now to replace each $+$-sign by the $-$-sign we get
$$ f_1(x) = (1-x)(1-x^2)(1-x^4)(1-x^8)... = prod_{k=0}^infty (1-x^{2^k})
tag {1.2}$$
The power series expression has now alternating signs which alternate according to the Thue-Morse-pattern:
$$ f_1(x ) = 1- x -x^2 + x^3 -x^4 + x^5 + x^6 - x^7 -...+... tag {1.3}$$
If we insert now $x=1/2$ we get a multiple of the Thue-Morse-constant, but we could also denote it as symbol-concatenation using $0$ for $+$ and $1$ for $-$ getting the well known string 0110 1001 1001 0110 ...

$$
g_2(x) = (1+qx+px^2)(1+qx^3+px^6)(1+qx^9+px^{18})... = prod_{k=0}^infty (1+ qx^{3^k}+px^{2 cdot 3^k}) tag {2.3}
$$
When we expand this infinite products formally we arrive at a power series whose coefficients follow the pattern 012 120 201 ... for $g_1(x)$ as indicated by @MLE and 021 210 102 ... for $g_2(x)$.

If we evaluate $w_f=f_0(1/2) cdot f_1(1/2)$ we get $w_f approx 0.700367730879$ Here the well known Thue-morse-constant $tau approx 0.425091932720$ is involved as rational scaling $w_f = 4 tau - 1$

If we evaluate $ w_g = g_0(1/2) cdot g_1(1/2) cdot g_2(1/2) $ we get $w_g approx 0.762637186607 $ . I don't have a relation between $w_g$ to some other known constants, but it might be interesting, that
$$sqrt {w_g ^{phantom {1^1 }}} = 2prod_{k=0}^infty (1 - 0.5^{3^k})
tag{3.1} $$
whose pattern is near to the Thue-Morse-expression in the product-formula (1.2) using $f_1(x)$ for $x=0.5$

Added: the latter relation seems to be generalizable. let $$G(x)=g_0(x)cdot g_1(x) cdot g_2(x) tag{3.2} $$
and similarly to the $f_r()$ functions
$$F_3(x)= prod_{k=0}^infty (1-x^{3^k}) tag{3.3} $$
It seems we can write
$$sqrt {G(x)^{phantom {1^1 }}} = {1 over 1-x} cdot F_3(x) tag{3.4}
$$
(but I've not yet proven this algebraically)