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, 2), lpad(m, 20), lpad(isprime(m), 8))
end
</lang>
- Output:
n M[n] Prime? ----------------------------------- 1 1 false 2 1 false 3 2 true 4 4 false 5 9 false 6 21 false 7 51 false 8 127 true 9 323 false 10 835 false 11 2188 false 12 5798 false 13 15511 true 14 41835 false 15 113634 false 16 310572 false 17 853467 false 18 2356779 false 19 6536382 false 20 18199284 false 21 50852019 false 22 142547559 false 23 400763223 false 24 1129760415 false 25 3192727797 false 26 9043402501 false 27 25669818476 false 28 73007772802 false 29 208023278209 false 30 593742784829 false 31 1697385471211 false 32 4859761676391 false 33 13933569346707 false 34 40002464776083 false 35 114988706524270 false 36 330931069469828 false 37 953467954114363 true 38 2750016719520991 false 39 7939655757745265 false 40 22944749046030949 false 41 66368199913921497 false 42 192137918101841817 false
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