Definition
The nth Motzkin number (denoted by M[n]) is the number of different ways of drawing non-intersecting chords between n points on a circle (not necessarily touching every point by a chord).

By convention M[0] = 1.



Task
Compute and show on this page the first 42 Motzkin numbers or, if your language does not support 64 bit integers, as many such numbers as you can. Indicate which of these numbers are prime.



See also
 oeis:A001006 Motzkin numbers 


#include <cstdint>
#include <iomanip>
#include <iostream>
 
bool is_prime(uint64_t n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    if (n % 3 == 0)
        return n == 3;
    for (uint64_t p = 5; p * p <= n; p += 4) {
        if (n % p == 0)
            return false;
        p += 2;
        if (n % p == 0)
            return false;
    }
    return true;
}
 
class motzkin_generator {
public:
    uint64_t next();
private:
    uint64_t n = 0;
    uint64_t m0 = 1;
    uint64_t m1 = 1;
};
 
uint64_t motzkin_generator::next() {
    uint64_t m = n > 1 ? (m1 * (2 * n + 1) + m0 * (3 * n - 3)) / (n + 2) : 1;
    ++n;
    m0 = m1;
    m1 = m;
    return m;
}
 
int main() {
    std::cout.imbue(std::locale(""));
    std::cout << " n          M(n)             Prime?\n";
    std::cout << "-----------------------------------\n";
    std::cout << std::boolalpha;
    motzkin_generator mgen;
    for (int i = 0; i < 42; ++i) {
        uint64_t n = mgen.next();
        std::cout << std::setw(2) << i << std::setw(25) << n << "  "
                  << is_prime(n) << '\n';
    }
}