Motzkin numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|C#|CSharp}}: added missing ordinal number suffix in comment) |
m (→{{header|Wren}}: Minor tidy) |
||
| (26 intermediate revisions by 15 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 149 ⟶ 220:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 196 ⟶ 267:
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}}==
<
#include <stdbool.h>
#include <stdint.h>
Line 232 ⟶ 375:
m1 = m;
}
}</
{{out}}
Line 284 ⟶ 427:
=={{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;
Line 312 ⟶ 455:
a = t);
}
}</
{{out}}
<pre style="height:121ex;"> 1
Line 396 ⟶ 539:
=={{header|C++}}==
<
#include <iomanip>
#include <iostream>
Line 445 ⟶ 588:
<< is_prime(n) << '\n';
}
}</
{{out}}
Line 493 ⟶ 636:
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 548 ⟶ 869:
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<
tools.memory.private ;
Line 568 ⟶ 889:
dup motzkin [ commas ] keep prime? "prime" "" ?
"%2d %24s %s\n" printf
] each-integer</
{{out}}
<pre>
Line 618 ⟶ 939:
=={{header|Fermat}}==
<
Array m[42];
m[1]:=1;
Line 633 ⟶ 954:
; {the smallest prime factor for composites, so this actually gives}
; {slightly more information than requested}
</syntaxhighlight>
{{out}}
Line 683 ⟶ 1,004:
=={{header|FreeBASIC}}==
Use any of the primality testing examples as an include.
<
#include "isprime.bas"
Line 697 ⟶ 1,018:
if isprime(M(n)) then print "is a prime" else print
next n
</syntaxhighlight>
{{out}}
<pre>
Line 742 ⟶ 1,063:
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 748 ⟶ 1,149:
{{libheader|Go-rcu}}
Assumes a 64 bit Go compiler.
<
import (
Line 772 ⟶ 1,173:
fmt.Printf("%2d %23s %t\n", i, rcu.Commatize(e), rcu.IsPrime(e))
}
}</
{{out}}
Line 820 ⟶ 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 830 ⟶ 1,461:
For a suitable implementation of `is_prime`, see e.g. # [[Erd%C5%91s-primes#jq]].
<
def motzkin:
Line 845 ⟶ 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 893 ⟶ 1,524:
41 192137918101841817
</pre>
=={{header|Julia}}==
{{trans|Wren}}
<
function motzkin(N)
Line 912 ⟶ 1,542:
println(lpad(i - 1, 2), lpad(m, 20), lpad(isprime(m), 8))
end
</
<pre>
n M[n] Prime?
Line 961 ⟶ 1,591:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{{out}}
Alignment lost in copying.
Line 1,006 ⟶ 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 1,034 ⟶ 1,683:
var m = motzkin(41)
for i, val in m:
echo &"{i:2} {insertSep($val):>23} {val.isPrime}"</
{{out}}
Line 1,083 ⟶ 1,732:
=={{header|PARI/GP}}==
<
M=vector(41)
M[1]=1
Line 1,090 ⟶ 1,739:
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 1,116 ⟶ 1,765:
printf "%3d%25s %s\n", $count++, s/\B(?=(\d\d\d)+$)/,/gr,
is_prime($_) ? 'prime' : '';
}</
{{out}}
<pre>
Line 1,165 ⟶ 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 1,190 ⟶ 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 1,240 ⟶ 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 1,258 ⟶ 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 1,273 ⟶ 2,008:
say " 𝐧 𝐌[𝐧] Prime?";
𝐌[^42].kv.map: { printf "%2d %24s %s\n", $^k, $^v.&comma, $v.is-prime };</
{{out}}
<pre> 𝐧 𝐌[𝐧] Prime?
Line 1,321 ⟶ 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,373 ⟶ 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,422 ⟶ 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,440 ⟶ 2,229:
puts "#{'%2d' % i}: #{m}#{m.prime? ? ' prime' : ''}"
end
</syntaxhighlight>
{{out}}
<pre >
Line 1,489 ⟶ 2,278:
=={{header|Rust}}==
{{trans|Wren}}
<
// primal = "0.3"
// num-format = "0.4"
Line 1,517 ⟶ 2,306:
);
}
}</
{{out}}
Line 1,569 ⟶ 2,358:
=={{header|Sidef}}==
Built-in:
<
Motzkin's triangle (the Motzkin numbers are on the hypotenuse of the triangle):
<
var row = []
{ |n|
Line 1,582 ⟶ 2,371:
motzkin_triangle(10, {|row|
row.map { "%4s" % _ }.join(' ').say
})</
{{out}}
Line 1,600 ⟶ 2,389:
Task:
<
var (a, b, n) = (0, 1, 1)
Line 1,614 ⟶ 2,403:
motzkin_numbers(42).each_kv {|k,v|
say "#{'%2d' % k}: #{v}#{v.is_prime ? ' prime' : ''}"
}</
{{out}}
Line 1,666 ⟶ 2,455:
{{trans|Rust}}
<
extension BinaryInteger {
Line 1,704 ⟶ 2,493:
for (i, n) in m.enumerated() {
print("\(i): \(n) \(n.isPrime ? "prime" : "")")
}</
{{out}}
Line 1,754 ⟶ 2,543:
{{libheader|Wren-long}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var motzkin = Fn.new { |n|
Line 1,772 ⟶ 2,561:
for (i in 0..41) {
Fmt.print("$2d $,23i $s", i, m[i], m[i].isPrime)
}</
{{out}}
Line 1,821 ⟶ 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>
| |||