Padovan sequence: Difference between revisions
m (→{{header|Haskell}}: preferred concatMap to =<< (fewer brackets needed)) |
|||
Line 635: | Line 635: | ||
rule 'B' = "C" |
rule 'B' = "C" |
||
rule 'C' = "AB" |
rule 'C' = "AB" |
||
f :: String -> Maybe (String, String) |
|||
f = Just . ((,) <*> concatMap rule) |
f = Just . ((,) <*> concatMap rule) |
||
Line 661: | Line 660: | ||
32 |
32 |
||
) |
) |
||
prefixesMatch :: Eq a => [a] -> [a] -> Int -> Bool |
prefixesMatch :: Eq a => [a] -> [a] -> Int -> Bool |
||
prefixesMatch xs ys n = and (zipWith (==) (take n xs) ys)</lang> |
prefixesMatch xs ys n = and (zipWith (==) (take n xs) ys)</lang> |
Revision as of 18:41, 27 February 2021
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
- The Plastic Ratio - Numberphile video.
ALGOL 68
<lang algol68>BEGIN # show members of the Padovan Sequence calculated in various ways #
# returns the first 0..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 0..n elements of the Padovan sequence by # # computing by truncation P(n)=floor(p^(n-1) / s + .5) # # where s = 1.0453567932525329623 and p = x^3-x-1 # 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 0..n L System stringss 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 # # first 20 terms # print( ( "First 20 terms of the Padovan Sequence", newline ) ); []INT iterative = PADOVANI 20; []INT calculated = PADOVANC 20; BOOL same := TRUE; FOR i FROM LWB iterative TO UPB iterative DO print( ( " ", whole( iterative[ i ], 0 ) ) ); IF iterative[ i ] /= calculated[ i ] THEN same := FALSE; print( ( " *or*", whole( calculated[ i ], 0 ) ) ) FI OD; print( ( newline ) ); IF same THEN print( ( "Iterative and calculated values are the same", newline ) ) FI; # print the first 10 values of the L System strings # []STRING l system = PADOVANL 10; print( ( newline, "First 10 L System strings", newline ) ); FOR i FROM LWB l system TO UPB l system DO print( ( " ", l system[ i ] ) ) OD; same := TRUE; print( ( newline, "First 10 L System string lengths", newline ) ); FOR i FROM LWB l system TO UPB l system DO INT length = ( UPB l system[ i ] - LWB l system[ i ] ) + 1; print( ( " ", whole( length, 0 ) ) ); IF iterative[ i ] /= length THEN same := FALSE; print( ( " *shoould be*", whole( iterative[ i ], 0 ) ) ) FI OD; print( ( newline ) ); IF same THEN print( ( "Iterative values and L System lengths are the same", newline ) ) FI
END</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 Iterative and calculated values are the same First 10 L System strings A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB First 10 L System string lengths 1 1 1 2 2 3 4 5 7 9 Iterative values and L System lengths are the same
C
<lang C>#include <stdio.h>
- include <stdlib.h>
- include <math.h>
- include <string.h>
/* Generate (and memoize) the Padovan sequence using
* the recurrence relationship */
int pRec(int n) {
static int *memo = NULL; static size_t curSize = 0; /* grow memoization array when necessary and fill with zeroes */ if (curSize <= (size_t) n) { size_t lastSize = curSize; while (curSize <= (size_t) n) curSize += 1024 * sizeof(int); memo = realloc(memo, curSize * sizeof(int)); memset(memo + lastSize, 0, (curSize - lastSize) * sizeof(int)); } /* if we don't have the value for N yet, calculate it */ if (memo[n] == 0) { if (n<=2) memo[n] = 1; else memo[n] = pRec(n-2) + pRec(n-3); } return memo[n];
}
/* Calculate the Nth value of the Padovan sequence
* using the floor function */
int pFloor(int n) {
long double p = 1.324717957244746025960908854; long double s = 1.0453567932525329623; return powl(p, n-1)/s + 0.5;
}
/* Given the previous value for the L-system, generate the
* next value */
void nextLSystem(const char *prev, char *buf) {
while (*prev) { switch (*prev++) { case 'A': *buf++ = 'B'; break; case 'B': *buf++ = 'C'; break; case 'C': *buf++ = 'A'; *buf++ = 'B'; break; } } *buf = '\0';
}
int main() {
// 8192 is enough up to P_33. #define BUFSZ 8192 char buf1[BUFSZ], buf2[BUFSZ]; int i; /* Print P_0..P_19 */ printf("P_0 .. P_19: "); for (i=0; i<20; i++) printf("%d ", pRec(i)); printf("\n"); /* Check that functions match up to P_63 */ printf("The floor- and recurrence-based functions "); for (i=0; i<64; i++) { if (pRec(i) != pFloor(i)) { printf("do not match at %d: %d != %d.\n", i, pRec(i), pFloor(i)); break; } } if (i == 64) { printf("match from P_0 to P_63.\n"); } /* Show first 10 L-system strings */ printf("\nThe first 10 L-system strings are:\n"); for (strcpy(buf1, "A"), i=0; i<10; i++) { printf("%s\n", buf1); strcpy(buf2, buf1); nextLSystem(buf2, buf1); } /* Check lengths of strings against pFloor up to P_31 */ printf("\nThe floor- and L-system-based functions "); for (strcpy(buf1, "A"), i=0; i<32; i++) { if ((int)strlen(buf1) != pFloor(i)) { printf("do not match at %d: %d != %d\n", i, (int)strlen(buf1), pFloor(i)); break; } strcpy(buf2, buf1); nextLSystem(buf2, buf1); } if (i == 32) { printf("match from P_0 to P_31.\n"); } return 0;
}</lang>
- Output:
P_0 .. P_19: 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 The floor- and recurrence-based functions match from P_0 to P_63. The first 10 L-system strings are: A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB The floor- and L-system-based functions match from P_0 to P_31.
C++
<lang cpp>#include <iostream>
- include <map>
- include <cmath>
// Generate the Padovan sequence using the recurrence // relationship. int pRec(int n) {
static std::map<int,int> memo; auto it = memo.find(n); if (it != memo.end()) return it->second;
if (n <= 2) memo[n] = 1; else memo[n] = pRec(n-2) + pRec(n-3); return memo[n];
}
// Calculate the N'th Padovan sequence using the // floor function. int pFloor(int n) {
long const double p = 1.324717957244746025960908854; long const double s = 1.0453567932525329623; return std::pow(p, n-1)/s + 0.5;
}
// Return the N'th L-system string std::string& lSystem(int n) {
static std::map<int,std::string> memo; auto it = memo.find(n); if (it != memo.end()) return it->second; if (n == 0) memo[n] = "A"; else { memo[n] = ""; for (char ch : memo[n-1]) { switch(ch) { case 'A': memo[n].push_back('B'); break; case 'B': memo[n].push_back('C'); break; case 'C': memo[n].append("AB"); break; } } } return memo[n];
}
// Compare two functions up to p_N using pFn = int(*)(int); void compare(pFn f1, pFn f2, const char* descr, int stop) {
std::cout << "The " << descr << " functions "; int i; for (i=0; i<stop; i++) { int n1 = f1(i); int n2 = f2(i); if (n1 != n2) { std::cout << "do not match at " << i << ": " << n1 << " != " << n2 << ".\n"; break; } } if (i == stop) { std::cout << "match from P_0 to P_" << stop << ".\n"; }
}
int main() {
/* Print P_0 to P_19 */ std::cout << "P_0 .. P_19: "; for (int i=0; i<20; i++) std::cout << pRec(i) << " "; std::cout << "\n"; /* Check that floor and recurrence match up to P_64 */ compare(pFloor, pRec, "floor- and recurrence-based", 64); /* Show first 10 L-system strings */ std::cout << "\nThe first 10 L-system strings are:\n"; for (int i=0; i<10; i++) std::cout << lSystem(i) << "\n"; std::cout << "\n"; /* Check lengths of strings against pFloor up to P_31 */ compare(pFloor, [](int n){return (int)lSystem(n).length();}, "floor- and L-system-based", 32); return 0;
}</lang>
- Output:
P_0 .. P_19: 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 The floor- and recurrence-based functions match from P_0 to P_64. The first 10 L-system strings are: A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB The floor- and L-system-based functions match from P_0 to P_32.
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.
Go
<lang go>package main
import (
"fmt" "math" "math/big" "strings"
)
func padovanRecur(n int) []int {
p := make([]int, n) p[0], p[1], p[2] = 1, 1, 1 for i := 3; i < n; i++ { p[i] = p[i-2] + p[i-3] } return p
}
func padovanFloor(n int) []int {
var p, s, t, u = new(big.Rat), new(big.Rat), new(big.Rat), new(big.Rat) p, _ = p.SetString("1.324717957244746025960908854") s, _ = s.SetString("1.0453567932525329623") f := make([]int, n) pow := new(big.Rat).SetInt64(1) u = u.SetFrac64(1, 2) t.Quo(pow, p) t.Quo(t, s) t.Add(t, u) v, _ := t.Float64() f[0] = int(math.Floor(v)) for i := 1; i < n; i++ { t.Quo(pow, s) t.Add(t, u) v, _ = t.Float64() f[i] = int(math.Floor(v)) pow.Mul(pow, p) } return f
}
type LSystem struct {
rules map[string]string init, current string
}
func step(lsys *LSystem) string {
var sb strings.Builder if lsys.current == "" { lsys.current = lsys.init } else { for _, c := range lsys.current { sb.WriteString(lsys.rules[string(c)]) } lsys.current = sb.String() } return lsys.current
}
func padovanLSys(n int) []string {
rules := map[string]string{"A": "B", "B": "C", "C": "AB"} lsys := &LSystem{rules, "A", ""} p := make([]string, n) for i := 0; i < n; i++ { p[i] = step(lsys) } return p
}
// assumes lists are same length func areSame(l1, l2 []int) bool {
for i := 0; i < len(l1); i++ { if l1[i] != l2[i] { return false } } return true
}
func main() {
fmt.Println("First 20 members of the Padovan sequence:") fmt.Println(padovanRecur(20)) recur := padovanRecur(64) floor := padovanFloor(64) same := areSame(recur, floor) s := "give" if !same { s = "do not give" } fmt.Println("\nThe recurrence and floor based functions", s, "the same results for 64 terms.")
p := padovanLSys(32) lsyst := make([]int, 32) for i := 0; i < 32; i++ { lsyst[i] = len(p[i]) } fmt.Println("\nFirst 10 members of the Padovan L-System:") fmt.Println(p[:10]) fmt.Println("\nand their lengths:") fmt.Println(lsyst[:10])
same = areSame(recur[:32], lsyst) s = "give" if !same { s = "do not give" } fmt.Println("\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.
Haskell
<lang haskell>-- list of Padovan numbers using recurrence pRec = map (\(a,_,_) -> a) $ iterate (\(a,b,c) -> (b,c,a+b)) (1,1,1)
-- list of Padovan numbers generated from floor function pFloor = map f [0..]
where f n = floor $ p**fromInteger (pred n) / s + 0.5 p = 1.324717957244746025960908854 s = 1.0453567932525329623
-- list of L-system strings lSystem = iterate f "A"
where f [] = [] f ('A':s) = 'B':f s f ('B':s) = 'C':f s f ('C':s) = 'A':'B':f s
-- check if first N elements match checkN n as bs = take n as == take n bs
main = do
putStr "P_0 .. P_19: " putStrLn $ unwords $ map show $ take 20 $ pRec putStr "The floor- and recurrence-based functions " putStr $ if checkN 64 pRec pFloor then "match" else "do not match" putStr " from P_0 to P_63.\n\n" putStr "The first 10 L-system strings are:\n" putStrLn $ unwords $ take 10 $ lSystem putStr "\nThe floor- and L-system-based functions " putStr $ if checkN 32 pFloor (map length lSystem) then "match" else "do not match" putStr " from P_0 to P_31.\n"</lang>
- Output:
P_0 .. P_19: 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 The floor- and recurrence-based functions match from P_0 to P_63. The first 10 L-system strings are: A B C AB BC CAB ABBC BCCAB CABABBC ABBCBCCAB The floor- and L-system-based functions match from P_0 to P_31.
and a variant expressed in terms of unfoldr:
<lang haskell>import Data.List (unfoldr)
PADOVAN NUMBERS --------------------
padovans :: [Integer] padovans = unfoldr f (1, 1, 1)
where f (a, b, c) = Just (a, (b, c, a + b))
padovanFloor :: [Integer] padovanFloor = unfoldr f 0
where p = 1.324717957244746025960908854 s = 1.0453567932525329623 f = Just . ( ( (,) . floor . (0.5 +) . (/ s) . (p **) . fromInteger . pred ) <*> succ )
padovanLSystem :: [String] padovanLSystem = unfoldr f "A"
where rule 'A' = "B" rule 'B' = "C" rule 'C' = "AB" f = Just . ((,) <*> concatMap rule)
TESTS -------------------------
main :: IO () main =
putStrLn "First 20 padovans:\n" >> print (take 20 padovans) >> putStrLn ( "\nThe recurrence and floor based functions" <> " match over 64 terms:\n" ) >> print (prefixesMatch padovans padovanFloor 64) >> putStrLn "\nFirst 10 L System strings:\n" >> print (take 10 padovanLSystem) >> putStrLn ( "\nThe length of the first 32 strings produced" <> " is the Padovan sequence:\n" ) >> print ( prefixesMatch padovans (fromIntegral . length <$> padovanLSystem) 32 )
prefixesMatch :: Eq a => [a] -> [a] -> Int -> Bool prefixesMatch xs ys n = and (zipWith (==) (take n xs) ys)</lang>
- Output:
First 20 padovans: [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 match over 64 terms: True First 10 L System strings: ["A","B","C","AB","BC","CAB","ABBC","BCCAB","CABABBC","ABBCBCCAB"] The length of the first 32 strings produced is the Padovan sequence: True
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
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.