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

50 Answers 50

1
2
2
\$\begingroup\$

Perl 5, 38 bytes (full program)

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

(1x<>.1)=~/^(...?)*$(?{++$i})\1/;say$i

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:

2+2+2+2+3
2+2+2+3+2
2+2+3+2+2
2+3+2+2+2
3+2+2+2+2
2+3+3+3
3+2+3+3
3+3+2+3
3+3+3+2

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 39 bytes - Try it online!
\$1\$-indexing”: (1x<>.1)=~/^(...?)*$(?{++$i})\1/;say$i 38 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 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:

(1x$_.1)=~/^(...?)*$(?{++$i})\1/;$i=!say$i

Try it online!

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

(1x$_.1)=~/^(...?)*$(?{++$i})\1/;$i%=say$i

Try it online!

\$0\$-indexing”: (1x$_.11)=~/^(...?)*$(?{++$i})\1/;$i=!say$i 43 bytes - Try it online!
\$1\$-indexing”: (1x$_.1)=~/^(...?)*$(?{++$i})\1/;$i=!say$i 42 bytes - Try it online!
\$2\$-indexing”: $_=1x$_;$i=!say/^(...?)*$(?{++$i})\1/+$i 40 bytes - Try it online!
\$3\$-indexing”: $_=1x$_;$i=!say/^.(...?)*$(?{++$i})\1/+$i 41 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 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):

(1x$_.1)=~/^(...?)*$(?{++$i})\1/;$i%=$_=$i

Try it online!

\$0\$-indexing”: (1x$_.11)=~/^(...?)*$(?{++$i})\1/;$i%=$_=$i 43 bytes - Try it online!
\$1\$-indexing”: (1x$_.1)=~/^(...?)*$(?{++$i})\1/;$i%=$_=$i 42 bytes - Try it online!
\$2\$-indexing”: $i=0;(1x$_)=~/^(...?)*$(?{++$i})\1/;$_=$i 41 bytes - Try it online!
\$3\$-indexing”: $i=0;(1x$_)=~/^.(...?)*$(?{++$i})\1/;$_=$i 42 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 bytes (anonymous function with no side effects)

sub{my$i;(1x"@_".1)=~/^(...?)*$(?{++$i})\1/;$i}

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} 48 bytes - Try it online!
\$1\$-indexing”: sub{my$i;(1x"@_".1)=~/^(...?)*$(?{++$i})\1/;$i} 47 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)

{+m:ex/^(...?)*$/}o¹x*+2

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!

\$\endgroup\$
2
\$\begingroup\$

J, 14 bytes

(>:%1-*:*>:)t.

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

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

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

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

Try it online!

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

Wolfram Language (Mathematica), 26 bytes

If[#<3,1,#0[#-2]+#0[#-3]]&

Try it online!

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

Pari/GP, 28 bytes

0-indexed.

f(n)=if(n<3,1,f(n-2)+f(n-3))

Try it online!


Pari/GP, 35 bytes

1-indexed.

n->Vec((1+x+O(x^n))/(1-x^2-x^3))[n]

Try it online!

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

\$\endgroup\$
1
\$\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\$
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\$
1
  • \$\begingroup\$ @ceilingcat Thanks, updated. \$\endgroup\$
    – Neil A.
    Apr 9 '19 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\$
1
  • \$\begingroup\$ Welcome to PPCG :) \$\endgroup\$
    – Shaggy
    Apr 10 '19 at 13:07
1
\$\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\$
1
\$\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\$
1
\$\begingroup\$

Stax, 7 bytes

ÉKΦΘÄO¢

Run and debug it

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

J, 17 bytes

$[2&(],_2{+/\)3##

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)
\$\endgroup\$
1
\$\begingroup\$

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
	ret

Try it online!

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

Julia, 21 bytes

!n=n<3||!(n-2)+!(n-3)

Try it online!

\$\endgroup\$
2
  • \$\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 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 at 11:56
1
\$\begingroup\$

Arn -al, 9 bytes

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

w®¦€•3=⁺■

Try it! 1-indexed, outputs the nth term

Explained

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
\$\endgroup\$
0
\$\begingroup\$

Groovy, 22 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\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 at 2:10
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\$

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

=LET(k,A1+2,m,SEQUENCE(INT(k/2)),SUM(IFERROR(COMBIN(m,k-2*m),0)))

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

=LET(
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)
\$\endgroup\$
0
\$\begingroup\$

MMIX, 40 bytes (10 instrs)

(jxd)

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
\$\endgroup\$
1
2

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.