Jeder kennt die Fibonacci-Folge:
Man nimmt ein Quadrat, fügt ein gleiches Quadrat hinzu und fügt dann wiederholt ein Quadrat hinzu, dessen Seitenlänge der größten Seitenlänge des resultierenden Rechtecks ​​entspricht.
Das Ergebnis ist eine wunderschöne Spirale aus Quadraten, deren Zahlenfolge die Fibonacci-Folge ist :

Was aber, wenn wir keine Quadrate verwenden wollten?

Wenn wir in ähnlicher Weise gleichseitige Dreiecke anstelle von Quadraten verwenden, erhalten wir eine ebenso schöne Dreiecksspirale und eine neue Folge: die Padovan-Folge , auch bekannt als A000931 :

Aufgabe:

Bei einer positiven ganzen Zahl wird ausgegeben , der te Term in der Padovan-Sequenz ODER die ersten Terme.$N$$a_N$$N$$N$

Angenommen, die ersten drei Terme der Sequenz sind alle . Die Sequenz beginnt also wie folgt: $1$

Eingang:

• Beliebige positive ganze Zahl$N\ge0$

• Ungültige Eingaben müssen nicht berücksichtigt werden

Ausgabe:

• Der te Term in der Padovan-Sequenz ODER die ersten Terms der Padovan-Sequenz.$N$N$N$

• Wenn die ersten Terme ausgedruckt werden, kann die Ausgabe nach Belieben erfolgen (Liste / Array, mehrzeilige Zeichenfolge usw.).$N$

• Kann entweder indiziert oder indiziert sein$0$$1$

Testfälle:
(0-indiziert, ter Term)$N$

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

(1-indiziert, erste Begriffe)$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

Regeln:

• Das ist Code-Golf : Je weniger Bytes, desto besser!

• Standardlücken sind verboten.

Gelee , 10 Bytes

9s3’Ẓæ*³FṀ

Probieren Sie es online!

1-indiziert. Berechnet das größte Element von: wobei die binäre Matrix wie folgt berechnet wird:

(Dies ist ein totaler Zufall.)

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

Oase , 5 Bytes

n - ter Term 0-indiziert

cd+1V

Probieren Sie es online!

Erläuterung

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

Jelly ,  10 9  8 Bytes

ŻṚm2Jc$S

Eine monadische Linkannahme n(0-indiziert), die ergibt P(n).

Probieren Sie es online!

Wie?

Implementiert$P(n) = \sum_{i=0}^{\lfloor\frac{n}2\rfloor}\binom{i+1}{n-2i}$

ŻṚ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

Und hier ist ein "Twofer"
... eine völlig andere Methode auch für 8 Bytes (diese ist 1-indiziert, aber viel langsamer):

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)

Haskell , 26 Bytes

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

Probieren Sie es online! Gibt den n-ten Term mit dem Index Null aus.

Ich dachte, dass die "offensichtliche" rekursive Lösung unten unschlagbar wäre, aber dann fand ich das. Es ähnelt dem klassischen Golf-Ausdruck l=1:scanl(+)1lfür die unendliche Fibonacci-Liste, aber hier ist der Unterschied zwischen benachbarten Elementen der Begriff 4 Positionen zurück. Wir können direkter schreiben l=1:1:zipWith(+)l(0:l), aber das ist länger.

Wenn diese Herausforderung eine unendliche Listenausgabe erlaubt, könnten wir die erste Zeile abschneiden und 20 Bytes haben.

27 Bytes

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

Probieren Sie es online!

Python 2 , 30 Bytes

f=lambda n:n<3or f(n-2)+f(n-3)

Probieren Sie es online!

Gibt den n-ten Term mit dem Index Null zurück. Ausgänge Truefür 1.

Wolfram Language (Mathematica) , 33 Byte

a@0=a@1=a@2=1;a@n_:=a[n-2]+a[n-3]   

1-indiziert, gibt den n-ten Ausdruck zurück

Probieren Sie es online!

Oktave / MATLAB, 35 33 Bytes

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

Gibt die ersten n Terme aus.

Probieren Sie es online!

Wie es funktioniert

Anonyme Funktion, die einen rekursiven Filter implementiert .

'cbaa'-98ist eine kürzere Form zu produzieren [1 0 -1 -1].

2:n<5ist eine kürzere zu erzeugende Form [1 1 1 0 0 ··· 0]( n −1 Terme).

filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])leitet die Eingabe [1 1 1 0 0 ··· 0]durch ein zeitdiskretes Filter, das durch eine Übertragungsfunktion mit Zähler- 1und Nennerkoeffizienten definiert ist [1 0 -1 -1].

J , 22 Bytes

-2 Bytes dank ngn und Galen

geschlossene Form, 26 Bytes

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

Probieren Sie es online!

iterativ 22 Bytes

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

Probieren Sie es online!

Retina , 47-42 Bytes

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

Probieren Sie es online! Gibt die ersten nTerme in separaten Zeilen aus. Erläuterung:

K`0¶1¶0

Ersetzen Sie die Eingabe durch die Begriffe -2, -1und 0.

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

Generieren Sie die nächsten nTerme mit der Wiederholungsrelation. *_Hier ist kurz, für $&*_die die (erste) Zahl in der Übereinstimmung in unär konvertiert wird , während $1*kurz ist, für $1*_die die mittlere Zahl in unär konvertiert wird. Der $.(liefert die dezimale Summe seiner unären Argumente, also die Summe der ersten und mittleren Zahlen.

6,G`

Verwerfen Sie die ersten sechs Zeichen, dh die ersten drei Zeilen.

Cubix , 20 Bytes

Dies ist 0-indiziert und gibt den N- ten Term aus

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

Probieren Sie es online!

Wickelt sich auf einen Würfel mit Seitenlänge 2

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

Schau es dir an

• I010 - Initiiert den Stapel
• +p? - Fügt die Oberseite des Stapels hinzu, zieht den Zähler von der Unterseite des Stapels ab und testet
• /;UO@ - Wenn der Zähler auf 0 steht, reflektieren Sie auf die Oberseite, entfernen Sie den TOS, wenden Sie ihn, geben Sie ihn aus und halten Sie ihn an
• \(sqq;W - Wenn der Zähler positiv ist, reflektieren Sie ihn, verringern Sie den Zähler, tauschen Sie die TOS aus, drücken Sie zweimal von oben nach unten, entfernen Sie die TOS und verschieben Sie die Spur zurück in die Hauptschleife.

Python 2 , 56 48 Bytes

f=lambda n,a=1,b=1,c=1:n>2and f(n-1,b,c,a+b)or c

Probieren Sie es online!

Gibt den n-ten Wert mit dem Index 0 zurück.

Perl 6 , 24 Bytes

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

Probieren Sie es online!

Eine ziemlich standardmäßige generierte Sequenz, bei der jedes neue Element vom Ausdruck generiert wird * + * + !*. Das fügt das drittvorhergehende Element, das zweitvorhergehende Element und die logische Negation des vorherigen Elements hinzu, die immer Falsenull ist.

05AB1E , 8 Bytes

1Ð)λ£₂₃+

Probieren Sie es online!

Halten Sie mit, ich habe eine Weile nicht mehr Golf gespielt. Ich frage mich , ob es ein kürzerer Ersatz ist für 1Ð)die in diesem Fall funktioniert (ich habe versucht 1D), 3Å1etc. , aber keiner von ihnen speichern Bytes). Gibt die ersten Terme der Sequenz aus. Oder ohne würde es einen unendlichen Strom der Terme der Sequenz ausgeben.$n$£

Wie?

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

APL (Dyalog Unicode) , 20 - 18 - 17 Byte ^SBCS

Dieser Code ist 1-indiziert. Es ist die gleiche Anzahl von Bytes, um nElemente der Padovan-Sequenz abzurufen, da Sie die letzten zusätzlichen Elemente löschen müssen. Es ist auch die gleiche Anzahl von Bytes, um eine 0-Indizierung zu erhalten.

Edit: -2 Bytes dank ngn. -1 Byte dank ngn

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

Probieren Sie es online!

Erläuterung

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.

K (NGN / k) , 24 20 Bytes

-4 Bytes dank ngn!

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

Probieren Sie es online!

0-indiziert, erste N Terme

x86-32-Bit-Computercode, 17 Byte

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

Demontage:

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

Es ist 0-indiziert. Die Initialisierung wird bequem durch Berechnen von eax * 0 erreicht. Das 128-Bit-Ergebnis ist 0 und geht in edx: eax.

Zu Beginn jeder Iteration lautet die Reihenfolge der Register ebx, eax, edx. Ich musste die richtige Reihenfolge wählen, um die Kodierung für den xchg eaxBefehl zu nutzen - 1 Byte.

Ich musste dem Schleifenzähler 4 hinzufügen, damit der Ausgang erreicht wird eax, der den Rückgabewert der Funktion in der fastcallKonvention enthält.

Ich könnte eine andere Aufrufkonvention verwenden, die kein Speichern und Wiederherstellen erfordert ebx, aber fastcalltrotzdem Spaß macht :)

Jelly , 11 Bytes

5B+Ɲ2ị;Ʋ⁸¡Ḣ

Probieren Sie es online!

0-indiziert.

Lua 5.3,49 48 Bytes

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

Probieren Sie es online!

Vanilla Lua hat keine Nötigung von Booleschen Werten zu Zeichenfolgen (sogar zu tonumber(true)Rückgaben nil), daher müssen Sie einen pseudo-ternären Operator verwenden. Diese Version ist wie alle Lua 1-indiziert. Das 1orTeil muss 1 orin Lua 5.1 geändert werden , das eine andere Art hat, Zahlen zu lexieren.

Ruby , 26 Bytes

f=->n{n<3?1:f[n-2]+f[n-3]}

Probieren Sie es online!

JavaScript (ES6), 23 Byte

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

$N$

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

Probieren Sie es online!

Japt -N , 12 Bytes

<3ªßUµ2 +ß´U

Versuch es

TI-BASIC (TI-84), 34 Byte

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

$N$

Eingang ist in Ans.
Die Ausgabe erfolgt in Ansund wird automatisch ausgedruckt.

Ich nahm an, dass genug Zeit vergangen war und mehrere Antworten gepostet worden waren, von denen es viele gab, die diese Antwort übertroffen hatten.

Beispiel:

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

Erläuterung:

[[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

Pyth, 16 Bytes

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

Dies definiert die Funktion y. Probieren Sie es hier aus!

Hier ist eine Lösung, die mehr Spaß macht, obwohl sie 9 Byte länger ist. Bytes könnten allerdings rasiert werden.

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

Dies verwendet die Definition von David Callan auf der OEIS-Seite: "a (n) = Anzahl der Kompositionen von n in ungerade Teile und> = 3." Probieren Sie es hier aus! Es werden Eingaben direkt übernommen, anstatt eine Funktion zu definieren.

Java, 41 Bytes

Lambda kann nicht verwendet werden (Laufzeitfehler). Port dieser Javascript-Antwort

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

TIO

R + pryr , 38 36 Bytes

Nullindexierte rekursive Funktion.

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

Probieren Sie es online!

Vielen Dank an @ Giuseppe für den Hinweis auf zwei offensichtlich unnötige Bytes.

C (clang) , 41 33 Bytes

a(i){return i<3?1:a(i-2)+a(i-3);}

Probieren Sie es online!

C # (Visual C # Interactive Compiler) , 34 Byte

int f(int g)=>g<3?1:f(g-2)+f(g-3);

Probieren Sie es online!

Perl 5 , 34 Bytes

sub f{"@_"<3||f("@_"-2)+f("@_"-3)}

Probieren Sie es online!

Wolfram Language (Mathematica) , 26 Byte

If[#<3,1,#0[#-2]+#0[#-3]]&

Probieren Sie es online!

Pari / GP , 28 Bytes

0-indiziert.

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

Probieren Sie es online!

Pari / GP , 35 Bytes

1-indiziert.

n->Vec((1+x+O(x^n))/(1-x^2-x^3))[n]

Probieren Sie es online!

$\frac{1+x}{1-x^2-x^3}$