Hi,

Suppose you let:

s(n) = 2^(-4ⁿ )
f(0) = 0
f(n+1) = (1-s(n)² )(s(n)+f(n)-s(n)f(n))
x = lim(n-> infinity )f(n)

then is it possible to calculate x in closed form?

Basically the idea behind this is that in binary form x starts:

x=0.0110100110010110100101100110100110010110011010
01011010011001011010010110011010010110100110010110
01101001100101101001011001101001100101100110100101
10100110010110011010011001011010010110011010010110
10011001011010010110011010011001011001101001011010
01100101101001011001101001011010011001011001101001
10010110100101100110100101101001100101101001011001
10100110010110011010010110100110010110011010011001
01101001011001101001100101100110100101101001100101
10100101100110100101101001100101100110100110010110
10010110011010011001011001101001011010011001011001
10100110010110100101100110100101101001100101101001
01100110100110010110011010010110100110010110011010
01100101101001011001101001100101100110100101101001
10010110100101100110100101101001100101100110100110
01011010010110011010010110100110010110100101100110
10011001011001101001011010011001011010010110011010
01011010011001011001101001100101101001011001101001
10010110011010010110100110010110011010011001011010
01011001101001011010011001011010010110011010011001
0110011010010110100110010110?

[Another way of generating this series of digits: write out 1, 2, 3, 4, etc in binary, then count the number of 1s in each number: if it is odd, write 1, if it is even write 0. - The Editor]

Notice that every block of 4 is either 0110 or 1001. Suppose you replace these blocks by A and B respectively. You get it starting:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAB
BABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBA
BAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABA
ABBAABABBAABBABAABBAABABBABAABABBAABBABAABABBABAAB
BAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBA
ABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAAB
ABBABAABABBAABBABAABABBABAABBAABABBABAABABBAABBABA
ABBAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBA
BAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABA
ABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAAB
ABBAABBABAABBAABABBAABBABAABABBABAABBAABABBAABBABA
ABBAABABBABAABABBAABBABAABABBABAABBAABABBABAABABBA
ABBABAABBAABABBAABBABAABABBABAABBAABABBAABBABAABBA
ABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAAB
ABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAABAB
BABAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAAB
BAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABAB
BABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABBAAB
ABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABAB
BAABBABAABABBABAABBAABABBABAABABBAABBABAABBAABABBA
ABBABAABABBABAABBAABABBA?.

Which is exactly the same pattern as the pattern of 0s and 1s! If you replaced blocks here as X = ABBA and Y = BAAB then of course you would get the same thing again in Xs and Ys.

Or alternatively you can construct the pattern of 0s and 1s from the base pattern ABBA.

First of all take ABBA. Now let A = XYYX and B = YXXY:

XYYXYXXYYXXYXYYX

Now let X = PQQP and Y = QPPQ:

PQQPQPPQQPPQPQQPQPPQPQQPPQQPQPPQQPPQPQQPPQQPQPPQPQQPQPPQQPPQPQQP

And so on. The ABBA pattern is sort of embedded at an infinite number of levels giving the overall pattern of 0s and 1s an almost fractal like nature. But is it possible to calculate as a binary number? And what about other patterns, e.g. ABA. This would start:

ABA
XYXYXYXYX
PQPQPQPQPQPQPQPQPQPQPQPQPQP

Which ends up extremely easy to calculate in binary form as the limit of the sequence is r = 0.01010101010101010101... so 4r = 1.01010101... = 1+ r, so r = 1/3

Of course the original number x at the top could also be constructed by the simpler pattern AB (or ABBABAABBAABABBA or anything else like that).

Is there any general way of calculating the binary form from the repeating pattern? (Or indeed the reverse process?)

Thanks a lot,

Michael

Well, having played about with it for a bit and not getting very far, I found a web page on the internet that has this number. It is called the Thue-Morse Constant, and it is transcendental. You can read more about it at http://mathworld.wolfram.com/Thue-MorseConstant.html .
In fact, it's a very interesting sequence, and you can download a fascinating paper about it at http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps (you might have to go through http://www.cs.uwaterloo.ca/~shallit/papers.html to download it).

I don't think you'll have much luck with the more general problem either, because these are somewhat like cellular automata, which are extremely complicated.

Thanks a lot for that reference! You're right it is a very interesting paper. I thought it would be transcendental but this must be highly complicated to prove if it was first shown in 1977!!! I don't quite understand what it means by "two consecutive blocks". Does a block mean a string of > 1 digit? I tried out the chess thing it mentions and I think I can see how it works. But I got a bit lost towards the end of the paper.

I am amazed it has so many applications, especially as the only reason I considered it was in answering a question that had very little to do with mathematics. One thing I would be interested in though is what base sequences (for instance the base in this case is AB) give rise to rational numbers in binary notation. The only one that is immediately obvious is ABA.

By the way, what does cellular automata mean?

Many thanks,

Michael

Yes, all transcendence proofs are difficult I think, but it might be an interesting exercise to the reader to prove that it is irrational (I might have a go at it later).

A cellular automaton is a bit like Conway's Game of Life (which you might have heard about). Basically, you have some set of cells which are on or off (you usually colour them black and white), and they evolve in discrete time steps based on which neighbouring cells are on and off. In Conway's Life, there is an infinite grid of cells, and they switch on or off depending on how many surrounding cells are on or off. In fact, a Life board can simulate the action of a universal Turing machine, in other words they can carry out any computation (albeit very slowly indeed). You can also have 1D cellular automata, which you usually plot in 2D with the cell dimension on the x axis, and the timestep extending downwards on the y axis. These have also been proven to be complicated in a Turing machine sort of sense I think. If you're interested, I can write a little more about cellular automata.

Also, in the paper I think that a block means any sequence of > =1 digits. Also, whether or not a number is rational doesn't depend on which base you represent it in. I'll have a further look at this, it might be interesting to generalise the problem to base-n, i.e. you have n symbols A₀ to A_n-1 , and you replace symbol A_i with the variable length sequence of symbols A_j(i,0) A_j(i,1) ...A_j(i,p(i)) , for which functions j and p is the limit rational / irrational / transcendental?

Doh, it's easy to prove that your constant is irrational, as all rational numbers repeat in blocks after some number of terms, and this sequence doesn't. I'll have a look at the more general problem at some point.

Yes, that looks very tricky. All I can think of at the moment is that if:

A₁ is mapped to A₁ A₂ ...A_n-1 A_n A₁
A₂ is mapped to A₂ A₃ ...A_n A₁ A₂
A₃ is mapped to A₃ ...A₃
...
A_n is mapped to A_n A₁ ...A_n

Then it will recur A₁ A₂ ...A_n

This can probably be generalised greatly (e.g. you could insert a string of A₁ A₂ ...A_n into any of strings which A_i are mapped to) and you can change round the order but I wonder if there is a fundamentally different way. I'll have a go a bit later.

Thanks,

Michael