

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.


 
program Padovan_sequence;
 
{$APPTYPE CONSOLE}
 
uses
  System.SysUtils,
  Velthuis.BigDecimals,
  Boost.Generics.Collection;
 
type
  TpFn = TFunc<Integer, Integer>;
 
var
  RecMemo: TDictionary<Integer, Integer>;
  lSystemMemo: TDictionary<Integer, string>;
 
function pRec(n: Integer): Integer;
begin
  if RecMemo.HasKey(n) then
    exit(RecMemo[n]);
 
  if (n <= 2) then
    RecMemo[n] := 1
  else
    RecMemo[n] := pRec(n - 2) + pRec(n - 3);
  Result := RecMemo[n];
end;
 
function pFloor(n: Integer): Integer;
var
  p, s, a: BigDecimal;
begin
  p := '1.324717957244746025960908854';
  s := '1.0453567932525329623';
  a := p.IntPower(n - 1, 64);
  Result := Round(BigDecimal.Divide(a, s));
end;
 
function lSystem(n: Integer): string;
begin
  if n = 0 then
    lSystemMemo[n] := 'A'
  else
  begin
    lSystemMemo[n] := '';
    for var ch in lSystemMemo[n - 1] do
    begin
      case ch of
        'A':
          lSystemMemo[n] := lSystemMemo[n] + 'B';
        'B':
          lSystemMemo[n] := lSystemMemo[n] + 'C';
        'C':
          lSystemMemo[n] := lSystemMemo[n] + 'AB';
      end;
    end;
  end;
  Result := lSystemMemo[n];
end;
 
procedure Compare(f1, f2: TpFn; descr: string; stop: Integer);
begin
  write('The ', descr, ' functions ');
  var i := 0;
  while i < stop do
  begin
    var n1 := f1(i);
    var n2 := f2(i);
    if n1 <> n2 then
    begin
      write('do not match at ', i);
      writeln(': ', n1, ' != ', n2, '.');
      break;
    end;
    inc(i);
  end;
  if i = stop then
    writeln('match from P_0 to P_', stop, '.');
end;
 
begin
  RecMemo := TDictionary<Integer, Integer>.Create([], []);
  lSystemMemo := TDictionary<Integer, string>.Create([], []);
 
  write('P_0 .. P_19: ');
  for var i := 0 to 19 do
    write(pRec(i), ' ');
  writeln;
 
  Compare(pFloor, pRec, 'floor- and recurrence-based', 64);
  writeln(#10'The first 10 L-system strings are:');
 
  for var i := 0 to 9 do
    writeln(lSystem(i));
  writeln;
 
  Compare(pFloor,
    function(n: Integer): Integer
    begin
      Result := length(lSystem(n));
    end, 'floor- and L-system-based', 32);
  readln;
end.