Padovan sequence
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.
Padovan Fibonacci Comment
============================== ============================== ==================================
Richard Padovan Leonardo of Pisa: Fibonacci Named after.
P(0)=P(1)=P(2)=1 F(0)=F(1)=1 Recurrence initial values.
P(n)=P(n-2)+P(n-3) F(n)=F(n-1)+F(n-2) Recurrence relation.
1,1,1,2,2,3,4,5,7,9 0,1,1,2,3,5,8,13,21,34 First 10 terms.
Plastic ratio, p Golden ratio, g Ratio of successive terms...
1.324717957244746025960908854… 1.6180339887498948482...
((9+69**.5)/18)**(1/3) + ((9-69**.5)/18)**(1/3) Exact formula of ratio p.
(1+5**0.5)/2 Exact formula of ratio g.
p: x**3-x-1 g: x**2-x-1 Ratio is real root of polynomial.
Equilateral triangles Squares Spirally tiling the plane using.
s= 1.0453567932525329623 a=5**0.5 Constants for ...
P(n)=floor(p**(n-1) / s + .5) F(n)=floor(g**n / a + .5) ... Computing by truncation.
A,B,C A,B L-System Variables.
A A L-System Start/Axiom.
A->B,B->C,C->AB A->B,B->A L-System Rules.
- 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.
Factor
<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.
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
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 /* " " " " " " */ sqrt69= sqrt(69); PR= cbrt((9+sqrt69)/18) + cbrt((9-sqrt69)/18) /*plastic ratio.*/
s= 1.0453567932525329623 /* "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)) /*──────────────────────────────────────────────────────────────────────────────────────*/ cbrt: procedure; parse arg x; x= abs(x); if x=0 | x=1 then return x; rm= 2
g= .5*x; old= .; do until g=old; old=g; g= (2*g**3 + x)/3/g**2
end /*until*/; return g/1
/*──────────────────────────────────────────────────────────────────────────────────────*/ 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=; $=
do j=1 for Ln; 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
/*──────────────────────────────────────────────────────────────────────────────────────*/ sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); numeric digits; h=d+6
numeric form; m.=9; parse value format(x,2,1,,0) 'E0' with g "E" _ .; g=g*.5'e'_ %2
do j=0 while h>9; m.j= h; h= h % 2 + 1; end /*j*/
do k=j+5 to 0 by -1; numeric digits m.k; g= (g+x/g) * .5; end /*k*/; return g</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: B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB BCCABCABABBC all 32 terms match for Padovan terms and lengths of L_sys terms.