### Call for Papers II

Remember this one?

0) We'll define this binary sequence in stages, punctuated by periods for clarity. (The periods are cosmetic; they are not part of the sequence.)

1) The first stage: 0.

2) The next stage: 1. So far: 0.1.

3) The next stage: a copy of all previous stages except the last: 0. So far: 0.1.0.

4) The next stage: same as for (3): 01. So far: 0.1.0.01.

5) Etc.: 0.1.0.01.010.01001.01001010.0100101001001. ...

6) Stripped of ".": 0100101001001010010100100101001001 ...

Remember my asking for the millionth digit of the "wine tasting sequence" 0110100110010110...?

OK, well, what is the millionth digit of this sequence? The answer is very cute. I'll include it as a comment to this very post, so no fair peeking unless you give up...

#### 1 comment:

1. OK, the answer--are you sure you want to peek?

Let F(k) be the k-th Fibonacci number. Then the algorithm for the value d of the N-th digit of our sequence is:

Given N;
WHILE N > 2
N = N - max(k)(F(k) < N);
d = N - 1;

Actually, a less efficient but equally correct algorithm consists in repeatedly subtracting any F(k) greater than 2 and less than N.