44
\$\begingroup\$

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:

\$\endgroup\$
  • 2
    \$\begingroup\$ 14 (0-indexed) is shown as outputting 28 while I believe it should yield 37 \$\endgroup\$ – Jonathan Allan Apr 7 at 20:53
  • \$\begingroup\$ @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. \$\endgroup\$ – Tau Apr 7 at 20:55
  • \$\begingroup\$ @LuisMendo I believe so. I'll edit the post. \$\endgroup\$ – Tau Apr 8 at 13:06
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Tau Apr 9 at 2:12
  • 1
    \$\begingroup\$ Note 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 then a_5=a_6=a_7=1 \$\endgroup\$ – Carmeister Apr 9 at 2:13

41 Answers 41

1
\$\begingroup\$

Japt, 12 9 bytes

Returns the nth term, 1-indexed.

@1gZÔä+}g

Try it

@1gZÔä+}g     :Implicit input of integer U
        g     :Starting with the array [0,1] do the following U times, pushing the result to the array each time
@             :  Pass the array through the following function as Z
 1g           :    Get the element at 0-based index 1, with wrapping, from the following
   ZÔ         :    Reverse Z
     ä+       :    Get the sums of each consecutive pair of elements
       }      :  End function
              :Implicit output of the last element in the array
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

This implementation of the binomial formula: a(n) = Sum_{k=0..floor(n/2)} binomial(k+1, n-2k) is interestingly the same length as the recursive solution.

;Ý·-āscO

Try it online!

Explanation

;Ý        # push [0 ... floor(input/2)]
  ·       # double each
   -      # subtract each from input
    ā     # push range [1 ... len(list)]
     s    # swap
      c   # choose
       O  # sum
\$\endgroup\$
1
\$\begingroup\$

Brain-Flak, 96 bytes

(()()()){({}[()]<{({}[()])<>(())(<>)}{}>)}{}{({}[()]<<>({}<(({}(({}))<>)<>[{}])>)<>({}<>)<>>)}<>

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C++ (gcc), 81 75 74 bytes

-6 bytes to small golfing

-1 byte thanks to @ceilingcat

int a(int n){int a=1,b=1,c=1,d,i=2;for(;i++<n;c=d)d=a+b,a=b,b=c;return c;}

Try it online!

Simple function to compute the values iteratively. No loop occurs for n<3, so the first cases default to the initial 1.

\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thanks, updated. \$\endgroup\$ – Neil A. Apr 9 at 23:15
1
\$\begingroup\$

Clojure, 46 bytes

(defn f[n](if(< n 3)1(+(f(- n 2))(f(- n 3)))))

Just for completeness sake :)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG :) \$\endgroup\$ – Shaggy Apr 10 at 13:07
0
\$\begingroup\$

Groovy, 22 bytes

a->a<3?1:f(a-2)+f(a-1)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Gaia, 16 14 12 bytes

7b@⟨ṇ;(++⟩ₓ(

Try it online!

0-based index. Only holds the last 3 values.

7b		| push [1 1 1]
  @		| push input
   ⟨     ⟩ₓ	| do the following that many times (0 times if 0 or less)
    ṇ		| pop the first element and leave the rest below
     ;		| copy from below
      (		| take the first element
       +	| add the two together
	+	| and concatenate to the list. End loop.
	   (	| finally, take the first element

Gaia, 14 bytes

ø@⟨18b+ₔ…Σ¦⟩ₓ<

Try it online!

Returns the first n elements, 1-based index. < could also be E to get just the nth element.

Uses the identity from the OEIS page \$a(n+5)=\sum\limits_{i=1}^n a(i)\$.

This is quite inefficient, as it repeatedly copies the first few lists.

ø		| push empty list
 @⟨	   ⟩ₓ	| do (input) number of times:
   18b		| push [1 0 0 1 0] by converting 18 to bits
      +ₔ	| append cumulative list (initially empty) to end of bits
	…Σ¦	| and calculate the cumulative sums, replacing old cumulative list
	     <	| finally, take the first (input) elements of cumulative sums
\$\endgroup\$
0
\$\begingroup\$

C# (.NET Core), 144 bytes, 0-indexed.

using C=System.Console;class A{static void Main(){int i=int.Parse(C.ReadLine());C.Write(p(i));}static int p(int i){return i<3?1:p(i-2)+p(i-3);}}

Try it online!

Quite frankly, this is not my best work ever. But here it is.

\$\endgroup\$
0
\$\begingroup\$

dc, 50 48 bytes

 2+sx3si1d:a[liddddd3-;ar2-;a+r:a1+silx>M]dsMx;ap

It's 1-indexed! Try it online! Previous version!

Golfed off two bytes by only populating the first element in the array.

Probably can be golfed a bit more, but it's tricky because you have to a: seed the initial values, and b: use arrays since dc doesn't let you pick from arbitrary stack positions.

2+sx3si adds two to the user input at top of stack into register x, and starts an increment counter register i at 3. We have to add two because the array is now populated in such a way that it's 3-indexed.

1d:a populates element 1 of array a with a 1. The 50 byte version populated elements 1 and 2 with 1d2:a1:a. The mechanism works with just the single element populated, however, it just takes a little while to get enough 1s in place such as to start the sequence. Even though going from 1d2:a1:a to 1d:a saves 4 bytes, we now have to 2+ our input. Still two bytes saved. Initially, I thought I had to seed the first three elements with 1dd3:a2:a1:a (+4 bytes), but... dc returns a zero for any unassigned array element, and if we start macro M (below) by creating the third element, adding 0 to 1... we're good to go.

Macro M:

liddddd loads register i and makes a bunch of copies of it. We subtract 3 from one of these, get the corresponding element from a and then swap top of stack. Subtract 2, get the corresponding element from a, add the two elements to get our new value, then swap the top of stack. At this point, :a puts our new value into a at position i. 1+si to increment i, and lx>M to keep running M until we hit our target (stored in x). dsMx runs M, and once M has finished running, the stack should be full of leftover i values, the topmost of which is the last one we made. Load the value from a with ;a and print it with p.

\$\endgroup\$
0
\$\begingroup\$

CJam, 16 bytes

qi7Yb{((_j\(j+}j

0-indexed, returns nth item
Try it online!

Explanation: It uses a recursive function to add a(n-2) to a(n-3) to find a(n).

qi7Yb{((_j\(j+}j
qi               - reads input as integer
  7Yb            - push an array of [1, 1, 1]. It does this by pushing 7, then 
                   turning it into binary.
     {        }j - define a recursive function to calculate a(n), where the 
                   predefined values for n = 0,1,2 are 1,1,1
      ((         - subtract 2 from n | Stack: n-2
        _        - duplicate | Stack: n-2, n-2
         j       - find a(n-2) | Stack: n-2, a(n-2)
          \      - swap the top two items in the stack | Stack: a(n-2), n-2
           (     - decrement | Stack: a(n-2), n-3
            j    - find a(n-3) | Stack: a(n-2), a(n-3)
             +   - add, finding a(n)
                 - implicit output

In pseudocode:

read input as integer
define padovan_sequence(n):
    return padovan_sequence(n-2) + padovan_sequence(n-3)
print(padovan_sequence(n))
\$\endgroup\$
0
\$\begingroup\$

Stax, 7 bytes

ÉKΦΘÄO¢

Run and debug it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.