OEIS hat eine Variation (A111439) von Golombs Sequenz . A(n)Beschreibt wie in Golombs Sequenz, wie oft nin der Sequenz vorkommt. Darüber hinaus dürfen jedoch keine zwei aufeinander folgenden Nummern identisch sein. Wird beim Aufbau der Sequenz A(n)immer als kleinste positive Ganzzahl gewählt, die diese beiden Eigenschaften nicht verletzt. Aufgrund unzulässiger fortlaufender identischer Nummern schwankt die Serie mit zunehmender Größe leicht auf und ab. Hier sind die ersten 100 Begriffe:

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

Die vollständige Liste der ersten 10.000 Nummern finden Sie auf OEIS .

Die Herausforderung besteht darin, ein A(n)gegebenes Programm oder eine gegebene Funktion zu schreiben, die berechnet n. nist 1-basiert, um sicherzustellen, dass die selbstbeschreibende Eigenschaft funktioniert.

Regeln

Sie können ein Programm oder eine Funktion schreiben und eine unserer Standardmethoden zum Empfangen und Bereitstellen von Eingaben verwenden.

Sie können jede Programmiersprache verwenden , beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind.

Das ist Code-Golf , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .

Testfälle

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

Haskell , 67 Bytes

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

Definiert eine Funktion f. Probieren Sie es online! Die Rechenzeit f 15für TIO ist sehr langsam .

Erläuterung

Gehen Sie einfach zur Definition über: Wählen Sie in jeder Phase die minimale positive Zahl aus n, die die Bedingungen erfüllt (ungleich der vorherigen Eingabe und noch nicht aufgetreten f n).

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 Bytes

Vielen Dank an Martin Ender für die Suche nach einem zusätzlichen Byte für mich!

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

Unbenannte Funktion, die eine positive Ganzzahl nals Eingabe verwendet und eine positive Ganzzahl zurückgibt. Wir konstruieren die gesamte Liste der ersten nElemente dieser Sequenz und nehmen dann das LastElement. Die Liste wird erstellt, indem mit der leeren Liste begonnen {}und mit einer Funktion nin Folge (via Nest) bearbeitet wird .

Es handelt sich um die Funktion {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, die (im Wesentlichen ##&@@#) eine Teilliste von Sequenzwerten aufnimmt und den nächsten Wert an diese anfügt. Der nächste Wert wird berechnet, indem mit begonnen x=1und dann wiederholt ersetzt xwird x+1, solange die Bedingung x==Last@#||#~Count~x==#[[x]]erfüllt ist - mit anderen Worten, wenn es sich entweder xum das vorherige Element handelt oder wenn xes sich bereits in der Liste um die korrekte Anzahl von Malen handelt. Diese Funktion spuckt einige Fehler aus, da wir (zum Beispiel) das xth-Element der Anfangsliste nicht aufrufen sollten {}; Die Werte sind jedoch alle korrekt.

Python 2, 99 86 Bytes

Vielen Dank an @Dennis für einige Verbesserungen von insgesamt 13 Bytes!

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]

Das Programm geht ziemlich naiv vor: Es verfolgt die Liste der Werte, die es bisher ermittelt hat, und versucht, den nächsten Wert anzufügen. Es wird versucht, ein 1an das Ende der Liste anzuhängen , wenn dies möglich ist. wenn nicht, dann probiert es a 2und so weiter, bis etwas erlaubt ist.

Nun beginnen wir damit, die Ergebnisse für 1,2,3zu setzen 1,2,3. Dies wird getan, um Probleme mit der zu kurzen Liste der bereits berechneten Werte zu vermeiden: Ich vermute, dass wenn nzumindest 4dann a(n)streng kleiner ist als n. (In diesem Programm s[n]ist gleich a(n). Unsere Liste tatsächlich initialisiert werden , [0,1,2,3]da Listen 0-indexed in Python. So zum Beispiel a(1)=s[1]=1, und a(2)=s[2]=2.)

Nehmen wir also an, wir versuchen festzustellen s[m], was bedeutet, dass unsere Liste bereits enthält s[0], s[1], ..., s[m-1]. Wir fangen an t=1und versuchen zu setzen s[m]=1. Wenn das nicht funktioniert, gehen wir zu t=2und versuchen einzustellen s[m]=2. Bei jedem Inkrementieren tprüfen wir, ob s.count(t)==s[t]... aber die rechte Seite erzeugt keinen Fehler, solange wir nicht so hoch gehen müssen wie t=m. Die Vermutung besagt, dass wir das niemals müssen, da der erste Wert, den wir berechnen, tatsächlich ist s[4].

Diese Implementierung berechnet 3 weitere Werte der Sequenz als erforderlich. Wenn dies beispielsweise der Fall nist 8, wird eine Berechnung durchgeführt, s[11]bevor der Wert von zurückgegeben wird s[8].

Ich würde mich freuen, einen Beweis für die Vermutung zu sehen. Ich glaube, es kann durch (starke?) Induktion bewiesen werden.

Bearbeiten: Hier ist ein Beweis für die Vermutung . Wir beweisen tatsächlich eine etwas stärkere Form der Aussage, da sie keinen zusätzlichen Aufwand erfordert.

Satz: Für alle ngrößer als oder gleich 4ist der Term a(n)kleiner als oder gleich (n-2).

Beweis (durch starke Induktion): (Basis n=4): Die Aussage gilt für n=4, da a(4) = 2 = 4-2.

Nehmen wir nun an a(k), dass k-2für alle kvon 4bis neinschließlich kleiner oder gleich ist (und nehmen wir nan, dass dies mindestens so ist 4). Dies bedeutet insbesondere, dass alle vorherigen Terme der Sequenz höchstens waren (n-2). Wir müssen zeigen, dass a(n+1)das höchstens sein wird (n-1). Nun ist per Definition a(n)die kleinste positive Ganzzahl, die keine der Bedingungen verletzt. Wir müssen also nur zeigen, dass der Wert (n-1)keine der Bedingungen verletzt.

Der Wert (n-1)verletzt nicht die Bedingung "keine aufeinanderfolgenden Wiederholungen", da nach der Induktionshypothese der vorherige Eintrag höchstens war (n-2). Und es wird nicht die Bedingung "Ist a(m)die Anzahl der mAuftritte" verletzen , es (n-1)sei denn, es wurden bereits a(n-1)Zeiten erreicht . Aber durch die starke Induktionsannahme (n-1)war das schon 0mal erreicht worden und a(n-1)ist nicht gleich 0da a(m)für alle positiv m.

Daher a(n+1)ist kleiner oder gleich n-1 = (n+1)-2, wie gewünscht. QED.

Gelee , 17 Bytes

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

Die letzten drei Testfälle sind für TIO zu viel. Ich habe 1000 und 1257 vor Ort überprüft .

Probieren Sie es online! oder überprüfen Sie die ersten 100 Begriffe .

Wie es funktioniert

⁸Ç¡Ṫ          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 Bytes

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)

Dies ist eine rekursive Implementierung des @ mathmandan-Algorithmus .

Die Implementierung ist O (verrückt) : Eingabe 9 dauert lokal 2 Sekunden, Eingabe 10 52 Sekunden und Eingabe 11 17 Minuten und 28 Sekunden. Wenn es sich jedoch nicht um ein Lambda, sondern um eine reguläre Funktion handelt, können die Testfälle mithilfe von Memoization überprüft werden.

Probieren Sie es online!

Beachten Sie, dass TIO auch bei der Speicherung nicht rechnen kann f (1257) oder f (10000) (beides wird lokal überprüft).

05AB1E , 32 31 Bytes

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

Probieren Sie es online!

Erläuterung

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

Wir sind technisch in der Schleife, Gwenn wir N zur globalen Liste hinzufügen , aber alle Schleifen in 05AB1E verwenden dieselbe Variable N als Index, sodass die innere Schleife [...]das N überschrieben hat der GBedeutung wir außerhalb der Schleife hinzufügen können.

Probleme mit verschachtelten Schleifen und Bedingungen hindern uns daran, dies innerhalb der Schleife zu tun.

Befunge, 141 136 Bytes

<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

Probieren Sie es online!

Aufgrund der Speicherbeschränkungen von Befunge ist es nicht sinnvoll, alle vorherigen Einträge in der Sequenz zu verfolgen. Daher verwendet diese Lösung einen Algorithmus mit geringerem Speicherbedarf, der die Werte direkter berechnet.

Das heißt, wir sind immer noch durch die Zellengröße begrenzt, die im Befunge-93-Referenzinterpreter ein vorzeichenbehafteter 8-Bit-Wert ist, sodass die höchste gerade Zahl in der Sequenz A(1876) = 126und die höchste ungerade Zahl unterstützt wird A(1915) = 127.

Wenn Sie größere Werte testen möchten, müssen Sie einen Interpreter mit einer größeren Zellengröße verwenden. Dies sollte die meisten Befunge-98-Implementierungen einschließen ( Online ausprobieren ! ).

Python 2, 117 Bytes

Meh. Nicht so kurz. Die einfache iterative Lösung.

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]

Probieren Sie es online aus

Hier ist ein wirklich schlechter Versuch einer rekursiven Lösung (129 Bytes):

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)