Zaczynamy od pustej sekwencji 1-indeksowanej:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,...

W n- ^tym kroku wypełniamy wszystkie puste pola (a) liczbami całkowitymi większymi niż 1, zaczynając od pierwszego pozostałego pustego miejsca, gdzie (n) jest n- ^tym wpisem w sekwencji.

Po pierwszym kroku:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,...

Zauważ, że a (1) musi być 2, ponieważ pierwsza liczba całkowita większa od 1 to 2.

W drugim kroku wypełniamy wszystkie (2) puste pola. Będzie oczywiste, że a (2) musi być 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,...

W trzecim kroku wypełniamy wszystkie (3) puste pola. Z sekwencji a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,...

W czwartym kroku wypełniamy wszystkie (4) puste pola. Z sekwencji a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,...

Ostatecznie:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,...

Zadanie

Biorąc pod uwagę n, zwróć n- ^ty element sekwencji.

Pierwsze 10 000 000 terminów sekwencji można znaleźć tutaj .

To jest golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa. Obowiązują standardowe luki .

Haskell , 80 67 bajtów

g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m

Wypróbuj online!

Haskell to idealny język do definiowania nieskończonej listy.

C, 123 bajty

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

Wypróbuj online!

Przewodnik

f(n){int*p=calloc(n,4),

Przydziel tablicę n liczb całkowitych do przechowywania pierwszych n elementów sekwencji. To hardcodes sizeof(int)as 4, co jest bezpiecznym założeniem w większości przypadków i na pewno takim, które jestem gotów zrobić w kontekście golfa kodu. :)

i=0,j,k;

Są to wszystkie liczniki: idla indeksu kroku, na którym jesteśmy, jaby przejść przez sekwencję w poszukiwaniu pustych miejsc i kpoliczyć, ile pustych miejsc zostało zauważonych.

for(*p=p[1]=2;i<n;++i)

Zanim zaczniemy naszą główną pętlę, podkradamy się podczas inicjalizacji pierwszych dwóch elementów sekwencji do 2. ( p[0]= *(p + 0)= *p.) Wyklucza to kjednak, ale ...

for(j=0,k=i/2?0:2-i;j<n;++j)

... wykonujemy również sprytną inicjalizację k, która sprawdza, czy wartość ijest mniejsza niż, 2i koryguje wartość początkową, kjeśli tak jest. Tutaj zaczyna się również wewnętrzna pętla, która iteruje się po całej sekwencji do tej pory podczas każdego kroku.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

Ta linia mogłaby naprawdę trochę wyjaśnić. Możemy rozwinąć to do:

if (!(p[j] || ((k++) % p[i]))) {
    p[j] = k / p[i] + 2;
}

przez zwarcie, a następnie przez prawa De Morgana i fakt, że 0jest to fałsz w C:

if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
}

Zasadniczo stwierdza się: „jeśli to miejsce jest puste, zwiększaj k. Jeśli kwcześniej była wielokrotnością wielkości kroku, uruchom następującą instrukcję”. Dlatego uruchamiamy instrukcję na każdym elemencie wielkości kroku , co dokładnie opisuje sekwencję. Samo zdanie jest proste; Wszystko robi to generuje 2, 3, 4, ....

n=p[n-1];}

Korzystając z funkcji tricky-return-without-a-return gcc, „zwracamy” ostatni element pierwszych n terminów w sekwencji, który przypadkiem jest n- tym terminem.

Pyth, 29 bajtów

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1

Wypróbuj online

Jak to działa

Zamiast wygłupiać się z listami, używa zwykłej rekurencyjnej formuły.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input())))

Haskell , 67 bajtów

0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j<i]
f=(%1).pred

Wypróbuj online!

Rekurencyjne rozwiązanie arytmetyczne, które okazało się w zasadzie tą samą metodą, co odpowiedź Pythona Andersa Kaseorga .

Ten kod jest pokryty brodawkami - brzydkimi częściami, które wyglądają, jakby można je było zagrać w golfa, ale nie widziałem, jak to zrobić.

Funkcja i%jnaprawdę chce użyć wartownika, aby sprawdzić, czy mod i(f j)>0i ocenić jedno z dwóch odpowiednich wyrażeń. Ale oba wyrażenia używają div i(f j). Wiązanie tego w osłonie nie spowoduje, że będzie miało zastosowanie do obu stron. O ile mi wiadomo, nie można zmusić strażnika do „rozdzielenia” się na innych strażników. leti wheresą za długie. Tak więc kod używa lastdo wybrania jednego z dwóch wyrażeń, podczas gdy wartownik wiąże zmienną. Ugh.

Idealnie byśmy użyli, divModponieważ zarówno divi modsą używane, ale (d,m)<-divMod ...jest to długie wyrażenie. Zamiast tego pospiesznie sprawdzamy, czy mod jest niezerowy, sprawdzając, czy divwartość razy dzielnik nie jest równa pierwotnej wartości.

0%j=2Sprawa nie byłaby potrzebna, jeśli Haskell zwarte div 0, których nie ma. W .predkonwertuje 1-indeksowane wejście do zera indeksowane, albo nie będzie -1korekty wszędzie.

JavaScript (ES6), 98 93 91 bajtów

Funkcja rekurencyjna, która zatrzymuje się, gdy tylko wynik będzie dostępny.

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Alternatywna wersja, 90 bajtów

Sugerowane przez Shaggy dla -1 bajtów

Ten musi być wywołany z f(n)(). Chociaż odpowiadający post w meta obecnie daje pozytywny wynik, ta składnia jest najwyraźniej kwestionowana.

n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Próbny

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

for(n = 1; n <= 50; n++) {
  console.log('a[' + n + '] = ' + f(n));
}

Java 8, 124 bajty

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];}

Wyrażenie lambda.

Tworzy tablicę liczb całkowitych i nieustannie ją zapełnia, dopóki n-ta wartość nie zostanie zapełniona.

Wstępnie zadeklaruj zmienne u góry, aby zmniejszyć jak najwięcej deklaracji, ponieważ każda intkosztuje 4 bajty miejsca, w przeciwieństwie do dodawania, ,nktóre wynosi 2.

Podczas j„iteracji obliczeń” liczba „odstępów”, które należy pominąć, jest równa a[j](lub 2, jeśli jest pusta). Okazuje się, że jeśli pierwsze puste miejsce, które musimy wypełnić, znajduje się w pozycji k, k * a[j]daje nam „krok” ( s).