La séquence de Sylvester, OEIS A000058 , est une séquence entière définie comme suit:

Chaque membre est le produit de tous les membres précédents plus un. Le premier membre de la séquence est 2.

Tâche

Créez le plus petit programme possible qui prend un n et calcule le nième terme de la séquence de Sylvester. L'entrée, la sortie et les failles standard s'appliquent. Étant donné que le résultat augmente très rapidement, vous ne devez pas prendre de terme dont le résultat entraînerait un débordement dans la langue choisie.

Cas de test

Vous pouvez utiliser zéro ou une indexation. (Ici, j'utilise l'indexation zéro)

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

Brain-Flak , 76 68 58 52 46 octets

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

Essayez-le en ligne!

Utilise cette relation à la place:

qui dérive de cette relation modifiée de celle fournie dans la séquence:

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

Explication

Pour une documentation de ce que fait chaque commande, veuillez visiter la page GitHub .

Il y a deux piles dans Brain-Flak, que je nommerai respectivement pile 1 et pile 2.

L'entrée est stockée dans la pile 1.

<>(()())<>             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.

Pour l'algorithme de génération:

({({}[()])({})}{}())      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).

Version alternative à 46 octets

Cela utilise une seule pile.

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

Essayez-le en ligne!

Gelée , 5 octets

Ḷ߀P‘

Il utilise l'indexation basée sur 0 et la définition de la spécification de défi.

Essayez-le en ligne! ou vérifier tous les cas de test .

Comment ça marche

Ḷ߀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.

Hexagonie , 27 octets

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

Déplié:

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

Essayez-le en ligne!

Explication

Examinons la séquence b(a) = a(n) - 1et faisons un petit réarrangement:

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)

Cette séquence est très similaire mais nous pouvons reporter l'incrément à la toute fin, ce qui arrive à enregistrer un octet dans ce programme.

Voici donc le code source annoté:

^{Créé avec HexagonyColorer de Timwi .}

Et voici un diagramme de mémoire (le triangle rouge montre la position et l'orientation initiales du pointeur de mémoire):

^{Créé avec de Timwi EsotericIDE .}

Le code commence sur le chemin gris qui enveloppe le coin gauche, donc le bit linéaire initial est le suivant:

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

Ensuite, le code frappe le <qui est une branche et indique le début (et la fin) de la boucle principale. Tant que le bord N a une valeur positive, le chemin vert sera exécuté. Ce chemin fait plusieurs fois le tour de la grille, mais il est en fait entièrement linéaire:

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

Il .n'y a pas d'opérations, donc le code réel est:

""~&}=*}=+={(
""             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.

Une fois cette décrémentation réduite Nà 0, le chemin rouge est exécuté:

")!@
"     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 octets

Cette version grâce à randomra. J'essaierai d'écrire une explication détaillée plus tard.

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

J, 14 octets

Cette version grâce aux miles. Utilisez l'adverbe de puissance ^:au lieu d'un agenda comme ci-dessous. Plus d'explications à venir.

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

J, 18 octets

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

0 indexé.

Exemples

   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

Explication

Voici un programme qui ressemble à ceci:

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

(Généré en utilisant (9!:7)'┌┬┐├┼┤└┴┘│─'alors 5!:4<'e')

Décomposition:

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

En utilisant la branche du haut comme gérondif Get le bas comme sélecteur F, c'est:

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

Celui-ci utilise la fonction constante 2:lorsque 0 = * n, c'est-à-dire lorsque le signe est nul (donc nnul). Sinon, nous utilisons cette fourchette:

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

Ce qui est un plus la série au sommet suivante:

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

Décomposant davantage, il s'agit du produit ( */) sur l'auto-référence ( $:) sur la plage ( i.).

Perl 6 , 24 octets

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

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

Explication

# 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
  )[ $_ ]
}

Usage:

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 octets

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

Exemple d'utilisation: f 4-> 1807.

Java 7, 46 42 octets

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

Utilise l'indexation 0 avec la formule habituelle. Je troqué n*n-npour n*(n-1)bien, puisque Java ne comportaient pas d'opérateur de puissance à portée de main, et les f()appels obtenions longtemps.

Haskell, 25 octets

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

SILOS , 60 octets

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

Essayez-le en ligne!

Port de ma réponse en C .

Brain-Flak , 158154 octets

Leaky Nun m'a fait battre ici

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

Essayez-le en ligne!

Explication

Mettez un deux sous l'entrée a (0)

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

Alors que l'entrée est supérieure à zéro, soustrayez un de l'entrée et ...

{
({}[()]

Silencieusement...

<

Mettez-en un sur l'autre pile pour servir de catalyseur à la multiplication <> (()) <>

Alors que la pile n'est pas vide

 ([])
 {
  {}

Déplacez le haut de la liste et copiez

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

Multipliez le catalyseur par la copie

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

Ajoute un

 <>({}())

Remettez la séquence dans la pile appropriée

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

Supprimer tout sauf le dernier élément (c'est-à-dire le dernier numéro créé)

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

C, 32 octets

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

Utilise l'indexation basée sur 1. Testez-le sur Ideone .

En fait , 9 octets

2@`rΣτu`n

Essayez-le en ligne!

Utilise cette relation à la place:

qui dérive de cette relation modifiée de celle fournie dans la séquence:

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

R, 44 42 41 octets

2 octets d'économie grâce à JDL

Sauvegarde de 1 octet grâce à user5957401

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

Oasis , 4 octets (non concurrent)

Probablement ma dernière langue de la famille du golf! Non compétitif, car la langue est postérieure au défi.

Code:

²->2

Solution alternative grâce à Zwei :

<*>2

Version étendue:

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

Explication:

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

Utilise le codage CP-1252 . Essayez-le en ligne!

Python, 38 36 octets

2 octets grâce à Dennis.

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

Ideone ça!

Utilise plutôt cette relation modifiée par rapport à celle fournie dans la séquence:

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

Explication

0**n*2renvoie 2quand n=0et 0sinon, car 0**0est défini pour être 1en Python.

Cheddar , 26 octets

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

Essayez-le en ligne!

Assez idiomatique.

Explication

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 octets

2{_(*)}ri*

Utilise l'indexation basée sur 0. Essayez-le en ligne!

05AB1E , 7 octets

2sFD<*>

A expliqué

Utilise une indexation à base zéro.

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

Essayez-le en ligne!

Prolog, 49 octets

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

SILOS 201 octets

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

N'hésitez pas à l' essayer en ligne!

Gelée , 7 octets

²_’
2Ç¡

Essayez-le en ligne!

Utilise plutôt cette relation fournie dans la séquence: a(n+1) = a(n)^2 - a(n) + 1

Explication

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 octets

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

Ideone ça!

Utilise pcomme stockage temporaire du produit.

Fondamentalement, j'ai défini deux séquences p(n)et r(n), où r(n)=p(n-1)+1et p(n)=p(n-1)*r(n).

r(n) est la séquence requise.

R, 50 46 44 octets

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

Plutôt que de suivre toute la séquence, nous suivons simplement le produit, qui suit la règle de mise à jour quadratique donnée tant que n> 1 n> 0. (Cette séquence utilise la convention "start at one zero")

L'utilisation de la convention de démarrage à zéro permet d'économiser quelques octets car nous pouvons utiliser if (n) plutôt que if (n> 1)

Méduse , 13 octets

p
\Ai
&(*
><2

Essayez-le en ligne!

Explication

Commençons par le bas:

(*
<

Ceci est un crochet, qui définit une fonction f(x) = (x-1)*x.

&(*
><

Cela compose le crochet précédent avec la fonction d'incrémentation de sorte qu'il nous donne une fonction g(x) = (x-1)*x+1.

\Ai
&(*
><

Enfin, cela génère une fonction hqui est une itération de la fonction précédente g, autant de fois que donné par l'entrée entière.

\Ai
&(*
><2

Et enfin, nous appliquons cette itération à la valeur initiale 2. Le phaut imprime simplement le résultat.

Alternative (également 13 octets)

p
>
\Ai
(*
>1

Cela reporte l'incrément jusqu'à la fin.

C, 43 , 34 , 33 octets

1 indexé:

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

Test principal:

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 octets

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

Essayez-le en ligne!

Utilise cette relation à la place:

qui dérive de cette relation modifiée de celle fournie dans la séquence:

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

Mathematica, 19 octets

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

Ou 21 octets:

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

Labyrinthe , 18 octets

Crédits à Sp3000 qui a trouvé la même solution indépendamment.

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

Essayez-le en ligne!

En fait , 14 12 octets

Cela a utilisé l'indexation 0. Les suggestions de golf sont les bienvenues. Essayez-le en ligne!

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 octets

2 octets grâce à Dennis.

~2\{.(*)}*

Essayez-le en ligne!

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