Motzkin numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Catskill549 (talk | contribs) (added AWK) |
m (→{{header|Wren}}: Minor tidy) |
||
| (38 intermediate revisions by 19 users not shown) | |||
Line 20:
Uses ALGOL 68G's LONG LONG INT which allows for programmer specifiable precision integers. The default precision is sufficient for this task.
{{libheader|ALGOL 68-primes}}
<
PR read "primes.incl.a68" PR
# returns a table of the Motzkin numbers 0 .. n #
Line 56:
# left-pads a string to at least n characters #
PROC pad left = ( STRING s, INT n )STRING:
IF INT len = ( UPB s - LWB s ) + 1; len >= n THEN s ELSE ( ( n - len ) * " " ) + s FI;
# show the Motzkin numbers #
Line 74 ⟶ 70:
)
OD
END</
{{out}}
<pre>
Line 122 ⟶ 118:
41 192,137,918,101,841,817
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">motzkin: function [n][
result: array.of:n+1 0
result\[0]: 1
result\[1]: 1
loop 2..n 'i ->
result\[i]: ((result\[i-1] * (inc 2*i)) + result\[i-2] * (sub 3*i 3)) / i+2
return result
]
printLine: function [items][
pads: [4 20 7]
loop.with:'i items 'item [
prints pad to :string item pads\[i]
]
print ""
]
motzkins: motzkin 41
printLine ["n" "M[n]" "prime"]
print repeat "=" 31
loop.with:'i motzkins 'm ->
printLine @[i m prime? m]</syntaxhighlight>
{{out}}
<pre> 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</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK --bignum -f MOTZKIN_NUMBERS.AWK
BEGIN {
Line 148 ⟶ 220:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 194 ⟶ 266:
40 66368199913921497 0
41 192137918101841817 0
</pre>
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256">dim M(42)
M[0] = 1 : M[1] = 1
print rjust("1",18) : print rjust("1",18)
for n = 2 to 41
M[n] = M[n-1]
for i = 0 to n-2
M[n] += M[i]*M[n-2-i]
next i
print rjust(string(M[n]),18); chr(9);
if isPrime(M[n]) then print "is a prime" else print
next n
end
function isPrime(v)
if v <= 1 then return False
for i = 2 to int(sqr(v))
if v % i = 0 then return False
next i
return True
end function</syntaxhighlight>
=={{header|Burlesque}}==
<syntaxhighlight lang="burlesque">41rz{{2./}c!rz2?*{nr}c!\/2?/{JJ2.*J#Rnr#r\/+.nr.-}m[?*++it+.}m[Jp^#R{~]}5E!{fCL[1==}f[#r</syntaxhighlight>
{{out}}
<pre>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
{2 127 15511 953467954114363}</pre>
=={{header|C}}==
<syntaxhighlight lang="c">#include <locale.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
bool is_prime(uint64_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (uint64_t p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
int main() {
setlocale(LC_ALL, "");
printf(" n M(n) Prime?\n");
printf("-----------------------------------\n");
uint64_t m0 = 1, m1 = 1;
for (uint64_t i = 0; i < 42; ++i) {
uint64_t m =
i > 1 ? (m1 * (2 * i + 1) + m0 * (3 * i - 3)) / (i + 2) : 1;
printf("%2llu%'25llu %s\n", i, m, is_prime(m) ? "true" : "false");
m0 = m1;
m1 = m;
}
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|C#|CSharp}}==
Arbitrary precision. Now showing results up to the 80th. Note comment about square root limit, one might think the limit should be a <code>long</code> instead of an <code>int</code>, since the square root of a 35 digit number could be up to 18 digits (too big for an <code>int</code>).
<
using BI = System.Numerics.BigInteger;
class Program {
// has multiple factors (other than 1 and x)
static bool hmf(BI x) {
if (x <
if ((x & 1) == 0
int l = (int)Math.Sqrt((double)x); // this limit works because the 40th to 80th Motzkin numbers have factors of 2 or 3
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 <=
Console.WriteLine
t = b / n++,
hmf(t) ? "" : "is prime.",
Line 227 ⟶ 455:
a = t);
}
}</
{{out}}
<pre style="height:121ex;"> 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
14,996,791,899,280,244,858,336,604
43,881,711,243,248,048,262,611,670
128,453,535,912,993,825,479,057,919
376,166,554,620,363,320,971,336,899
1,101,997,131,244,113,831,001,323,618
3,229,547,920,421,385,142,120,565,580
9,468,017,265,749,942,384,739,441,267
27,766,917,351,255,946,264,000,229,811
81,459,755,507,915,876,737,297,376,646
239,056,762,740,830,735,069,669,439,852
701,774,105,036,927,170,410,592,656,651
2,060,763,101,398,061,220,299,787,957,807
6,053,261,625,552,368,838,017,538,638,577
17,785,981,695,172,350,686,294,020,499,397
52,274,487,460,035,748,810,950,928,411,209
153,681,622,703,766,437,645,990,598,724,233
451,929,928,113,276,686,826,984,901,736,388
1,329,334,277,731,700,374,912,787,442,584,082
3,911,184,337,415,864,255,099,077,969,308,357
11,510,402,374,965,653,734,436,362,305,721,089
33,882,709,435,158,403,490,429,948,661,355,518
99,762,777,233,730,236,158,474,945,885,114,348</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <cstdint>
#include <iomanip>
#include <iostream>
bool is_prime(uint64_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (uint64_t p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
class motzkin_generator {
public:
uint64_t next();
private:
uint64_t n = 0;
uint64_t m0 = 1;
uint64_t m1 = 1;
};
uint64_t motzkin_generator::next() {
uint64_t m = n > 1 ? (m1 * (2 * n + 1) + m0 * (3 * n - 3)) / (n + 2) : 1;
++n;
m0 = m1;
m1 = m;
return m;
}
int main() {
std::cout.imbue(std::locale(""));
std::cout << " n M(n) Prime?\n";
std::cout << "-----------------------------------\n";
std::cout << std::boolalpha;
motzkin_generator mgen;
for (int i = 0; i < 42; ++i) {
uint64_t n = mgen.next();
std::cout << std::setw(2) << i << std::setw(25) << n << " "
<< is_prime(n) << '\n';
}
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Dart}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="dart">import 'dart:math';
void main() {
var M = List<int>.filled(42, 1);
M[0] = 1;
M[1] = 1;
print('1');
print('1');
for (int n = 2; n < 42; ++n) {
M[n] = M[n - 1];
for (int i = 0; i <= n - 2; ++i) {
M[n] += M[i] * M[n - 2 - i];
}
if (isPrime(M[n])) {
print('${M[n]} is a prime');
} else {
print('${M[n]}');
}
}
}
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) return false;
}
return true;
}</syntaxhighlight>
{{out}}
<pre>1
1
2 is a prime
4
9
21
51
127 is a prime
323
835
2188
5798
15511 is a prime
41835
113634
310572
853467
2356779
6536382
18199284
50852019
142547559
400763223
1129760415
3192727797
9043402501
25669818476
73007772802
208023278209
593742784829
1697385471211
4859761676391
13933569346707
40002464776083
114988706524270
330931069469828
953467954114363 is a prime
2750016719520991
7939655757745265
22944749046030956
66368199913921500
192137918101841820</pre>
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang=easylang>
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
m[] = [ 1 1 ]
print 1 ; print 1
len m[] 39
arrbase m[] 0
for n = 2 to 38
m[n] = m[n - 1]
for i = 0 to n - 2
m[n] += m[i] * m[n - 2 - i]
.
if isprim m[n] = 1
print m[n] & " is a prime"
else
print m[n]
.
.
</syntaxhighlight>
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun isPrime = logic by int n
if n <= 1 do return false end
for int i = 2; i <= int!sqrt(n); ++i
if n % i == 0 do return false end
end
return true
end
fun format = text by var n, int max do return " " * (max - length(text!n)) + n end
fun motzkin = List by int n
List m = int[].with(n)
m[0] = 1
m[1] = 1
for int i = 2; i < m.length; ++i
m[i] = (m[i - 1] * (2 * i + 1) + m[i - 2] * (3 * i - 3)) / (i + 2)
end
return m
end
int n = 0
writeLine(format("n", 2) + format("motzkin(n)", 20) + format("prime", 6))
for each int m in motzkin(42)
writeLine(format(n, 2) + format(m, 20) + format(isPrime(m), 4))
++n
end
</syntaxhighlight>
{{out}}
<pre>
n motzkin(n) prime
0 1 ⊥
1 1 ⊥
2 2 ⊤
3 4 ⊥
4 9 ⊥
5 21 ⊥
6 51 ⊥
7 127 ⊤
8 323 ⊥
9 835 ⊥
10 2188 ⊥
11 5798 ⊥
12 15511 ⊤
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 ⊤
37 2750016719520991 ⊥
38 7939655757745265 ⊥
39 22944749046030949 ⊥
40 66368199913921497 ⊥
41 192137918101841817 ⊥
</pre>
=={{header|F_Sharp|F#}}==
<
// 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")
</syntaxhighlight>
{{out}}
<pre>
Line 343 ⟶ 869:
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<
tools.memory.private ;
Line 363 ⟶ 889:
dup motzkin [ commas ] keep prime? "prime" "" ?
"%2d %24s %s\n" printf
] each-integer</
{{out}}
<pre>
Line 410 ⟶ 936:
40 66,368,199,913,921,497
41 192,137,918,101,841,817
</pre>
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">
Array m[42];
m[1]:=1;
m[2]:=2;
!!(1,0); {precompute and print m[0] thru m[2]}
!!(1,0);
!!(2,1);
for n=3 to 41 do
m[n]:=(m[n-1]*(2*n+1) + m[n-2]*(3*n-3))/(n+2);
!!(m[n],Isprime(m[n]));
od;
; {built-in Isprime function returns 0 for 1, 1 for primes, and}
; {the smallest prime factor for composites, so this actually gives}
; {slightly more information than requested}
</syntaxhighlight>
{{out}}
<pre>
1 0
1 0
2 1
4 2
9 3
21 3
51 3
127 1
323 17
835 5
2188 2
5798 2
15511 1
41835 3
113634 2
310572 2
853467 3
2356779 3
6536382 2
18199284 2
50852019 3
142547559 3
400763223 3
1129760415 3
3192727797 3
9043402501 7
25669818476 2
73007772802 2
208023278209 107
593742784829 31
1697385471211 1483
4859761676391 3
13933569346707 3
40002464776083 3
114988706524270 2
330931069469828 2
953467954114363 1
2750016719520991 1601
7939655757745265 5
22944749046030949 1063
66368199913921497 3
192137918101841817 3
</pre>
=={{header|FreeBASIC}}==
Use any of the primality testing examples as an include.
<syntaxhighlight lang="freebasic">
#include "isprime.bas"
dim as ulongint M(0 to 41)
M(0) = 1 : M(1) = 1
print "1" : print "1"
for n as integer = 2 to 41
M(n) = M(n-1)
for i as uinteger = 0 to n-2
M(n) += M(i)*M(n-2-i)
next i
print M(n),
if isprime(M(n)) then print "is a prime" else print
next n
</syntaxhighlight>
{{out}}
<pre>
1
1
2 is a prime
4
9
21
51
127 is a prime
323
835
2188
5798
15511 is a prime
41835
113634
310572
853467
2356779
6536382
18199284
50852019
142547559
400763223
1129760415
3192727797
9043402501
25669818476
73007772802
208023278209
593742784829
1697385471211
4859761676391
13933569346707
40002464776083
114988706524270
330931069469828
953467954114363 is a prime
2750016719520991
7939655757745265
22944749046030949
66368199913921497
192137918101841817
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn IsPrime( n as NSUInteger ) as BOOL
BOOL isPrime = YES
NSUInteger i
if n < 2 then exit fn = NO
if n = 2 then exit fn = YES
if n mod 2 == 0 then exit fn = NO
for i = 3 to int(n^.5) step 2
if n mod i == 0 then exit fn = NO
next
end fn = isPrime
local fn IsMotzkin
NSUInteger M(42) : M(0) = 1 : M(1) = 1
NSInteger i, n
printf @" 0.%20ld\n 1.%20ld", 1, 1
for n = 2 to 41
M(n) = M(n-1)
for i = 0 to n-2
M(n) += M(i) * M(n-2-i)
next
printf @"%2ld.%20ld\b", n, M(n)
if fn IsPrime( M(n) ) then print " <-- is a prime" else print
next
end fn
fn IsMotzkin
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
0. 1
1. 1
2. 2 <-- is a prime
3. 4
4. 9
5. 21
6. 51
7. 127 <-- is a prime
8. 323
9. 835
10. 2188
11. 5798
12. 15511 <-- is a 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 <-- is a prime
37. 2750016719520991
38. 7939655757745265
39. 22944749046030949
40. 66368199913921497
41. 192137918101841817
</pre>
Line 416 ⟶ 1,149:
{{libheader|Go-rcu}}
Assumes a 64 bit Go compiler.
<
import (
Line 440 ⟶ 1,173:
fmt.Printf("%2d %23s %t\n", i, rcu.Commatize(e), rcu.IsPrime(e))
}
}</
{{out}}
Line 488 ⟶ 1,221:
40 66,368,199,913,921,497 false
41 192,137,918,101,841,817 false
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Control.Monad.Memo (Memo, memo, startEvalMemo)
import Math.NumberTheory.Primes.Testing (isPrime)
import System.Environment (getArgs)
import Text.Printf (printf)
type I = Integer
-- The n'th Motzkin number, where n is assumed to be ≥ 0. We memoize the
-- computations using MonadMemo.
motzkin :: I -> Memo I I I
motzkin 0 = return 1
motzkin 1 = return 1
motzkin n = do
m1 <- memo motzkin (n-1)
m2 <- memo motzkin (n-2)
return $ ((2*n+1)*m1 + (3*n-3)*m2) `div` (n+2)
-- The first n+1 Motzkin numbers, starting at 0.
motzkins :: I -> [I]
motzkins = startEvalMemo . mapM motzkin . enumFromTo 0
-- For i = 0 to n print i, the i'th Motzkin number, and if it's a prime number.
printMotzkins :: I -> IO ()
printMotzkins n = mapM_ prnt $ zip [0 :: I ..] (motzkins n)
where prnt (i, m) = printf "%2d %20d %s\n" i m $ prime m
prime m = if isPrime m then "prime" else ""
main :: IO ()
main = do
[n] <- map read <$> getArgs
printMotzkins n</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|J}}==
Implementation:
<syntaxhighlight lang="j">nextMotzkin=: , (({:*1+2*#) + _2&{*3*#-1:)%2+#</syntaxhighlight>
Task example:
<syntaxhighlight lang="j"> (":,.' ',.('prime'#~ 1&p:@{.)"1) ,.nextMotzkin^:40(1 1x)
1
1
2 prime
4
9
21
51
127 prime
323
835
2188
5798
15511 prime
41835
113634
310572
853467
2356779
6536382
18199284
50852019
142547559
400763223
1129760415
3192727797
9043402501
25669818476
73007772802
208023278209
593742784829
1697385471211
4859761676391
13933569346707
40002464776083
114988706524270
330931069469828
953467954114363 prime
2750016719520991
7939655757745265
22944749046030949
66368199913921497
192137918101841817</syntaxhighlight>
This might not be a particularly interesting to describe algorithm (which might be why the task description currently fails to provide any details of the algorithm). Still... it's probably worth an attempt:
This is an inductive sequence on integers with X<sub>0</sub>=1 and X<sub>1</sub>=1 and for the general case of X<sub>n</sub> where n>1, (2+n)X<sub>n</sub> = ((1+2n)X<sub>n-1</sub>+3(n-1)X<sub>n-2</sub>).
So basically we calculate (X<sub>n-1</sub>(1+2n)+3X<sub>n-2</sub>(n-1)) and divide that by 2+n and append this new value to the list. For n we use the list length. For X<sub>n-1</sub> we use the last element of the list. And, for X<sub>n-2</sub> we use the second to last element of the list. For the task we repeat this list operation 40 times, starting with the list 1 1 and check to see which elements of the resulting list are prime. Because these values get large, we need to use arbitrary precision integers for our list values.
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
public final class MotzkinNumbers {
public static void main(String[] aArgs) {
final int count = 42;
List<BigInteger> motzkins = motzkinNumbers(count);
NumberFormat ukNumberFormat = NumberFormat.getInstance(Locale.UK);
System.out.println(" n Motzkin[n]");
System.out.println("-----------------------------");
for ( int n = 0; n < count; n++ ) {
BigInteger motzkin = motzkins.get(n);
boolean prime = motzkin.isProbablePrime(PROBABILITY);
System.out.print(String.format("%2d %23s", n, ukNumberFormat.format(motzkin)));
System.out.println( prime ? " prime" : "" );
}
}
private static List<BigInteger> motzkinNumbers(int aSize) {
List<BigInteger> result = new ArrayList<BigInteger>(aSize);
result.add(BigInteger.ONE);
result.add(BigInteger.ONE);
for ( int i = 2; i < aSize; i++ ) {
BigInteger nextMotzkin = result.get(i - 1).multiply(BigInteger.valueOf(2 * i + 1))
.add(result.get(i - 2).multiply(BigInteger.valueOf(3 * i - 3)))
.divide(BigInteger.valueOf(i + 2));
result.add(nextMotzkin);
}
return result;
}
private static final int PROBABILITY = 20;
}
</syntaxhighlight>
{{ out }}
<pre>
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
</pre>
Line 498 ⟶ 1,461:
For a suitable implementation of `is_prime`, see e.g. # [[Erd%C5%91s-primes#jq]].
<
def motzkin:
Line 513 ⟶ 1,476:
(41 | motzkin
| range(0;length) as $i
|"\($i|lpad(2)) \(.[$i]|lpad(20)) \(.[$i]|if is_prime then "prime" else "" end)")</
{{out}}
<pre>
Line 561 ⟶ 1,524:
41 192137918101841817
</pre>
=={{header|Julia}}==
{{trans|Wren}}
<
function motzkin(N)
Line 580 ⟶ 1,542:
println(lpad(i - 1, 2), lpad(m, 20), lpad(isprime(m), 8))
end
</
<pre>
n M[n] Prime?
Line 629 ⟶ 1,591:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{{out}}
Alignment lost in copying.
Line 674 ⟶ 1,636:
40 66368199913921497 False
41 192137918101841817 False</pre>
=={{header|Maxima}}==
There are many formulas for these numbers
<syntaxhighlight lang="maxima">
motzkin[0]:1$
motzkin[1]:1$
motzkin[n]:=((2*n+1)*motzkin[n-1]+(3*n-3)*motzkin[n-2])/(n+2)$
/* Test cases */
makelist(motzkin[i],i,0,41);
sublist(%,primep);
</syntaxhighlight>
{{out}}
<pre>
[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]
[2,127,15511,953467954114363]
</pre>
=={{header|Nim}}==
{{trans|Wren}}
<
func isPrime(n: Positive): bool =
Line 702 ⟶ 1,683:
var m = motzkin(41)
for i, val in m:
echo &"{i:2} {insertSep($val):>23} {val.isPrime}"</
{{out}}
Line 749 ⟶ 1,730:
40 66_368_199_913_921_497 false
41 192_137_918_101_841_817 false</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="parigp">
M=vector(41)
M[1]=1
M[2]=2
for(n=3, 41, M[n]=(M[n-1]*(2*n+1) + M[n-2]*(3*n-3))/(n+2))
M=concat([1], M)
for(n=1, 42, print(M[n]," ",isprime(M[n])))
</syntaxhighlight>
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Motzkin_numbers
Line 774 ⟶ 1,765:
printf "%3d%25s %s\n", $count++, s/\B(?=(\d\d\d)+$)/,/gr,
is_prime($_) ? 'prime' : '';
}</
{{out}}
<pre>
Line 823 ⟶ 1,814:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 848 ⟶ 1,839:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d %23s %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 898 ⟶ 1,889:
===native===
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.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">motzkin</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 916 ⟶ 1,907:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d %,23d %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
Aside: <small>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.</small>
=={{header|Python}}==
{{trans|Go}}
<syntaxhighlight lang="python">""" rosettacode.org/wiki/Motzkin_numbers """
from sympy import isprime
def motzkin(num_wanted):
""" Return list of the first N Motzkin numbers """
mot = [1] * (num_wanted + 1)
for i in range(2, num_wanted + 1):
mot[i] = (mot[i-1]*(2*i+1) + mot[i-2]*(3*i-3)) // (i + 2)
return mot
def print_motzkin_table(N=41):
""" Print table of first N Motzkin numbers, and note if prime """
print(
" n M[n] Prime?\n-----------------------------------")
for i, e in enumerate(motzkin(N)):
print(f'{i : 3}{e : 24,}', isprime(e))
print_motzkin_table()
</syntaxhighlight>{{out}} Same as Go example.
=={{header|Quackery}}==
<code>isprime</code> is defined at [[Primality by trial division#Quackery]].
<syntaxhighlight lang="quackery"> ' [ 1 1 ]
41 times
[ dup -2 split nip do
i^ 2 + 2 * 1 - *
swap i^ 2 + 3 * 6 - * +
i^ 3 + / join ]
behead drop
witheach
[ i^ echo sp dup echo isprime if [ say " prime" ] cr ]</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Raku}}==
===Using binomial coefficients and Catalan numbers===
<syntaxhighlight lang="raku"
constant \C = 1, |[\×] (2, 6 … ∞) Z/ 2 .. *;
Line 931 ⟶ 2,008:
say " 𝐧 𝐌[𝐧] Prime?";
𝐌[^42].kv.map: { printf "%2d %24s %s\n", $^k, $^v.&comma, $v.is-prime };</
{{out}}
<pre> 𝐧 𝐌[𝐧] Prime?
Line 979 ⟶ 2,056:
===Using recurrence relationship===
<syntaxhighlight lang="raku"
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
=={{header|REXX}}==
<
numeric digits 92 /*max number of decimal digits for task*/
parse arg n . /*obtain optional argument from the CL.*/
Line 1,031 ⟶ 2,108:
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.*/</
{{out|output|text= when using the default input:}}
<pre>
Line 1,080 ⟶ 2,157:
─── ─────────────────────── ───────────
</pre>
=={{header|RPL}}==
It is unfortunately impossible to check M[36] primality without awaking the emulator's watchdog timer.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
{ #1 #1 } 2 ROT '''FOR''' j
DUP DUP SIZE GET j 2 * 1 + *
OVER DUP SIZE 1 - GET j 3 * 3 - * +
j 2 + /
+ '''NEXT'''
≫ 'MOTZK' STO
|
'''MOTZK''' ''( n -- { M(0)..M(n) } )''
Loop from 2 to n
( M[i-1]*(2*i+1)
+ M[i-2]*(3*i-3))
/ (i + 2)
add to list
|}
{{in}}
<pre>
41 MOTZK
</pre>
{{out}}
<pre>
1: { # 1d # 1d # 2d # 4d # 9d # 21d # 51d # 127d # 323d # 835d # 2188d # 5798d # 15511d # 41835d # 113634d # 310572d # 853467d # 2356779d # 6536382d # 18199284d # 50852019d # 142547559d # 400763223d # 1129760415d # 3192727797d # 9043402501d # 25669818476d # 73007772802d # 208023278209d # 593742784829d # 1697385471211d # 4859761676391d # 13933569346707d # 40002464776083d # 114988706524270d # 330931069469828d # 953467954114363d # 2750016719520991d # 7939655757745265d # 22944749046030949d # 66368199913921497d # 192137918101841817d }
</pre>
Since M(n) is fast to compute, we can sacrify execution time to improve code readability, such as:
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
{ #1 #1 } 2 ROT '''FOR''' j
DUP DUP SIZE GET LAST SWAP 1 - GET → m1 m2
≪ '(m1*(2*j+1)+m2*(3*j-3))/(j+2)' EVAL ≫
+ '''NEXT'''
≫ 'MOTZK' STO
|
'''MOTZK''' ''( n -- { M(0)..M(n) } )''
Loop from 2 to n
get last 2 values of M(n) from the list
get M(n)
add to list
|}
Inputs and output are the same.
=={{header|Ruby}}==
<
motzkin = Enumerator.new do |y|
Line 1,098 ⟶ 2,229:
puts "#{'%2d' % i}: #{m}#{m.prime? ? ' prime' : ''}"
end
</syntaxhighlight>
{{out}}
<pre >
Line 1,147 ⟶ 2,278:
=={{header|Rust}}==
{{trans|Wren}}
<
// primal = "0.3"
// num-format = "0.4"
Line 1,175 ⟶ 2,306:
);
}
}</
{{out}}
Line 1,227 ⟶ 2,358:
=={{header|Sidef}}==
Built-in:
<
Motzkin's triangle (the Motzkin numbers are on the hypotenuse of the triangle):
<
var row = []
{ |n|
Line 1,240 ⟶ 2,371:
motzkin_triangle(10, {|row|
row.map { "%4s" % _ }.join(' ').say
})</
{{out}}
Line 1,258 ⟶ 2,389:
Task:
<
var (a, b, n) = (0, 1, 1)
Line 1,272 ⟶ 2,403:
motzkin_numbers(42).each_kv {|k,v|
say "#{'%2d' % k}: #{v}#{v.is_prime ? ' prime' : ''}"
}</
{{out}}
Line 1,319 ⟶ 2,450:
41: 192137918101841817
</pre>
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">import Foundation
extension BinaryInteger {
@inlinable
public var isPrime: Bool {
if self == 0 || self == 1 {
return false
} else if self == 2 {
return true
}
let max = Self(ceil((Double(self).squareRoot())))
for i in stride(from: 2, through: max, by: 1) where self % i == 0 {
return false
}
return true
}
}
func motzkin(_ n: Int) -> [Int] {
var m = Array(repeating: 0, count: 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)
}
return m
}
let m = motzkin(42)
for (i, n) in m.enumerated() {
print("\(i): \(n) \(n.isPrime ? "prime" : "")")
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Wren}}==
{{libheader|Wren-long}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var motzkin = Fn.new { |n|
Line 1,341 ⟶ 2,561:
for (i in 0..41) {
Fmt.print("$2d $,23i $s", i, m[i], m[i].isPrime)
}</
{{out}}
Line 1,390 ⟶ 2,610:
41 192,137,918,101,841,817 false
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">dim M(41)
M(0) = 1 : M(1) = 1
print str$(M(0), "%19g")
print str$(M(1), "%19g")
for n = 2 to 41
M(n) = M(n-1)
for i = 0 to n-2
M(n) = M(n) + M(i)*M(n-2-i)
next i
print str$(M(n), "%19.0f"),
if isPrime(M(n)) then print "is a prime" else print : fi
next n
end
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub</syntaxhighlight>
| |||