Motzkin numbers: Difference between revisions

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 #

)

OD

{{out}}

<pre>

 

=={{header|AWK}}==

# syntax: GAWK --bignum -f MOTZKIN_NUMBERS.AWK

BEGIN {

return(1)

}

{{out}}

<pre>

 

=={{header|BASIC256}}==

M[0] = 1 : M[1] = 1

print rjust("1",18) : print rjust("1",18)

next i

return True

 

 

=={{header|Burlesque}}==

{{out}}

<pre>1

 

=={{header|C}}==

#include <stdbool.h>

#include <stdint.h>

m1 = m;

}

 

{{out}}

=={{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;

a = t);

}

{{out}}

<pre style="height:121ex;"> 1

 

=={{header|C++}}==

#include <iomanip>

#include <iostream>

<< is_prime(n) << '\n';

}

 

{{out}}

 

=={{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")

{{out}}

<pre>

=={{header|Factor}}==

{{works with|Factor|0.99 2021-06-02}}

tools.memory.private ;

 

dup motzkin [ commas ] keep prime? "prime" "" ?

"%2d %24s %s\n" printf

{{out}}

<pre>

 

=={{header|Fermat}}==

Array m[42];

m[1]:=1;

; {the smallest prime factor for composites, so this actually gives}

; {slightly more information than requested}

 

{{out}}

=={{header|FreeBASIC}}==

Use any of the primality testing examples as an include.

#include "isprime.bas"

 

if isprime(M(n)) then print "is a prime" else print

next n

{{out}}

<pre>

{{libheader|Go-rcu}}

Assumes a 64 bit Go compiler.

 

import (

fmt.Printf("%2d %23s %t\n", i, rcu.Commatize(e), rcu.IsPrime(e))

}

 

{{out}}

 

=={{header|Haskell}}==

import Math.NumberTheory.Primes.Testing (isPrime)

import System.Environment (getArgs)

main = do

[n] <- map read <$> getArgs

 

{{out}}

Implementation:

 

 

Task example:

1

1

22944749046030949

66368199913921497

 

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:

For a suitable implementation of `is_prime`, see e.g. # [[Erd%C5%91s-primes#jq]].

 

 

def motzkin:

(41 | motzkin

| range(0;length) as $i

{{out}}

<pre>

=={{header|Julia}}==

{{trans|Wren}}

 

function motzkin(N)

println(lpad(i - 1, 2), lpad(m, 20), lpad(isprime(m), 8))

end

<pre>

n M[n] Prime?

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

{{out}}

Alignment lost in copying.

=={{header|Nim}}==

{{trans|Wren}}

 

func isPrime(n: Positive): bool =

var m = motzkin(41)

for i, val in m:

 

{{out}}

 

=={{header|PARI/GP}}==

M=vector(41)

M[1]=1

M=concat([1], M)

for(n=1, 42, print(M[n]," ",isprime(M[n])))

 

=={{header|Perl}}==

 

use strict; # https://rosettacode.org/wiki/Motzkin_numbers

printf "%3d%25s %s\n", $count++, s/\B(?=(\d\d\d)+$)/,/gr,

is_prime($_) ? 'prime' : '';

{{out}}

<pre>

 

=={{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>

<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>

===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>

<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>

<code>isprime</code> is defined at [[Primality by trial division#Quackery]].

 

41 times

[ dup -2 split nip do

behead drop

witheach

 

{{out}}

=={{header|Raku}}==

===Using binomial coefficients and Catalan numbers===

 

constant \C = 1, |[\×] (2, 6 … ∞) Z/ 2 .. *;

 

say " 𝐧 𝐌[𝐧] Prime?";

{{out}}

<pre> 𝐧 𝐌[𝐧] Prime?

===Using recurrence relationship===

 

 

my \𝐌 = 1, 1, { state $i = 2; ++$i; ($^b × (2 × $i - 1) + $^a × (3 × $i - 6)) ÷ ($i + 1) } … *;

 

say " 𝐧 𝐌[𝐧] Prime?";

 

Same output

 

=={{header|REXX}}==

numeric digits 92 /*max number of decimal digits for task*/

parse arg n . /*obtain optional argument from the CL.*/

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

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ruby}}==

 

motzkin = Enumerator.new do |y|

puts "#{'%2d' % i}: #{m}#{m.prime? ? ' prime' : ''}"

end

{{out}}

<pre >

=={{header|Rust}}==

{{trans|Wren}}

// primal = "0.3"

// num-format = "0.4"

);

}

 

{{out}}

=={{header|Sidef}}==

Built-in:

 

Motzkin's triangle (the Motzkin numbers are on the hypotenuse of the triangle):

var row = []

{ |n|

motzkin_triangle(10, {|row|

row.map { "%4s" % _ }.join(' ').say

 

{{out}}

Task:

 

 

var (a, b, n) = (0, 1, 1)

motzkin_numbers(42).each_kv {|k,v|

say "#{'%2d' % k}: #{v}#{v.is_prime ? ' prime' : ''}"

 

{{out}}

{{trans|Rust}}

 

 

extension BinaryInteger {

for (i, n) in m.enumerated() {

print("\(i): \(n) \(n.isPrime ? "prime" : "")")

 

{{out}}

{{libheader|Wren-long}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

 

for (i in 0..41) {

Fmt.print("$2d $,23i $s", i, m[i], m[i].isPrime)

 

{{out}}

 

=={{header|Yabasic}}==

M(0) = 1 : M(1) = 1

print str$(M(0), "%19g")

wend

return True