44
3
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.
2
14
(0-indexed) is shown as outputting28
while I believe it should yield37
– Jonathan Allan – 2019-04-07T20:53:08.170@JonathanAllan yes, you are correct. I fixed the last two test cases for $N$th term but not that one. The post has been edited. – Tau – 2019-04-07T20:55:32.390
@LuisMendo I believe so. I'll edit the post. – Tau – 2019-04-08T13:06:25.653
Not to detract from the question, but is this the actual definition of the Fibonacci sequence? I was taught it as a sequence of numbers, in which the first two numbers are 1, and the 3rd and subsequent numbers are the sum of the prior two numbers. Then again, I was taught this as an example of a problem to solve with recursion... – sharur – 2019-04-08T23:30:19.333
1@sharur this definition for the Fibonacci sequence is the visual definition. Each successive square added has a length of that term in the sequence. The sequence you describe is the numerical reasoning behind it. Both sequences work just as well as the other. – Tau – 2019-04-09T02:12:33.303
1Note that the OEIS sequence you linked is slightly different, since it uses
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
– Carmeister – 2019-04-09T02:13:04.680@Carmeister yes, that is correct. The OEIS sequence is the true Padovan sequence, but I shifted it over to $a_0=a_1=a_2=1$ for convenience (plus most mentions I've seen of this sequence start it at the aforementioned shift). – Tau – 2019-04-09T02:17:40.773
Questions in Code Golf that result in answers under 10 bytes should automatically get a hat or something. Yet again the compact answers were mind boggling and it is hard to think that this question was not considered when the languages were developed. – KalleMP – 2019-04-09T22:35:33.350