Paciencia, joven "Padovan"

44

Todo el mundo conoce la secuencia de Fibonacci: se
toma un cuadrado, se le asigna un cuadrado igual y luego se une repetidamente un cuadrado cuya longitud lateral es igual a la longitud lateral más grande del rectángulo resultante.
El resultado es una hermosa espiral de cuadrados cuya secuencia de números es la secuencia de Fibonacci :

Pero, ¿y si no quisiéramos usar cuadrados?

Si utilizamos triángulos equiláteros, en lugar de cuadrados, de manera similar, obtenemos una espiral igualmente hermosa de triángulos y una nueva secuencia: la secuencia de Padovan , también conocida como A000931 :

Tarea:

Dado un número entero positivo, , salida , la º término en la secuencia de Padovan o los primeros términos.NaNNN

Suponga que los primeros tres términos de la secuencia son todos . Por lo tanto, la secuencia comenzará de la siguiente manera: 1

1,1,1,2,2,3,...

Entrada:

  • Cualquier número entero positivoN0

  • La entrada inválida no tiene que ser tomada en cuenta

Salida:

  • El º término en la secuencia de Padovan OR los primeros términos de la secuencia de Padovan.NNN

  • Si se imprimen los primeros términos, la salida puede ser lo que sea conveniente (lista / matriz, cadena de varias líneas, etc.)N

  • Puede ser indexado o indexado01

Casos de prueba:
(0 indexados, º plazo)N

Input | Output
--------------
0     | 1
1     | 1
2     | 1
4     | 2
6     | 4
14    | 37
20    | 200
33    | 7739

(1 indexado, primeros términos)N

Input | Output
--------------
1     | 1
3     | 1,1,1
4     | 1,1,1,2
7     | 1,1,1,2,2,3,4
10    | 1,1,1,2,2,3,4,5,7,9
12    | 1,1,1,2,2,3,4,5,7,9,12,16

Reglas:

Tau
fuente
2
14(Índice 0) se muestra como salida 28mientras creo que debería ceder37
Jonathan Allan
@ JonathanAllan sí, tienes razón. He arreglado los dos últimos casos de prueba para º plazo, pero no que uno. La publicación ha sido editada. N
Tau
@LuisMendo, creo que sí. Editaré la publicación.
Tau
1
@sharur esta definición para la secuencia de Fibonacci es la definición visual . Cada cuadrado sucesivo agregado tiene una longitud de ese término en la secuencia. La secuencia que describe es el razonamiento numérico detrás de ella. Ambas secuencias funcionan tan bien como la otra.
Tau
1
Tenga en cuenta que la secuencia OEIS que ha vinculado es ligeramente diferente, ya que utiliza a_0=1, a_1=0, a_2=0. Termina siendo desplazado un poco porque entoncesa_5=a_6=a_7=1
Carmeister

Respuestas:

59

Jalea , 10 bytes

9s3’Ẓæ*³FṀ

Pruébalo en línea!

1 indexado. Calcula el elemento más grande de: donde la matriz binaria se calcula convenientemente como:

[001101010]n
[isprime(0)isprime(1)isprime(2)isprime(3)isprime(4)isprime(5)isprime(6)isprime(7)isprime(8)]

(Esto es una coincidencia total).

9s3         [[1,2,3],[4,5,6],[7,8,9]]    9 split 3
   ’        [[0,1,2],[3,4,5],[6,7,8]]    decrease
    Ẓ       [[0,0,1],[1,0,1],[0,1,0]]    isprime
     æ*³    [[0,0,1],[1,0,1],[0,1,0]]^n  matrix power by input
        FṀ                               flatten, maximum
Lynn
fuente
33
esto es claramente una especie de vudú
Pureferret
77
Esto debería ser publicado.
YSC
66
@YSC Ya se ha publicado en A000931 . Nunca hubiera adivinado el truco de los primos :)
error
1
... haz que "a menos que alguien pueda jugar dos bytes de este" :) (ahora que tengo un byte de 9 )
Jonathan Allan
1
Estoy tan acostumbrado a ver respuestas absurdamente pequeñas aquí, que pensé que la coma después de 'Jelly' era de hecho el código para este problema
Tasos Papastylianou
28

Oasis , 5 bytes

enésimo término indexado 0

cd+1V

Pruébalo en línea!

Explicación

   1V   # a(0) = 1
        # a(1) = 1
        # a(2) = 1
        # a(n) =
c       #        a(n-2)
  +     #              +
 d      #               a(n-3)
Emigna
fuente
26

Jalea ,  10 9  8 bytes

ŻṚm2Jc$S

Un enlace monádico que acepta n(indexado a 0) que produce P(n).

Pruébalo en línea!

¿Cómo?

ImplementaP(n)=i=0n2(i+1n2i)

ŻṚm2Jc$S - Link: integer, n       e.g. 20
Ż        - zero range                  [0, 1, 2, 3, 4, ..., 19, 20]
 Ṛ       - reverse                     [20, 19, ..., 4, 3, 2, 1, 0]
  m2     - modulo-slice with 2         [20, 18, 16, 14, 12, 10,  8,  6,  4,  2,  0]  <- n-2i
      $  - last two links as a monad:
    J    -   range of length           [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11]  <- i+1
     c   -   left-choose-right         [ 0,  0,  0,  0,  0,  0,  0, 28,126, 45,  1]
       S - sum                         200

Y aquí hay un "twofer"
... un método totalmente diferente también para 8 bytes (este es 1 indexado, pero mucho más lento):

3ḊṗRẎ§ċ‘ - Link: n
3Ḋ       - 3 dequeued = [2,3]
   R     - range = [1,2,3,...,n]
  ṗ      -   Cartesian power         [[[2],[3]],[[2,2],[2,3],[3,2],[3,3]],[[2,2,2],...],...]
    Ẏ    - tighten                   [[2],[3],[2,2],[2,3],[3,2],[3,3],[2,2,2],...]
     §   - sums                      [ 2,  3,   4,    5,    5,    6,     6,...]
       ‘ - increment                 n+1
      ċ  - count occurrences         P(n)
Jonathan Allan
fuente
18

Haskell , 26 bytes

(l!!)
l=1:1:1:2:scanl(+)2l

Pruébalo en línea! Emite el enésimo término indexado a cero.

Pensé que la solución recursiva "obvia" a continuación sería inmejorable, pero entonces encontré esto. Es similar a la expresión clásica de golf l=1:scanl(+)1lpara la lista infinita de Fibonacci, pero aquí la diferencia entre los elementos adyacentes es el término 4 posiciones atrás. Podemos escribir más directamente l=1:1:zipWith(+)l(0:l), pero eso es más largo.

Si este desafío permitiera una salida de lista infinita, podríamos cortar la primera línea y tener 20 bytes.

27 bytes

f n|n<3=1|1>0=f(n-2)+f(n-3)

Pruébalo en línea!

xnor
fuente
6

Octava / MATLAB, 35 33 bytes

@(n)[1 filter(1,'cbaa'-98,2:n<5)]

Emite los primeros n términos.

Pruébalo en línea!

Cómo funciona

Función anónima que implementa un filtro recursivo .

'cbaa'-98Es una forma más corta de producir [1 0 -1 -1].

2:n<5es una forma más corta de producir [1 1 1 0 0 ··· 0]( n −1 términos).

filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])pasa la entrada a [1 1 1 0 0 ··· 0]través de un filtro de tiempo discreto definido por una función de transferencia con coeficientes de numerador 1y coeficientes de denominador [1 0 -1 -1].

Luis Mendo
fuente
6

J , 22 bytes

-2 bytes gracias a ngn y Galen

forma cerrada, 26 bytes

0.5<.@+1.04535%~1.32472^<:

Pruébalo en línea!

iterativo, 22 bytes

(],1#._2 _3{ ::1])^:[#

Pruébalo en línea!

Jonás
fuente
1
Otra solución de 24 bytes (aburrida): (1 # .2 3 $: @ - ~]) `1: @. (3 &>) ¡ Pruébelo en línea!
Galen Ivanov
23 bytes gracias a ngn 1:-> #: ¡ Pruébelo en línea!
Galen Ivanov
@GalenIvanov tyvm, ese es un gran truco.
Jonás
2
1:-> 1. "adverso" funciona con un sustantivo a la derecha, aparentemente
ngn
@ngn TIL ... Ty de nuevo!
Jonás
5

Retina , 47 42 bytes

K`0¶1¶0
"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*
6,G`

Pruébalo en línea! Emite los primeros ntérminos en líneas separadas. Explicación:

K`0¶1¶0

Vuelva a colocar la entrada con los términos de -2, -1y 0.

"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*

Genere los siguientes ntérminos usando la relación de recurrencia. *_aquí es corto para lo $&*_que convierte el (primer) número en el partido en unario, mientras que $1*es corto para lo $1*_que convierte el número del medio en unario. Los $.(devuelve la suma decimal de sus argumentos unarios, es decir, la suma de los primer y segundo números.

6,G`

Deseche los primeros seis caracteres, es decir, las primeras tres líneas.

Neil
fuente
5

Cubix , 20 bytes

Este es 0 indexado y da salida a la N º plazo

;@UOI010+p?/sqq;W.\(

Pruébalo en línea!

Se envuelve en un cubo con longitud lateral 2

    ; @
    U O
I 0 1 0 + p ? /
s q q ; W . \ (
    . .
    . .

Míralo correr

  • I010 - Inicia la pila
  • +p? - Agrega la parte superior de la pila, tira del contador desde la parte inferior de la pila y prueba
  • /;UO@ - Si el contador es 0, reflexionar sobre la cara superior, eliminar TOS, giro en U, salida y detener
  • \(sqq;W - Si el contador es positivo, refleje, disminuya el contador, cambie los TOS, presione de arriba a abajo dos veces, quite los TOS y cambie el carril nuevamente al bucle principal.
MickyT
fuente
4

Perl 6 , 24 bytes

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

Pruébalo en línea!

Una secuencia generada bastante estándar, con cada nuevo elemento generado por la expresión * + * + !*. Eso agrega el tercer elemento anterior, el segundo elemento anterior y la negación lógica del elemento anterior, que siempre es False, que es numéricamente cero.

Sean
fuente
¿Por qué es esta wiki comunitaria?
Jo King
@JoKing me gana. Si lo hice de alguna manera, no fue a propósito.
Sean
4

05AB1E , 8 bytes

1Ð)λ£₂₃+

Pruébalo en línea!

Ten paciencia conmigo, no he jugado al golf en mucho tiempo. Me pregunto si hay un sustituto más corto para el 1Ð)que funciona en este caso (lo he intentado 1D), 3Å1etc. pero ninguno de ellos guarda bytes). Emite los primeros términos de la secuencia. O, sin el , generaría un flujo infinito de los términos de la secuencia.n£

¿Cómo?

1Ð)λ£₂₃+ | Full program.
1Ð)      | Initialize the stack with [1, 1, 1].
   λ     | Begin the recursive generation of a list: Starting from some base case,
         | this command generates an infinite list with the pattern function given.
    £    | Flag for λ. Instead of outputting an infinite stream, only print the first n.
     ₂₃+ | Add a(n-2) and a(n-3).
Sr. Xcoder
fuente
No creo que 1Ð)puedan ser 2 bytes tbh. Puedo pensar en seis alternativas diferentes de 3 bytes , pero no en 2 bytes.
Kevin Cruijssen
4

APL (Dyalog Unicode) , SBCS 20 18 17 bytes

Este código tiene 1 índice. Es el mismo número de bytes para obtener nelementos de la secuencia de Padovan, ya que debe eliminar los últimos miembros adicionales. También es el mismo número de bytes para obtener la indexación 0.

Editar: -2 bytes gracias a ngn. -1 byte gracias a ngn

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

Pruébalo en línea!

Explicación

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

  ⍺(. . . .)⍣⎕⍵   This format simply takes the input ⎕ and applies the function
                   inside the brackets (...) to its operands (here marked ⍵ and ⍺).
  2(. . .+/)⍣⎕×⍳3  In this case, our ⍵, the left argument, is the array 1 1 1,
                   where we save our results as the function is repeatedly applied
                   and our ⍺, 2, is our right argument and is immediately applied to +/,
                   so that we have 2+/ which will return the pairwise sums of our array.
       2⌷          We take the second pairwise sum, f(n-2) + f(n-3)
    ⊢,⍨            And add it to the head of our array.
4⌷                 When we've finished adding Padovan numbers to the end of our list,
                   the n-th Padovan number (1-indexed) is the 4th member of that list,
                   and so, we implicitly return that.
Sherlock9
fuente
4

K (ngn / k) , 24 20 bytes

-4 bytes gracias a ngn!

{$[x<3;1;+/o'x-2 3]}

Pruébalo en línea!

Indexados a 0, primeros N términos

Galen Ivanov
fuente
1
f[x-2]+f[x-3]-> +/o'x-2 3( oes "recur")
ngn
@ngn Gracias! Lo intenté (sin éxito) en J; Es elegante aquí.
Galen Ivanov
@ngn De hecho, aquí hay una posibilidad de cómo se ve en J: (1 # .2 3 $: @ - ~]) `1: @. (3 &>)
Galen Ivanov
ah, correcto, la decodificación de base 1 es una forma amigable de entrenar para sumar :)
ngn
2
1:-> #en la solución j
ngn
4

Código de máquina x86 de 32 bits, 17 bytes

53 33 db f7 e3 43 83 c1 04 03 d8 93 92 e2 fa 5b c3

Desmontaje

00CE1250 53                   push        ebx  
00CE1251 33 DB                xor         ebx,ebx  
00CE1253 F7 E3                mul         eax,ebx  
00CE1255 43                   inc         ebx  
00CE1256 83 C1 04             add         ecx,4  
00CE1259 03 D8                add         ebx,eax  
00CE125B 93                   xchg        eax,ebx  
00CE125C 92                   xchg        eax,edx  
00CE125D E2 FA                loop        myloop (0CE1259h)  
00CE125F 5B                   pop         ebx  
00CE1260 C3                   ret

Está indexado a 0. La inicialización se logra convenientemente calculando eax * 0. El resultado de 128 bits es 0, y va en edx: eax.

Al comienzo de cada iteración, el orden de los registros es ebx, eax, edx. Tuve que elegir el orden correcto para aprovechar la codificación de la xchg eaxinstrucción: 1 byte.

Tuve que agregar 4 al contador de bucle para permitir que la salida alcance eax, que contiene el valor de retorno de la función en la fastcallconvención.

Podría usar alguna otra convención de llamadas, que no requiere guardar y restaurar ebx, pero de fastcalltodos modos es divertido :)

anatolyg
fuente
2
¡Me encanta ver las respuestas del código de máquina en PP&CG! +1
Tau
3

Lua 5.3,49 48 bytes

function f(n)return n<4 and 1or f(n-2)+f(n-3)end

Pruébalo en línea!

Vanilla Lua no tiene coerción de booleanos a cadenas (incluso tonumber(true)retornos nil), por lo que debe usar un operador pseudoternario. Esta versión está indexada en 1, como todos los de Lua. La 1orparte debe cambiarse 1 oren Lua 5.1, que tiene una forma diferente de lexing números.

ciclaminista
fuente
3

JavaScript (ES6), 23 bytes

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

N

f=n=>n<3||f(n-2)+f(n-3)

Pruébalo en línea!

Arnauld
fuente
No creo que sea razonable decir que regresar truees lo mismo que regresar 1si el resto de la salida son números.
Nit
2
@Nit Meta publicación relevante .
Arnauld
Creo que te faltan algunos requisitos: echa un vistazo a mi modificación (versión en Java) aquí .
Shaq
@Shaq El desafío especifica claramente que los primeros tres términos de la secuencia son todos 1 . Así que, es no la secuencia definida en A000931 (pero la fórmula es la misma).
Arnauld
@Arnauld sí, puedo verlo ahora. ¡Lo siento!
Shaq
2

Japt -N , 12 bytes

<3ªßUµ2 +ß´U

Intentalo

Encarnación de la ignorancia
fuente
Parece que 12 es lo mejor que podemos hacer: \
Shaggy
Estoy corregido!
Shaggy
2

TI-BASIC (TI-84), 34 bytes

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1

N

La entrada está adentro Ans.
La salida está adentro Ansy se imprime automáticamente.

Supuse que había pasado suficiente tiempo, además de que se habían publicado varias respuestas, de las cuales había muchas que superaron esta respuesta.

Ejemplo:

0
               0
prgmCDGFD
               1
9
               9
prgmCDGFD
               9
16
              16
prgmCDGFD
              65

Explicación:

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1      ;full program (example input: 6)

[[0,1,0][0,0,1][1,1,0]]                     ;generate the following matrix:
                                            ; [0 1 0]
                                            ; [0 0 1]
                                            ; [1 1 0]
                       ^(Ans+5              ;then raise it to the power of: input + 5
                                            ; [4  7 5]
                                            ; [5  9 7]
                                            ; [7 12 9]
                               Ans(1,1      ;get the top-left index and leave it in "Ans"
                                            ;implicitly print Ans
Tau
fuente
2

Pyth, 16 bytes

L?<b3!b+y-b2y-b3

Esto define la función y. Pruébalo aquí!

Aquí hay una solución más divertida, aunque es 9 bytes más larga; Sin embargo, los bytes pueden ser afeitados.

+l{sa.pMf.Am&>d2%d2T./QY!

Utiliza la definición dada por David Callan en la página OEIS: "a (n) = número de composiciones de n en partes que son impares y> = 3." Pruébalo aquí! Toma entrada directamente en lugar de definir una función.

RK.
fuente
y-b2y-b3tal vez podría ser refactorizado con bifurcado o L? Aunque declarar una matriz de 2 elementos es costoso. yL-Lb2,3es más largo :(
Ven
@Ven pude reemplazar +y-b2y-b3con smy-bdhB2cuál es la misma cantidad de bytes; hB2resultados en la matriz[2, 3]
RK.
Bien hecho en hB2. Lástima que sea el mismo número de bytes.
Ven
Sí, aunque me pregunto si hay alguna forma de deshacerse de eso den el mapa.
RK.
2

Java, 41 bytes

No se puede usar una lambda (error de tiempo de ejecución). Puerto de esta respuesta Javascript

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

TIO

Benjamin Urquhart
fuente
Creo que te faltan algunos requisitos: mira mi modificación aquí .
Shaq
No tenga en cuenta el comentario de Shaq: su respuesta es correcta y es la respuesta Java más corta posible (a partir de Java 12).
Olivier Grégoire
OK entonces. No estoy seguro de lo que me "perdí", pero está bien. Editar: nvm leí la respuesta JS.
Benjamin Urquhart
2

R + pryr , 38 36 bytes

Función recursiva indexada a cero.

f=pryr::f(`if`(n<3,1,f(n-2)+f(n-3)))

Pruébalo en línea!

Gracias a @Giuseppe por señalar dos bytes obviamente innecesarios.

rturnbull
fuente
2
Si va a utilizar pryr, el idioma debe ser R + pryry esto puede ser 36 bytes
Giuseppe
@Giuseppe gracias! Actualizado ahora.
rturnbull