Where are the runs in this infinite string? (CCCCCC Found!) Starting with the string ABC, consider the result of repeatedly appending the last half of itself to itself (using the larger half if the length is odd).
We get the progression:
ABC
ABCBC
ABCBCCBC
ABCBCCBCCCBC
ABCBCCBCCCBCBCCCBC
etc...

Let S represent the resulting infinite string (or sequence) that results as this procedure is repeated forever.
Goal
The goal in this code challenge is to find the index of the first occurrence of runs of C's in S.
It's easy at first: C first occurs at index 2, CC at 4, CCC at 7, CCCC at 26, but CCCCC is all the way at index 27308! After that my memory runs out.
The winner will be the submission that correctly generates the most run indices (in order, starting at C). You can use any sort of algorithm but be sure to explain it if you aren't using basic brute force. The input and output can be in any easy to understand format.
Important Note: I do not officially know whether or not S actually contains all runs of C's. This question is derived from this one on the Mathematics Stack Exchange, in which the author hasn't found CCCCCC either. I'm curious if anyone here can.  (That question is in turn based on my original question on the topic.)
If you can prove that not all runs of C occur in S then you will win automatically since this question will no longer be valid. If no one can prove that nor find CCCCCC then the winner will be the person who can get the highest lower bound on the index of CCCCCC (or whatever the largest unsolved run is if CCCCCC is found).
Update: Humongous kudos to isaacg and r.e.s. who have found CCCCCC at the astronomical index of 2.124*10^519. At this rate I can't imagine finding CCCCCCC with any method that relies on brute force. Good work guys!
CCCCCC found at 2.124*10^519.
Precise index is 2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215
Found by r.e.s., using the (old version of) code below, after 3.5 hours of searching.
Around that index, the string is: ...BCCBCBCCCBCCCCCCBCCB...
To verify, change the indicated line in the code below to start at 2946, instead of 5. Verification takes 20 seconds.
Update: Improved program. Old program searched ~10x more locations than necessary.
New version finds the CCCCCC in only 33 minutes.
How the code works: Basically, I only look at the regions which correspond to the ends of incremental strings, and calculate the letters by looking recursively back to the original string. Note that it uses a memo table, which may fill up your memory. Put a cap on the length of the memo table if necessary.
import time
import sys
sys.setrecursionlimit(4000)
ULIMIT=4000
end_positions=[]
current_end=2
while len(end_positions)&lt;ULIMIT+3:
    end_positions.append(current_end)
    next_end=((current_end+1)*3+1)//2-1
    current_end=next_end
memo={}
def find_letter(pos):
    if pos in memo:
        return memo[pos]
    if pos&lt;3:
        return 'ABC'[pos]
    for end_num in range(len(end_positions)-1):
        if pos&gt;end_positions[end_num] and pos&lt;=end_positions[end_num+1]:
            delta=end_positions[end_num+1]-end_positions[end_num]
            if len(memo)&gt;5*10**6:
                return find_letter(pos-delta)
            memo[pos]=find_letter(pos-delta)
            return memo[pos]
time.clock()
for end_num in range(5,ULIMIT+1): # This line.
    diff = 1 # Because end_num is guaranteed to be a C
    while True:
        last_letter=find_letter(end_positions[end_num]+diff)
        if not last_letter=='C':
            break
        diff+=1
    if end_num%100==0:
        pos_str=str(end_positions[end_num])
        print(end_num,'%s.%s*10^%i'%(pos_str[0],pos_str[1:5],len(pos_str)-1),
        len(memo),diff,time.clock())
    if diff&gt;=6:
        print(end_num,end_positions[end_num],diff,time.clock())

Current max searched to: 4000 iterations
CCCCCC found at iteration(s):
2946