

The Padovan sequence is similar to the Fibonacci sequence in several ways.
Some are given in the table below, and the referenced video shows some of the geometric
similarities.



 Comment 
 Padovan 
 Fibonacci


 
 



 Named after. 
 Richard Padovan 
 Leonardo of Pisa: Fibonacci


 
 



 Recurrence initial values. 
 P(0)=P(1)=P(2)=1 
 F(0)=0, F(1)=1


 Recurrence relation. 
 P(n)=P(n-2)+P(n-3) 
 F(n)=F(n-1)+F(n-2)


 
 



 First 10 terms. 
 1,1,1,2,2,3,4,5,7,9 
 0,1,1,2,3,5,8,13,21,34


 
 



 Ratio of successive terms... 
 Plastic ratio, p 
 Golden ratio, g


 
 1.324717957244746025960908854… 
 1.6180339887498948482...


 Exact formula of ratios p and q. 
 ((9+69**.5)/18)**(1/3) + ((9-69**.5)/18)**(1/3) 
 (1+5**0.5)/2


 Ratio is real root of polynomial. 
 p: x**3-x-1 
 g: x**2-x-1


 
 



 Spirally tiling the plane using. 
 Equilateral triangles 
 Squares


 
 



 Constants for ... 
 s= 1.0453567932525329623 
 a=5**0.5


 ... Computing by truncation. 
 P(n)=floor(p**(n-1) / s + .5) 
 F(n)=floor(g**n / a + .5)


 
 



 L-System Variables. 
 A,B,C 
 A,B


 L-System Start/Axiom. 
 A 
 A


 L-System Rules. 
 A->B,B->C,C->AB 
 A->B,B->AB

Task

 Write a function/method/subroutine to compute successive members of the Padovan series using the recurrence relation.
 Write a function/method/subroutine to compute successive members of the Padovan series using the floor function.
 Show the first twenty terms of the sequence.
 Confirm that the recurrence and floor based functions give the same results for 64 terms,
 Write a function/method/... using the L-system to generate successive strings.
 Show the first 10 strings produced from the L-system
 Confirm that the length of the first 32 strings produced is the Padovan sequence.
Show output here, on this page.

Ref

 The Plastic Ratio - Numberphile video.


BEGIN # show members of the Padovan Sequence calculated in various ways #
    # returns the first n elements of the Padovan sequence by the       #
    #         recurance relation: P(n)=P(n-2)+P(n-3)	                #
    OP PADOVANI = ( INT n )[]INT:
       BEGIN
           [ 0 : n - 1 ]INT p; p[ 0 ] := p[ 1 ] := p[ 2 ] := 1;
           FOR i FROM 3 TO UPB p DO
               p[ i ] := p[ i - 2 ] + p[ i - 3 ]
           OD;
           p
       END; # PADOVANI #
    # returns the first n elements of the Padovan sequence by           #
    #         computing by truncation P(n)=floor(p^(n-1) / s + .5)      #
    #                where s = 1.0453567932525329623                    #
    #                  and p = the "plastic ratio"                      #
    OP PADOVANC = ( INT n )[]INT:
       BEGIN
           LONG REAL    s   = 1.0453567932525329623;
           LONG REAL    p   = 1.324717957244746025960908854;
           LONG REAL    pf := 1 / p;
           [ 0 : n - 1 ]INT result;
           FOR i FROM LWB result TO UPB result DO
               result[ i ] := SHORTEN ENTIER ( pf / s + 0.5 );
               pf         *:= p
           OD;
           result
       END; # PADOVANC #
    # returns the first n L System strings of the Padovan sequence      #
    OP PADOVANL = ( INT n )[]STRING:
       BEGIN
           [ 0 : n - 1 ]STRING l; l[ 0 ] := "A"; l[ 1 ] := "B"; l[ 2 ] := "C";
           FOR i FROM 3 TO UPB l DO
               l[ i ] := l[ i - 3 ] + l[ i - 2 ]
           OD;
           l
    END; # PADOVANC #
    # returns TRUE if a and b have the same values, FALSE otherwise     #
    OP = = ( []INT a, b )BOOL:
       IF LWB a /= LWB b OR UPB a /= UPB b
       THEN # rows are not the same size # FALSE
       ELSE
           BOOL result := TRUE;
           FOR i FROM LWB a TO UPB a WHILE result := a[ i ] = b[ i ] DO SKIP OD;
           result
       FI; # = #
    # returns the number of elements in a                               #
    OP LENGTH = ( []INT a )INT: ( UPB a - LWB a ) + 1;
    # returns the number of characters in s                             #
    OP LENGTH = ( STRING s )INT: ( UPB s - LWB s ) + 1;
    # returns a string representation of n                              #
    OP TOSTRING = ( INT n )STRING: whole( n, 0 );
    # generate 64 elements of the sequence and 32 L System values       #
    []INT    iterative  = PADOVANI 64;
    []INT    calculated = PADOVANC 64;
    []STRING l system   = PADOVANL 32;
    [ LWB l system : UPB l system ]INT l length;
    FOR i FROM LWB l length TO UPB l length DO l length[ i ] := LENGTH l system[ i ] OD;
    # first 20 terms                                                    #
    print( ( "First 20 terms of the Padovan Sequence", newline ) );
    FOR i FROM LWB iterative TO 19 DO
        print( ( " ", TOSTRING iterative[ i ] ) )
    OD;
    print( ( newline ) );
    print( ( "The first "
           , TOSTRING LENGTH iterative
           , " iterative and calculated values "
           , IF iterative = calculated THEN "are the same" ELSE "differ" FI
           , newline
           )
         );
    # print the first 10 values of the L System strings                 #
    print( ( newline, "First 10 L System strings", newline ) );
    FOR i FROM LWB l system TO 9 DO
        print( ( " ", l system[ i ] ) )
    OD;
    print( ( newline ) );
    print( ( "The first "
           , TOSTRING LENGTH l length
           , " iterative values and L System lengths "
           , IF l length = iterative[ LWB l length : UPB l length @ LWB l length ] THEN "are the same" ELSE "differ" FI
           ,  newline
           )
         )
END
 