Rozpoczynając od łańcucha ABC, rozważ wynik wielokrotnego dołączania do siebie ostatniej połowy siebie (użycie większej połowy, jeśli długość jest nieparzysta).

Otrzymujemy postęp:

ABC
ABCBC
ABCBCCBC
ABCBCCBCCCBC
ABCBCCBCCCBCBCCCBC
etc...

Niech Sreprezentuje wynikowy nieskończony ciąg (lub sekwencję), który powstaje, ponieważ ta procedura jest powtarzana na zawsze.

Cel

Celem tego wyzwania kodu jest znalezienie indeksu pierwszego wystąpienia uruchomień Cw S.

Na początku jest to łatwe: Cnajpierw pojawia się przy indeksie 2, CCo 4, CCCo 7, CCCCo 26, ale CCCCCcały czas o indeksie 27308! Potem skończyła się moja pamięć.

Zwycięzcą zostanie zgłoszenie, które poprawnie generuje najwięcej uruchomionych indeksów (w kolejności, zaczynając od C). Możesz użyć dowolnego algorytmu, ale wyjaśnij go, jeśli nie używasz podstawowej brutalnej siły. Dane wejściowe i wyjściowe mogą mieć dowolny łatwy do zrozumienia format.

Ważna uwaga: oficjalnie nie wiem, czy Sfaktycznie zawiera wszystkie serie C. To pytanie pochodzi od tego z Mathematics Stack Exchange , w którym autor również nie znalazł CCCCCC. Jestem ciekawy, czy ktoś tu może. (To pytanie z kolei oparte jest na moim pierwotnym pytaniu na ten temat ).

Jeśli udowodnisz, że nie wszystkie serie Cwystępują S, wygrasz automatycznie, ponieważ to pytanie nie będzie już ważne. Jeśli nikt nie może tego udowodnić ani znaleźć, CCCCCCzwycięzcą zostanie osoba, która uzyska najwyższą dolną granicę indeksu CCCCCC(lub cokolwiek, co będzie największym nierozstrzygniętym przebiegiem, jeśli CCCCCCzostanie znaleziony).

Aktualizacja: Ogromne pochwały dla isaacga i res, którzy znaleźli CCCCCCprzy indeksie astronomicznym 2,124 * 10 ^ 519. W tym tempie nie wyobrażam sobie znalezienia CCCCCCCjakiejkolwiek metody opartej na brutalnej sile. Dobra robota chłopaki!

CCCCCC znaleziono w 2.124 * 10 ^ 519.

Precyzyjny wskaźnik jest 2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215

Znaleziono przez res, używając (starej wersji) kodu poniżej, po 3,5 godzinach wyszukiwania.

Wokół tego indeksu ciąg jest następujący: ...BCCBCBCCCBCCCCCCBCCB...

Aby to zweryfikować, zmień wskazany wiersz w poniższym kodzie, aby rozpocząć od 2946, zamiast 5. Weryfikacja zajmuje 20 sekund.

Aktualizacja: ulepszony program. Stary program szukał ~ 10 razy więcej lokalizacji niż to konieczne.

Nowa wersja znajduje się za CCCCCC33 minuty.

Jak działa kod: Zasadniczo patrzę tylko na regiony odpowiadające końcom przyrostowych ciągów i obliczam litery, patrząc rekurencyjnie z powrotem na oryginalny ciąg. Pamiętaj, że korzysta z tabeli notatek, która może zapełnić pamięć. W razie potrzeby nałóż czapkę na długość tabeli notatek.

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

Bieżące maks. Wyszukiwane: 4000 iteracji

CCCCCC znaleziono w iteracji: 2946

CCCCCC znaleziono w 2.124 * 10 ^ 519.

Do wyszukiwania użyto następującego kodu ruby 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]}*""

Indeks jest taki sam jak w odpowiedzi @isaacg .

Czas działania powyższego kodu dla 6 jest rzędu dziesięciu sekund na moim komputerze. Niemniej jednak wciąż szuka odpowiedzi na CCCCCCC(jeśli chcesz spróbować samodzielnie ustawić stałą SEARCHna 7).

Możesz użyć, getcaby znaleźć znak w określonej pozycji, itak jak ma to miejsce w ostatnim wierszu, w którym drukowany jest ciąg znaków wokół indeksu.

(Nie odpowiedź, ale za długa na komentarz).

Poniżej znajduje się tłumaczenie w języku Python programu Ruby @ Howarda (przyspieszone trzykrotnie, ponieważ tylko jeden znajduje się getcw pętli wyszukiwania). W moim systemie znajduje to pierwsze C ^ 6 w ciągu 3 sekund. W ciągu 93 godzin nie znajduje C ^ 7 w 231 000 iteracjach, więc pierwsze C ^ 7 (jeśli istnieje) musi wystąpić po ostatnich 10 ^ 40677 pozycjach w nieskończonym ciągu.

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