How to resolve the algorithm Motzkin numbers step by step in the AWK programming language

Published on 12 May 2024 09:40 PM
#Awk

How to resolve the algorithm Motzkin numbers step by step in the AWK programming language

Table of Contents

Problem Statement

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.

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Motzkin numbers step by step in the AWK programming language

Source code in the awk programming language

# syntax: GAWK --bignum -f MOTZKIN_NUMBERS.AWK
BEGIN {
    print(" n         Motzkin[n] prime")
    limit = 41
    m[0] = m[1] = 1
    for (i=2; i<=limit; i++) {
      m[i] = (m[i-1]*(2*i+1) + m[i-2]*(3*i-3)) / (i + 2)
    }
    for (i=0; i<=limit; i++) {
      printf("%2d %18d %3d\n",i,m[i],is_prime(m[i]))
    }
    exit(0)
}
function is_prime(x,  i) {
    if (x <= 1) {
      return(0)
    }
    for (i=2; i<=int(sqrt(x)); i++) {
      if (x % i == 0) {
        return(0)
      }
    }
    return(1)
}

You may also check:How to resolve the algorithm File input/output step by step in the C# programming language
You may also check:How to resolve the algorithm De Polignac numbers step by step in the Raku programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the VAX Assembly programming language
You may also check:How to resolve the algorithm Order disjoint list items step by step in the jq programming language
You may also check:How to resolve the algorithm K-d tree step by step in the Go programming language