OEIS ma odmianę (A111439) w sekwencji Golomb . Podobnie jak w sekwencji Golomb, A(n)opisuje, jak często npojawia się w sekwencji. Ale dodatkowo żadne dwie kolejne liczby nie mogą być identyczne. Podczas budowania sekwencji A(n)jest zawsze wybierana jako najmniejsza dodatnia liczba całkowita, która nie narusza tych dwóch właściwości. Z powodu niedozwolonych kolejnych identycznych liczb, seria kołysze się nieznacznie w górę i w dół, gdy rośnie. Oto pierwsze 100 warunków:

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9, 
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12, 
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15, 
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18, 
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

Pełna lista pierwszych 10 000 numerów znajduje się w OEIS .

Wyzwanie polega na napisaniu A(n)podanego programu lub funkcji n. nopiera się na 1, aby upewnić się, że własność samoopisująca działa.

Zasady

Możesz napisać program lub funkcję i użyć dowolnej z naszych standardowych metod otrzymywania danych wejściowych i dostarczania danych wyjściowych.

Możesz używać dowolnego języka programowania , ale pamiętaj, że te luki są domyślnie zabronione.

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Przypadki testowe

n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

Haskell , 67 bajtów

f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

Definiuje funkcję f. Wypróbuj online! Jest to bardzo wolny f 15czas obliczeń w TIO.

Wyjaśnienie

Po prostu z definicją: na każdym etapie wybierz minimalną liczbę dodatnią, nktóra spełnia ograniczenia (nie jest równa poprzedniej pozycji i nie wystąpiła f njeszcze razy).

f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

Mathematica, 69 68 bajtów

Dzięki Martinowi Enderowi za znalezienie dla mnie dodatkowego 1 bajtu!

Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Nienazwana funkcja przyjmująca dodatnią liczbę całkowitą njako dane wejściowe i zwracająca dodatnią liczbę całkowitą. Tworzymy całą listę pierwszych nelementów tej sekwencji, a następnie pobieramy Lastelement. Lista jest konstruowana, zaczynając od pustej listy{} i operując na niej z funkcją nrazy z rzędu (via Nest).

Chodzi o tę funkcję {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, która pobiera częściową listę wartości sekwencji (zasadniczo ##&@@#) i dołącza do niej następną wartość. Następna wartość jest obliczana przez zaczynając x=1, a następnie wielokrotnie zastępując xprzez x+1tak długo jak warunek x==Last@#||#~Count~x==#[[x]]jest spełniony, innymi słowy, czy też xjest element poprzedni, albo xjest już na liście prawidłowa ilość razy. Ta funkcja wyrzuca kilka błędów, ponieważ (na przykład) nie powinniśmy wywoływać xelementu th z początkowej listy {}; jednak wszystkie wartości są prawidłowe.

Python 2, 99 86 bajtów

Dzięki @Dennis za kilka ulepszeń o łącznej wartości 13 bajtów!

s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

Program działa dość naiwnie: śledzi listę ustalonych do tej pory wartości i szuka kolejnej wartości. 1Jeśli to możliwe, próbuje dołączyć a na końcu listy; jeśli nie, to spróbuje 2i tak dalej, aż coś będzie dozwolone.

Teraz możemy zacząć od wysiewu wyniki dla 1,2,3być 1,2,3. Odbywa się to w celu uniknięcia problemów z zbyt krótką listą już obliczonych wartości: przypuszczam, że jeśli nprzynajmniej jest, 4to a(n)jest dokładnie mniejsze niż n. (W tym programie s[n]jest równy a(n). Nasza lista jest faktycznie inicjowana, [0,1,2,3]ponieważ listy są 0w Pythonie indeksowane. Więc na przykład a(1)=s[1]=1i a(2)=s[2]=2.)

Powiedzmy, że próbujemy ustalić s[m], co oznacza, że ​​nasza lista już zawiera s[0], s[1], ..., s[m-1]. Zaczniemy od t=1i spróbujemy ustawić s[m]=1. Kiedy to nie działa, idziemy do t=2i próbujemy ustawić s[m]=2. Za każdym razem zwiększamy t, sprawdzamy, czy s.count(t)==s[t]... ale prawa strona nie spowoduje błędu, o ile nigdy nie będziemy musieli sięgać tak wysoko t=m. Przypuszczenie mówi, że nigdy nie musimy, ponieważ pierwsza wartość, którą obliczamy, jest w rzeczywistości s[4].

Ta implementacja oblicza 3 kolejne wartości sekwencji, niż jest to konieczne. Na przykład, jeśli ntak 8, oblicza, s[11]zanim zwróci wartość s[8].

Byłbym szczęśliwy widząc dowód przypuszczenia. Wierzę, że można to udowodnić za pomocą (silnej?) Indukcji.

Edycja: Oto dowód przypuszczenia . W rzeczywistości okazujemy się nieco mocniejszą formą oświadczenia, ponieważ nie wymaga dodatkowej pracy.

Twierdzenie: dla wszystkich nwiększych lub równych 4termin a(n)jest mniejszy lub równy (n-2).

Dowód (według silnej indukcji): (Podstawa n=4): Od tego n=4momentu stwierdzenie jest prawdziwe a(4) = 2 = 4-2.

Załóżmy teraz, a(k)jest mniejszy niż lub równy k-2dla wszystkich kod 4poprzez nwłącznie (a zakładamy, njest co najmniej 4). W szczególności oznacza to, że wszystkie poprzednie warunki sekwencji były co najwyżej (n-2). Musimy pokazać, że a(n+1)będzie co najwyżej (n-1). Teraz, z definicji, a(n)jest najmniejszą dodatnią liczbą całkowitą, która nie narusza żadnego z warunków, więc musimy tylko pokazać, że wartość (n-1)nie naruszy żadnego z warunków.

Wartość (n-1)nie narusza warunku „brak kolejnych powtórzeń”, ponieważ według hipotezy indukcyjnej poprzedni wpis był co najwyżej (n-2). I nie narusza warunku „ile a(m)razy się mpojawia”, chyba (n-1)że zostały już osiągnięte a(n-1)czasy. Ale przy silnym założeniu indukcyjnym, (n-1)osiągnięto już 0czasy i a(n-1)nie jest równy, 0ponieważ a(m)jest pozytywny dla wszystkich m.

Dlatego a(n+1)jest mniejszy lub równy n-1 = (n+1)-2, jak pożądane. CO BYŁO DO OKAZANIA.

Galaretka , 17 bajtów

Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

Ostatnie trzy przypadki testowe to za dużo dla TIO. Lokalnie zweryfikowałem 1000 i 1257 .

Wypróbuj online! lub sprawdź pierwsze 100 warunków .

Jak to działa

⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.


Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

Python 2 , 77 74 bajtów

f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

To jest rekurencyjna implementacja algorytmu @ mathmandan .

Implementacja jest O (szalona) : wejście 9 zajmuje lokalnie 2 sekundy, wejście 10 52 sekund i wejście 11 17 minut i 28 sekund. Jeśli jednak zadeklarowano go jako funkcję zwykłą, a nie lambda, do weryfikacji przypadków testowych można użyć memoizacji.

Wypróbuj online!

Należy pamiętać, że nawet w przypadku zapamiętywania TIO nie może obliczyć f (1257) lub f (10000) (oba zweryfikowane lokalnie).

05AB1E , 32 31 bajtów

XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

Wypróbuj online!

Wyjaśnienie

XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true     
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list 
                                   and output last value in list and end of program

Jesteśmy technicznie w pętli G, gdy dodamy N do globalnej listy, ale wszystkie pętle 05AB1E używać tej samej zmiennej N jako wskaźnika, więc wewnętrzna pętla [...]ma nadpisane na N o Gsens możemy dodać ją na zewnątrz pętli.

Problemy z zagnieżdżonymi pętlami i warunkami warunkowymi uniemożliwiają nam wykonanie tego w pętli.

Befunge, 141 136 bajtów

<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

Wypróbuj online!

Ze względu na ograniczenia pamięci Befunge, śledzenie wszystkich poprzednich wpisów w sekwencji nie jest zbyt praktyczne, dlatego w tym rozwiązaniu zastosowano algorytm o mniejszej powierzchni pamięci, który oblicza wartości bardziej bezpośrednio.

To powiedziawszy, wciąż jesteśmy ograniczeni wielkością komórki, która w interpretera referencyjnym Befunge-93 jest 8-bitową wartością ze znakiem, więc najwyższą obsługiwaną liczbą parzystą w sekwencji jest A(1876) = 126, a najwyższą obsługiwaną liczbą nieparzystą jest A(1915) = 127.

Jeśli chcesz przetestować większe wartości, musisz użyć interpretera o większym rozmiarze komórki. Powinno to obejmować większość implementacji Befunge-98 ( wypróbuj online! ).

Python 2, 117 bajtów

Meh Nie tak krótko. Proste iteracyjne rozwiązanie.

L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

Wypróbuj online

Oto naprawdę zła próba rozwiązania rekurencyjnego (129 bajtów):

def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)