Inspiriert von der vorherigen Frage .

Golombs selbstbeschreibende Sequenz g (n) ist eine Sequenz, bei der jede natürliche Zahl ninnerhalb der Sequenz g (n) mal wiederholt wird.

Die ersten Zahlen in der Sequenz sind:

n    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
g(n) 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Sie können sehen, dass g (4) = 3 ist und dass "4" dreimal in der Sequenz wiederholt wird.

Bei einer Eingabe von n, Ausgabe g(n).

Einschränkungen: n <100000.

Der kleinste Code gewinnt.

GolfScript (31 Zeichen)

~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=

Demo

Gelee , nicht konkurrierend

10 Bytes Diese Antwort ist nicht konkurrierend, da die Herausforderung vor der Erstellung von Jelly liegt.

’ßßạ¹ß‘µṖ¡

Dies verwendet die rekursive Formel a (1) = 1, a (n + 1) = 1 + a (n + 1 - a (a (n))) von der OEIS-Seite.

Probieren Sie es online aus!

Wie es funktioniert

’ßßạ¹ß‘µṖ¡ Main link. Input: n

’          Decrement; yield n - 1.
 ßß        Recursively call the main link twice, with argument n - 1.
   ạ¹      Take the absolute difference of a(a(n - 1)) and n.
     ß     Recursively call the main link, with argument n - a(a(n - 1)).
      ‘    Increment the result, yielding 1 + a(n - a(a(n - 1))).
       µ   Combine the chain to the left into a single link.
        Ṗ  Pop [1, ..., n]. This yields [] iff n == 1.
         ¡ Execute the chain iff Ṗ returned a non-empty array.

PHP - 63 Zeichen

function g($n){for(;++$i<=$n;){for(;++$j<=$i;){echo $i;}$j=0;}}

Schnell UND kurz.

Ich habe anscheinend die falsche Reihenfolge im Sinn gehabt. Derp.

Dies ist RICHTIG, schnell und kurz.

function g($n){for(;++$i<$n;){echo round(1.201*pow($i,.618));}}

Die Genauigkeit kann über die erforderliche Marke von 100.000 hinaus leiden, aber ich habe die Marke tatsächlich erreicht.

PHP

Diese rekursive Version ist kürzer (60), aber rechnerisch ineffizient:

function g($n){return$n==1?1:1+g($n-g(g($n-1)));}echo g($n);

Das geht viel schneller, aber länger (78):

$a=[1,2,2];for($i=3;$i<$n;$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Viel schneller, aber mit 89 Zeichen wäre:

$a=[1,2,2];for($i=3;!isset($a[$n-1]);$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Welches ist O (n)

Haskell, 30 27 Zeichen

g 1=1
g n=1+(g$n-g(g$n-1))

Oase , 7 Bytes (nicht konkurrierend)

Code:

n<aae>T

Probieren Sie es online aus!

Oasis ist eine von Adnan entworfene Sprache, die auf Sequenzen spezialisiert ist.

Derzeit kann diese Sprache Rekursion und geschlossene Form ausführen.

Das Tam Ende ist eine Abkürzung für 10, was darauf hinweist, dass a(0) = 0und a(1) = 1. Um weitere Testfälle hinzuzufügen, fügen Sie diese einfach der Liste am Ende hinzu.

n<aae>T
n<aae>10  expanded

       0  a(0) = 0
      1   a(1) = 1

n         push n (input)
 <        -1
  a       a(above)  [a is the sequence]
   a      a(above)
    e     a(n-above)
     >    +1

Jetzt haben wir im Wesentlichen berechnet a(n-a(a(n-1))+1.

Perl, 48 Zeichen

(@a=(@a,($,)x($a[$,++]||$,)))<$_?redo:say$,for<>

Eingabe auf stdin, Ausgabe auf stdout. Benötigt Perl 5.10+ und das -M5.010, um die sayFunktion zu aktivieren . Dauert aufgrund ineffizienter Array-Manipulation etwa O ( n ² ), ist aber immer noch schnell genug, um problemlos bis zum 100.000sten Term zu berechnen.

Julia - 28

Auf rekursive Weise:

a(n)=n==1?1:1+a(n-a(a(n-1)))

Ausgabe:

[a(i) for i=1:20]'
1x20 Array{Int64,2}:
 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Python - 64 Zeichen

n=input()
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]

Javascript, 93 Zeichen

c=[,1],i=c.length;function g(n){for(i;i<n;i++) c[i]=g(i);return c[n]||(c[n]=1+g(n-g(g(n-1))))}

J, 43 Zeichen

f=:3 :'<.@:+&0.5(p^2-p)*y^p-1[p=:(+%)/20$1'

Definiert eine Funktion unter Verwendung des asymptotischen Ausdrucks auf der Wikipedia-Seite.

   f 5
3
   f 20
8
   f 100000
1479

Ärgerlicherweise werden 9 Zeichen verwendet, die nur auf die nächste Ganzzahl gerundet werden.

Vorspiel , 69 55 54 Bytes

?1-(v  #1)-
1   0v ^(#    0 (1+0)#)!
    (#)  ^#1-(0)#

Wenn ein standardkonformer Interpreter verwendet wird, werden Eingabe und Ausgabe als Bytewerte verwendet . Um Dezimalzahlen in STDIN / STDOUT tatsächlich verwenden zu können, benötigen Sie den Python-Interpreter mit NUMERIC_OUTPUT = Trueund eine zusätzliche Option NUMERIC_INPUT = True.

Erläuterung

Das Grundgerüst des Programms ist

?1-(    1 -
1                     )!

Wir lesen die Eingabe Nauf die erste Stimme und dekrementieren sie, um sie zu erhalten N-1. Wir initialisieren auch die zweite Stimme zu 1. Dann schleifen wir N-1einmal, wobei jede Iteration den nächsten Wert der Sequenz auf dem zweiten Stapel erhält. Am Ende drucken wir die Nth Nummer.

Die Idee des Programms besteht darin, jedes Element der Sequenz in eine Warteschlange bei der dritten Stimme zu stellen und den Kopf dieser Warteschlange in jeder Iteration zu dekrementieren. Wenn der Kopf erreicht ist 0, erhöhen wir den Wert der Sequenz und entfernen diesen 0.

Das Problem ist nun, dass Prelude Stapel und keine Warteschlangen verwendet. Wir müssen diesen Stapel also ein wenig verschieben, um ihn wie eine Warteschlange zu verwenden.

v  #
0v ^
(#)

Dies kopiert den aktuellen Wert der Sequenz in die erste Stimme (als temporäre Kopie) und drückt a 0auf die zweite Stimme (um das Ende der Warteschlange zu markieren). Und führt dann eine Schleife aus, um den dritten Stapel auf den zweiten zu verschieben (und dadurch umzukehren). Nach der Schleife legen wir die Kopie des aktuellen Sequenzwerts auf den zweiten Stapel (der das Ende unserer Warteschlange darstellt).

 )
(#
 ^#1-

Das sieht ein bisschen hässlich aus, aber im Grunde ist es eine Schleife, die den Stack zurück auf die dritte Stimme verschiebt. Da sich das )in derselben Spalte wie die Schaltanweisungen befindet, wird das, was 0wir früher auf die zweite Stimme gesetzt haben, auch auf die dritte Stimme landen, sodass wir es mit einer anderen entfernen müssen #. Verringern Sie dann die Spitze der 3. Stimme, dh den Kopf der Warteschlange.

Jetzt wird es etwas nervig - wir wollen etwas Code ausführen, wenn dieser Wert ist 0, aber die einzige Kontrollstruktur von Prelude (die Schleife) reagiert nur auf Werte ungleich Null.

 0 (1+0)#
(0)#

Beachten Sie, dass die Spitze der zweiten Stimme wahr ist (da die Golomb-Sequenz keine 0s enthält). Die Arbeitslast geht also in diese Stimme (das letztere Klammerpaar). Wir müssen nur verhindern, dass dies geschieht, wenn der Leiter der Warteschlange noch 0nicht vorhanden ist. Also haben wir zuerst eine "Schleife" bei der dritten Stimme, die a 0auf die zweite Stimme drückt, wenn der Kopf der Warteschlange immer noch nicht Null ist. Wir setzen auch eine 0dritte Stimme ein, um die Schleife sofort zu verlassen. Die #auf der dritten Stimme entfernt dann entweder das 0oder entfernt den Kopf der Warteschlange , wenn das bereits Null war. Jetzt wird diese zweite Schleife nur eingegeben, wenn der Kopf der Warteschlange Null war (und die0auf die zweite Stimme wurde nie gedrückt). In diesem Fall erhöhen wir den aktuellen Wert der Sequenz und drücken a 0, um die Schleife zu verlassen. Schließlich wird es immer eine 0oben auf dem Stapel geben, die wir verwerfen müssen.

Ich habe dir gesagt, dass logische Negation im Präludium nervt ...

Mathematica, 27 Bytes

f@1=1;f@n_:=1+f[n-f@f[n-1]]

Eine andere rekursive Lösung.

CJam, 14 Bytes

CJam ist viel jünger als diese Herausforderung, daher ist diese Antwort nicht für das grüne Häkchen geeignet. Es ist jedoch ziemlich selten, dass Sie jdies gut nutzen können, deshalb wollte ich es trotzdem posten.

l~2,{_(jj-j)}j

Testen Sie es hier.

Erläuterung

jist im Grunde der "gespeicherte Rekursionsoperator". Es braucht eine ganze Zahl N, ein Array und einen Block F. Das Array wird zum Initialisieren der Memoisierung verwendet: Das Element am Index iwird für zurückgegeben F(i). jBerechnet dann F(N)entweder durch nNachschlagen oder durch Ausführen des Blocks (mit auf dem Stapel), wenn der Wert noch nicht gespeichert wurde. Die wirklich raffinierte Funktion ist, dass innerhalb des Blocks jnur eine Ganzzahl verwendet iwird und F(i)rekursiv aufgerufen wird. Also hier ist der Code:

l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";

J, 16 Bytes

    <:{1($1+I.)^:[~]

    (<:{1($1+I.)^:[~]) every 1+i.20  NB. results for inputs 1..20
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8

Diese Lösung basiert stark auf der Lösung von algorithmshark für ein ähnliches Problem. Dort finden Sie eine Erklärung zu dieser Methode.

J, 33 Bytes

In diesem Ansatz baue ich eine Sequenz h(k)mit den Werten der ersten Indizes auf, iwo die g(i)=kso sind h = 1 2 4 6 9 12 16.... Wir können h(k)ziemlich einfach h(1..k-1)mit dem Ausdruck kommen, ({:+1+[:+/#<:])wo die Eingabe ist h(1..k-1).

Die Berechnung der Ausgabe von hist unkompliziert.h ([:+/]>:[) input

[:+/]>:1 2(,{:+1+[:+/#<:])@]^:[~]

Brachylog , 13 Bytes (nicht konkurrierend)

1|-₁↰↰:?-ṅ↰+₁

Probieren Sie es online aus!

Erläuterung

1                Input = 1 = Output
 |               Or
  -₁↰            a(Input - 1)
     ↰           a(a(Input - 1))
      :?-ṅ       Input - a(a(Input - 1))
          ↰      a(Input - a(a(Input - 1))
           +₁    1 + a(Input - a(a(Input -1))

Python - 76 Zeichen

n=20;g=[1,2,2];[[g.append(i)for j in range(g[i-1])]for i in range(3,n)];g[n]

JavaScript - 48 Zeichen

for(g=[,i=j=k=1,2];i<1e5;k=--k?k:g[++j])g[i++]=j

Erstellt ein 1-indiziertes Array gmit den Sequenzwerten.

Bearbeiten - JavaScript - 46 Zeichen

v=[,1];for(x=2;x<1e5;)v[x]=1+v[x-v[v[x++-1]]]

Erstellt ein 1-indiziertes Array vmit den Sequenzwerten.

Bearbeiten 2 - ECMAScript 6 - 27 Zeichen

g=x=>x-1?1+g(x-g(g(x-1))):1

Die ersten beiden sind ziemlich schnell - die dritte ist sehr langsam

Haskell, 63 Bytes

f n|n<3=n|n<4=2|1>0=foldr1(++)[replicate(f m)m|m<-[1..]]!!(n-1)

Dies ist der naive Ansatz, ich war mir der sehr kurzen Wiederholung nicht bewusst, als ich dies schrieb, aber ich dachte, ich würde es trotzdem posten, auch wenn es länger ist als alle anderen Haskell-Implementierungen, wie z

Berechnen Sie den n-ten Term von Golombs selbstbeschreibender Sequenz

und

/codegolf//a/23979/24877