As the Fibonacci sequence expands to the Fibonacci n-step number sequences; We similarly expand the Padovan sequence to form these Padovan n-step number sequences.

The Fibonacci-like sequences can be defined like this:

   For n == 2:
       start:      1, 1
       Recurrence: R(n, x) = R(n, x-1) + R(n, x-2); for n == 2
   For n == N:
       start:      First N terms of R(N-1, x)
       Recurrence: R(N, x) = sum(R(N, x-1) + R(N, x-2) + ... R(N, x-N))

For this task we similarly define terms of the first 2..n-step Padovan sequences as:

   For n == 2:
       start:      1, 1, 1
       Recurrence: R(n, x) = R(n, x-2) + R(n, x-3); for n == 2
   For n == N:
       start:      First N + 1 terms of R(N-1, x)
       Recurrence: R(N, x) = sum(R(N, x-2) + R(N, x-3) + ... R(N, x-N-1))

The initial values of the sequences are:


 Padovan 



n


{\displaystyle n}

-step sequences


 



n


{\displaystyle n}

 
 Values 
 OEIS Entry


 2 
 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37, ... 
 A134816: 'Padovan's spiral numbers'


 3 
 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129, ... 
 A000930: 'Narayana's cows sequence'


 4 
 1,1,1,2,3,5,7,11,17,26,40,61,94,144,221, ... 
 A072465: 'A Fibonacci-like model in which each pair of rabbits dies after the birth of their 4th litter'


 5 
 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286, ... 
 A060961: 'Number of compositions (ordered partitions) of n into 1's, 3's and 5's'


 6 
 1,1,1,2,3,5,8,13,20,32,51,81,129,205,326, ... 
 <not found>


 7 
 1,1,1,2,3,5,8,13,21,33,53,85,136,218,349, ... 
 A117760: 'Expansion of 1/(1 - x - x^3 - x^5 - x^7)'


 8 
 1,1,1,2,3,5,8,13,21,34,54,87,140,225,362, ... 
 <not found>




Task

 Write a function to generate the first 



t


{\displaystyle t}

 terms, of the first 2..max_n Padovan 



n


{\displaystyle n}

-step number sequences as defined above.
 Use this to print and show here at least the first t=15 values of the first 2..8 



n


{\displaystyle n}

-step sequences.
 (The OEIS column in the table above should be omitted).


begin % show some valuies of the Padovan n-step number sequences  %
    % sets R(i,j) to the jth element of the ith padovan sequence  %
    % maxS is the number of sequences to generate and maxE is the %
    % maximum number of elements for each sequence                %
    % maxS must be >= 2                                           %
    procedure PadovanSequences ( integer array R ( *, * )
                               ; integer value maxS, maxE
                               ) ;
    begin
        integer procedure min( integer value a, b ) ; if a < b then a else b;
        % sequence 2                                              %
        for x := 1 until min( maxE, 3 ) do R( 2, x ) := 1;
        for x := 4 until maxE do R( 2, x ) := R( 2, x - 2 ) + R( 2, x - 3 );
        % sequences 3 and above                                   %
        for N := 3 until maxS do begin
            for x := 1 until min( maxE, N + 1 ) do R( N, x ) := R( N - 1, x );
            for x := N + 2 until maxE do begin
                R( N, x ) := 0;
                for p := x - N - 1 until x - 2 do R( N, x ) := R( N, x ) + R( N, p )
            end for_x
        end for_N
    end PadovanSequences ;
    integer MAX_SEQUENCES, MAX_ELEMENTS;
    MAX_SEQUENCES :=  8;
    MAX_ELEMENTS  := 15;
    begin % calculate and show the sequences                      %
        % array to hold the Padovan Sequences                     %
        integer array R ( 2 :: MAX_SEQUENCES, 1 :: MAX_ELEMENTS );
        % construct the sequences                                 %
        PadovanSequences( R, MAX_SEQUENCES, MAX_ELEMENTS );
        % show the sequences                                      %
        write( "Padovan n-step sequences:" );
        for n := 2 until MAX_SEQUENCES do begin
            write( i_w := 1, s_w := 0, n, " |" );
            for x := 1 until MAX_ELEMENTS do writeon( i_w := 3, s_w := 0, " ", R( n, x ) )
        end for_n
    end
end.