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:
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,... $$
Any positive integer \$N\ge0\$
Invalid input does not have to be taken into account
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
(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