Catalan numbers/Pascal's triangle: Difference between revisions
Content deleted Content added
m →{{header|Phix}}: added syntax colouring the hard way |
m →{{header|Wren}}: Changed to Wren S/H |
||
(16 intermediate revisions by 13 users not shown) | |||
Line 14:
[[Pascal's triangle]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<
V t = [0] * (n + 2)
t[1] = 1
Line 26 ⟶ 25:
L(j) (i + 1 .< 1).step(-1)
t[j] += t[j - 1]
print(t[i + 1] - t[i], end' ‘ ’)</
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|360 Assembly}}==
For maximum compatibility, this program uses only the basic instruction set.
<
USING CATALAN,R13,R12
SAVEAREA B STM-SAVEAREA(R15)
Line 124 ⟶ 122:
WTOBUF DC CL80' '
YREGS
END</
{{out}}
<pre style="height:20ex">00000001
Line 141 ⟶ 139:
02674440
09694845</pre>
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<syntaxhighlight lang="action!">INCLUDE "D2:REAL.ACT" ;from the Action! Tool Ki
DEFINE PTR="CARD"
DEFINE REALSIZE="6"
PTR FUNC GetItemAddr(PTR buf BYTE i)
RETURN (buf+REALSIZE*i)
PROC Main()
DEFINE COUNT="15"
BYTE ARRAY buf(102) ;(COUNT+2)*REALSIZE
REAL POINTER r1,r2
REAL c
BYTE i,j
Put(125) PutE() ;clear the screen
r1=GetItemAddr(buf,1)
IntToReal(1,r1)
FOR i=1 TO COUNT
DO
j=i+1
WHILE j>=2
DO
r1=GetItemAddr(buf,j)
r2=GetItemAddr(buf,j-1)
RealAdd(r1,r2,r1) ;t(j)==+t(j-1)
j==-1
OD
r1=GetItemAddr(buf,i)
r2=GetItemAddr(buf,i+1)
RealAssign(r1,r2) ;t(i+1)=t(i)
j=i+2
WHILE j>=2
DO
r1=GetItemAddr(buf,j)
r2=GetItemAddr(buf,j-1)
RealAdd(r1,r2,r1) ;t(j)==+t(j-1)
j==-1
OD
r1=GetItemAddr(buf,i)
r2=GetItemAddr(buf,i+1)
RealSub(r2,r1,c) ;c=t(i+1)-t(i)
PrintF("C(%B)=",i) PrintRE(c)
OD
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Catalan_numbers_Pascal's_triangle.png Screenshot from Atari 8-bit computer]
<pre>
C(1)=1
C(2)=2
C(3)=5
C(4)=14
C(5)=42
C(6)=132
C(7)=429
C(8)=1430
C(9)=4862
C(10)=16796
C(11)=58786
C(12)=208012
C(13)=742900
C(14)=2674440
C(15)=9694845
</pre>
=={{header|Ada}}==
Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]]
<
procedure Catalan is
Line 159 ⟶ 225:
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2)));
end loop;
end Catalan;</
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|ALGOL 68}}==
{{trans|C++}}
<
[ 0 : n + 1 ]INT t;
t[0] := 0;
Line 176 ⟶ 241:
FOR j FROM i+1 BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD;
print( ( whole( t[i+1] - t[i], 0 ), " " ) )
OD</
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|ALGOL W}}==
<
% print the first 15 Catalan numbers from Pascal's triangle %
integer n;
Line 202 ⟶ 266:
end for_c
end
end.</
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|APL}}==
<
⍝ Based heavily on the J solution
CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2}
</syntaxhighlight>
{{out}}
<pre>
Line 218 ⟶ 281:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">n: 15
t: new array.of:n+2 0
t\[1]: 1
loop 1..n 'i [
loop i..1 'j -> t\[j]: t\[j] + t\[j-1]
t\[i+1]: t\[i]
loop (i+1)..1 'j -> t\[j]: t\[j] + t\[j-1]
prints t\[i+1] - t\[i]
prints " "
]
print ""</syntaxhighlight>
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
//
// smgs: 20th Feb, 2014
Line 250 ⟶ 332:
}
}
MsgBox % result</
{{out|Produces}}
<pre>
Line 257 ⟶ 339:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f CATALAN_NUMBERS_PASCALS_TRIANGLE.AWK
# converted from C
Line 274 ⟶ 356:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
{{trans|MSX-BASIC}}
<syntaxhighlight lang="qbasic">10 HOME
20 n = 15
30 DIM t(n+2)
50 t(1) = 1
55 PRINT "The first 15 Catalan numbers are: "; CHR$(10)
60 FOR i = 1 TO n
70 FOR j = i TO 1 STEP -1 : t(j) = t(j) + t(j-1) : NEXT j
80 t(i+1) = t(i)
90 FOR j = i+1 TO 1 STEP -1 : t(j) = t(j) + t(j-1) : NEXT j
100 PRINT i; ": "; t(i+1) - t(i)
120 NEXT i
130 END</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{trans|MSX-BASIC}}
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 cls
110 n = 15
120 dim t(n+2)
130 t(1) = 1
140 print "The first 15 Catalan numbers are: ";chr$(10)
150 for i = 1 to n
160 for j = i to 1 step -1 : t(j) = t(j)+t(j-1) : next j
170 t(i+1) = t(i)
180 for j = i+1 to 1 step -1 : t(j) = t(j)+t(j-1) : next j
190 print using "###";i;": ";
200 print using "#########";t(i+1)-t(i)
210 next i
220 end</syntaxhighlight>
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|QBasic}}
{{works with|MSX BASIC}}
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
<syntaxhighlight lang="qbasic">100 CLS
110 N = 15
120 DIM T(N+2)
130 T(1) = 1
140 PRINT "The first 15 Catalan numbers are: "; CHR$(10)
150 FOR I = 1 TO N
160 FOR J = I TO 1 STEP -1 : T(J) = T(J) + T(J-1) : NEXT J
170 T(I+1) = T(I)
180 FOR J = I+1 TO 1 STEP -1 : T(J) = T(J) + T(J-1) : NEXT J
190 PRINT USING "###: #########";I; T(I+1) - T(I)
200 NEXT I
210 END</syntaxhighlight>
{{out}}
<pre>The first 15 Catalan numbers are:
1: 1
2: 2
3: 5
4: 14
5: 42
6: 132
7: 429
8: 1430
9: 4862
10: 16796
11: 58786
12: 208012
13: 742900
14: 2674440
15: 9694845</pre>
==={{header|QBasic}}===
The [[#MSX-BASIC|MSX-BASIC]] solution works without any changes.
==={{header|XBasic}}===
{{trans|MSX-BASIC}}
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Pascal's triangle"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
N = 15
DIM T[N+2]
T[1] = 1
PRINT "The first 15 Catalan numbers are: "; CHR$(10)
FOR I = 1 TO N
FOR J = I TO 1 STEP -1
T[J] = T[J] + T[J-1]
NEXT J
T[I+1] = T[I]
FOR J = I+1 TO 1 STEP -1
T[J] = T[J] + T[J-1]
NEXT J
PRINT FORMAT$("###",I); ": "; FORMAT$("#########",(T[I+1] - T[I]))
NEXT I
END FUNCTION
END PROGRAM</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|MSX-BASIC}}
<syntaxhighlight lang="vb">n = 15
dim t(n+2)
t(1) = 1
print "The first 15 Catalan numbers are: \n"
for i = 1 to n
for j = i to 1 step -1
t(j) = t(j) + t(j-1)
next j
t(i+1) = t(i)
for j = i+1 to 1 step -1
t(j) = t(j) + t(j-1)
next j
print i using("###");
print ": ";
print t(i+1)-t(i) using ("#########")
next i</syntaxhighlight>
=={{header|Batch File}}==
<
setlocal ENABLEDELAYEDEXPANSION
set n=15
Line 302 ⟶ 509:
)
)
pause</
{{Out}}
<pre style="height:20ex">1
Line 319 ⟶ 526:
2674440
9694845</pre>
=={{header|C}}==
<syntaxhighlight lang="c">
//This code implements the print of 15 first Catalan's Numbers
//Formula used:
Line 367 ⟶ 573:
return 0;
}
</syntaxhighlight>
{{out}}
Line 373 ⟶ 579:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|C sharp|C#}}==
{{trans|C++}}
<
int n = 15;
List<int> t = new List<int>() { 0, 1 };
Line 386 ⟶ 591:
Console.Write(((i == 1) ? "" : ", ") + (t[i + 1] - t[i]));
}
</syntaxhighlight>
{{out|Produces}}
<pre>
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
</pre>
=={{header|C++}}==
<
//
// Nigel Galloway: June 9th., 2012
Line 408 ⟶ 612:
}
return 0;
}</
{{out|Produces}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|Common Lisp}}==
<
"Return the n-th Catalan number"
(if (<= n 1) 1
Line 425 ⟶ 628:
(dotimes (n 15)
(print (catalan (1+ n))) )</
{{out}}
Line 444 ⟶ 647:
2674440
9694845</pre>
=={{header|D}}==
{{trans|C++}}
<
import std.stdio;
Line 462 ⟶ 664:
write(t[i + 1] - t[i], ' ');
}
}</
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Catalan_numbers/Pascal%27s_triangle#Pascal Pascal].
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang="easylang">
print 1
for n = 2 to 15
num = 1
den = 1
for k = 2 to n
num *= n + k
den *= k
cat = num / den
.
print cat
.
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(define dim 100)
(define-syntax-rule (Tidx i j) (+ i (* dim j)))
Line 484 ⟶ 703:
(remember 'T #(1))
</syntaxhighlight>
{{out}}
<
;; take elements on diagonal = Catalan numbers
(for ((i (in-range 0 16))) (write (T (Tidx i i))))
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
=={{header|EDSAC order code}}==
Rather than store a triangular array, this solution stores the right-hand half of the current row and updates it in place. It uses the third method in the link, e.g. once we have the half row (70, 56, 28, 8, 1), the Catalan number 42 appears as 70 - 28.
<
[Catalan numbers from Pascal triangle, Rosetta Code website.
EDSAC program, Initial Orders 2]
Line 555 ⟶ 774:
[75] O4@ ZF [flush printer buffer; stop]
E9Z PF [define entry point; enter with acc = 0]
</syntaxhighlight>
{{out}}
<pre>
Line 574 ⟶ 793:
15 9694845
</pre>
=={{header|Elixir}}==
<
def numbers(num) do
{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} ->
Line 590 ⟶ 808:
end
IO.inspect Catalan.numbers(15)</
{{out}}
Line 596 ⟶ 814:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
</pre>
=={{header|Erlang}}==
<
-module(catalin).
-compile(export_all).
Line 616 ⟶ 833:
main()->
Ans=catl(1,2).
</syntaxhighlight>
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM CATALAN
Line 658 ⟶ 874:
END FOR
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 677 ⟶ 893:
15 9694845
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
let mutable nm=uint64(1)
let mutable dm=uint64(1)
Line 695 ⟶ 910:
if(i<>15) then
printf ", "
</syntaxhighlight>
=={{header|Factor}}==
<
IN: rosetta-code.catalan-pascal
Line 711 ⟶ 925:
[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if
pprint bl
] each drop</
{{out}}
<pre>
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
</pre>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 773 ⟶ 986:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>The first 15 Catalan numbers are
Line 792 ⟶ 1,005:
14: 2674440
15: 9694845</pre>
=={{header|Go}}==
{{trans|C++}}
<
import "fmt"
Line 812 ⟶ 1,024:
fmt.Printf("%2d : %d\n", i, t[i+1]-t[i])
}
}</
{{out}}
Line 832 ⟶ 1,044:
15 : 9694845
</pre>
=={{header|Groovy}}==
{{trans|C}}
<syntaxhighlight lang="groovy">
class Catalan
{
Line 859 ⟶ 1,070:
}
}
</
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|Haskell}}==
As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather
than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers.
<
-- Pascal's triangle.
Line 886 ⟶ 1,096:
main = do
ns <- fmap (map read) getArgs :: IO [Int]
mapM_ (print . flip take catalan) ns</
{{out}}
Line 893 ⟶ 1,103:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
=={{header|Icon}} and {{header|Unicon}}==
Line 899 ⟶ 1,108:
that aren't used.
<
procedure main(A)
limit := (integer(A[1])|15)+1
every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30))
end</
Sample run:
Line 926 ⟶ 1,135:
->
</pre>
=={{header|J}}==
<
{{out|Example use}}
<
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</
A structured derivation of Catalan follows:
<
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5
1 1 1 1 1
Line 953 ⟶ 1,161:
Catalan
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</
=={{header|Java}}==
{{trans|C++}}
<
public static void main(String[] args) {
int N = 15;
Line 976 ⟶ 1,183:
}
}
}</
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|JavaScript}}==
===ES5===
Iteration
{{trans|C++}}
<
for (var t = [0, 1], i = 1; i <= n; i++) {
for (var j = i; j > 1; j--) t[j] += t[j - 1];
Line 990 ⟶ 1,196:
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1];
document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]);
}</
{{out}}
<pre>
Line 1,000 ⟶ 1,206:
{{Trans|Haskell}}
<
'use strict';
Line 1,063 ⟶ 1,269:
return tail(catalanSeries(16));
})();</
{{Out}}
<
=={{header|jq}}==
The first identity (C(2n,n) - C(2n, n-1)) given in the reference is used in accordance with the task description, but it would of course be more efficient to factor out C(2n,n) and use the expression C(2n,n)/(n+1). See also [[Catalan_numbers#jq]] for other alternatives.
Line 1,073 ⟶ 1,278:
''Warning'': jq uses IEEE 754 64-bit arithmetic,
so the algorithm used here for Catalan numbers loses precision for n > 30 and fails completely for n > 510.
<
if k > n / 2 then binomial(n; n-k)
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
Line 1,079 ⟶ 1,284:
# Direct (naive) computation using two numbers in Pascal's triangle:
def catalan_by_pascal: . as $n | binomial(2*$n; $n) - binomial(2*$n; $n-1);</
'''Example''':
(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal]
{{Out}}
<
[0,0]
[1,1]
Line 1,104 ⟶ 1,309:
[31,14544636039226880]
[510,5.491717746183512e+302]
[511,null]</
=={{header|Julia}}==
{{trans|Matlab}}
<
function pascal(n::Int)
Line 1,123 ⟶ 1,327:
end
@show catalan_num(15)</
{{out}}
<pre>catalan_num(15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre>
=={{header|Kotlin}}==
<
import java.math.BigInteger
Line 1,153 ⟶ 1,356:
val n = 15
catalanFromPascal(n * 2)
}</
{{out}}
Line 1,173 ⟶ 1,376:
15 : 9694845
</pre>
=={{header|Lua}}==
For each line of odd-numbered length from Pascal's triangle, print the middle number minus the one immediately to its right.
This solution is heavily based on the Lua code to generate Pascal's triangle from the page for that task.
<
local ret = {}
t[0], t[#t + 1] = 0, 0
Line 1,193 ⟶ 1,395:
end
catalans(15)</
{{out}}
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre>
=={{header|M2000 Interpreter}}==
{{trans|FreeBasic}}
Line 1,207 ⟶ 1,408:
We use & to pass by reference, here anarray, to sub, but because a sub can see anything in module we can change array name inside sub to same as triangle and we can remove arguments (including size).
<syntaxhighlight lang="m2000 interpreter">
Module CatalanNumbers {
Def Integer count, t_row, size=31
Line 1,241 ⟶ 1,442:
}
CatalanNumbers
</syntaxhighlight>
{{out}}
<pre>
Line 1,260 ⟶ 1,461:
15: 9694845
</pre>
=={{header|Maple}}==
<
local i,a:=[1],C:=[1];
for i to n do
Line 1,274 ⟶ 1,474:
catalan(10);
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
This builds the entire Pascal triangle that's needed and holds it in memory. Very inefficienct, but seems to be what is asked in the problem.
<
output = ConstantArray[1, Length[lastrow] + 1];
Do[
Line 1,293 ⟶ 1,492:
]
(* testing *)
catalannumbers[15]</
{{out}}
<pre>{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}</pre>
=={{header|MATLAB}} / {{header|Octave}}==
<
p = pascal(n + 2);
p(n + 4 : n + 3 : end - 1)' - diag(p, 2)</
{{Out}}
<pre>ans =
Line 1,319 ⟶ 1,517:
2674440
9694845</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* The Catalan triangle can be generated using genmatrix */
genmatrix(lambda([n,k],if n>=k then binomial(n+k-1,k-1)-2*binomial(n+k-2,k-2) else 0),15,15)$
/* The Catalan numbers are in the main diagonal */
makelist(%[i,i],i,1,15);
</syntaxhighlight>
{{out}}
<pre>
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
=={{header|Nim}}==
{{trans|Python}}
<
var t = newSeq[int](n + 2)
Line 1,331 ⟶ 1,542:
for j in countdown(i+1, 1): t[j] += t[j-1]
stdout.write t[i+1] - t[i], " "
stdout.write '\n'</
{{Out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>
=={{header|OCaml}}==
<
let catalan : int ref = ref 0 in
Printf.printf "%d ," 1 ;
Line 1,349 ⟶ 1,559:
print_int (!catalan); print_string "," ;
done;;
</syntaxhighlight>
{{out}}
<pre>
Line 1,355 ⟶ 1,565:
1 ,2,5,14,42,132,429,1430,4862
</pre>
=={{header|Oforth}}==
<
: pascal( n -- [] )
Line 1,364 ⟶ 1,573:
: catalan( n -- m )
n 2 * pascal at( n 1+ ) n 1+ / ;</
{{out}}
Line 1,371 ⟶ 1,580:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
</pre>
=={{header|PARI/GP}}==
<
{{out}}
<pre>%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre>
=={{header|Pascal}}==
<
Program CatalanNumbers
type
Line 1,414 ⟶ 1,621:
For i := 1 to L do
Writeln(i:3,Catalan[i]:20);
end.</
<pre> 1 1
2 2
Line 1,432 ⟶ 1,639:
</pre>
=={{header|Perl}}==
{{trans|C++}}
<
my @t = (0, 1);
for(my $i = 1; $i <= N; $i++) {
Line 1,442 ⟶ 1,648:
for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] }
print $t[$i+1] - $t[$i], " ";
}</
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
Line 1,448 ⟶ 1,654:
After the 28th Catalan number, this overflows 64-bit integers. We could add <tt>use bigint;</tt> <tt>use Math::GMP ":constant";</tt> to make it work, albeit not at a fast pace. However we can use a module to do it much faster:
{{libheader|ntheory}}
<
print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</
The <tt>Math::Pari</tt> module also has a binomial, but isn't as fast and overflows its stack after 3400.
=={{header|Phix}}==
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example
<!--<
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">15</span> <span style="color: #000080;font-style:italic;">-- accurate to 30, nan/inf for anything over 514 (gmp version is below).</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">catalan</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000080;font-style:italic;">-- (>=1 only)</span>
Line 1,470 ⟶ 1,675:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">catalan</span>
<!--</
{{out}}
<pre>
Line 1,476 ⟶ 1,681:
</pre>
Explanatory comments to accompany the above
<
--' 1 1 1 1 1 1
--' 1 2 3 4 5 6
Line 1,508 ⟶ 1,713:
-- 10 15 21
-- 35 56
-- 126 (unused)</
=== gmp version ===
{{libheader|Phix/mpfr}}
<!--<
<span style="color: #008080;">
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">catalanB</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: #000080;font-style:italic;">-- very very fast!</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">catalan</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">p1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
Line 1,531 ⟶ 1,737:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">"%d: %s
<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;">"%d: %s
<!--</
{{out}}
<pre>
100: 89651994709013149668...20837521538745909320 (57 digits)
250: 46511679596923379649...69029457769094808256 (147 digits)
</pre>
The above is significantly faster than the equivalent(s) on [[Catalan_numbers#Phix|Catalan_numbers]],
Line 1,546 ⟶ 1,752:
catalan2m: 0.7s 7.0s 64.9s 644s
</pre>
=={{header|PicoLisp}}==
<
(let f
'((N)
Line 1,561 ⟶ 1,766:
(bino (* 2 N) N)
(bino (* 2 N) (inc N)) ) ) )
(bye)</
=={{header|PureBasic}}==
{{trans|C}}
<
Declare catalan()
Line 1,590 ⟶ 1,794:
Print(Str(cat)+" ")
Next
EndProcedure</
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|Python}}==
===Procedural===
{{trans|C++}}
<
>>> t = [0] * (n + 2)
>>> t[1] = 1
Line 1,609 ⟶ 1,812:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
>>> </
{{Works with|Python|2.7}}
<
nm = dm = 1
for k in range(2, n+1):
Line 1,620 ⟶ 1,823:
print [catalan_number(n) for n in range(1, 16)]
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</
===Composition of pure functions===
Line 1,629 ⟶ 1,832:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<
from itertools import (islice)
Line 1,762 ⟶ 1,965:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ [] 0 rot 0 join
witheach
[ tuck +
rot join swap ]
drop ] is nextline ( [ --> [ )
[ ' [ 1 ] swap times
[ nextline nextline
dup dup size 2 /
split nip
2 split drop
do - echo sp ]
drop ] is catalan ( n --> )
15 catalan</syntaxhighlight>
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 1,779 ⟶ 2,002:
;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900
;; 2674440 9694845)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku"
constant @catalan = gather for 2, 4 ... * -> $ix {
Line 1,792 ⟶ 2,014:
}
.say for @catalan[^20];</
{{out}}
<pre>1
Line 1,814 ⟶ 2,036:
1767263190
6564120420</pre>
=={{header|REXX}}==
===explicit subscripts===
All of the REXX program examples can handle arbitrary large numbers.
<
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
Line 1,828 ⟶ 2,049:
@.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k*/
say @.ip - @.i /*display the Ith Catalan number. */
end /*i*/ /*stick a fork in it, we're all done. */</
'''output''' when using the default input:
<pre>
Line 1,849 ⟶ 2,070:
===implicit subscripts===
<
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
Line 1,861 ⟶ 2,082:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
@: parse arg !; return @.! /*return the value of @.[arg(1)] */</
'''output''' is the same as the 1<sup>st</sup> version.
===using binomial coefficients===
<
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
Line 1,877 ⟶ 2,098:
/*──────────────────────────────────────────────────────────────────────────────────────*/
comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</
'''output''' is the same as the 1<sup>st</sup> version.
===binomial coefficients, memoized===
This REXX version uses memoization for the calculation of factorials.
<
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
Line 1,896 ⟶ 2,117:
/*──────────────────────────────────────────────────────────────────────────────────────*/
comb: procedure expose !.; parse arg x,y; if x=y then return 1; if y>x then return 0
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</
'''output''' is the same as the 1<sup>st</sup> version. <br><br>
=={{header|Ring}}==
<
n=15
cat = list(n+2)
Line 1,914 ⟶ 2,134:
see "" + (cat[i+1]-cat[i]) + " "
next
</syntaxhighlight>
Output:
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|RPL}}==
We have taken the opportunity provided by the task to develop a routine that recursively computes Pascal's triangle.
If the challenge was to look for high Catalan numbers, memoizing the triangle would make sense.
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ '''IF THEN''' LAST 1 + → n1
≪ n1 2 - '''PASLIN'''
{ } n1 + RDM
DUP ARRY→ DROP n1 ROLLD n1 →ARRY +
≫ '''ELSE''' [ 1 ] '''END'''
≫ ‘'''PASLIN'''’ STO
≪
DUP DUP + '''PASLIN'''
SWAP GETI ROT ROT GET SWAP -
≫ ‘'''CATLN'''’ STO
|
'''PASLIN''' ''( n -- [ 1..(n,p)..1 ] ) ''
get previous line
add a zero at tail
duplicate it, rotate right coeffs and sum
'''CATLN''' ''( n -- C(n) )''
get Pascal_line(2n)
return line[n+1]-line[n]
|}
{{in}}
<pre>
≪ { } 1 15 FOR j CATLN j + NEXT ≫ EVAL
</pre>
{{out}}
<pre>
1: { 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 }
</pre>
Runs in 119 seconds on an HP-28S.
===Fast, idiomatic approach===
Using the built-in <code>COMB</code> function, which returns coefficients of Pascal's triangle:
≪ { } 1 15 '''FOR''' j
j DUP + j COMB LAST 1 - COMB - + '''NEXT'''
≫ EVAL
Same output than above, runs in 2.4 seconds on an HP-28S.
=={{header|Ruby}}==
<
t = [0, 1] #grows as needed
(1..num).map do |i|
Line 1,931 ⟶ 2,199:
end
p catalan(15)</
{{out}}
<pre>
Line 1,938 ⟶ 2,206:
=={{header|Run BASIC}}==
<
dim t(n+2)
t(1) = 1
Line 1,946 ⟶ 2,214:
for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j
print t(i+1) - t(i);" ";
next i</
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>
=={{header|Rust}}==
<
fn main()
Line 1,980 ⟶ 2,247:
}
}
</syntaxhighlight>
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>
=={{header|Scala}}==
<
if (n <= 1) 1
else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum
(1 to 15).map(catalan(_))</
{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/2ybpRZxCTOyrx3mIy8yIDw Scastie (JVM)].
=={{header|Scilab}}==
<syntaxhighlight lang="text">n=15
t=zeros(1,n+2)
t(1)=1
Line 2,005 ⟶ 2,270:
end
disp(t(i+1)-t(i))
end</
{{out}}
<pre style="height:20ex"> 1.
Line 2,022 ⟶ 2,287:
2674440.
9694845. </pre>
=={{header|Seed7}}==
<
const proc: main is func
Line 2,044 ⟶ 2,308:
end for;
writeln;
end func;</
{{out}}
Line 2,050 ⟶ 2,314:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
<
var t = [0, 1]
(1..num).map { |i|
Line 2,063 ⟶ 2,326:
}
say catalan(15).join(' ')</
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|smart BASIC}}==
<
x = 15
DIM t(x+2)
Line 2,081 ⟶ 2,343:
NEXT m
PRINT n,"#######":t(n+1) - t(n)
NEXT n</
=={{header|Tcl}}==
<
set result {}
array set t {0 0 1 1}
Line 2,096 ⟶ 2,357:
}
puts [catalan 15]</
{{out}}
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
=={{header|TI-83 BASIC}}==
<
15→N
seq(0,I,1,N+2)→L1
Line 2,114 ⟶ 2,374:
End
Disp L1(I+1)-L1(I)
End</
{{out}}
<pre> 1
Line 2,132 ⟶ 2,392:
9694845
Done </pre>
=={{header|Vala}}==
{{trans|C++}}
<
const int N = 15;
uint64[] t = {0, 1};
Line 2,145 ⟶ 2,404:
}
print("\n");
}</
{{out}}
Line 2,151 ⟶ 2,410:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|VBScript}}==
To run in console mode with cscript.
<
if Wscript.arguments.count=1 then
n=Wscript.arguments.item(0)
Line 2,173 ⟶ 2,431:
next 'j
Wscript.echo t(i+1)-t(i)
next 'i</
=={{header|Visual Basic}}==
{{trans|Rexx}}
{{works with|Visual Basic|VB6 Standard}}
<syntaxhighlight lang="vb">
Sub catalan()
Const n = 15
Line 2,195 ⟶ 2,452:
Next i
End Sub 'catalan
</syntaxhighlight>
{{Out}}
<pre style="height:20ex">
Line 2,214 ⟶ 2,471:
9694845
</pre>
=={{header|Wren}}==
{{trans|C++}}
<
var t = List.filled(n+2, 0)
t[1] = 1
Line 2,226 ⟶ 2,482:
System.write("%(t[i+1]-t[i]) ")
}
System.print()</
{{out}}
Line 2,233 ⟶ 2,489:
</pre>
=={{header|XPL0}}==
{{trans|C++}}
<syntaxhighlight lang "XPL0">def N = 15;
int T(N+2), I, J;
[T(0):= 0; T(1):= 1;
for I:= 1 to N do
[for J:= I downto 2 do T(J):= T(J) + T(J-1);
T(I+1):= T(I);
for J:= I+1 downto 2 do T(J):= T(J) + T(J-1);
IntOut(0, T(I+1) - T(I)); ChOut(0, ^ );
];
]</syntaxhighlight>
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>
=={{header|Zig}}==
Uses comptime functionality to compile Pascal's triangle into the object code, then at runtime, it's simply a table lookup. (uses code from [[AKS test for primes|AKS primality task]].)
<syntaxhighlight lang="zig">
const std = @import("std");
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
var n: u32 = 1;
while (n <= 15) : (n += 1) {
Line 2,258 ⟶ 2,530:
const rmax = 68;
// evaluated and created at compile-time
const pascal = build: {
@setEvalBranchQuota(100_000);
Line 2,278 ⟶ 2,551:
break :build coefficients;
};
</syntaxhighlight>
{{Out}}
<pre>
Line 2,300 ⟶ 2,573:
=={{header|zkl}}==
{{trans|PARI/GP}} using binomial coefficients.
<
(1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</
{{out}}
<pre>
L(1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845)
</pre>
=={{header|ZX Spectrum Basic}}==
{{trans|C++}}
<
20 DIM t(N+2)
30 LET t(2)=1
Line 2,317 ⟶ 2,589:
70 FOR j=i+1 TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j
80 PRINT t(i+1)-t(i);" ";
90 NEXT i</
|