Padovan sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Wren}}: Minor simplification.)
(Added Go)
Line 122: Line 122:


The L-system, recurrence and floor based algorithms match to n=31.
The L-system, recurrence and floor based algorithms match to n=31.
</pre>

=={{header|Go}}==
{{trans|Wren}}
<lang go>import "/big" for BigRat
import "/dynamic" for Struct

var padovanRecur = Fn.new { |n|
var p = List.filled(n, 1)
if (n < 3) return p
for (i in 3...n) p[i] = p[i-2] + p[i-3]
return p
}

var padovanFloor = Fn.new { |n|
var p = BigRat.fromDecimal("1.324717957244746025960908854")
var s = BigRat.fromDecimal("1.0453567932525329623")
var f = List.filled(n, 0)
var pow = BigRat.one
f[0] = (pow/p/s + 0.5).floor.toInt
for (i in 1...n) {
f[i] = (pow/s + 0.5).floor.toInt
pow = pow * p
}
return f
}

var LSystem = Struct.create("LSystem", ["rules", "init", "current"])

var step = Fn.new { |lsys|
var s = ""
if (lsys.current == "") {
lsys.current = lsys.init
} else {
for (c in lsys.current) s = s + lsys.rules[c]
lsys.current = s
}
return lsys.current
}

var padovanLSys = Fn.new { |n|
var rules = {"A": "B", "B": "C", "C": "AB"}
var lsys = LSystem.new(rules, "A", "")
var p = List.filled(n, null)
for (i in 0...n) p[i] = step.call(lsys)
return p
}

System.print("First 20 members of the Padovan sequence:")
System.print(padovanRecur.call(20))

var recur = padovanRecur.call(64)
var floor = padovanFloor.call(64)
var areSame = (0...64).all { |i| recur[i] == floor[i] }
var s = areSame ? "give" : "do not give"
System.print("\nThe recurrence and floor based functions %(s) the same results for 64 terms.")

var p = padovanLSys.call(32)
var lsyst = p.map { |e| e.count }.toList
System.print("\nFirst 10 members of the Padovan L-System:")
System.print(p.take(10).toList)
System.print("\nand their lengths:")
System.print(lsyst.take(10).toList)

recur = recur.take(32).toList
areSame = (0...32).all { |i| recur[i] == lsyst[i] }
s = areSame ? "give" : "do not give"
System.print("\nThe recurrence and L-system based functions %(s) the same results for 32 terms.")</lang>

{{out}}
<pre>
First 20 members of the Padovan sequence:
[1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151]

The recurrence and floor based functions give the same results for 64 terms.

First 10 members of the Padovan L-System:
[A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB]

and their lengths:
[1 1 1 2 2 3 4 5 7 9]

The recurrence and L-system based functions give the same results for 32 terms.
</pre>
</pre>


Revision as of 12:12, 27 February 2021

Task
Padovan sequence
You are encouraged to solve this task according to the task description, using any language you may know.


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)=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) (115**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->A
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

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: L-system accessors io kernel make math math.functions memoize prettyprint qw sequences ;

CONSTANT: p 1.324717957244746025960908854 CONSTANT: s 1.0453567932525329623

pfloor ( m -- n ) 1 - p swap ^ s /f .5 + >integer ;

MEMO: precur ( m -- n ) 

   dup 3 < [ drop 1 ]
   [ [ 2 - precur ] [ 3 - precur ] bi + ] if ;
plsys, ( L-system -- )
   [ iterate-L-system-string ] [ string>> , ] bi ;
plsys ( n -- seq )
   <L-system>
   "A" >>axiom
   { qw{ A B } qw{ B C } qw{ C AB } } >>rules
   swap 1 - '[ "A" , _ [ dup plsys, ] times ] { } make nip ;

"First 20 terms of the Padovan sequence:" print 20 [ pfloor pprint bl ] each-integer nl nl

64 [ [ pfloor ] [ precur ] bi assert= ] each-integer "Recurrence and floor based algorithms match to n=63." print nl

"First 10 L-system strings:" print 10 plsys . nl

32 <iota> [ pfloor ] map 32 plsys [ length ] map assert= "The L-system, recurrence and floor based algorithms match to n=31." print</lang>

Output:
First 20 terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 

Recurrence and floor based algorithms match to n=63.

First 10 L-system strings:
{
    "A"
    "B"
    "C"
    "AB"
    "BC"
    "CAB"
    "ABBC"
    "BCCAB"
    "CABABBC"
    "ABBCBCCAB"
}

The L-system, recurrence and floor based algorithms match to n=31.

Go

Translation of: Wren

<lang go>import "/big" for BigRat import "/dynamic" for Struct

var padovanRecur = Fn.new { |n| 

   var p = List.filled(n, 1)
   if (n < 3) return p
   for (i in 3...n) p[i] = p[i-2] + p[i-3]
   return p

}

var padovanFloor = Fn.new { |n| 

   var p = BigRat.fromDecimal("1.324717957244746025960908854")
   var s = BigRat.fromDecimal("1.0453567932525329623")
   var f = List.filled(n, 0)
   var pow = BigRat.one
   f[0] = (pow/p/s + 0.5).floor.toInt
   for (i in 1...n) {
       f[i] = (pow/s + 0.5).floor.toInt
       pow = pow * p
   }
   return f

}

var LSystem = Struct.create("LSystem", ["rules", "init", "current"])

var step = Fn.new { |lsys| 

   var s = ""
   if (lsys.current == "") {
       lsys.current = lsys.init
   } else {
       for (c in lsys.current) s = s + lsys.rules[c]
       lsys.current = s
   }
   return lsys.current

}

var padovanLSys = Fn.new { |n| 

   var rules = {"A": "B", "B": "C", "C": "AB"}
   var lsys = LSystem.new(rules, "A", "")
   var p = List.filled(n, null)
   for (i in 0...n) p[i] = step.call(lsys)
   return p

}

System.print("First 20 members of the Padovan sequence:") System.print(padovanRecur.call(20))

var recur = padovanRecur.call(64) var floor = padovanFloor.call(64) var areSame = (0...64).all { |i| recur[i] == floor[i] } var s = areSame ? "give" : "do not give" System.print("\nThe recurrence and floor based functions %(s) the same results for 64 terms.")

var p = padovanLSys.call(32) var lsyst = p.map { |e| e.count }.toList System.print("\nFirst 10 members of the Padovan L-System:") System.print(p.take(10).toList) System.print("\nand their lengths:") System.print(lsyst.take(10).toList)

recur = recur.take(32).toList areSame = (0...32).all { |i| recur[i] == lsyst[i] } s = areSame ? "give" : "do not give" System.print("\nThe recurrence and L-system based functions %(s) the same results for 32 terms.")</lang>

Output:
First 20 members of the Padovan sequence:
[1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151]

The recurrence and floor based functions give the same results for 64 terms.

First 10 members of the Padovan L-System:
[A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB]

and their lengths:
[1 1 1 2 2 3 4 5 7 9]

The recurrence and L-system based functions give the same results for 32 terms.

Julia

<lang julia>""" recursive Padowan """ rPadovan(n) = (n < 4) ? one(n) : rPadovan(n - 3) + rPadovan(n - 2)

""" floor based rounding calculation Padowan """ function fPadovan(n)::Int 

   p, s = big"1.324717957244746025960908854", big"1.0453567932525329623"
   return Int(floor(p^(n-2) / s + .5))

end

mutable struct LSystemPadowan 

   rules::Dict{String, String}
   init::String
   current::String
   LSystemPadowan() = new(Dict("A" => "B", "B" => "C", "C" => "AB"), "A", "")

end

""" LSystem Padowan """ function step(lsys::LSystemPadowan) 

   s = ""
   if isempty(lsys.current)
       lsys.current = lsys.init
   else
       for c in lsys.current
           s *= lsys.rules[string(c)]
       end
       lsys.current = s
   end
   return lsys.current

end

function list_LsysPadowan(N) 

   lsys = LSystemPadowan()
   seq = Int[]
   for i in 1:N
       step(lsys)
       push!(seq, length(lsys.current))
   end
   return seq

end

list_rPadowan(N) = [rPadovan(i) for i in 1:N]

list_fPadowan(N) = [fPadovan(i) for i in 1:N]

const lr, lf = list_rPadowan(64), list_fPadowan(64) const lL = list_LsysPadowan(32)

println("N Recursive Floor LSystem\n=====================================") foreach(i -> println(rpad(i, 4), rpad(lr[i], 12), rpad(lf[i], 12), lL[i]), 1:32)

if all(i -> lr[i] == lf[i], 1:64) 

   println("\nThe recursive and floor methods match to an N of 64")

end

if all(i -> lr[i] == lf[i] == lL[i], 1:32) 

   println("\nThe recursive, floor, and LSys methods match to an N of 32\n")

end

println("N LSystem string\n===========================") const lsys = LSystemPadowan() for i in 1:10 

   step(lsys)
   println(rpad(i, 10), lsys.current)

end

</lang>

Output:
N  Recursive  Floor      LSystem     
=====================================
1   1           1           1
2   1           1           1
3   1           1           1
4   2           2           2
5   2           2           2
6   3           3           3
7   4           4           4
8   5           5           5
9   7           7           7
10  9           9           9
11  12          12          12
12  16          16          16
13  21          21          21
14  28          28          28
15  37          37          37
16  49          49          49
17  65          65          65
18  86          86          86
19  114         114         114
20  151         151         151
21  200         200         200
22  265         265         265
23  351         351         351
24  465         465         465
25  616         616         616
26  816         816         816
27  1081        1081        1081
28  1432        1432        1432
29  1897        1897        1897
30  2513        2513        2513
31  3329        3329        3329
32  4410        4410        4410

The recursive and floor methods match to an N of 64

The recursive, floor, and LSys methods match to an N of 32

N    LSystem string
===========================
1         A
2         B
3         C
4         AB
5         BC
6         CAB
7         ABBC
8         BCCAB
9         CABABBC
10        ABBCBCCAB

Phix

<lang Phix>sequence padovan = {1,1,1} function padovanr(integer n) 

   while length(padovan)<n do
       padovan &= padovan[$-2]+padovan[$-1]
   end while
   return padovan[n]

end function

constant p = 1.324717957244746025960908854, 

        s = 1.0453567932525329623

function padovana(integer n) 

   return floor(power(p,n-2)/s + 0.5)

end function

constant l = {"B","C","AB"} function padovanl(string prev) 

   string res = ""
   for i=1 to length(prev) do
       res &= l[prev[i]-64]
   end for
   return res

end function

sequence pl = "A", l10 = {} for n=1 to 64 do 

   integer pn = padovanr(n)
   if padovana(n)!=pn or length(pl)!=pn then crash("oops") end if
   if n<=10 then l10 = append(l10,pl) end if
   pl = padovanl(pl)

end for printf(1,"The first 20 terms of the Padovan sequence: %v\n\n",{padovan[1..20]}) printf(1,"The first 10 L-system strings: %v\n\n",{l10}) printf(1,"recursive, algorithmic, and l-system agree to n=64\n")</lang>

Output:
The first 20 terms of the Padovan sequence: {1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151}

The first 10 L-system strings: {"A","B","C","AB","BC","CAB","ABBC","BCCAB","CABABBC","ABBCBCCAB"}

recursive, algorithmic, and l-system agree to n=64

Python

<lang python>from math import floor from collections import deque from typing import Dict, Generator


def padovan_r() -> Generator[int, None, None]: 

   last = deque([1, 1, 1], 4)
   while True:
       last.append(last[-2] + last[-3])
       yield last.popleft()

_p, _s = 1.324717957244746025960908854, 1.0453567932525329623

def padovan_f(n: int) -> int: 

   return floor(_p**(n-1) / _s + .5)

def padovan_l(start: str='A', 

            rules: Dict[str, str]=dict(A='B', B='C', C='AB')
            ) -> Generator[str, None, None]:
   axiom = start
   while True:
       yield axiom
       axiom = .join(rules[ch] for ch in axiom)


if __name__ == "__main__": 

   from itertools import islice

   print("The first twenty terms of the sequence.")
   print(str([padovan_f(n) for n in range(20)])[1:-1])

   r_generator = padovan_r()
   if all(next(r_generator) == padovan_f(n) for n in range(64)):
       print("\nThe recurrence and floor based algorithms match to n=63 .")
   else:
       print("\nThe recurrence and floor based algorithms DIFFER!")

   print("\nThe first 10 L-system string-lengths and strings")
   l_generator = padovan_l(start='A', rules=dict(A='B', B='C', C='AB'))
   print('\n'.join(f"  {len(string):3} {repr(string)}"
                   for string in islice(l_generator, 10)))

   r_generator = padovan_r()
   l_generator = padovan_l(start='A', rules=dict(A='B', B='C', C='AB'))
   if all(len(next(l_generator)) == padovan_f(n) == next(r_generator)
          for n in range(32)):
       print("\nThe L-system, recurrence and floor based algorithms match to n=31 .")
   else:
       print("\nThe L-system, recurrence and floor based algorithms DIFFER!")</lang>
Output:
The first twenty terms of the sequence.
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151

The recurrence and floor based algorithms match to n=63 .

The first 10 L-system string-lengths and strings
    1 'A'
    1 'B'
    1 'C'
    2 'AB'
    2 'BC'
    3 'CAB'
    4 'ABBC'
    5 'BCCAB'
    7 'CABABBC'
    9 'ABBCBCCAB'

The L-system, recurrence and floor based algorithms match to n=31 .

Raku

<lang perl6>constant p = 1.32471795724474602596; constant s = 1.0453567932525329623; constant %rules = A => 'B', B => 'C', C => 'AB';

my @pad-recur = 1, 1, 1, -> $c, $b, $ { $b + $c } … *;

my @pad-floor = { floor 1/2 + p ** ($++ - 1) / s } … *;

my @pad-L-sys = 'A', { %rules{$^axiom.comb}.join } … *; my @pad-L-len = @pad-L-sys.map: *.chars;

say @pad-recur.head(20); say @pad-L-sys.head(10);

say "Recurrence == Floor to N=64" if (@pad-recur Z== @pad-floor).head(64).all; say "Recurrence == L-len to N=32" if (@pad-recur Z== @pad-L-len).head(32).all;</lang>

Output:
(1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151)
(A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB)
Recurrence == Floor to N=64
Recurrence == L-len to N=32

REXX

<lang rexx>/*REXX pgm computes the Padovan seq. (using 2 methods), and also computes the L─strings.*/ numeric digits 40 /*better precision for Plastic ratio. */ parse arg n nF Ln cL . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 20 /*Not specified? Then use the default.*/ if nF== | nF=="," then nF= 64 /* " " " " " " */ if Ln== | Ln=="," then Ln= 10 /* " " " " " " */ if cL== | cL=="," then cL= 32 /* " " " " " " */ PR= 1.324717957244746025960908854 /*the plastic ratio (constant). */ 

s= 1.0453567932525329623                        /*tge  "s"  constant.                  */
   @.= .;      @.0= 1;      @.1= 1;      @.2= 1 /*initialize 3 terms of the Padovan seq*/
   !.= .;      !.0= 1;      !.1= 1;      !.2= 1 /*     "     "   "    "  "     "     " */

call req1; call req2; call req3; call req4 /*invoke the four task's requirements. */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ floor: procedure; parse arg x; t= trunc(x); return t - (x<0) * (x\=t) pF: procedure expose !. PR s; parse arg x;  !.x= floor(PR**(x-1)/s + .5); return !.x th: parse arg th; return th||word('th st nd rd',1+(th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ L_sys: procedure: arg x; q=; a.A= 'B'; a.B= 'C'; a.C= 'AB'; if x== then return 'A' 

                               do k=1  for length(x);  _= substr(x, k, 1);  q= q  ||  a._
                               end   /*k*/;                           return q

/*──────────────────────────────────────────────────────────────────────────────────────*/ p: procedure expose @.; parse arg x; if @.x\==. then return @.x /*@.X defined?*/ 

      xm2= x - 2;    xm3= x - 3;    @.x= @.xm2 + @.xm3;   return @.x

/*──────────────────────────────────────────────────────────────────────────────────────*/ req1: say 'The first ' n " terms of the Pandovan sequence:"; 

      $= @.0;  do j=1  for n-1;   $= $  p(j)
               end   /*j*/
      say $;                                                          return

/*──────────────────────────────────────────────────────────────────────────────────────*/ req2: ok= 1; what= ' terms match for recurrence and floor─based functions.' 

               do j=0  for nF;  if p(j)==pF(j)  then iterate
               say 'the '   th(j)   " terms don't match:"   p(j)  pF(j);   ok= 0
               end   /*j*/
      say
      if ok  then say 'all '    nF    what;                           return

/*──────────────────────────────────────────────────────────────────────────────────────*/ req3: y=; $= 'A' 

               do j=1  for Ln-1;   y= L_sys(y);    $= $  L_sys(y)
               end   /*j*/
      say
      say 'L_sys:'  $;                                                return

/*──────────────────────────────────────────────────────────────────────────────────────*/ req4: y=; what=' terms match for Padovan terms and lengths of L_sys terms.' 

      ok= 1;   do j=1  for cL;  y= L_sys(y);   L= length(y)
      if       L==p(j-1)  then iterate
               say 'the '    th(j)    " Padovan term doesn't match the length of the",
                                      'L_sys term:'   p(j-1)  L;           ok= 0
               end   /*j*/
      say
      if ok  then say 'all '    cL    what;                           return</lang>
output   when using the default inputs:
The first  20  terms of the Padovan sequence:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151

all  64  terms match for  recurrence  and  floor─based  functions.

L_sys:  A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB 

all  32  terms match for Padovan terms and lengths of L_sys terms.

Wren

Library: Wren-big
Library: Wren-dynamic

L-System stuff is based on the Julia implementation. <lang ecmascript>import "/big" for BigRat import "/dynamic" for Struct

var padovanRecur = Fn.new { |n| 

   var p = List.filled(n, 1)
   if (n < 3) return p
   for (i in 3...n) p[i] = p[i-2] + p[i-3]
   return p

}

var padovanFloor = Fn.new { |n| 

   var p = BigRat.fromDecimal("1.324717957244746025960908854")
   var s = BigRat.fromDecimal("1.0453567932525329623")
   var f = List.filled(n, 0)
   var pow = BigRat.one
   f[0] = (pow/p/s + 0.5).floor.toInt
   for (i in 1...n) {
       f[i] = (pow/s + 0.5).floor.toInt
       pow = pow * p
   }
   return f

}

var LSystem = Struct.create("LSystem", ["rules", "init", "current"])

var step = Fn.new { |lsys| 

   var s = ""
   if (lsys.current == "") {
       lsys.current = lsys.init
   } else {
       for (c in lsys.current) s = s + lsys.rules[c]
       lsys.current = s
   }
   return lsys.current

}

var padovanLSys = Fn.new { |n| 

   var rules = {"A": "B", "B": "C", "C": "AB"}
   var lsys = LSystem.new(rules, "A", "")
   var p = List.filled(n, null)
   for (i in 0...n) p[i] = step.call(lsys)
   return p

}

System.print("First 20 members of the Padovan sequence:") System.print(padovanRecur.call(20))

var recur = padovanRecur.call(64) var floor = padovanFloor.call(64) var areSame = (0...64).all { |i| recur[i] == floor[i] } var s = areSame ? "give" : "do not give" System.print("\nThe recurrence and floor based functions %(s) the same results for 64 terms.")

var p = padovanLSys.call(32) var lsyst = p.map { |e| e.count }.toList System.print("\nFirst 10 members of the Padovan L-System:") System.print(p.take(10).toList) System.print("\nand their lengths:") System.print(lsyst.take(10).toList)

recur = recur.take(32).toList areSame = (0...32).all { |i| recur[i] == lsyst[i] } s = areSame ? "give" : "do not give" System.print("\nThe recurrence and L-system based functions %(s) the same results for 32 terms.")</lang>

Output:
First 20 members of the Padovan sequence:
[1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151]

The recurrence and floor based functions give the same results for 64 terms.

First 10 members of the Padovan L-System:
[A, B, C, AB, BC, CAB, ABBC, BCCAB, CABABBC, ABBCBCCAB]

and their lengths:
[1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

The recurrence and L-system based functions give the same results for 32 terms.
Retrieved from "https://rosettacode.org/wiki/Padovan_sequence?oldid=308781"