En commençant par la chaîne ABC, considérez le résultat de l'ajout répétitif de la dernière moitié de lui-même (en utilisant la plus grande moitié si la longueur est impaire).

Nous obtenons la progression:

ABC
ABCBC
ABCBCCBC
ABCBCCBCCCBC
ABCBCCBCCCBCBCCCBC
etc...

Laisser Sreprésenter la chaîne infinie résultante (ou séquence) que les résultats que cette procédure est répétée pour toujours.

Objectif

Le but de ce défi de code est de trouver l'index de la première occurrence de runs de C's in S.

C'est facile au début: Cse produit d'abord à l'index 2, CCà 4, CCCà 7, CCCCà 26, mais CCCCCest tout au long à l'index 27308! Après cela, ma mémoire s'épuise.

Le gagnant sera la soumission qui génère correctement les indices les plus exécutés (dans l'ordre, à partir de C). Vous pouvez utiliser n'importe quel type d'algorithme, mais assurez-vous de l'expliquer si vous n'utilisez pas la force brute de base. L'entrée et la sortie peuvent être dans n'importe quel format facile à comprendre.

Remarque importante: je ne sais pas officiellement si Scontient réellement toutes les séries de C. Cette question est dérivée de celle-ci sur le Mathematics Stack Exchange , dans laquelle l'auteur n'a pas trouvé non CCCCCCplus. Je suis curieux de savoir si quelqu'un ici peut. (Cette question est à son tour basée sur ma question initiale sur le sujet .)

Si vous pouvez prouver que tous les runs ne se Cproduisent pas, Svous gagnerez automatiquement car cette question ne sera plus valide. Si personne ne peut le prouver ni le trouver, CCCCCCle gagnant sera la personne qui peut obtenir la borne inférieure la plus élevée de l'index CCCCCC(ou quelle que soit la plus grande course non résolue si elle CCCCCCest trouvée).

Mise à jour: bravo énormes à isaacg et res qui ont trouvé CCCCCCà l'indice astronomique de 2.124 * 10 ^ 519. À ce rythme, je ne peux pas imaginer trouver CCCCCCCavec une méthode qui repose sur la force brute. Bon travail les gars!

Trouvé à 2,124 * 10 ^ 519.

Indice précis est 2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215

Trouvé par res, en utilisant (l'ancienne version de) le code ci-dessous, après 3,5 heures de recherche.

Autour de cet index, la chaîne est: ...BCCBCBCCCBCCCCCCBCCB...

Pour vérifier, modifiez la ligne indiquée dans le code ci-dessous pour commencer à 2946, au lieu de 5. La vérification prend 20 secondes.

Mise à jour: programme amélioré. L'ancien programme a recherché ~ 10 fois plus d'emplacements que nécessaire.

La nouvelle version trouve le CCCCCCen seulement 33 minutes.

Comment le code fonctionne: Fondamentalement, je ne regarde que les régions qui correspondent aux extrémités des chaînes incrémentielles, et je calcule les lettres en revenant récursivement à la chaîne d'origine. Notez qu'il utilise une table de mémos, qui peut remplir votre mémoire. Mettez un bouchon sur la longueur de la table mémo si nécessaire.

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())

Courant maximum recherché: 4000 itérations

CCCCCC trouvé à itération (s): 2946

Trouvé à 2,124 * 10 ^ 519.

Le code rubis suivant a été utilisé pour la recherche 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]}*""

L'index est le même que dans la réponse de @isaacg .

Le temps d'exécution du code ci-dessus pour 6 est de l'ordre de dix secondes sur mon ordinateur. Néanmoins, il est toujours à la recherche d'une réponse CCCCCCC(si vous voulez l'essayer vous-même, réglez constant SEARCHsur 7).

Vous pouvez utiliser getcpour trouver le caractère à une position spécifique icomme cela se fait dans la dernière ligne où la chaîne autour de l'index est imprimée.

(Pas une réponse, mais trop long pour un commentaire.)

Ce qui suit est une traduction Python du programme Ruby de @ Howard (accéléré par un facteur proche de 3 en n'en ayant qu'un getcdans la boucle de recherche). Sur mon système, cela trouve le premier C ^ 6 en 3 secondes. En 93 heures, il ne trouve aucun C ^ 7 dans 231 000 itérations, donc le premier C ^ 7 (s'il existe) doit se produire après les 10 ^ 40677 positions les plus à gauche dans la chaîne infinie.

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