We start by fixing the source code and defining a function to compute F(n) for small n . We will also print the first few values of F All the code below is for Python 3; if you are using Python 2, you need to make some minor changes, for example, replace str.maketrans with string.maketrans and range with xrange .
swap_ac = str.maketrans({ord('a'): 'c', ord('c'): 'a'}) def F(n): s = '' for _ in range(n): s = s + 'a' + s[::-1].translate(swap_ac) return s for n in range(7): print("F({}) = {!r}".format(n, F(n)))
This gives the following result:
F(0) = '' F(1) = 'a' F(2) = 'aac' F(3) = 'aacaacc' F(4) = 'aacaaccaaaccacc' F(5) = 'aacaaccaaaccaccaaacaacccaaccacc' F(6) = 'aacaaccaaaccaccaaacaacccaaccaccaaacaaccaaaccacccaacaacccaaccacc'
A few observations at this point:
F(n) is a string of length 2**n-1 . This means that F(n) is growing rapidly. Computing F(50) already requires some serious equipment: even if we saved one character per bit, we would need more than 100 terabytes to store the complete string. F(200) has more characters than putative atoms in the solar system. Therefore, the idea of calculating F(10**2017) directly ridiculous: we need a different approach.
By construction, each F(n) is a prefix of F(n+1) . So we really have a clear infinite string, where each F(n) just gives us the first 2**n-1 characters of this infinite string, and we expect to calculate its character k th. And for any practical purpose, F(10**2017) can be such an infinite string: for example, when we do our calculations, we do not need to check that k < 2**(10**2017)-1 , since a k exceeding this cannot even be represented in normal binary notation in this universe.
Fortunately, the structure of the string is simple enough that the calculation of the character k th is straightforward. The main key arises when we look at characters in even and odd positions:
>>> F(6)[::2] 'acacacacacacacacacacacacacacacac' >>> F(6)[1::2] 'aacaaccaaaccaccaaacaacccaaccacc'
Characters in even positions simply alternate between a and c (and this simply proves that this is true based on the construction). Therefore, if our k even, we can just see if k/2 odd or even determine if we get a or c .
How about weird positions? Well, F(6)[1::2] should look somewhat familiar: just F(5) :
>>> F(6)[1::2] == F(5) True
Again, directly prove (for example, by induction) that this is not just a coincidence and that F(n+1)[1::2] == F(n) for all non-negative n .
Now we have an effective way to calculate the character k th in our infinite line: if k even, we just look at the parity k/2 . If k is odd, then we know that the symbol at position k is equal to the value at position (k-1)/2 . So here is the first solution to calculate this character:
def char_at_pos(k): """ Return the character at position k of the string F(n), for any n satisfying 2**n-1 > k. """ while k % 2 == 1: k //= 2 return 'ac'[k//2%2]
And check that it is correct:
>>> ''.join(char_at_pos(i) for i in range(2**6-1)) 'aacaaccaaaccaccaaacaacccaaccaccaaacaaccaaaccacccaacaacccaaccacc' >>> ''.join(char_at_pos(i) for i in range(2**6-1)) == F(6) True
But we can do better. We effectively look at the binary representation of k , removing all trailing '1' and the following '0' , and then just looking at the next bit to determine if we have 'a' or 'c' , Identification of the trailing 1s can be done by bypassing bit operations. This gives us the following semi-omitted solution without a loop, which I leave for you to talk about:
def char_at_pos2(k): """ Return the character at position k of the string F(n), for any n satisfying 2**n-1 > k. """ return 'ac'[k//(1+(k+1^k))%2]
Again, check:
>>> F(20) == ''.join(char_at_pos2(i) for i in range(2**20-1)) True
Concluding comments: this is a very well-known and well-studied sequence: it is called the dragon curve sequence or regular paper folding , and the sequence A014577 in the online encyclopedia of integer sequences. Some Google searches will likely give you many other ways to figure out its elements. See also this question-question ....