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

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


  • 2
    \$\begingroup\$ 14 (0-indexed) is shown as outputting 28 while I believe it should yield 37 \$\endgroup\$ Apr 7, 2019 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\$ Apr 7, 2019 at 20:55
  • \$\begingroup\$ @LuisMendo I believe so. I'll edit the post. \$\endgroup\$ Apr 8, 2019 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\$ Apr 9, 2019 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, 2019 at 2:13

52 Answers 52


J, 14 bytes


Try it online!

Asks for the (input)-th Taylor coefficient of the generating function $$x \mapsto \frac{x+1}{1-x^2\cdot(x+1)}.$$

(The parenthesized train >: % 1 - *: * >: is read as: “increment over one minus square times increment.”)


Perl 5, 38 36 bytes (full program)

-2 bytes thanks to dingledooper

By the challenge's specification, this is \$1\$-indexed:


Try it online!

This uses the same trick as Fibonacci function or sequence, with the 1 byte modification of inserting an extra . in the regex, so that the number of ordered partitions as a sum of the numbers \$2\$ and \$3\$ is counted. For example, \$11\$ can be represented \$9\$ ways:


This tells us that the term at index \$11-1\$ (in the \$1\$-indexing requested by the challenge) is \$9\$.

In the form of a full program, Xcali's recursive answer is longer at 43 bytes:

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

Try it online!

But the most mathematically consistent indexing for the Padovan sequence would have it start with \$0,1,0,1,1,1,2,2,3...\$ at index \$0\$, based on the Fibonacci indexing in which \$0,1,1,2,3,5,8...\$ starts at index \$0\$. By this challenge's specification that would be “\$3\$-indexing”. The regex backtracking method golfs best with “\$2\$-indexing”, and the recursive method golfs best with “\$0\$-indexing”.

With “\$2\$-indexing” and higher, 1 0 bytes must be taken to coerce the return value into an integer, because the term at index \$1\$ is \$0\$, and ++$i would never get executed – which would leave it with a non-value if it were not initialized. This can be golfed by adding the boolean falsey return value of the regex match operator (which gets coerced to the integer 0) to $i, though Perl gives the runtime warning Use of uninitialized value $i in addition (+) if this happens with use warnings enabled.

Something similar happens with the “\$2\$-indexing” recursive version, requiring the use of a ^1 XOR which gives the warning Possible precedence problem on bitwise ^ operator with use warnings enabled.

\$0\$-indexing”: 1x<>.11~~/^(...?)*$(?{++$i})\1/;say$i 37 bytes - Try it online!
\$1\$-indexing”: 1x<>.1~~/^(...?)*$(?{++$i})\1/;say$i 36 bytes - Try it online!
\$2\$-indexing”: $_=1x<>;say/^(...?)*$(?{++$i})\1/+$i 36 bytes - Try it online!
\$3\$-indexing”: $_=1x<>;say/^.(...?)*$(?{++$i})\1/+$i 37 bytes - Try it online!

\$0\$-indexing”: sub f{"@_"<3||f("@_"-2)+f("@_"-3)}say f(<>) 43 bytes - Try it online!
\$1\$-indexing”: sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}say f(<>) 48 bytes - Try it online!
\$2\$-indexing”: sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}say f(<>) 51 bytes - Try it online!
\$3\$-indexing”: sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}say f(<>) 48 bytes - Try it online!

Perl 5 -n, 43 42 40 bytes (full program with implied loop)

It is longer when required to be executed in a loop, due to the need to initialize $i each time, but this can be golfed to cost only 4 bytes:


Try it online!

Alternative 40 bytes (doesn't work for “\$2\$-indexing” and higher):


Try it online!

\$0\$-indexing”: 1x$_.11~~/^(...?)*$(?{++$i})\1/;$i=!say$i 41 bytes - Try it online!
\$1\$-indexing”: 1x$_.1~~/^(...?)*$(?{++$i})\1/;$i=!say$i 40 bytes - Try it online!
\$2\$-indexing”: $i=0;1x$_~~/^(...?)*$(?{++$i})\1/;say$i 39 bytes - Try it online!
\$3\$-indexing”: $i=0;1x$_~~/^.(...?)*$(?{++$i})\1/;say$i 40 bytes - Try it online!

\$0\$-indexing”: sub f{"@_"<3||f("@_"-2)+f("@_"-3)}say f($_) 43 bytes - Try it online!
\$1\$-indexing”: sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}say f($_) 48 bytes - Try it online!
\$2\$-indexing”: sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}say f($_) 51 bytes - Try it online!
\$3\$-indexing”: sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}say f($_) 48 bytes - Try it online!

Perl 5 -pl, 43 42 40 bytes (full program with implied loop)

The initialization can be golfed in this form as well (but this doesn't work for “\$2\$-indexing” and higher):


Try it online!

\$0\$-indexing”: 1x$_.11~~/^(...?)*$(?{++$i})\1/;$i%=$_=$i 41 bytes - Try it online!
\$1\$-indexing”: 1x$_.1~~/^(...?)*$(?{++$i})\1/;$i%=$_=$i 40 bytes - Try it online!
\$2\$-indexing”: $i=0;1x$_~~/^(...?)*$(?{++$i})\1/;$_=$i 39 bytes - Try it online!
\$3\$-indexing”: $i=0;1x$_~~/^.(...?)*$(?{++$i})\1/;$_=$i 40 bytes - Try it online!

\$0\$-indexing”: sub f{"@_"<3||f("@_"-2)+f("@_"-3)}$_=f($_) 42 bytes - Try it online!
\$1\$-indexing”: sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}$_=f($_) 47 bytes - Try it online!
\$2\$-indexing”: sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}$_=f($_) 50 bytes - Try it online!
\$3\$-indexing”: sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}$_=f($_) 47 bytes - Try it online!

Perl 5, 47 45 bytes (anonymous function with no side effects)


Try it online! - displays terms \$1\$ through \$46\$ with “\$1\$-indexing”

As a function already, Xcali's 34 byte answer is shorter, although significantly slower:

Try it online! - displays terms \$0\$ through \$45\$ with “\$0\$-indexing”

\$0\$-indexing”: sub{my$i;1x(2+pop)~~/^(...?)*$(?{++$i})\1/;$i} 46 bytes - Try it online!
\$1\$-indexing”: sub{my$i;1x"@_".1~~/^(...?)*$(?{++$i})\1/;$i} 45 bytes - Try it online!
\$2\$-indexing”: sub{my$i;(1x pop)=~/^(...?)*$(?{++$i})\1/+$i} 45 bytes - Try it online!
\$3\$-indexing”: sub{my$i;(1x pop)=~/^.(...?)*$(?{++$i})\1/+$i} 46 bytes - Try it online!

\$0\$-indexing”: sub f{"@_"<3||f("@_"-2)+f("@_"-3)} 34 bytes - Try it online!
\$1\$-indexing”: sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)} 39 bytes - Try it online!
\$2\$-indexing”: sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)} 42 bytes - Try it online!
\$3\$-indexing”: sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)} 39 bytes - Try it online!

Perl 6, 27 26 25 24 bytesSBCS (anonymous function)


Try it online!

Thanks to Jo King for extending the idea to this language.

\$0\$-indexing”: {+m:ex/^(...?)*$/}o¹x*+2 24 bytes - Try it online!
\$1\$-indexing”: {+m:ex/^(...?)*$/}o¹x*+1 24 bytes - Try it online!
\$2\$-indexing”: {+m:ex/^(...?)*$/}o¹x* 22 bytes - Try it online!
\$3\$-indexing”: {+m:ex/^.(...?)*$/}o¹x* 23 bytes - Try it online!

Sean's non-regex answer (shown below adapted to different indexings) is still shorter, but only by 2 bytes (though it's longer at “\$3\$-indexing” and ties at “\$2\$-indexing”). Fibonacci is not even close.

\$0\$-indexing”: {(1,1,1,*+*+!*…*)[$_]} 22 bytes - Try it online!
\$1\$-indexing”: {(0,1,1,*+*+!*…*)[$_]} 22 bytes - Try it online!
\$2\$-indexing”: {(1,0,1,*+*+!*…*)[$_]} 22 bytes - Try it online!
\$3\$-indexing”: {(0,1,~0,*+*+!*…*)[$_]} 23 bytes - Try it online!
\$3\$-indexing”: {(0,1,0,*+*+*%1…*)[$_]} 23 bytes - Try it online!
\$3\$-indexing”: {(0,1,0,*+*+*×0…*)[$_]} 23 bytes - Try it online!

Note that the same regex method used in the Perl 5 versions can also be directly ported to Perl 6:

\$0\$-indexing”: {my$i;¹x$_+2~~/^(...?)*${++$i}./;$i} 36 bytes - Try it online!
\$1\$-indexing”: {my$i;¹x$_+1~~/^(...?)*${++$i}./;$i} 36 bytes - Try it online!
\$2\$-indexing”: {my$i;¹x$_~~/^(...?)*${++$i}./;+$i} 35 bytes - Try it online!
\$3\$-indexing”: {my$i;¹x$_~~/^.(...?)*${++$i}./;+$i} 36 bytes - Try it online!


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

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

Try it online!


Wolfram Language (Mathematica), 26 bytes


Try it online!


Pari/GP, 28 bytes



Try it online!

Pari/GP, 35 bytes



Try it online!

The generating function of the sequence is \$\frac{1+x}{1-x^2-x^3}\$.


Gaia, 16 14 12 bytes


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


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

Brain-Flak, 96 bytes


Try it online!


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.


Clojure, 46 bytes

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

Just for completeness sake :)

Try it online!

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

dc, 50 48 bytes


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.


CJam, 16 bytes


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

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)

Stax, 7 bytes


Run and debug it


J, 17 bytes


Try it online!

                #   length of input, 1
              3#    1,1,1
 [                     N times:
  2       +/\          sums of length 2 windows
       _2{             pick second to last
     ],                append
$                   take N 
{                   (or pick Nth term for same score)

x86, 19 bytes

f:	xor eax, eax
.a:	push edi
.a2:	sub edi, 3
	jc  .l
	call .a
	inc edi
	jmp .a2
.l:	inc eax
	pop edi

Try it online!


Julia, 21 bytes


Try it online!

  • \$\begingroup\$ Is there any shorter way to get the first three terms to be 1 instead of true than !n=+(n<3||!(n-2)+!(n-3)) Try it online! (24 bytes)? \$\endgroup\$
    – Deadcode
    Apr 13, 2021 at 4:11
  • \$\begingroup\$ @Deadcode true == 1, i think I can leave it like that. Otherwise with Julia 0.7 Try it online! \$\endgroup\$
    – MarcMush
    Apr 13, 2021 at 11:56

Arn -al, 9 bytes

I'm not particularly sure why this works...


Try it! 1-indexed, outputs the nth term


Unpacked: 1 1 1{#+}-> Exploits Arn's weird precedence bugs to save a byte. A more "normal" version would have {_ _+} as the block or something like {#_+} (as # is a suffix)

[ ... ]      Implied by `-a` flag
  1          First entry = 1
  1          Second entry = 1
  1          Third entry = 1
    {        Other entries determined by
        _      a[n - 1], throwaway implied
      #        This implies the `_` before it while allowing + to not have it b/c bugs
        _    a[n - 2], implied
      +      Plus
        _    a[n - 3]
    }        Return this last value
  ->         Sequence has length of
    _        STDIN; implied
         Then, get last item

tinylisp, 63 bytes

(d f(q((x y z u)(i u(f y z(a x y)(s u 1))x
(d g(q((x)(f 1 1 1 x

Try it online!

-10 from dlosc

  • \$\begingroup\$ lol my bad..... \$\endgroup\$
    – Razetime
    Feb 2, 2022 at 1:45
  • \$\begingroup\$ What do you think of (d g(q((x)(i(l x 3)1(a(g(s x 2))(g(s x 3 \$\endgroup\$
    – Axuary
    Feb 2, 2022 at 2:41
  • \$\begingroup\$ I did not think about naive recursion, lol. You should post it separately \$\endgroup\$
    – Razetime
    Feb 2, 2022 at 2:44

Vyxal, 8 bytes


Try it Online! Woo, we beat Jelly!

‡  T      # A triadic lambda function taking three arguments...
 _+       # Pop the first and add the next two
    ⁺NL   # With the initial vector [1, 1, 1]...
       Ḟ  # Create an infinite generator that calls the function with the last <arity> (3 in this case) arguments and appends that to the list.
        Ẏ # Get the first n items.

NL in the explanation represents a literal newline. In Vyxal, takes the index of the next character in the Vyxal codepage and adds 101 to it. As Vyxal's codepage is aligned with ASCII, a newline is #10, so the number 111 can be represented by and a newline.

  • \$\begingroup\$ 8 bytes \$\endgroup\$
    – lyxal
    Feb 1, 2022 at 23:46
  • \$\begingroup\$ @lyxal Nice, forgot about that! \$\endgroup\$
    – emanresu A
    Feb 2, 2022 at 0:55

Groovy, 22 bytes


Try it online!

  • \$\begingroup\$ This is Fibonacci with an extra \$1\$ term, not Padovan. The correct form for the latter would be a->a<3?1:f(a-3)+f(a-2) Try it online! at the same byte length. \$\endgroup\$
    – Deadcode
    Apr 13, 2021 at 2:10

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.


Excel, 79 77 65 bytes

-2 bytes, sequence didn't need to be horizontal

-12 bytes, change lower bound to 1 and handle errors from COMBIN


It uses the equation \$P(k-2)=\sum_{m=\lceil k/3\rceil}^{\lfloor k/2\rfloor}{m \choose k-2m}.\$

k=A1+2                        'k = N + 2
m=SEQUENCE(INT(k/2))          'm = 1 .. floor k/2
SUM(IFERROR(COMBIN(m,k-2*m))) 'Sum of combinations (m, k-2m)

MMIX, 40 bytes (10 instrs)


00000000: e3010000 e3020001 e3030001 22ff0102  ẉ¢¡¡ẉ£¡¢ẉ¤¡¢"”¢£
00000010: c1010200 c1020300 c103ff00 27000001  Ḋ¢£¡Ḋ£¤¡Ḋ¤”¡'¡¡¢
00000020: 5b00fffb f8020000                    [¡”»ẏ£¡¡

(disassembly and explanation)

pado    SETL $1,0       // a(4) - pad(0) except that doesn't work properly
        SETL $2,1       // a(5) - pad(1)
        SETL $3,1       // a(6) - pad(2)
0H      ADDU $255,$1,$2 // a(n + 3) = a(n) + a(n + 1)
        SET  $1,$2      // shift down
        SET  $2,$3
        SET  $3,$255
        SUBU $0,$0,1    // one cycle done
        PBNZ $0,0B      // return if done
        POP  2,0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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