Everyone knows the Fibonacci sequence:
You take a square, attach an equal square to it, then repeatedly attach a square whose side length is equal to the largest side length of the resulting rectangle.
The result is a beautiful spiral of squares whose sequence of numbers is the Fibonacci sequence:
But, what if we didn't want to use squares?
If we use equilateral triangles—instead of squares—in a similar fashion, we get an equally beautiful spiral of triangles and a new sequence: the Padovan sequence, aka A000931:
Task:
Given a positive integer, \$N\$, output \$a_N\$, the \$N\$th term in the Padovan sequence OR the first \$N\$ terms.
Assume that the first three terms of the sequence are all \$1\$. Thus, the sequence will start as follows: $$ 1,1,1,2,2,3,... $$
Input:
Any positive integer \$N\ge0\$
Invalid input does not have to be taken into account
Output:
The \$N\$th term in the Padovan sequence OR the first \$N\$ terms of the Padovan sequence.
If the first \$N\$ terms are printed out, the output can be whatever is convenient (list/array, multi-line string, etc.)
Can be either \$0\$-indexed or \$1\$-indexed
Test Cases:
(0-indexed, \$N\$th term)
Input | Output
--------------
0 | 1
1 | 1
2 | 1
4 | 2
6 | 4
14 | 37
20 | 200
33 | 7739
(1-indexed, first \$N\$ terms)
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
Rules:
This is code-golf: the fewer bytes, the better!
Standard loopholes are forbidden.
14
(0-indexed) is shown as outputting28
while I believe it should yield37
\$\endgroup\$a_0=1, a_1=0, a_2=0
. It ends up being shifted by a bit because thena_5=a_6=a_7=1
\$\endgroup\$