I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Motzkin numbers

From Rosetta Code
Task
Motzkin numbers
You are encouraged to solve this task according to the task description, using any language you may know.
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



ALGOL 68[edit]

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32
Translation of: Wren

Uses ALGOL 68G's LONG LONG INT which allows for programmer specifiable precision integers. The default precision is sufficient for this task.

BEGIN # find some Motzkin numbers #
PR read "primes.incl.a68" PR
# returns a table of the Motzkin numbers 0 .. n #
OP MOTZKIN = ( INT n )[]LONG LONG INT:
BEGIN
[ 0 : n ]LONG LONG INT m;
IF n >= 0 THEN
m[ 0 ] := 1;
IF n >= 1 THEN
m[ 1 ] := 1;
FOR i FROM 2 TO UPB m DO
m[ i ] := ( ( m[ i - 1 ] * ( ( 2 * i ) + 1 ) )
+ ( m[ i - 2 ] * ( ( 3 * i ) - 3 ) )
)
OVER ( i + 2 )
OD
FI
FI;
m
END # MOTZKIN # ;
# returns a string representation of n with commas #
PROC commatise = ( LONG LONG INT n )STRING:
BEGIN
STRING result := "";
STRING unformatted = whole( n, 0 );
INT ch count := 0;
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
IF ch count <= 2 THEN ch count +:= 1
ELSE ch count := 1; "," +=: result
FI;
unformatted[ c ] +=: result
OD;
result
END; # commatise #
# left-pads a string to at least n characters #
PROC pad left = ( STRING s, INT n )STRING:
BEGIN
STRING result := s;
WHILE ( UPB result - LWB result ) + 1 < n DO " " +=: result OD;
result
END; # pad left #
 
# show the Motzkin numbers #
print( ( " n M[n] Prime?", newline ) );
print( ( "-----------------------------------", newline ) );
[]LONG LONG INT m = MOTZKIN 41;
FOR i FROM LWB m TO UPB m DO
print( ( whole( i, -2 )
, pad left( commatise( m[ i ] ), 26 )
, IF is probably prime( m[ i ] ) THEN " prime" ELSE "" FI
, newline
)
)
OD
END
Output:
 n                      M[n] Prime?
-----------------------------------
 0                         1
 1                         1
 2                         2  prime
 3                         4
 4                         9
 5                        21
 6                        51
 7                       127  prime
 8                       323
 9                       835
10                     2,188
11                     5,798
12                    15,511  prime
13                    41,835
14                   113,634
15                   310,572
16                   853,467
17                 2,356,779
18                 6,536,382
19                18,199,284
20                50,852,019
21               142,547,559
22               400,763,223
23             1,129,760,415
24             3,192,727,797
25             9,043,402,501
26            25,669,818,476
27            73,007,772,802
28           208,023,278,209
29           593,742,784,829
30         1,697,385,471,211
31         4,859,761,676,391
32        13,933,569,346,707
33        40,002,464,776,083
34       114,988,706,524,270
35       330,931,069,469,828
36       953,467,954,114,363  prime
37     2,750,016,719,520,991
38     7,939,655,757,745,265
39    22,944,749,046,030,949
40    66,368,199,913,921,497
41   192,137,918,101,841,817

C#[edit]

Arbitrary precision.

using System;
using BI = System.Numerics.BigInteger;
 
class Program {
 
// has multiple factors (other than 1 and x)
static bool hmf(BI x) {
if (x < 2) return true;
if ((x & 1) == 0) return x > 2;
if ( x % 3 == 0) return x > 3;
int l = (int)Math.Sqrt((double)x);
for (int j = 5, d = 4; j <= l; j += d = 6 - d)
if (x % j == 0) return x > j;
return false;
}
 
static void Main(string[] args) {
BI a = 0, b = 1, t;
int n = 1, s = 0, d = 1, c = 0, f = 1;
while (n <= 60)
Console.WriteLine ("{0,34:n0} {1}",
t = b / n++,
hmf(t) ? "" : "is prime.",
t = b,
b = ((c += d * 3 + 3) * a +
(f += d * 2 + 3) * b) /
(s += d += 2),
a = t);
}
}
Output:
                                 1 
                                 1 
                                 2 is prime.
                                 4 
                                 9 
                                21 
                                51 
                               127 is prime.
                               323 
                               835 
                             2,188 
                             5,798 
                            15,511 is prime.
                            41,835 
                           113,634 
                           310,572 
                           853,467 
                         2,356,779 
                         6,536,382 
                        18,199,284 
                        50,852,019 
                       142,547,559 
                       400,763,223 
                     1,129,760,415 
                     3,192,727,797 
                     9,043,402,501 
                    25,669,818,476 
                    73,007,772,802 
                   208,023,278,209 
                   593,742,784,829 
                 1,697,385,471,211 
                 4,859,761,676,391 
                13,933,569,346,707 
                40,002,464,776,083 
               114,988,706,524,270 
               330,931,069,469,828 
               953,467,954,114,363 is prime.
             2,750,016,719,520,991 
             7,939,655,757,745,265 
            22,944,749,046,030,949 
            66,368,199,913,921,497 
           192,137,918,101,841,817 
           556,704,809,728,838,604 
         1,614,282,136,160,911,722 
         4,684,478,925,507,420,069 
        13,603,677,110,519,480,289 
        39,532,221,379,621,112,004 
       114,956,499,435,014,161,638 
       334,496,473,194,459,009,429 
       973,899,740,488,107,474,693 
     2,837,208,756,709,314,025,578 
     8,270,140,811,590,103,129,028 
    24,119,587,499,879,368,045,581 
    70,380,687,801,729,972,163,737 
   205,473,381,836,953,330,090,977 
   600,161,698,382,141,668,958,313 
 1,753,816,895,177,229,449,263,803 
 5,127,391,665,653,918,424,581,931 
14,996,791,899,280,244,858,336,604 
43,881,711,243,248,048,262,611,670 

F#[edit]

 
// Motzkin numbers. Nigel Galloway: September 10th., 2021
let M=let rec fN g=seq{yield List.item 1 g; yield! fN(0L::(g|>List.windowed 3|>List.map(List.sum))@[0L;0L])} in fN [0L;1L;0L;0L]
M|>Seq.take 42|>Seq.iter(printfn "%d")
 
Output:
1
1
2
4
9
21
51
127
323
835
2188
5798
15511
41835
113634
310572
853467
2356779
6536382
18199284
50852019
142547559
400763223
1129760415
3192727797
9043402501
25669818476
73007772802
208023278209
593742784829
1697385471211
4859761676391
13933569346707
40002464776083
114988706524270
330931069469828
953467954114363
2750016719520991
7939655757745265
22944749046030949
66368199913921497
192137918101841817

Factor[edit]

Works with: Factor version 0.99 2021-06-02
USING: combinators formatting io kernel math math.primes
tools.memory.private ;
 
MEMO: motzkin ( m -- n )
dup 2 < [
drop 1
] [
{
[ 2 * 1 + ]
[ 1 - motzkin * ]
[ 3 * 3 - ]
[ 2 - motzkin * + ]
[ 2 + /i ]
} cleave
] if ;
 
" n motzkin(n)\n" print
42 [
dup motzkin [ commas ] keep prime? "prime" "" ?
"%2d %24s  %s\n" printf
] each-integer
Output:
 n        motzkin(n)

 0                        1  
 1                        1  
 2                        2  prime
 3                        4  
 4                        9  
 5                       21  
 6                       51  
 7                      127  prime
 8                      323  
 9                      835  
10                    2,188  
11                    5,798  
12                   15,511  prime
13                   41,835  
14                  113,634  
15                  310,572  
16                  853,467  
17                2,356,779  
18                6,536,382  
19               18,199,284  
20               50,852,019  
21              142,547,559  
22              400,763,223  
23            1,129,760,415  
24            3,192,727,797  
25            9,043,402,501  
26           25,669,818,476  
27           73,007,772,802  
28          208,023,278,209  
29          593,742,784,829  
30        1,697,385,471,211  
31        4,859,761,676,391  
32       13,933,569,346,707  
33       40,002,464,776,083  
34      114,988,706,524,270  
35      330,931,069,469,828  
36      953,467,954,114,363  prime
37    2,750,016,719,520,991  
38    7,939,655,757,745,265  
39   22,944,749,046,030,949  
40   66,368,199,913,921,497  
41  192,137,918,101,841,817  

Go[edit]

Translation of: Wren
Library: Go-rcu

Assumes a 64 bit Go compiler.

package main
 
import (
"fmt"
"rcu"
)
 
func motzkin(n int) []int {
m := make([]int, n+1)
m[0] = 1
m[1] = 1
for i := 2; i <= n; i++ {
m[i] = (m[i-1]*(2*i+1) + m[i-2]*(3*i-3)) / (i + 2)
}
return m
}
 
func main() {
fmt.Println(" n M[n] Prime?")
fmt.Println("-----------------------------------")
m := motzkin(41)
for i, e := range m {
fmt.Printf("%2d  %23s  %t\n", i, rcu.Commatize(e), rcu.IsPrime(e))
}
}
Output:
 n          M[n]             Prime?
-----------------------------------
 0                        1  false
 1                        1  false
 2                        2  true
 3                        4  false
 4                        9  false
 5                       21  false
 6                       51  false
 7                      127  true
 8                      323  false
 9                      835  false
10                    2,188  false
11                    5,798  false
12                   15,511  true
13                   41,835  false
14                  113,634  false
15                  310,572  false
16                  853,467  false
17                2,356,779  false
18                6,536,382  false
19               18,199,284  false
20               50,852,019  false
21              142,547,559  false
22              400,763,223  false
23            1,129,760,415  false
24            3,192,727,797  false
25            9,043,402,501  false
26           25,669,818,476  false
27           73,007,772,802  false
28          208,023,278,209  false
29          593,742,784,829  false
30        1,697,385,471,211  false
31        4,859,761,676,391  false
32       13,933,569,346,707  false
33       40,002,464,776,083  false
34      114,988,706,524,270  false
35      330,931,069,469,828  false
36      953,467,954,114,363  true
37    2,750,016,719,520,991  false
38    7,939,655,757,745,265  false
39   22,944,749,046,030,949  false
40   66,368,199,913,921,497  false
41  192,137,918,101,841,817  false

jq[edit]

Translation of: Julia

Works with gojq, the Go implementation of jq (*)

(*) The C implementation of jq only produces accurate results up to and including n == 37.

For a suitable implementation of `is_prime`, see e.g. # Erdős-primes#jq.

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
 
def motzkin:
. as $n
| reduce range(2; $n+1) as $i (
{m: [1,1]};
.m[$i] = (.m[$i-1] * (2*$i + 1) + .m[$i-2] * (3*$i -3))/($i + 2))
| .m ;
 
 
" n M[n] Prime?",
"------------------------------",
 
(41 | motzkin
| range(0;length) as $i
|"\($i|lpad(2)) \(.[$i]|lpad(20)) \(.[$i]|if is_prime then "prime" else "" end)")
Output:
 n          M[n]        Prime?
------------------------------
 0                    1 
 1                    1 
 2                    2 prime
 3                    4 
 4                    9 
 5                   21 
 6                   51 
 7                  127 prime
 8                  323 
 9                  835 
10                 2188 
11                 5798 
12                15511 prime
13                41835 
14               113634 
15               310572 
16               853467 
17              2356779 
18              6536382 
19             18199284 
20             50852019 
21            142547559 
22            400763223 
23           1129760415 
24           3192727797 
25           9043402501 
26          25669818476 
27          73007772802 
28         208023278209 
29         593742784829 
30        1697385471211 
31        4859761676391 
32       13933569346707 
33       40002464776083 
34      114988706524270 
35      330931069469828 
36      953467954114363 prime
37     2750016719520991 
38     7939655757745265 
39    22944749046030949 
40    66368199913921497 
41   192137918101841817 


Julia[edit]

Translation of: Wren
using Primes
 
function motzkin(N)
m = zeros(Int, N)
m[1] = m[2] = 1
for i in 3:N
m[i] = (m[i - 1] * (2i - 1) + m[i - 2] * (3i - 6)) ÷ (i + 1)
end
return m
end
 
println(" n M[n] Prime?\n-----------------------------------")
for (i, m) in enumerate(motzkin(42))
println(lpad(i - 1, 2), lpad(m, 20), lpad(isprime(m), 8))
end
 
Output:
 n               M[n]     Prime?
-----------------------------------
 0                   1   false
 1                   1   false
 2                   2    true
 3                   4   false
 4                   9   false
 5                  21   false
 6                  51   false
 7                 127    true
 8                 323   false
 9                 835   false
10                2188   false
11                5798   false
12               15511    true
13               41835   false
14              113634   false
15              310572   false
16              853467   false
17             2356779   false
18             6536382   false
19            18199284   false
20            50852019   false
21           142547559   false
22           400763223   false
23          1129760415   false
24          3192727797   false
25          9043402501   false
26         25669818476   false
27         73007772802   false
28        208023278209   false
29        593742784829   false
30       1697385471211   false
31       4859761676391   false
32      13933569346707   false
33      40002464776083   false
34     114988706524270   false
35     330931069469828   false
36     953467954114363    true
37    2750016719520991   false
38    7939655757745265   false
39   22944749046030949   false
40   66368199913921497   false
41  192137918101841817   false

Mathematica/Wolfram Language[edit]

Table[With[{o = Hypergeometric2F1[(1 - n)/2, -n/2, 2, 4]}, {n, o, PrimeQ[o]}], {n, 0, 41}] // Grid
Output:

Alignment lost in copying.

0	1	False
1	1	False
2	2	True
3	4	False
4	9	False
5	21	False
6	51	False
7	127	True
8	323	False
9	835	False
10	2188	False
11	5798	False
12	15511	True
13	41835	False
14	113634	False
15	310572	False
16	853467	False
17	2356779	False
18	6536382	False
19	18199284	False
20	50852019	False
21	142547559	False
22	400763223	False
23	1129760415	False
24	3192727797	False
25	9043402501	False
26	25669818476	False
27	73007772802	False
28	208023278209	False
29	593742784829	False
30	1697385471211	False
31	4859761676391	False
32	13933569346707	False
33	40002464776083	False
34	114988706524270	False
35	330931069469828	False
36	953467954114363	True
37	2750016719520991	False
38	7939655757745265	False
39	22944749046030949	False
40	66368199913921497	False
41	192137918101841817	False

Nim[edit]

Translation of: Wren
import strformat, strutils
 
func isPrime(n: Positive): bool =
if n == 1: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var d = 5
while d * d <= n:
if n mod d == 0: return false
inc d, 2
if n mod d == 0: return false
inc d, 4
result = true
 
func motzkin(n: Positive): seq[int64] =
result.setLen(n + 1)
result[0] = 1
result[1] = 1
for i in 2..n:
result[i] = (result[i-1] * (2 * i + 1) + result[i-2] * (3 * i - 3)) div (i + 2)
 
echo " n M[n] Prime?"
echo "-----------------------------------"
var m = motzkin(41)
for i, val in m:
echo &"{i:2} {insertSep($val):>23} {val.isPrime}"
Output:
 n          M[n]             Prime?
-----------------------------------
 0                        1  false
 1                        1  false
 2                        2  true
 3                        4  false
 4                        9  false
 5                       21  false
 6                       51  false
 7                      127  true
 8                      323  false
 9                      835  false
10                    2_188  false
11                    5_798  false
12                   15_511  true
13                   41_835  false
14                  113_634  false
15                  310_572  false
16                  853_467  false
17                2_356_779  false
18                6_536_382  false
19               18_199_284  false
20               50_852_019  false
21              142_547_559  false
22              400_763_223  false
23            1_129_760_415  false
24            3_192_727_797  false
25            9_043_402_501  false
26           25_669_818_476  false
27           73_007_772_802  false
28          208_023_278_209  false
29          593_742_784_829  false
30        1_697_385_471_211  false
31        4_859_761_676_391  false
32       13_933_569_346_707  false
33       40_002_464_776_083  false
34      114_988_706_524_270  false
35      330_931_069_469_828  false
36      953_467_954_114_363  true
37    2_750_016_719_520_991  false
38    7_939_655_757_745_265  false
39   22_944_749_046_030_949  false
40   66_368_199_913_921_497  false
41  192_137_918_101_841_817  false

Perl[edit]

#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Motzkin_numbers
use warnings;
use ntheory qw( is_prime );
 
sub motzkin
{
my $N = shift;
my @m = ( 0, 1, 1 );
for my $i ( 3 .. $N )
{
$m[$i] = ($m[$i - 1] * (2 * $i - 1) + $m[$i - 2] * (3 * $i - 6)) / ($i + 1);
}
return splice @m, 1;
}
 
print " n M[n]\n";
my $count = 0;
for ( motzkin(42) )
{
printf "%3d%25s  %s\n", $count++, s/\B(?=(\d\d\d)+$)/,/gr,
is_prime($_) ? 'prime' : '';
}
Output:
  n          M[n]
  0                        1  
  1                        1  
  2                        2  prime
  3                        4  
  4                        9  
  5                       21  
  6                       51  
  7                      127  prime
  8                      323  
  9                      835  
 10                    2,188  
 11                    5,798  
 12                   15,511  prime
 13                   41,835  
 14                  113,634  
 15                  310,572  
 16                  853,467  
 17                2,356,779  
 18                6,536,382  
 19               18,199,284  
 20               50,852,019  
 21              142,547,559  
 22              400,763,223  
 23            1,129,760,415  
 24            3,192,727,797  
 25            9,043,402,501  
 26           25,669,818,476  
 27           73,007,772,802  
 28          208,023,278,209  
 29          593,742,784,829  
 30        1,697,385,471,211  
 31        4,859,761,676,391  
 32       13,933,569,346,707  
 33       40,002,464,776,083  
 34      114,988,706,524,270  
 35      330,931,069,469,828  
 36      953,467,954,114,363  prime
 37    2,750,016,719,520,991  
 38    7,939,655,757,745,265  
 39   22,944,749,046,030,949  
 40   66,368,199,913,921,497  
 41  192,137,918,101,841,817  

Phix[edit]

with javascript_semantics
include mpfr.e
function motzkin(integer n)
    sequence m = mpz_inits(2,1) -- {1,1}
    mpz m2 = mpz_init()         -- (scratch)
    for i=3 to n do
        mpz m1 = mpz_init()     -- (a new mpz rqd for every m[i])
        mpz_mul_si(m1,m[i-1],2*i-1)     -- (nb i is 1-based)
        mpz_mul_si(m2,m[i-2],3*i-6)     --        ""
        mpz_add(m1,m1,m2)
        assert(mpz_fdiv_q_ui(m1,m1,i+1)==0) -- (verify rmdr==0)
        m &= m1
    end for
    return m
end function
 
printf(1," n                     M[n]\n")
printf(1,"---------------------------\n")
sequence m = motzkin(42)
for i=1 to 42 do
    string mi = mpz_get_str(m[i],comma_fill:=true),
           pi = iff(mpz_prime(m[i])?"prime":"")
    printf(1,"%2d  %23s  %s\n", {i-1, mi, pi})
end for
Output:
 n                     M[n]
---------------------------
 0                        1
 1                        1
 2                        2  prime
 3                        4
 4                        9
 5                       21
 6                       51
 7                      127  prime
 8                      323
 9                      835
10                    2,188
11                    5,798
12                   15,511  prime
13                   41,835
14                  113,634
15                  310,572
16                  853,467
17                2,356,779
18                6,536,382
19               18,199,284
20               50,852,019
21              142,547,559
22              400,763,223
23            1,129,760,415
24            3,192,727,797
25            9,043,402,501
26           25,669,818,476
27           73,007,772,802
28          208,023,278,209
29          593,742,784,829
30        1,697,385,471,211
31        4,859,761,676,391
32       13,933,569,346,707
33       40,002,464,776,083
34      114,988,706,524,270
35      330,931,069,469,828
36      953,467,954,114,363  prime
37    2,750,016,719,520,991
38    7,939,655,757,745,265
39   22,944,749,046,030,949
40   66,368,199,913,921,497
41  192,137,918,101,841,817

native[edit]

Normally I'd start with this simpler and perfectly valid 64-bit code, but at the moment am somewhat biased towards things that run online, without limiting things as this does.

with javascript_semantics
function motzkin(integer n)
    sequence m = {1,1}
    for i=3 to n do
        m &= (m[i-1]*(2*i-1)+m[i-2]*(3*i-6))/(i+1)
    end for
    return m
end function
 
printf(1," n                     M[n]\n")
printf(1,"---------------------------\n")
integer lim = iff(machine_bits()=32?38:42)
sequence m = motzkin(lim)
for i=1 to lim do
    string pi = iff(is_prime(m[i])?"prime":"")
    printf(1,"%2d  %,23d  %s\n", {i-1, m[i], pi})
end for

Aside: Note that, under 32-bit and p2js, M[36] and M[37] happen only by chance to be correct: an intermediate value exceeds precision (in this case for M[36] it is a multiple of 2 and hence ok, for M[37] it is rounded to the nearest multiple of 4, and the final divide by (i+1) results in an integer simply because there isn't enough precision to hold any fractional part). Output as above on 64-bit, less four entries under 32-bit and pwa/p2js, since unlike M[36..37], M[38..41] don't quite get away with the precision loss, plus M[39] and above exceed precision and hence is_prime() limits on 32-bit anyway.

Raku[edit]

Using binomial coefficients and Catalan numbers[edit]

use Lingua::EN::Numbers;
 
constant \C = 1, |[] (2, 6 … ∞) Z/ 2 .. *;
 
sub binomial { [×] ($^n0) Z/ 1 .. $^p }
 
my \𝐌 = 1, |(1..).map: -> \𝐧 { sum ^𝐧 .map( -> \𝐤 { C[𝐤] × binomial 𝐧, 2×𝐤 } ) };
 
say " 𝐧 𝐌[𝐧] Prime?";
𝐌[^42].kv.map: { printf "%2d %24s  %s\n", $^k, $^v.&comma, $v.is-prime };
Output:
 𝐧          𝐌[𝐧]            Prime?
 0                        1  False
 1                        1  False
 2                        2  True
 3                        4  False
 4                        9  False
 5                       21  False
 6                       51  False
 7                      127  True
 8                      323  False
 9                      835  False
10                    2,188  False
11                    5,798  False
12                   15,511  True
13                   41,835  False
14                  113,634  False
15                  310,572  False
16                  853,467  False
17                2,356,779  False
18                6,536,382  False
19               18,199,284  False
20               50,852,019  False
21              142,547,559  False
22              400,763,223  False
23            1,129,760,415  False
24            3,192,727,797  False
25            9,043,402,501  False
26           25,669,818,476  False
27           73,007,772,802  False
28          208,023,278,209  False
29          593,742,784,829  False
30        1,697,385,471,211  False
31        4,859,761,676,391  False
32       13,933,569,346,707  False
33       40,002,464,776,083  False
34      114,988,706,524,270  False
35      330,931,069,469,828  False
36      953,467,954,114,363  True
37    2,750,016,719,520,991  False
38    7,939,655,757,745,265  False
39   22,944,749,046,030,949  False
40   66,368,199,913,921,497  False
41  192,137,918,101,841,817  False

Using recurrence relationship[edit]

use Lingua::EN::Numbers;
 
my \𝐌 = 1, 1, { state $i = 2; ++$i; ($^b × (2 × $i - 1) + $^a × (3 × $i - 6)) ÷ ($i + 1) }*;
 
say " 𝐧 𝐌[𝐧] Prime?";
𝐌[^42].kv.map: { printf "%2d %24s  %s\n", $^k, $^v.&comma, $v.is-prime };

Same output

REXX[edit]

/*REXX program to display the first  N  Motzkin numbers,  and if that number is prime.  */
numeric digits 92 /*max number of decimal digits for task*/
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 42 /*Not specified? Then use the default.*/
w= length(n) + 1; wm= digits()%4 /*define maximum widths for two columns*/
say center('n', w ) center("Motzkin[n]", wm) center(' primality', 11)
say center('' , w, "─") center('' , wm, "─") center('', 11, "─")
@.= 1 /*define default vale for the @. array.*/
do m=0 for n /*step through indices for Motzkin #'s.*/
if m>1 then @.m= (@(m-1)*(m+m+1) + @(m-2)*(m*3-3))%(m+2) /*calculate a Motzkin #*/
call show /*display a Motzkin number ──► terminal*/
end /*m*/
 
say center('' , w, "─") center('' , wm, "─") center('', 11, "─")
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
@: parse arg i; return @.i /*return function expression based on I*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
prime: if isPrime(@.m) then return " prime"; return ''
show: y= commas(@.m); say right(m, w) right(y, max(wm, length(y))) prime(); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPrime: procedure expose p?. p#. p_.; parse arg x /*persistent P·· REXX variables.*/
if symbol('P?.#')\=='VAR' then /*1st time here? Then define primes. */
do /*L is a list of some low primes < 100.*/
L= 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
p?.=0 /* [↓] define P_index, P, P squared.*/
do i=1 for words(L); _= word(L,i); p?._= 1; p#.i= _; p_.i= _*_
end /*i*/; p?.0= x2d(3632c8eb5af3b) /*bypass big ÷*/
p?.n= _ + 4 /*define next prime after last prime. */
p?.#= i - 1 /*define the number of primes found. */
end /* p?. p#. p_ must be unique. */
if x<p?.n then return p?.x /*special case, handle some low primes.*/
if x==p?.0 then return 1 /*save a number of primality divisions.*/
parse var x '' -1 _ /*obtain right─most decimal digit of X.*/
if _==5 then return 0; if x//2 ==0 then return 0 /*X ÷ by 5? X ÷ by 2?*/
if x//3==0 then return 0; if x//7 ==0 then return 0 /*" " " 3? " " " 7?*/
/*weed numbers that're ≥ 11 multiples. */
do j=5 to p?.# while p_.j<=x; if x//p#.j ==0 then return 0
end /*j*/
/*weed numbers that're>high multiple Ps*/
do k=p?.n by 6 while k*k<=x; if x//k ==0 then return 0
if x//(k+2)==0 then return 0
end /*k*/; return 1 /*Passed all divisions? It's a prime.*/
output   when using the default input:
 n        Motzkin[n]         primality
─── ─────────────────────── ───────────
  0                       1
  1                       1
  2                       2    prime
  3                       4
  4                       9
  5                      21
  6                      51
  7                     127    prime
  8                     323
  9                     835
 10                   2,188
 11                   5,798
 12                  15,511    prime
 13                  41,835
 14                 113,634
 15                 310,572
 16                 853,467
 17               2,356,779
 18               6,536,382
 19              18,199,284
 20              50,852,019
 21             142,547,559
 22             400,763,223
 23           1,129,760,415
 24           3,192,727,797
 25           9,043,402,501
 26          25,669,818,476
 27          73,007,772,802
 28         208,023,278,209
 29         593,742,784,829
 30       1,697,385,471,211
 31       4,859,761,676,391
 32      13,933,569,346,707
 33      40,002,464,776,083
 34     114,988,706,524,270
 35     330,931,069,469,828
 36     953,467,954,114,363    prime
 37   2,750,016,719,520,991
 38   7,939,655,757,745,265
 39  22,944,749,046,030,949
 40  66,368,199,913,921,497
 41 192,137,918,101,841,817
─── ─────────────────────── ───────────

Ruby[edit]

require "prime"
 
motzkin = Enumerator.new do |y|
m = [1,1]
m.each{|m| y << m }
 
2.step do |i|
m << (m.last*(2*i+1) + m[-2]*(3*i-3)) / (i+2)
m.unshift # an arr with last 2 elements is sufficient
y << m.last
end
end
 
motzkin.take(42).each_with_index do |m, i|
puts "#{'%2d' % i}: #{m}#{m.prime? ? ' prime' : ''}"
end
 
Output:
 0: 1
 1: 1
 2: 2 prime
 3: 4
 4: 9
 5: 21
 6: 51
 7: 127 prime
 8: 323
 9: 835
10: 2188
11: 5798
12: 15511 prime
13: 41835
14: 113634
15: 310572
16: 853467
17: 2356779
18: 6536382
19: 18199284
20: 50852019
21: 142547559
22: 400763223
23: 1129760415
24: 3192727797
25: 9043402501
26: 25669818476
27: 73007772802
28: 208023278209
29: 593742784829
30: 1697385471211
31: 4859761676391
32: 13933569346707
33: 40002464776083
34: 114988706524270
35: 330931069469828
36: 953467954114363 prime
37: 2750016719520991
38: 7939655757745265
39: 22944749046030949
40: 66368199913921497
41: 192137918101841817

Rust[edit]

Translation of: Wren
// [dependencies]
// primal = "0.3"
// num-format = "0.4"
 
fn motzkin(n: usize) -> Vec<usize> {
let mut m = vec![0; n];
m[0] = 1;
m[1] = 1;
for i in 2..n {
m[i] = (m[i - 1] * (2 * i + 1) + m[i - 2] * (3 * i - 3)) / (i + 2);
}
m
}
 
fn main() {
use num_format::{Locale, ToFormattedString};
let count = 42;
let m = motzkin(count);
println!(" n M(n) Prime?");
println!("-----------------------------------");
for i in 0..count {
println!(
"{:2} {:>23} {}",
i,
m[i].to_formatted_string(&Locale::en),
primal::is_prime(m[i] as u64)
);
}
}
Output:
 n          M(n)             Prime?
-----------------------------------
 0                        1  false
 1                        1  false
 2                        2  true
 3                        4  false
 4                        9  false
 5                       21  false
 6                       51  false
 7                      127  true
 8                      323  false
 9                      835  false
10                    2,188  false
11                    5,798  false
12                   15,511  true
13                   41,835  false
14                  113,634  false
15                  310,572  false
16                  853,467  false
17                2,356,779  false
18                6,536,382  false
19               18,199,284  false
20               50,852,019  false
21              142,547,559  false
22              400,763,223  false
23            1,129,760,415  false
24            3,192,727,797  false
25            9,043,402,501  false
26           25,669,818,476  false
27           73,007,772,802  false
28          208,023,278,209  false
29          593,742,784,829  false
30        1,697,385,471,211  false
31        4,859,761,676,391  false
32       13,933,569,346,707  false
33       40,002,464,776,083  false
34      114,988,706,524,270  false
35      330,931,069,469,828  false
36      953,467,954,114,363  true
37    2,750,016,719,520,991  false
38    7,939,655,757,745,265  false
39   22,944,749,046,030,949  false
40   66,368,199,913,921,497  false
41  192,137,918,101,841,817  false

Sidef[edit]

Built-in:

say 50.of { .motzkin }

Motzkin's triangle (the Motzkin numbers are on the hypotenuse of the triangle):

func motzkin_triangle(num, callback) {
var row = []
{ |n|
row = [0, 1, {|i| row[i+2] + row[i] + row[i+1] }.map(0 .. n-3)..., 0]
callback(row.grep{ .> 0 })
} << 2..(num+1)
}
 
motzkin_triangle(10, {|row|
row.map { "%4s" % _ }.join(' ').say
})
Output:
   1
   1    1
   1    2    2
   1    3    5    4
   1    4    9   12    9
   1    5   14   25   30   21
   1    6   20   44   69   76   51
   1    7   27   70  133  189  196  127
   1    8   35  104  230  392  518  512  323
   1    9   44  147  369  726 1140 1422 1353  835

Task:

func motzkin_numbers(N) {
 
var (a, b, n) = (0, 1, 1)
 
N.of {
var M = b//n #/
n += 1
(a, b) = (b, (3*(n-1)*n*a + (2*n - 1)*n*b) // ((n+1)*(n-1))) #/
M
}
}
 
motzkin_numbers(42).each_kv {|k,v|
say "#{'%2d' % k}: #{v}#{v.is_prime ? ' prime' : ''}"
}
Output:
 0: 1
 1: 1
 2: 2 prime
 3: 4
 4: 9
 5: 21
 6: 51
 7: 127 prime
 8: 323
 9: 835
10: 2188
11: 5798
12: 15511 prime
13: 41835
14: 113634
15: 310572
16: 853467
17: 2356779
18: 6536382
19: 18199284
20: 50852019
21: 142547559
22: 400763223
23: 1129760415
24: 3192727797
25: 9043402501
26: 25669818476
27: 73007772802
28: 208023278209
29: 593742784829
30: 1697385471211
31: 4859761676391
32: 13933569346707
33: 40002464776083
34: 114988706524270
35: 330931069469828
36: 953467954114363 prime
37: 2750016719520991
38: 7939655757745265
39: 22944749046030949
40: 66368199913921497
41: 192137918101841817

Wren[edit]

Library: Wren-long
Library: Wren-fmt
import "/long" for ULong
import "/fmt" for Fmt
 
var motzkin = Fn.new { |n|
var m = List.filled(n+1, 0)
m[0] = ULong.one
m[1] = ULong.one
for (i in 2..n) {
m[i] = (m[i-1] * (2*i + 1) + m[i-2] * (3*i -3))/(i + 2)
}
return m
}
 
System.print(" n M[n] Prime?")
System.print("-----------------------------------")
var m = motzkin.call(41)
for (i in 0..41) {
Fmt.print("$2d $,23i $s", i, m[i], m[i].isPrime)
}
Output:
 n          M[n]             Prime?
-----------------------------------
 0                        1  false
 1                        1  false
 2                        2  true
 3                        4  false
 4                        9  false
 5                       21  false
 6                       51  false
 7                      127  true
 8                      323  false
 9                      835  false
10                    2,188  false
11                    5,798  false
12                   15,511  true
13                   41,835  false
14                  113,634  false
15                  310,572  false
16                  853,467  false
17                2,356,779  false
18                6,536,382  false
19               18,199,284  false
20               50,852,019  false
21              142,547,559  false
22              400,763,223  false
23            1,129,760,415  false
24            3,192,727,797  false
25            9,043,402,501  false
26           25,669,818,476  false
27           73,007,772,802  false
28          208,023,278,209  false
29          593,742,784,829  false
30        1,697,385,471,211  false
31        4,859,761,676,391  false
32       13,933,569,346,707  false
33       40,002,464,776,083  false
34      114,988,706,524,270  false
35      330,931,069,469,828  false
36      953,467,954,114,363  true
37    2,750,016,719,520,991  false
38    7,939,655,757,745,265  false
39   22,944,749,046,030,949  false
40   66,368,199,913,921,497  false
41  192,137,918,101,841,817  false