Fibonacci string array

I have an array: A B AB BAB ABBAB BABABBAB ... The number of each term of the array is base on the Fibonacci number.Put the n-th string and the n+1-th string together, then prod开发者_Go百科ucing the n+2-th string,eg.BABABBAB = BAB + ABBAB. Then is the 10^16-th letter is A or B?

Let f[n] be the nth fibonacci number.

Assume we want to find the value at position x in the string obtained by concatenating f[1], f[2], ..., f[n].

1. Find the lowest k such that f[1] + f[2] + ... + f[k] >= x. So position x belongs to word that has f[k] characters (at least in the concatenation it does. But since all words are made up from a and b, we'll try to reduce the problem to just those two).
2. To find the position corresponding to x in the term f[k], subtract f[1] + ... + f[k - 1] from x.
3. if k = 1 print a, if k = 2 print b, else go to step 4.
4. 1. if f[k - 2] < x, then the position we're looking for is in the word corresponding to (with length) f[k - 1]. Subtract 1 from k and f[k - 2] from x and go to step 3.
   2. Else, the position we're looking for is in the word corresponding to f[k - 2]. Subtract 2 from k, leave x unchanged and go to step 3.

This doesn't require generating the actual words, just their lengths, which are the basic fibonacci numbers.

Worked example - note that I'm only using the actual words for illustration purposes, they are not needed.

n  f[n]  corresponding word
1  1     a
2  1     b
3  2     ab
4  3     bab
5  5     abbab 
6  8     bababbab

Concatenating all these we get: ababbababbabbababbab. Let's ask ourselves what's at position 10 (it's b).

1. f[1] + f[2] + f[3] + f[4] + f[5] >= 10, so k = 5
2. x = 10, f[1] + f[2] + f[3] + f[4] = 7, so subtract 7 from x, giving x = 3
3'. k isn't 1 or 2, skip this.
4'. f[k - 2 = 3] = 2 < x. k = 4, x = 1
3''. still ignoring this.
4'' f[k - 2 = 2] = 1 >= x. k = 2, x = 1
3'''. k = 2, print 'b'.

please don't take this answer too serious:

i never was good and math and this sounds like this task should be too heavy to calculate without a freaky algorithm, so my solution would be to simply have a guess. to choose between A and B, i would write a very simple programm like this in php to print out the first 15 or 20 "lines":

<?php
$var1 = "B";
$var2 = "A";
for($i=3;$i<=15;$i++){
    $tmp = $var2;
    $var2 = $var1;
    $var1 = $tmp.$var1;
    echo $i." ".$var1."<br>";
}
echo strlen(implode('',explode('B',$var1)));
echo "<br>";
echo strlen(implode('',explode('A',$var1)));
?>

the result shows there are always less As (38%) than Bs (62%) - so the chance to be right when guessing B aren't that bad.