Secuencia de Sylvester

32

La secuencia de Sylvester, OEIS A000058 , es una secuencia entera definida de la siguiente manera:

Cada miembro es el producto de todos los miembros anteriores más uno. El primer miembro de la secuencia es 2.

Tarea

Cree el programa más pequeño posible que tome una n y calcule el enésimo término de la secuencia de Sylvester. Se aplican entradas, salidas y lagunas estándar. Dado que el resultado crece muy rápido, no se espera que tome ningún término cuyo resultado causaría un desbordamiento en el idioma elegido.

Casos de prueba

Puede usar cero o una indexación. (Aquí uso la indexación cero)

>>0
2
>>1
3
>>2
7
>>3
43
>>4
1807
Asistente de trigo
fuente
¿Qué entradas se espera manejar? La producción crece bastante rápido.
Geobits
1
@Geobits que se espera que manejes todo lo que tu idioma pueda
Wheat Wizard
¿Se acepta una matriz que cuando se indexa con ndevuelve el nthnúmero de la secuencia?
user6245072
@ user6245072 No, debe indexar sus propias matrices
Wheat Wizard

Respuestas:

26

Brain-Flak , 76 68 58 52 46 bytes

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

Pruébalo en línea!

Utiliza esta relación en su lugar:

fórmula

que se deriva de esta relación modificada de la proporcionada en la secuencia:

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

Explicación

Para obtener una documentación de lo que hace cada comando, visite la página de GitHub .

Hay dos pilas en Brain-Flak, que nombraré como Pila 1 y Pila 2 respectivamente.

La entrada se almacena en la Pila 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.

Para el algoritmo de generación:

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

Versión alternativa de 46 bytes.

Esto usa solo una pila.

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

Pruébalo en línea!

Monja permeable
fuente
1
Solo 10 bytes más para mostrar que los desarrolladores de Java deberían ir al cerebro
Rohan Jhunjhunwala
1
@RohanJhunjhunwala Me temo que es imposible ...
Leaky Nun
@LeakyNun todavía es interesante pensar en eso. Brain Flak tiene algo de poder, y es sorprendentemente breve
Rohan Jhunjhunwala
55
La versión de una pila también es limpia de pila. Lo que tiende a ser un punto importante para la modularidad del código en brain-flak.
Wheat Wizard
Guau. Esta es una respuesta extremadamente impresionante.
DJMcMayhem
12

Jalea , 5 bytes

Ḷ߀P‘

Utiliza la indexación basada en 0 y la definición de la especificación de desafío.

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

Ḷ߀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.
Dennis
fuente
Ah, olvidé que el producto vacío es 1.
Leaky Nun
12

Hexagonía , 27 bytes.

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

Desplegado:

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

Pruébalo en línea!

Explicación

Consideremos la secuencia b(a) = a(n) - 1y reorganicemos un poco:

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)

Esta secuencia es muy similar, pero podemos diferir el incremento hasta el final, lo que sucede al guardar un byte en este programa.

Así que aquí está el código fuente anotado:

ingrese la descripción de la imagen aquí
Creado con el HexagonyColorer de Timwi .

Y aquí hay un diagrama de memoria (el triángulo rojo muestra la posición y orientación iniciales del puntero de memoria):

ingrese la descripción de la imagen aquí
Creado con Timwi de EsotericIDE .

El código comienza en la ruta gris que envuelve la esquina izquierda, por lo que el bit lineal inicial es el siguiente:

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

Luego, el código golpea el <cual es una rama e indica el inicio (y el final) del bucle principal. Mientras el borde N tenga un valor positivo, se ejecutará la ruta verde. Ese camino se ajusta alrededor de la cuadrícula varias veces, pero en realidad es completamente lineal:

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

No .hay operaciones, por lo que el código real es:

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

Una vez que esta disminución se reduce Na 0, se ejecuta la ruta roja:

")!@
"     Move MP back to edge b(i) (which now holds b(N)).
 )    Increment to get a(N).
  !   Print as integer.
   @  Terminate the program.
Martin Ender
fuente
¿Puedes ejecutar tu bruteforcer en esto?
CalculatorFeline
@CalculatorFeline El brute forcer puede hacer como máximo programas de 7 bytes (e incluso eso solo con un montón de suposiciones) en un período de tiempo razonable. No veo que esto sea remotamente posible en 7 bytes.
Martin Ender
¿Asi que? ¿Qué hay de malo en intentarlo?
CalculatorFeline
@CalculatorFeline Pereza. El forzador bruto siempre requiere un poco de ajustes manuales que no puedo molestarme por la posibilidad prácticamente 0 de que encuentre algo. Sin embargo, algunas versiones del script están en GitHub, por lo que cualquier otra persona es libre de probarlo.
Martin Ender
¿Y cómo hago eso?
CalculatorFeline
9

J, 18 14 12 bytes

Esta versión gracias a randomra. Intentaré escribir una explicación detallada más adelante.

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

J, 14 bytes

Esta versión gracias a las millas. Usó el adverbio de poder en ^:lugar de una agenda como se muestra a continuación. Más explicaciones por venir.

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

J, 18 bytes

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

0 indexado.

Ejemplos

   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

Explicación

Esta es una agenda que se ve así:

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

(Generado usando (9!:7)'┌┬┐├┼┤└┴┘│─'entonces 5!:4<'e')

Descomponiendo:

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

Usando la rama superior como el gerundio G, y la inferior como el selector F, esto es:

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

Esto utiliza la función constante 2:cuando 0 = * n, es decir, cuando el signo es cero (por lo tanto, nes cero). De lo contrario, usamos este tenedor:

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

Cuál es uno más la siguiente serie superior:

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

Descomponiéndose aún más, este es producto ( */) sobre autorreferencia ( $:) sobre rango ( i.).

Conor O'Brien
fuente
2
También puede usar el adverbio de potencia para obtener 2(]*:-<:)^:[~]14 bytes usando la fórmula a(0) = 2y a(n+1) = a(n)^2 - (a(n) - 1). Para calcular valores más grandes, 2al principio deberá marcarse como un entero extendido.
millas
Ambas soluciones son muy buenas. Creo que no tenía conocimiento del v`$:@.uformato recursivo. Siempre usé un ^:vformato que a menudo es más complejo. @miles También nunca usé el (]v)truco. Me llevó unos buenos 5 minutos entenderlo.
randomra
1
Para completar un tercer tipo de bucle (14 bytes usando el método de millas): 2(]*:-<:)~&0~](o 2:0&(]*:-<:)~]). Y combinándolos 13 bytes ]0&(]*:-<:)2: .
randomra
12 Bytes: 0&(]*:-<:)2:. (Lo siento, no debería jugar golf en los comentarios.)
randomra
@randomra Ese es un uso muy bueno del vínculo. Tuve que leer la página para averiguar exactamente qué sucedió, ya que normalmente uno pensaría que el verbo del medio estaba recibiendo tres argumentos.
millas
9

Perl 6 , 24 bytes

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

Explicación

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

Uso:

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
Brad Gilbert b2gills
fuente
¿Una rebanada de matriz con $_? ¿Qué brujería es esta?
Zaid
8

Haskell, 26 bytes

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

Ejemplo de uso: f 4-> 1807.

nimi
fuente
7

Java 7, 46 42 bytes

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

Utiliza la indexación 0 con la fórmula habitual. Sin embargo, cambié n*n-npor n*(n-1), ya que Java no tiene un operador de energía útil, y las f()llamadas se estaban haciendo largas.

Geobits
fuente
3
f(n)*~-f(n)Deberia trabajar.
Dennis
1
¿Cómo me olvido de ese truco cada vez ? Si eso no está en la página de consejos, está muy seguro de estarlo.
Geobits
2
return--n<0ahorra un byte más.
Dennis
6

Haskell, 25 bytes

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

SILOS , 60 bytes

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

Pruébalo en línea!

Puerto de mi respuesta en C .

Monja permeable
fuente
Yay: D finalmente un golfista de SILOS, lo interesante es que vence a Scala :)
Rohan Jhunjhunwala
5

Brain-Flak , 158154 bytes

Leaky Nun me tiene vencido aquí

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

Pruébalo en línea!

Explicación

Pon un dos debajo de la entrada a (0)

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

Mientras que la entrada es mayor que cero, resta uno de la entrada y ...

{
({}[()]

Silenciosamente...

<

Coloque uno en la otra pila para actuar como catalizador para la multiplicación <> (()) <>

Mientras la pila no está vacía

 ([])
 {
  {}

Mueva la parte superior de la lista y copie

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

Multiplica el catalizador por la copia

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

Agrega uno

 <>({}())

Mueve la secuencia de vuelta a la pila adecuada

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

Elimine todo menos el elemento inferior (es decir, el último número creado)

([][()])
{
{}
{}
([][()])
}
{}
Asistente de trigo
fuente
5

C, 32 bytes

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

Utiliza indexación basada en 1. Pruébalo en Ideone .

Dennis
fuente
5

En realidad , 9 bytes

2@`rΣτu`n

Pruébalo en línea!

Utiliza esta relación en su lugar:

fórmula

que se deriva de esta relación modificada de la proporcionada en la secuencia:

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

Monja permeable
fuente
5

R, 44 42 41 bytes

2 bytes de ahorro gracias a JDL

1 byte guardar gracias al usuario5957401

f=function(n)ifelse(n,(a=f(n-1))^2-a+1,2)
Mamie
fuente
1
El enunciado del problema no lo aclara, pero siempre y cuando nse garantice que no será negativo, la condición puede reducirse n>0a justa n.
JDL
@JDL Nice! Gracias !
Mamie
f(n-1)es de 6 bytes. Creo que guarda un byte asignándolo a algo. es decirifelse(n,(a=f(n-1))^2-a+1,2)
usuario5957401
5

Oasis , 4 bytes (no competitivos)

¡Probablemente mi último idioma de la familia del golf! No competitiva, ya que el lenguaje es posterior al desafío.

Código:

²->2

Solución alternativa gracias a Zwei :

<*>2

Versión ampliada:

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

Explicación:

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

Utiliza la codificación CP-1252 . Pruébalo en línea!

Adnan
fuente
¿Último idioma de golf? ¿No vas a hacer más? D:
Conor O'Brien el
@ ConorO'Brien Probablemente, ya no tengo ideas :(
Adnan
Antes de pasar a este reto, tengo b<*>2usandoa(n-1)*(a(n-1)+1)-1
Zwei
@Zwei Muy ordenado! En realidad, puede omitir el bya que se completará automáticamente (en lugar de la entrada) :).
Adnan
1
Sí, me di cuenta de eso después de publicar. Me sorprende lo bien que funciona este lenguaje para esto, a pesar de que está diseñado para secuencias.
Zwei
3

Python, 38 36 bytes

2 bytes gracias a Dennis.

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

Ideone it!

Utiliza esta relación modificada de la proporcionada en la secuencia en su lugar:

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

Explicación

0**n*2devuelve 2cuándo n=0y de lo 0contrario, porque 0**0está definido para estar 1en Python.

Monja permeable
fuente
3

Cheddar , 26 bytes

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

Pruébalo en línea!

Bastante idiomático

Explicación

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
Downgoat
fuente
Ahora 4 veces (casi)
Leaky Nun
¿Por qué eliminaste el enlace TIO?
Leaky Nun
@LeakyNun oh, debes haber estado editando mientras yo estaba
Downgoat
3

05AB1E , 7 bytes

2sFD<*>

Explicado

Utiliza indexación basada en cero.

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

Pruébalo en línea!

Emigna
fuente
3

Prólogo, 49 bytes

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

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

¡Siéntase libre de probarlo en línea!

Rohan Jhunjhunwala
fuente
2
¿Qué demonios está pasando?
TuxCrafting
1
@ Brujería TùxCräftîñg
Rohan Jhunjhunwala
2

Jalea , 7 bytes

²_’
2Ç¡

Pruébalo en línea!

Utiliza esta relación proporcionada en la secuencia en su lugar: a(n+1) = a(n)^2 - a(n) + 1

Explicación

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
Monja permeable
fuente
2

C, 46 bytes

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

Ideone it!

Usos p como almacenamiento temporal del producto.

Básicamente, definí dos secuencias p(n)y r(n), donde r(n)=p(n-1)+1y p(n)=p(n-1)*r(n).

r(n) es la secuencia requerida

Monja permeable
fuente
1
¿Alguna razón por la que no estás usando la misma relación de tu respuesta de Python aquí? Eso debería ser mucho más corto ...
Dennis
@ Dennis Esto es más interesante.
Leaky Nun
@ Dennis Y esta respuesta puede ser portada
Leaky Nun
2

R, 50 46 44 bytes

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

En lugar de rastrear toda la secuencia, solo hacemos un seguimiento del producto, que sigue la regla de actualización cuadrática dada siempre que n> 1 n> 0. (Esta secuencia usa la convención "comenzar en un cero")

El uso de la convención de inicio en cero ahorra un par de bytes ya que podemos usar if (n) en lugar de if (n> 1)

JDL
fuente
2

Medusa , 13 bytes

p
\Ai
&(*
><2

Pruébalo en línea!

Explicación

Comencemos de abajo hacia arriba:

(*
<

Este es un gancho, que define una función f(x) = (x-1)*x.

&(*
><

Esto compone el gancho anterior con la función de incremento, por lo que nos da una función g(x) = (x-1)*x+1.

\Ai
&(*
><

Finalmente, esto genera una función hque es una iteración de la función anterior g, tantas veces como sea dada por la entrada entera.

\Ai
&(*
><2

Y finalmente, aplicamos esta iteración al valor inicial 2. El pen la parte superior solo imprime el resultado.

Alternativa (también 13 bytes)

p
>
\Ai
(*
>1

Esto difiere el incremento hasta el final.

Martin Ender
fuente
2

C, 43 , 34 , 33 bytes

1 indexado:

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

Prueba 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));
}
Stefano Sanfilippo
fuente
2

Brachylog , 13 bytes

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

Pruébalo en línea!

Utiliza esta relación en su lugar:

fórmula

que se deriva de esta relación modificada de la proporcionada en la secuencia:

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

Monja permeable
fuente
2

Mathematica, 19 bytes

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

O 21 bytes:

Array[#0,#,0,1+1##&]&
alephalpha
fuente
La Arraysolución es mágica. Lástima, ##0no es una cosa. ;)
Martin Ender
1

En realidad , 14 12 bytes

Esto usó la indexación 0. Sugerencias de golf bienvenidas. Pruébalo en línea!

2#,`;πu@o`nF

No golfista:

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
Sherlock9
fuente
1

GolfScript , 12 10 bytes

2 bytes gracias a Dennis.

~2\{.(*)}*

Pruébalo en línea!

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

Monja permeable
fuente
2
( es la abreviatura de 1- ; )es la abreviatura de 1+.
Dennis
3
@ Dennis Gracias, debo ser un tipo especial de estúpido.
Leaky Nun