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