Motzkin numbers
- 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
Factor
<lang factor>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 M[n] Prime?" print "-----------------------------------" print 42 [
dup motzkin [ commas ] keep prime? "✅" "❌" ? "%2d %24s %s\n" printf
] each-integer</lang>
- Output:
n M[n] Prime? ----------------------------------- 0 1 ❌ 1 1 ❌ 2 2 ✅ 3 4 ❌ 4 9 ❌ 5 21 ❌ 6 51 ❌ 7 127 ✅ 8 323 ❌ 9 835 ❌ 10 2,188 ❌ 11 5,798 ❌ 12 15,511 ✅ 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 ✅ 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 ❌
Julia
<lang julia>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
</lang>
- 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
Perl
<lang perl>#!/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' : ;
}</lang>
- 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
Raku
<lang perl6>use Lingua::EN::Numbers;
constant \C = 1, |[\×] (2, 6 … ∞) Z/ 2 .. *;
sub binomial { [×] ($^n … 0) 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 };</lang>
- 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
Wren
<lang ecmascript>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)
}</lang>
- 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