

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.


(() => {
    "use strict";
 
    // ----------------- PADOVAN NUMBERS -----------------
 
    // padovans :: [Int]
    const padovans = () => {
        // Non-finite series of Padovan numbers,
        // defined in terms of recurrence relations.
        const f = ([a, b, c]) => [
            a,
            [b, c, a + b]
        ];
 
        return unfoldr(f)([1, 1, 1]);
    };
 
 
    // padovanFloor :: [Int]
    const padovanFloor = () => {
        // The Padovan series, defined in terms
        // of a floor function.
        const
            // NB JavaScript loses some of this
            // precision at run-time.
            p = 1.324717957244746025960908854,
            s = 1.0453567932525329623;
 
        const f = n => [
            Math.floor(((p ** (n - 1)) / s) + 0.5),
            1 + n
        ];
 
        return unfoldr(f)(0);
    };
 
 
    // padovanLSystem : [Int]
    const padovanLSystem = () => {
        // An L-system generating terms whose lengths
        // are the values of the Padovan integer series.
        const rule = c =>
            "A" === c ? (
                "B"
            ) : "B" === c ? (
                "C"
            ) : "AB";
 
        const f = s => [
            s,
            chars(s).flatMap(rule)
            .join("")
        ];
 
        return unfoldr(f)("A");
    };
 
 
    // ---------------------- TEST -----------------------
    // main :: IO ()
    const main = () => {
        // prefixesMatch :: [a] -> [a] -> Bool
        const prefixesMatch = xs =>
            ys => n => and(
                zipWith(a => b => a === b)(
                    take(n)(xs)
                )(
                    take(n)(ys)
                )
            );
 
        return [
                "First 20 padovans:",
                take(20)(padovans()),
 
                "\nThe recurrence and floor-based functions",
                "match over the first 64 terms:\n",
                prefixesMatch(
                    padovans()
                )(
                    padovanFloor()
                )(64),
 
                "\nFirst 10 L-System strings:",
                take(10)(padovanLSystem()),
 
                "\nThe lengths of the first 32 L-System",
                "strings match the Padovan sequence:\n",
                prefixesMatch(
                    padovans()
                )(
                    fmap(length)(padovanLSystem())
                )(32)
            ]
            .map(str)
            .join("\n");
    };
 
    // --------------------- GENERIC ---------------------
 
    // and :: [Bool] -> Bool
    const and = xs =>
        // True unless any value in xs is false.
        [...xs].every(Boolean);
 
 
    // chars :: String -> [Char]
    const chars = s =>
        s.split("");
 
 
    // fmap <$> :: (a -> b) -> Gen [a] -> Gen [b]
    const fmap = f =>
        function* (gen) {
            let v = take(1)(gen);
 
            while (0 < v.length) {
                yield f(v[0]);
                v = take(1)(gen);
            }
        };
 
 
    // length :: [a] -> Int
    const length = xs =>
        // Returns Infinity over objects without finite
        // length. This enables zip and zipWith to choose
        // the shorter argument when one is non-finite,
        // like cycle, repeat etc
        "GeneratorFunction" !== xs.constructor
        .constructor.name ? (
            xs.length
        ) : Infinity;
 
 
    // take :: Int -> [a] -> [a]
    // take :: Int -> String -> String
    const take = n =>
        // The first n elements of a list,
        // string of characters, or stream.
        xs => "GeneratorFunction" !== xs
        .constructor.constructor.name ? (
            xs.slice(0, n)
        ) : [].concat(...Array.from({
            length: n
        }, () => {
            const x = xs.next();
 
            return x.done ? [] : [x.value];
        }));
 
 
    // str :: a -> String
    const str = x =>
        "string" !== typeof x ? (
            JSON.stringify(x)
        ) : x;
 
 
    // unfoldr :: (b -> Maybe (a, b)) -> b -> Gen [a]
    const unfoldr = f =>
        // A lazy (generator) list unfolded from a seed value
        // by repeated application of f to a value until no
        // residue remains. Dual to fold/reduce.
        // f returns either Null or just (value, residue).
        // For a strict output list,
        // wrap with `list` or Array.from
        x => (
            function* () {
                let valueResidue = f(x);
 
                while (null !== valueResidue) {
                    yield valueResidue[0];
                    valueResidue = f(valueResidue[1]);
                }
            }()
        );
 
 
    // zipWithList :: (a -> b -> c) -> [a] -> [b] -> [c]
    const zipWith = f =>
        // A list constructed by zipping with a
        // custom function, rather than with the
        // default tuple constructor.
        xs => ys => ((xs_, ys_) => {
            const lng = Math.min(length(xs_), length(ys_));
 
            return take(lng)(xs_).map(
                (x, i) => f(x)(ys_[i])
            );
        })([...xs], [...ys]);
 
    // MAIN ---
    return main();
})();