Die Sylvester-Sequenz OEIS A000058 ist eine Ganzzahlsequenz, die wie folgt definiert ist:

Jedes Mitglied ist das Produkt aller vorherigen Mitglieder plus eins. Das erste Mitglied der Sequenz ist 2.

Aufgabe

Erstellen Sie das kleinstmögliche Programm, das ein n benötigt und den n-ten Term von Sylvester's Sequence berechnet. Es gelten Standardeingaben, -ausgaben und -lücken. Da das Ergebnis sehr schnell wächst, ist nicht zu erwarten, dass ein Begriff verwendet wird, dessen Ergebnis in der von Ihnen gewählten Sprache einen Überlauf verursachen würde.

Testfälle

Sie können entweder keine oder eine Indizierung verwenden. (Hier verwende ich die Nullindizierung)

>>0
2
>>1
3
>>2
7
>>3
43
>>4
1807

Brain-Flak , 76 68 58 52 46 Bytes

<>(()())<>{({}[()])<>({({}[()])({})}{}())<>}<>

Probieren Sie es online!

Verwendet stattdessen diese Beziehung:

welches von dieser Beziehung abgeleitet ist, modifiziert von der, die in der Sequenz angegeben ist:

a(n+1) = a(n) * (a(n) - 1) + 1.

Erläuterung

Eine Dokumentation der einzelnen Befehle finden Sie auf der GitHub-Seite .

Es gibt zwei Stapel in Brain-Flak, die ich als Stapel 1 bzw. Stapel 2 bezeichnen werde.

Die Eingabe wird in Stapel 1 gespeichert.

<>(()())<>             Store 2 in Stack 2.

{                      while(Stack_1 != 0){
  ({}[()])                 Stack_1 <- Stack_1 - 1;
  <>                       Switch stack.
  ({({}[()])({})}{}())     Generate the next number in Stack 2.
  <>                       Switch back to Stack 1.
}

<>                     Switch to Stack 2, implicitly print.

Für den Generierungsalgorithmus:

({({}[()])({})}{}())      Top <- (Top + Top + (Top-1) + (Top-1) + ... + 0) + 1

(                  )      Push the sum of the numbers evaluated in the process:

 {            }               while(Top != 0){
  ({}[()])                        Pop Top, push Top-1    (added to sum)
          ({})                    Pop again, push again  (added to sum)
                              }

               {}             Top of stack is now zero, pop it.
                 ()           Evaluates to 1 (added to sum).

Alternative 46-Byte-Version

Dies verwendet nur einen Stapel.

({}<(()())>){({}<({({}[()])({})}{}())>[()])}{}

Probieren Sie es online!

Gelee , 5 Bytes

Ḷ߀P‘

Dies verwendet eine 0-basierte Indizierung und die Definition aus der Herausforderungsspezifikation.

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Ḷ߀P‘  Main link. Argument: n

Ḷ      Unlength; yield [0, ..., n - 1].
 ߀    Recursively apply the main link to each integer in that range.
   P   Take the product. This yields 1 for an empty range.
    ‘  Increment.

Hexagony , 27 Bytes

1{?)=}&~".>")!@(</=+={"/>}*

Entfaltet:

    1 { ? )
   = } & ~ "
  . > " ) ! @
 ( < / = + = {
  " / > } * .
   . . . . .
    . . . .

Probieren Sie es online!

Erläuterung

Betrachten wir die Reihenfolge b(a) = a(n) - 1und ordnen sie ein wenig um:

b(a) = a(n) - 1
     = a(n-1)*(a(n-1)-1) + 1 - 1
     = (b(n-1) + 1)*(b(n-1) + 1 - 1)
     = (b(n-1) + 1)*b(n-1)
     = b(n-1)^2 + b(n-1)

Diese Sequenz ist sehr ähnlich, aber wir können das Inkrement bis zum Ende verschieben, wodurch ein Byte in diesem Programm gespeichert wird.

Also hier ist der kommentierte Quellcode:

^{Erstellt mit Timwis HexagonyColorer .}

Und hier ist ein Speicherdiagramm (das rote Dreieck zeigt die ursprüngliche Position und Ausrichtung des Speicherzeigers):

^{Erstellt mit Timwis EsotericIDE .}

Der Code beginnt auf dem grauen Pfad, der die linke Ecke einhüllt, sodass das anfängliche lineare Bit wie folgt lautet:

1{?)(
1      Set edge b(1) to 1.
 {     Move MP to edge N.
  ?    Read input into edge N.
   )(  Increment, decrement (no-op).

Dann trifft der Code die <Verzweigung und zeigt den Anfang (und das Ende) der Hauptschleife an. Solange die N- Flanke einen positiven Wert hat, wird der grüne Pfad ausgeführt. Dieser Pfad wird ein paar Mal um das Raster gewickelt, ist aber eigentlich völlig linear:

""~&}=.*}=+={....(

Das .sind No-Ops, der eigentliche Code lautet also:

""~&}=*}=+={(
""             Move the MP to edge "copy".
  ~            Negate. This is to ensure that the value is negative so that &...
   &           ...copies the left-hand neighbour, i.e. b(i).
    }=         Move the MP to edge b(i)^2 and turn it around.
      *        Multiply the two copies of b(i) to compute b(i)^2.
       }=      Move the MP back to edge b(i) and turn it around.
         +     Add the values in edges "copy" and b(i)^2 to compute
               b(i) + b(i)^2 = b(i+1).
          ={   Turn the memory pointer around and move to edge N.
            (  Decrement.

Sobald diese Dekrementierung auf reduziert ist N, 0wird der rote Pfad ausgeführt:

")!@
"     Move MP back to edge b(i) (which now holds b(N)).
 )    Increment to get a(N).
  !   Print as integer.
   @  Terminate the program.

J, 18 14 12 Bytes

Diese Version dank Randomra. Ich werde später versuchen, eine detaillierte Erklärung zu schreiben.

0&(]*:-<:)2:

J, 14 Bytes

Diese Version dank Meilen. Verwendete das Power-Adverb ^:anstelle der folgenden Agenda. Weitere Erklärungen folgen.

2(]*:-<:)^:[~]

J, 18 Bytes

2:`(1+*/@$:@i.)@.*

0-indiziert.

Beispiele

   e =: 2:`(1+*/@$:@i.)@.*
   e 1
3
   e 2
7
   e 3
43
   e 4
1807
   x: e i. 10
2 3 7 43 1807 3263443 10650056950807 113423713055421862298779648 12864938683278674737956996400574416174101565840293888 1655066473245199944217466828172807675196959605278049661438916426914992848    91480678309535880456026315554816
   |: ,: x: e i. 10
                                                                                                        2
                                                                                                        3
                                                                                                        7
                                                                                                       43
                                                                                                     1807
                                                                                                  3263443
                                                                                           10650056950807
                                                                              113423713055421862298779648
                                                    12864938683278674737956996400574416174101565840293888
165506647324519994421746682817280767519695960527804966143891642691499284891480678309535880456026315554816

Erläuterung

Dies ist eine Agenda, die so aussieht:

           ┌─ 2:
           │    ┌─ 1
       ┌───┤    ├─ +
       │   └────┤           ┌─ / ─── *
── @. ─┤        │     ┌─ @ ─┴─ $:
       │        └─ @ ─┴─ i.
       └─ *

(Generiert mit (9!:7)'┌┬┐├┼┤└┴┘│─'then 5!:4<'e')

Zerlegen:

       ┌─ ...
       │
── @. ─┤
       │
       └─ *

Mit dem oberen Zweig als Gerundium Gund dem unteren als Selektor Fist dies:

e n     <=>     ((F n) { G) n

Dies nutzt die konstante Funktion , 2:wenn 0 = * n, das heißt, wenn die Vorzeichen Null ist (also nNull ist ). Ansonsten verwenden wir diese Gabel:

  ┌─ 1
  ├─ +
──┤           ┌─ / ─── *
  │     ┌─ @ ─┴─ $:
  └─ @ ─┴─ i.

Welches ist eins plus die folgenden auf Serie:

            ┌─ / ─── *
      ┌─ @ ─┴─ $:
── @ ─┴─ i.

Bei weiterer Zerlegung ist dies product ( */) über self-reference ( $:) über range ( i.).

Perl 6 , 24 Bytes

{(2,{1+[*] @_}...*)[$_]}

{(2,{1+.²-$_}...*)[$_]}

Erläuterung

# bare block with implicit parameter ｢$_｣
{
  (
    # You can replace 2 with 1 here
    # so that it uses 1 based indexing
    # rather than 0 based
    2,

    # bare block with implicit parameter ｢@_｣
    {
      1 +

      # reduce the input of this inner block with ｢&infix:<*>｣
      # ( the input is all of them generated when using a slurpy @ var )
      [*] @_

      # that is the same as:
      # ｢@_.reduce: &infix:<*>｣
    }

    # keep calling that to generate more values until:
    ...

    # forever
    *

  # get the value as indexed by the input
  )[ $_ ]
}

Verwendung:

my &code = {(2,{1+[*] @_}...*)[$_]}

say code 0; # 2
say code 1; # 3
say code 2; # 7
say code 3; # 43
say code 4; # 1807

# you can even give it a range
say code 4..7;
# (1807 3263443 10650056950807 113423713055421844361000443)

say code 8;
# 12864938683278671740537145998360961546653259485195807
say code 9;
# 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
say code 10;
# 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807

my $start = now;
# how many digits are there in the 20th value
say chars code 20;
# 213441

my $finish = now;
# how long did it take to generate the values up to 20
say $finish - $start, ' seconds';
# 49.7069076 seconds

Haskell, 26 Bytes

f n|n<1=2|m<-f$n-1=1+m*m-m

Anwendungsbeispiel: f 4-> 1807.

Java 7, 46 42 Bytes

int f(int n){return--n<0?2:f(n)*~-f(n)+1;}

Verwendet die 0-Indizierung mit der üblichen Formel. Ich tauschte n*n-nfür n*(n-1)obwohl, da Java keine handliche Strombetreiber haben, und die f()Anrufe wurden immer lang.

Haskell, 25 Bytes

(iterate(\m->m*m-m+1)2!!)

SILOS , 60 Bytes

readIO 
p = 2
lblL
r = p
r + 1
p * r
i - 1
if i L
printInt r

Probieren Sie es online!

Port of meine Antwort in C .

Brain-Flak , 158 154 Bytes

Undichte Nonne hat mich hier geschlagen

({}<(()())>){({}[()]<<>(())<>([]){{}<>({}<<>(({}<>))><>)<>({<({}[()])><>({})<>}{})<>{}([])}{}<>({}())([]){{}({}<>)<>([])}{}<>>)}{}([][()]){{}{}([][()])}{} 

Probieren Sie es online!

Erläuterung

Setze eine Zwei unter die Eingabe a (0)

({}<(()())>) 

Wenn die Eingabe größer als Null ist, subtrahieren Sie Eins von der Eingabe und ...

{
({}[()]

Schweigend...

<

Legen Sie einen auf den anderen Stapel, um als Katalysator für die Multiplikation <> (()) <> zu wirken

Während der Stapel nicht leer ist

 ([])
 {
  {}

Bewegen Sie den oberen Rand der Liste und kopieren Sie

  <>({}<<>(({}<>))><>)

Den Katalysator mit der Kopie multiplizieren

  <>({<({}[()])><>({})<>}{})<>{}
  ([])
 }
 {}

Füge eins hinzu

 <>({}())

Verschieben Sie die Sequenz zurück zum richtigen Stapel

 ([])
 {
 {}
 ({}<>)<>
 ([])
 }
 {}
 <>
>)
}{}

Entfernen Sie alle Elemente außer dem untersten Element (dh der zuletzt erstellten Nummer).

([][()])
{
{}
{}
([][()])
}
{}

C 32 Bytes

f(n){return--n?f(n)*~-f(n)+1:2;}

Verwendet 1-basierte Indizierung. Teste es auf Ideone .

Eigentlich 9 Bytes

2@`rΣτu`n

Probieren Sie es online!

Verwendet stattdessen diese Beziehung:

welches von dieser Beziehung abgeleitet ist, modifiziert von der, die in der Sequenz angegeben ist:

a(n+1) = a(n) * (a(n) - 1) + 1.

R, 44 42 41 Bytes

2 Bytes sparen dank JDL

1 Byte sparen dank user5957401

f=function(n)ifelse(n,(a=f(n-1))^2-a+1,2)

Oasis , 4 Bytes (nicht konkurrierend)

Wahrscheinlich meine letzte Sprache aus der Golffamilie! Nicht konkurrierend, da die Sprache die Herausforderung datiert.

Code:

²->2

Alternative Lösung dank Zwei :

<*>2

Erweiterte Version:

a(n) = ²->
a(0) = 2

Erläuterung:

²    # Stack is empty, so calculate a(n - 1) ** 2.
 -   # Subtract, arity 2, so use a(n - 1).
  >  # Increment by 1.

Verwendet die CP-1252- Codierung. Probieren Sie es online!

Python, 38 36 Bytes

2 Bytes dank Dennis.

f=lambda n:0**n*2or~-f(n-1)*f(n-1)+1

Ideone es!

Verwendet stattdessen diese Beziehung, die von der in der Sequenz angegebenen abgewandelt wurde:

a(n+1) = a(n) * (a(n) - 1) + 1

Erläuterung

0**n*2Gibt 2wann n=0und 0andernfalls zurück, da 0**0dies 1in Python definiert ist.

Cheddar , 26 Bytes

n g->n?g(n-=1)**2-g(n)+1:2

Probieren Sie es online!

Ziemlich idiomatisch.

Erläuterung

n g ->    // Input n, g is this function
  n ?     // if n is > 1
    g(n-=1)**2-g(n)+1   // Do equation specified in OEIS
  : 2     // if n == 0 return 2

CJam, 10 Bytes

2{_(*)}ri*

Verwendet eine 0-basierte Indizierung. Probieren Sie es online!

05AB1E , 7 Bytes

2sFD<*>

Erklärt

Verwendet nullbasierte Indizierung.

2         # push 2 (initialization for n=0)
 sF       # input nr of times do
   D<*    # x(x-1)
      >   # add 1

Probieren Sie es online!

Prolog, 49 Bytes

a(0,2).
a(N,R):-N>0,M is N-1,a(M,T),R is T*T-T+1.

SILOS 201 Bytes

readIO 
def : lbl
set 128 2
set 129 3
j = i
if j z
print 2
GOTO e
:z
j - 1
if j Z
print 3
GOTO e
:Z
i - 1
:a
a = 127
b = 1
c = 1
:b
b * c
a + 1
c = get a
if c b
b + 1
set a b
i - 1
if i a
printInt b
:e

Probieren Sie es einfach online aus!

Gelee , 7 Bytes

²_’
2Ç¡

Probieren Sie es online!

Verwendet stattdessen die in der Sequenz angegebene Beziehung: a(n+1) = a(n)^2 - a(n) + 1

Erläuterung

2Ç¡   Main chain, argument in input

2     Start with 2
  ¡   Repeat as many times as the input:
 Ç        the helper link.


²_’   Helper link, argument: z
²     z²
  ’   z - 1
 _    subtraction, yielding z² - (z-1) = z² - z + 1

C 46 Bytes

s(n,p,r){for(p=r=2;n-->0;p*=r)r=p+1;return r;}

Ideone es!

Verwendet pals vorübergehende Lagerung des Produkts.

Grundsätzlich habe ich zwei Sequenzen definiert p(n)und r(n), wo r(n)=p(n-1)+1und p(n)=p(n-1)*r(n).

r(n) ist die erforderliche Reihenfolge.

R 50 46 44 Bytes

    n=scan();v=2;if(n)for(i in 1:n){v=v^2-v+1};v

Anstatt die gesamte Sequenz zu verfolgen, verfolgen wir nur das Produkt, das der angegebenen quadratischen Aktualisierungsregel folgt, solange n> 1 n> 0 ist. (Diese Sequenz verwendet die Konvention "Start bei einer Null".)

Durch die Verwendung der Null-Start-Konvention werden einige Bytes gespart, da wir if (n) anstelle von if (n> 1) verwenden können.

Qualle , 13 Bytes

p
\Ai
&(*
><2

Probieren Sie es online!

Erläuterung

Beginnen wir von unten nach oben:

(*
<

Dies ist ein Hook, der eine Funktion definiert f(x) = (x-1)*x.

&(*
><

Dies setzt den vorherigen Hook mit der Inkrementierungsfunktion zusammen, sodass wir eine Funktion erhalten g(x) = (x-1)*x+1.

\Ai
&(*
><

Schließlich wird eine Funktion generiert, hdie eine Iteration der vorherigen Funktion ist g, und zwar so oft, wie dies durch die Ganzzahleingabe gegeben ist.

\Ai
&(*
><2

Und schließlich wenden wir diese Iteration auf den Anfangswert an 2. Das pan der Spitze druckt nur das Ergebnis.

Alternative (auch 13 Bytes)

p
>
\Ai
(*
>1

Dies verschiebt das Inkrement bis zum Ende.

C, 43 , 34 , 33 Bytes

1-indiziert:

F(n){return--n?n=F(n),n*n-n+1:2;}

Testleitung:

int main() {
  printf("%d\n", F(1));
  printf("%d\n", F(2));
  printf("%d\n", F(3));
  printf("%d\n", F(4));
  printf("%d\n", F(5));
}

Brachylog , 13 Bytes

0,2|-:0&-y+*+

Probieren Sie es online!

Verwendet stattdessen diese Beziehung:

welches von dieser Beziehung abgeleitet ist, modifiziert von der, die in der Sequenz angegeben ist:

a(n+1) = a(n) * (a(n) - 1) + 1.

Mathematica, 19 Bytes

Nest[#^2-#+1&,2,#]&

Oder 21 Bytes:

Array[#0,#,0,1+1##&]&

Labyrinth , 18 Bytes

Dank an Sp3000, die unabhängig voneinander die gleiche Lösung gefunden haben.

?
#
)}"{!@
* (
(:{

Probieren Sie es online!

Eigentlich , 14 12 Bytes

Dies verwendete eine 0-Indizierung. Golfvorschläge sind willkommen. Probieren Sie es online!

2#,`;πu@o`nF

Ungolfing:

2#              Start with [2]
  ,`     `n     Take 0-indexed input and run function (input) times
    ;           Duplicate list
     πu         Take product of list and increment
       @o       Swap and append result to the beginning of the list
           F    Return the first item of the resulting list

GolfScript , 12 10 Bytes

2 Bytes dank Dennis.

~2\{.(*)}*

Probieren Sie es online!

Verwendet a(n) = a(n-1) * (a(n-1)-1) + 1.