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...
S represent the resulting infinite string (or sequence) that results as this procedure is repeated forever.
The goal in this code challenge is to find the index of the first occurrence of runs of
It's easy at first:
C first occurs at index
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!