# 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!

-
I don't get it - You're saying you've found `CCCCC` at index 27308, but later it sounds like you don't know where it first occurs. Did you mean `CCCCCC`? – isaacg Jul 27 '14 at 3:35
@isaacg Oops. 6 C's is the one that's hard to find. I'll fix that. – Helka Homba Jul 27 '14 at 3:39
If the conjecture is wrong, there is a N for which c^N is the longest run. I'm pretty sure it should be possible to construct a longer sequence, leading to a contradiction and proving the conjecture. I also don't think it's too hard, but on the other hand problems can easily underestimated... – Ingo Bürk Jul 28 '14 at 4:47
I am definitely coming back here at midnight with my new batch of votes - for both the question and the answers! – trichoplax Jul 28 '14 at 20:04
For those who are searching, this can make it a bit easier: If you remove the first "A" then you only have to play with "AB" and you append half+1 for the next iteration. – Faquarl Aug 1 '14 at 10:01

# 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)<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<3:
return 'ABC'[pos]
for end_num in range(len(end_positions)-1):
if pos>end_positions[end_num] and pos<=end_positions[end_num+1]:
delta=end_positions[end_num+1]-end_positions[end_num]
if len(memo)>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>=6:
print(end_num,end_positions[end_num],diff,time.clock())
``````

Current max searched to: 4000 iterations

`CCCCCC` found at iteration(s): 2946

-
This is Python right? – Helka Homba Jul 27 '14 at 4:44
Yeah, I'll add that. – isaacg Jul 27 '14 at 4:45
(+1) Your program, with `sys.setrecursionlimit(4000)` and `ULIMIT=4000`, found (in about 3.5 hours on my system) the first occurrence of CCCCCC at index = 2.124*10^519. The exact index is in the next comment ... – r.e.s. Jul 28 '14 at 2:02
21240022271567105375495820702837860723013158551699872604508198291647560279229983‌​603640440103866600765507647498492615953957347456082551624681434831360304038572416‌​676041971461333433676289030226195515355344303779298318609184938752798945199099443‌​791226207048645793660980150864196294390094159476348705923939745578603584126800680‌​863812315777731401823767678111429883298387529640173826414546910377142404147505015‌​352130216386012913854122060757638574902543826704266050454193123128802048880456659‌​38646319068208885093114686859061215 – r.e.s. Jul 28 '14 at 2:03
Awesome! I never suspected it was so close to succeeding. – isaacg Jul 28 '14 at 2:10

### CCCCCC found at 2.124*10^519.

The following ruby code was used to search for `CCCCCC`.

``````SEARCH = 6

k = [5,3]

getc=->i{
j=i
k.unshift(k[0]+(k[0]+1)/2)while(k[0]<=j)
k.each_cons(2){|f,g|j-=f-g if j>=g}
"ABC"[j]
}

while true
x=k[0]
x-=1 while getc[x]=="C"
x+=1
l=1
l+=1 while getc[x+l]=="C"

break if l>=SEARCH
end

puts x
puts (x-14..x+l+13).map{|i|getc[i]}*""
``````

The index is the same as in @isaacg's answer.

The runtime of above code for 6 is in the order of ten seconds on my computer. Nevertheless, it is still search for an answer for `CCCCCCC` (if you want to try it yourself set constant `SEARCH` to `7`).

You can use `getc` to find the character at a specific position `i` as it is done in the last line where the string around the index is printed.

-
Good job speeding it up - my solution was very rough and unpolished. – isaacg Jul 28 '14 at 5:44
Something weird: I've run the above code up to iteration #34000 after removing the break and changing the tests around a bit, and it only finds the one run of 6. Is this a problem with the code (I doubt it) or is it just an odd property of the sequence? – isaacg Jul 28 '14 at 9:31
@isaacg Note that we only check on the breaks of each sequence and thus miss all the copy-sequences C^6. At the breaks those seem to be very rare - thus I think we won't see a C^7 soon. – Howard Jul 28 '14 at 10:09
I know, but since one was found on a sequence break after only 2946 iterations, I'd expect to see a second one by 40000 iterations, which is where I am now. – isaacg Jul 28 '14 at 10:49
@isaacg You may use the (much much faster) code here: ideone.com/HoEKOB. Even with that I couldn't find another C^6 at a sequence point (even less a C^7). – Howard Jul 28 '14 at 16:57

(Not an answer, but too long for a comment.)

The following is a Python translation of @Howard's Ruby program (sped up by a factor near 3 by having only one `getc` in the search loop). On my system, this finds the first C^6 in 3 seconds. In 93 hours, it finds no C^7 in 231,000 iterations, so the first C^7 (if it exists) must occur after the leftmost 10^40677 positions in the infinite string.

``````import time

L = [5, 3]      #list grows "backwards" (by insertion on the left)

def getc(i):    #return the letter at index i
while L[0] <= i: L.insert(0,L[0] + (L[0] + 1)//2)
for k in range(len(L)-1):
if i >= L[k+1]: i -= L[k] - L[k+1]
return 'abc'[i]

def search(k):  #find the first occurrence of c^k
start = time.time()
iter = 0
while True:
iter += 1
if iter % 1000 == 0: print iter, time.time()-start
p = L[0] - 1
l = 1
while getc(p+l)=='c': l += 1
if l == k: break
return p, iter, time.time()-start

k = 6

(indx, iter, extime) = search(k)
print 'run length:', k
print 'index:', indx, '    (',len(str(indx)),'digits )'
print 'iteration count:', iter
print 'neighborhood:', ''.join([getc(i) for i in range(indx-1,indx+k+10)])
print 'execution time:', extime
``````
-
With PyPy, it finds C^6 in less than a second on my machine. – Dennis Aug 11 '14 at 4:09