kdb programming challenge – the Morse-Thue sequence

This week’s post is going to be a little different from the last few in that there won’t be one challenge, but rather a series of bite-size challenges in an attempt to tie together what we’ve done in the last three posts.

I love it when a plan comes together

First definition

The Morse-Thue sequence is an infinite binary sequence that looks like

 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ... 

and has some pretty cool properties. The simplest way to generate this sequence is using recursive bitwise negation (say what?). For example starting with 0, the bitwise negation of this is 1, so we add this to 0 and our sequence becomes 0 1. In the next step the negation of 0 1 is 1 0, so adding this our sequence becomes 0 1 1 0, and so on.

So the first challenge of the day is to write a function that performs this a given number of times and outputs the Morse-Thue sequence. For example:

q)mt1[2]
0110b
q)mt1[5]
01101001100101101001011001101001b

[showhide type=”post1″ more_text=”Show Solution 1″ less_text=”Solution” hidden=”yes”]

We can use the over adverb here for a nice concise solution:

mt1:{x{x,not x}/0b}

Or a slightly less nice version that takes the length of sequence you want, rather than the number of interations:

mt1:{x#{x{x,not x}/0b}"j"$2 xlog x}

[/showhide]

Another definition

So now we can generate the Morse-Thue sequence, and I’m sure you’re starting to wonder, “what does this have to do with anything?” Good question. It turns out there is another way to generate exactly the same sequence; first we take a given number and write it as binary, then sum the digits in this expansion. If the sum of the digits is even this number is known as an evil number, while is it’s odd we call this an odious number. If we do this for every number and return a bool indicating if a number is odious or not, we get the exact same Morse-Thue sequence!

So this time can you make another function to return Morse-Thue, but using the base-number function you made a few weeks back? For example (this time the argument is just the length of the list, rather than the number of iterations):

q)mt2[10]
0110100110b
q)mt2[30]
011010011001011010010110011010b

[showhide type=”post2″ more_text=”Show Solution 2″ less_text=”Solution” hidden=”yes”]

So if b is our base number function:

b:{1_reverse div[;y]\[x]mod y};
mt2:{{1=mod[sum b[x;2];2]}each til x};

[/showhide]

A cool property and yet another definition

So that’s pretty cool, we can make exactly the same sequence in two totally different ways!

q)mt1[32]
01101001100101101001011001101001b
q)mt2[32]
01101001100101101001011001101001b
q)mt1[32]~mt2[32]
1b

So what can we do with this? As I said earlier this sequence has some pretty cool properties, which we can demonstrate using the functions we wrote to test for self-similarity and square-free sequences. First, the Morse-Thue sequence is self similar with a magnification of 2; no matter how long the sequence is, our function will always return true:

q)sim:{#[0N,x;y][;0]~#[x,0N;y]0};
q)sim[2;mt2 64]
1b

And in fact the sequence is infinitely self-similar i.e. if we keep magnifying by 2 it will always look the same:

q)all sim[;mt2 128]each 2 4 8 16 32 64
1b

Not bad huh? Leading on from this property there is in fact yet another way to make this sequence, using the recurrence relation:

t_2n+1 = 1 – t_2n
t_2n = t_n

So can you write another function to produce Morse-Thue of a given length using this relation?

[showhide type=”post3″ more_text=”Show Solution 3″ less_text=”Solution” hidden=”yes”]

So we can do this quite nicely using a scan and a conditional:

mt3:{{x,$[y mod 2;1-x y-1;x y div 2]}/[1#0;1+til x-1]}

or another even nicer vectorized way, once again from the mind of – you guessed it – Kent Lee:

mt3:{x#{raze a,'1-a:(2 0N#x)0}/[x#0 1]}

This solution starts with a generic list like 0 1 0 1 0 1 0 1…. and iterates towards a solution using the first equation above (if n is odd it must be 1-prev value). If the second equation is fulfilled (the list is self similar), it will return the same as the input and the iterate will stop. Nice huh?

[/showhide]

In the challenge on square-free sequences I mentioned that any sequence with an alphabet of 2 can only be square-free for lengths of three or less, so of course the Morse-Thue sequence is not square-free. However, if we take the difference between successive terms in the sequence our alphabet becomes 3 characters (-1, 0 and 1), and the sequence is completely square-free. There are never any repeats!

q)sf:{not any{any raze(~':')cut/:[x;til[x]_\:y]}\:[1+til count x;x]};
q)sf mt2[50]
0b
q)sf deltas mt2[50]
1b

So there you go. Maths huh?