Motzkin numbers: Difference between revisions

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

{{Trans|Wren}}

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

<lang algol68>BEGIN # find some Motzkin numbers #

PR read "primes.incl.a68" PR

# returns a table of the Motzkin numbers 0 .. n #

OP MOTZKIN = ( INT n )[]LONG LONG INT:

BEGIN

[ 0 : n ]LONG LONG INT m;

IF n >= 0 THEN

m[ 0 ] := 1;

IF n >= 1 THEN

m[ 1 ] := 1;

FOR i FROM 2 TO UPB m DO

m[ i ] := ( ( m[ i - 1 ] * ( ( 2 * i ) + 1 ) )

+ ( m[ i - 2 ] * ( ( 3 * i ) - 3 ) )

)

OVER ( i + 2 )

OD

FI

FI;

m

END # MOTZKIN # ;

# returns a string representation of n with commas #

PROC commatise = ( LONG LONG INT n )STRING:

BEGIN

STRING result := "";

STRING unformatted = whole( n, 0 );

INT ch count := 0;

FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO

IF ch count <= 2 THEN ch count +:= 1

ELSE ch count := 1; "," +=: result

FI;

unformatted[ c ] +=: result

OD;

result

END; # commatise #

# left-pads a string to at least n characters #

PROC pad left = ( STRING s, INT n )STRING:

BEGIN

STRING result := s;

WHILE ( UPB result - LWB result ) + 1 < n DO " " +=: result OD;

result

END; # pad left #

# show the Motzkin numbers #

print( ( " n M[n] Prime?", newline ) );

print( ( "-----------------------------------", newline ) );

[]LONG LONG INT m = MOTZKIN 41;

FOR i FROM LWB m TO UPB m DO

print( ( whole( i, -2 )

, pad left( commatise( m[ i ] ), 26 )

, IF is probably prime( m[ i ] ) THEN " prime" ELSE "" FI

, newline

)

)

OD

END</lang>

{{out}}

<pre>

n M[n] Prime?

-----------------------------------

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>