Catalan numbers/Pascal's triangle: Difference between revisions
Added Common Lisp |
m →{{header|Wren}}: Changed to Wren S/H |
||
(38 intermediate revisions by 23 users not shown) | |||
Line 9: | Line 9: | ||
<!-- '''http://milan.milanovic.org/math/english/fibo/fibo4.html is broken. --> |
<!-- '''http://milan.milanovic.org/math/english/fibo/fibo4.html is broken. --> |
||
* [http://mathworld.wolfram.com/CatalansTriangle.html Catalan's Triangle] for a Number Triangle that generates Catalan Numbers using only addition. |
* [http://mathworld.wolfram.com/CatalansTriangle.html Catalan's Triangle] for a Number Triangle that generates Catalan Numbers using only addition. |
||
* Sequence [ |
* Sequence [[oeis:A000108|A000108 on OEIS]] has a lot of information on Catalan Numbers. |
||
;Related Tasks: |
;Related Tasks: |
||
[[Pascal's triangle]] |
[[Pascal's triangle]] |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
=={{header|11l}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">V n = 15 |
||
V t = [0] * (n + 2) |
V t = [0] * (n + 2) |
||
t[1] = 1 |
t[1] = 1 |
||
Line 26: | Line 25: | ||
L(j) (i + 1 .< 1).step(-1) |
L(j) (i + 1 .< 1).step(-1) |
||
t[j] += t[j - 1] |
t[j] += t[j - 1] |
||
print(t[i + 1] - t[i], end' ‘ ’)</ |
print(t[i + 1] - t[i], end' ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
For maximum compatibility, this program uses only the basic instruction set. |
For maximum compatibility, this program uses only the basic instruction set. |
||
< |
<syntaxhighlight lang="360asm">CATALAN CSECT |
||
USING CATALAN,R13,R12 |
USING CATALAN,R13,R12 |
||
SAVEAREA B STM-SAVEAREA(R15) |
SAVEAREA B STM-SAVEAREA(R15) |
||
Line 124: | Line 122: | ||
WTOBUF DC CL80' ' |
WTOBUF DC CL80' ' |
||
YREGS |
YREGS |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:20ex">00000001 |
<pre style="height:20ex">00000001 |
||
Line 141: | Line 139: | ||
02674440 |
02674440 |
||
09694845</pre> |
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}}== |
=={{header|Ada}}== |
||
Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]] |
Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]] |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Pascal; |
||
procedure Catalan is |
procedure Catalan is |
||
Line 159: | Line 225: | ||
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2))); |
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2))); |
||
end loop; |
end loop; |
||
end Catalan;</ |
end Catalan;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="algol68">INT n = 15; |
||
[ 0 : n + 1 ]INT t; |
[ 0 : n + 1 ]INT t; |
||
t[0] := 0; |
t[0] := 0; |
||
Line 176: | Line 241: | ||
FOR j FROM i+1 BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD; |
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 ), " " ) ) |
print( ( whole( t[i+1] - t[i], 0 ), " " ) ) |
||
OD</ |
OD</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% print the first 15 Catalan numbers from Pascal's triangle % |
% print the first 15 Catalan numbers from Pascal's triangle % |
||
integer n; |
integer n; |
||
Line 202: | Line 266: | ||
end for_c |
end for_c |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|APL}}== |
=={{header|APL}}== |
||
< |
<syntaxhighlight lang="apl"> |
||
⍝ Based heavily on the J solution |
⍝ Based heavily on the J solution |
||
CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2} |
CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 218: | Line 281: | ||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</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}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey_L}} |
{{works with|AutoHotkey_L}} |
||
< |
<syntaxhighlight lang="autohotkey">/* Generate Catalan Numbers |
||
// |
// |
||
// smgs: 20th Feb, 2014 |
// smgs: 20th Feb, 2014 |
||
Line 250: | Line 332: | ||
} |
} |
||
} |
} |
||
MsgBox % result</ |
MsgBox % result</syntaxhighlight> |
||
{{out|Produces}} |
{{out|Produces}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|AWK}}== |
|||
<syntaxhighlight lang="awk"> |
|||
# syntax: GAWK -f CATALAN_NUMBERS_PASCALS_TRIANGLE.AWK |
|||
# converted from C |
|||
BEGIN { |
|||
printf("1") |
|||
for (n=2; n<=15; n++) { |
|||
num = den = 1 |
|||
for (k=2; k<=n; k++) { |
|||
num *= (n + k) |
|||
den *= k |
|||
catalan = num / den |
|||
} |
|||
printf(" %d",catalan) |
|||
} |
|||
printf("\n") |
|||
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}}== |
=={{header|Batch File}}== |
||
< |
<syntaxhighlight lang="dos">@echo off |
||
setlocal ENABLEDELAYEDEXPANSION |
setlocal ENABLEDELAYEDEXPANSION |
||
set n=15 |
set n=15 |
||
Line 278: | Line 509: | ||
) |
) |
||
) |
) |
||
pause</ |
pause</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre style="height:20ex">1 |
<pre style="height:20ex">1 |
||
Line 295: | Line 526: | ||
2674440 |
2674440 |
||
9694845</pre> |
9694845</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang="c"> |
|||
<lang c> |
|||
//This code implements the print of 15 first Catalan's Numbers |
//This code implements the print of 15 first Catalan's Numbers |
||
//Formula used: |
//Formula used: |
||
Line 324: | Line 554: | ||
printf("1 "); |
printf("1 "); |
||
//iterating |
//iterating from 2 to 15 |
||
for (n=2; n<=N; ++n) { |
for (n=2; n<=N; ++n) { |
||
//initializaing for products |
//initializaing for products |
||
Line 343: | Line 573: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 349: | Line 579: | ||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|C sharp|C#}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="csharp"> |
|||
int n = 15; |
|||
List<int> t = new List<int>() { 0, 1 }; |
|||
for (int i = 1; i <= n; i++) |
|||
{ |
|||
for (var j = i; j > 1; j--) t[j] += t[j - 1]; |
|||
t.Add(t[i]); |
|||
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; |
|||
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++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">// Generate Catalan Numbers |
||
// |
// |
||
// Nigel Galloway: June 9th., 2012 |
// Nigel Galloway: June 9th., 2012 |
||
Line 366: | Line 612: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out|Produces}} |
{{out|Produces}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|C Sharp}}== |
|||
{{trans|C++}} |
|||
<lang csharp> |
|||
int n = 15; |
|||
List<int> t = new List<int>() { 0, 1 }; |
|||
for (int i = 1; i <= n; i++) |
|||
{ |
|||
for (var j = i; j > 1; j--) t[j] += t[j - 1]; |
|||
t.Add(t[i]); |
|||
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; |
|||
Console.Write(((i == 1) ? "" : ", ") + (t[i + 1] - t[i])); |
|||
} |
|||
</lang> |
|||
{{out|Produces}} |
|||
<pre> |
|||
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845 |
|||
</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun catalan (n) |
||
"Return the n-th Catalan number" |
"Return the n-th Catalan number" |
||
(if (<= n 1) 1 |
(if (<= n 1) 1 |
||
Line 402: | Line 628: | ||
(dotimes (n 15) |
(dotimes (n 15) |
||
(print (catalan (1+ n))) )</ |
(print (catalan (1+ n))) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 421: | Line 647: | ||
2674440 |
2674440 |
||
9694845</pre> |
9694845</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="d">void main() { |
||
import std.stdio; |
import std.stdio; |
||
Line 440: | Line 664: | ||
write(t[i + 1] - t[i], ' '); |
write(t[i + 1] - t[i], ' '); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<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}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(define dim 100) |
(define dim 100) |
||
(define-syntax-rule (Tidx i j) (+ i (* dim j))) |
(define-syntax-rule (Tidx i j) (+ i (* dim j))) |
||
Line 461: | Line 703: | ||
(remember 'T #(1)) |
(remember 'T #(1)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="scheme"> |
||
;; take elements on diagonal = Catalan numbers |
;; take elements on diagonal = Catalan numbers |
||
(for ((i (in-range 0 16))) (write (T (Tidx i i)))) |
(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 |
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{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. |
|||
<syntaxhighlight lang="edsac"> |
|||
[Catalan numbers from Pascal triangle, Rosetta Code website. |
|||
EDSAC program, Initial Orders 2] |
|||
..PZ [blank tape and terminator] |
|||
T54K [refer to working array with 'C'] |
|||
P300F [address of working array] |
|||
T46K [to call print subroutine with 'G N'] |
|||
P56F [address of print subroutine] |
|||
[Modification of library subroutine P7. |
|||
Prints non-negative integer, up to 10 digits, right-justified. |
|||
55 locations, load at even address.] |
|||
E25KTN |
|||
GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@ |
|||
TFH17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@ |
|||
T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@ |
|||
[Main program] |
|||
PK T200K GK |
|||
[Constants] |
|||
[0] PD [short constant 1] |
|||
[1] P2F [to inc address by 2] |
|||
[2] T#C [used in manufacturing EDSAC orders] |
|||
[3] MF [add to T order to make A order with same address] |
|||
[4] #F [set figures] |
|||
[5] &F [line feed] |
|||
[6] @F [carriage return] |
|||
[7] P7D [maximum n = 15] |
|||
[Variable] |
|||
[8] PF [n] |
|||
[Enter with acc = 0] |
|||
[9] O4@ [set teleprinter to figures] |
|||
T4#C T2#C T#C A@ TC [initialize first 3 terms to 1, 0, 0] |
|||
T8@ E58@ [set n := 0; jump to inc n and print C_n] |
|||
[Outer loop; here with n updated] |
|||
[17] TF A8@ [acc := latest n] |
|||
L1F A2@ T22@ [make and store order 'T 2n #C'] |
|||
[22] T#C [sets term := 0; also used to test for end of loop] |
|||
A2@ [load 'T#C', initial value of order 31] |
|||
[Loop to convert e.g. (20, 15, 6, 1) to (35, 21, 7, 1); works left to right] |
|||
[24] U31@ A3@ U29@ A1@ T30@ [set up orders on next line] |
|||
[29] A#C A#C T#C [replaced by manufactured orders] |
|||
A31@ A1@ S22@ E38@ [inc address in order 31, jump out if done] |
|||
A22@ E24@ [not done, loop back] |
|||
[38] A22@ T48@ [initialize order 48] |
|||
[Loop to convert e.g. (35, 21, 7, 1) to (70, 56, 28, 8, 1); works right to left] |
|||
[40] TF A48@ A3@ U46@ S1@ T47@ [set up orders on next line] |
|||
[46] A#C A#C T#C [replaced by manufactured orders] |
|||
A48@ S1@ T48@ [dec address in order 48] |
|||
A2@ S48@ G40@ [test for done, loop back if not] |
|||
A#C LD T#C [double first term, e.g. 35 -> 70 (not done in loop)] |
|||
[Increment n and print Catalan number C_n] |
|||
[58] TD [clear 0D, ensures sandwich bit = 0] |
|||
A8@ A@ U8@ TF [inc n; set 0D := n by setting 0F := n] |
|||
A63@ GN [print n] |
|||
A#C S4#C TD A68@ GN [print Catalan number C_n, e.g. C_5 = 70 - 28 = 42] |
|||
O6@ O5@ [print CR, LF] |
|||
A8@ S7@ G17@ [test for maximum n, loop back if not] |
|||
[75] O4@ ZF [flush printer buffer; stop] |
|||
E9Z PF [define entry point; enter with acc = 0] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule Catalan do |
||
def numbers(num) do |
def numbers(num) do |
||
{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} -> |
{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} -> |
||
Line 485: | Line 808: | ||
end |
end |
||
IO.inspect Catalan.numbers(15)</ |
IO.inspect Catalan.numbers(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 492: | Line 815: | ||
</pre> |
</pre> |
||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang"> |
||
-module(catalin). |
-module(catalin). |
||
-compile(export_all). |
-compile(export_all). |
||
Line 510: | Line 833: | ||
main()-> |
main()-> |
||
Ans=catl(1,2). |
Ans=catl(1,2). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<syntaxhighlight lang="erre"> |
|||
<lang ERRE> |
|||
PROGRAM CATALAN |
PROGRAM CATALAN |
||
Line 551: | Line 874: | ||
END FOR |
END FOR |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 570: | Line 893: | ||
15 9694845 |
15 9694845 |
||
</pre> |
</pre> |
||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
=={{header|F#}}== |
|||
<lang F#> |
|||
let mutable nm=uint64(1) |
let mutable nm=uint64(1) |
||
let mutable dm=uint64(1) |
let mutable dm=uint64(1) |
||
Line 588: | Line 910: | ||
if(i<>15) then |
if(i<>15) then |
||
printf ", " |
printf ", " |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: arrays grouping io kernel math prettyprint sequences ; |
||
IN: rosetta-code.catalan-pascal |
IN: rosetta-code.catalan-pascal |
||
Line 604: | Line 925: | ||
[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if |
[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if |
||
pprint bl |
pprint bl |
||
] each drop</ |
] each drop</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 |
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' version 15-09-2015 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 666: | Line 986: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 15 Catalan numbers are |
<pre>The first 15 Catalan numbers are |
||
Line 685: | Line 1,005: | ||
14: 2674440 |
14: 2674440 |
||
15: 9694845</pre> |
15: 9694845</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 705: | Line 1,024: | ||
fmt.Printf("%2d : %d\n", i, t[i+1]-t[i]) |
fmt.Printf("%2d : %d\n", i, t[i+1]-t[i]) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 725: | Line 1,044: | ||
15 : 9694845 |
15 : 9694845 |
||
</pre> |
</pre> |
||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang="groovy"> |
|||
<lang Groovy> |
|||
class Catalan |
class Catalan |
||
{ |
{ |
||
Line 752: | Line 1,070: | ||
} |
} |
||
} |
} |
||
</ |
</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather |
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. |
than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers. |
||
< |
<syntaxhighlight lang="haskell">import System.Environment (getArgs) |
||
-- Pascal's triangle. |
-- Pascal's triangle. |
||
Line 779: | Line 1,096: | ||
main = do |
main = do |
||
ns <- fmap (map read) getArgs :: IO [Int] |
ns <- fmap (map read) getArgs :: IO [Int] |
||
mapM_ (print . flip take catalan) ns</ |
mapM_ (print . flip take catalan) ns</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 786: | Line 1,103: | ||
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440] |
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440] |
||
</pre> |
</pre> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Line 792: | Line 1,108: | ||
that aren't used. |
that aren't used. |
||
< |
<syntaxhighlight lang="unicon">link math |
||
procedure main(A) |
procedure main(A) |
||
limit := (integer(A[1])|15)+1 |
limit := (integer(A[1])|15)+1 |
||
every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30)) |
every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30)) |
||
end</ |
end</syntaxhighlight> |
||
Sample run: |
Sample run: |
||
Line 819: | Line 1,135: | ||
-> |
-> |
||
</pre> |
</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j"> Catalan=. }:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
< |
<syntaxhighlight lang="j"> Catalan 15 |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</ |
</syntaxhighlight> |
||
A structured derivation of Catalan follows: |
A structured derivation of Catalan follows: |
||
< |
<syntaxhighlight lang="j"> o=. @: NB. Composition of verbs (functions) |
||
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5 |
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5 |
||
1 1 1 1 1 |
1 1 1 1 1 |
||
Line 846: | Line 1,161: | ||
Catalan |
Catalan |
||
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</ |
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="java">public class Test { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
int N = 15; |
int N = 15; |
||
Line 869: | Line 1,183: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
===ES5=== |
===ES5=== |
||
Iteration |
Iteration |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="javascript">var n = 15; |
||
for (var t = [0, 1], i = 1; i <= n; i++) { |
for (var t = [0, 1], i = 1; i <= n; i++) { |
||
for (var j = i; j > 1; j--) t[j] += t[j - 1]; |
for (var j = i; j > 1; j--) t[j] += t[j - 1]; |
||
Line 883: | Line 1,196: | ||
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; |
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; |
||
document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]); |
document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 893: | Line 1,206: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 956: | Line 1,269: | ||
return tail(catalanSeries(16)); |
return tail(catalanSeries(16)); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">[1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845]</syntaxhighlight> |
||
=={{header|jq}}== |
=={{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. |
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 966: | Line 1,278: | ||
''Warning'': jq uses IEEE 754 64-bit arithmetic, |
''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. |
so the algorithm used here for Catalan numbers loses precision for n > 30 and fails completely for n > 510. |
||
< |
<syntaxhighlight lang="jq">def binomial(n; k): |
||
if k > n / 2 then binomial(n; n-k) |
if k > n / 2 then binomial(n; n-k) |
||
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i) |
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i) |
||
Line 972: | Line 1,284: | ||
# Direct (naive) computation using two numbers in Pascal's triangle: |
# 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);</ |
def catalan_by_pascal: . as $n | binomial(2*$n; $n) - binomial(2*$n; $n-1);</syntaxhighlight> |
||
'''Example''': |
'''Example''': |
||
(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal] |
(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal] |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -n -c -f Catalan_numbers_Pascal.jq |
||
[0,0] |
[0,0] |
||
[1,1] |
[1,1] |
||
Line 997: | Line 1,309: | ||
[31,14544636039226880] |
[31,14544636039226880] |
||
[510,5.491717746183512e+302] |
[510,5.491717746183512e+302] |
||
[511,null]</ |
[511,null]</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Matlab}} |
{{trans|Matlab}} |
||
< |
<syntaxhighlight lang="julia"># v0.6 |
||
function pascal(n::Int) |
function pascal(n::Int) |
||
Line 1,016: | Line 1,327: | ||
end |
end |
||
@show catalan_num(15)</ |
@show catalan_num(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>catalan_num(15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
<pre>catalan_num(15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 1,046: | Line 1,356: | ||
val n = 15 |
val n = 15 |
||
catalanFromPascal(n * 2) |
catalanFromPascal(n * 2) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,066: | Line 1,376: | ||
15 : 9694845 |
15 : 9694845 |
||
</pre> |
</pre> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
For each line of odd-numbered length from Pascal's triangle, print the middle number minus the one immediately to its right. |
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. |
This solution is heavily based on the Lua code to generate Pascal's triangle from the page for that task. |
||
< |
<syntaxhighlight lang="lua">function nextrow (t) |
||
local ret = {} |
local ret = {} |
||
t[0], t[#t + 1] = 0, 0 |
t[0], t[#t + 1] = 0, 0 |
||
Line 1,086: | Line 1,395: | ||
end |
end |
||
catalans(15)</ |
catalans(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre> |
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre> |
||
Line 1,099: | Line 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). |
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"> |
|||
<lang M2000 Interpreter> |
|||
Module CatalanNumbers { |
Module CatalanNumbers { |
||
Def Integer count, t_row, size=31 |
Def Integer count, t_row, size=31 |
||
Line 1,133: | Line 1,442: | ||
} |
} |
||
CatalanNumbers |
CatalanNumbers |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,152: | Line 1,461: | ||
15: 9694845 |
15: 9694845 |
||
</pre> |
</pre> |
||
=={{header|Maple}}== |
|||
<syntaxhighlight lang="maple">catalan:=proc(n) |
|||
local i,a:=[1],C:=[1]; |
|||
for i to n do |
|||
a:=[0,op(a)]+[op(a),0]; |
|||
a:=[0,op(a)]+[op(a),0]; |
|||
C:=[op(C),a[i+1]-a[i]]; |
|||
od; |
|||
C |
|||
end: |
|||
catalan(10); |
|||
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]</syntaxhighlight> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="mathematica">nextrow[lastrow_] := Module[{output}, |
||
output = ConstantArray[1, Length[lastrow] + 1]; |
output = ConstantArray[1, Length[lastrow] + 1]; |
||
Do[ |
Do[ |
||
Line 1,171: | Line 1,492: | ||
] |
] |
||
(* testing *) |
(* testing *) |
||
catalannumbers[15]</ |
catalannumbers[15]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}</pre> |
<pre>{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}</pre> |
||
=={{header|MATLAB}} / {{header|Octave}}== |
=={{header|MATLAB}} / {{header|Octave}}== |
||
< |
<syntaxhighlight lang="matlab">n = 15; |
||
p = pascal(n + 2); |
p = pascal(n + 2); |
||
p(n + 4 : n + 3 : end - 1)' - diag(p, 2)</ |
p(n + 4 : n + 3 : end - 1)' - diag(p, 2)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>ans = |
<pre>ans = |
||
Line 1,197: | Line 1,517: | ||
2674440 |
2674440 |
||
9694845</pre> |
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}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">const n = 15 |
||
var t = newSeq[int](n + 2) |
var t = newSeq[int](n + 2) |
||
Line 1,208: | Line 1,541: | ||
t[i+1] = t[i] |
t[i+1] = t[i] |
||
for j in countdown(i+1, 1): t[j] += t[j-1] |
for j in countdown(i+1, 1): t[j] += t[j-1] |
||
stdout.write t[i+1] - t[i], " " |
stdout.write t[i+1] - t[i], " " |
||
stdout.write '\n'</syntaxhighlight> |
|||
{{Out}} |
{{Out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml"> |
||
let catalan : int ref = ref 0 in |
let catalan : int ref = ref 0 in |
||
Printf.printf "%d ," 1 ; |
Printf.printf "%d ," 1 ; |
||
Line 1,226: | Line 1,559: | ||
print_int (!catalan); print_string "," ; |
print_int (!catalan); print_string "," ; |
||
done;; |
done;; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,232: | Line 1,565: | ||
1 ,2,5,14,42,132,429,1430,4862 |
1 ,2,5,14,42,132,429,1430,4862 |
||
</pre> |
</pre> |
||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang="oforth">import: mapping |
||
: pascal( n -- [] ) |
: pascal( n -- [] ) |
||
Line 1,241: | Line 1,573: | ||
: catalan( n -- m ) |
: catalan( n -- m ) |
||
n 2 * pascal at( n 1+ ) n 1+ / ;</ |
n 2 * pascal at( n 1+ ) n 1+ / ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,248: | Line 1,580: | ||
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845] |
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845] |
||
</pre> |
</pre> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">vector(15,n,binomial(2*n,n)-binomial(2*n,n+1))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
<pre>%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang="pascal"> |
||
Program CatalanNumbers |
|||
type |
|||
tElement = Uint64; |
tElement = Uint64; |
||
var |
var |
||
Line 1,289: | Line 1,621: | ||
For i := 1 to L do |
For i := 1 to L do |
||
Writeln(i:3,Catalan[i]:20); |
Writeln(i:3,Catalan[i]:20); |
||
end.</ |
end.</syntaxhighlight> |
||
<pre> 1 1 |
<pre> 1 1 |
||
2 2 |
2 2 |
||
Line 1,307: | Line 1,639: | ||
</pre> |
</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="perl">use constant N => 15; |
||
my @t = (0, 1); |
my @t = (0, 1); |
||
for(my $i = 1; $i <= N; $i++) { |
for(my $i = 1; $i <= N; $i++) { |
||
Line 1,317: | Line 1,648: | ||
for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] } |
for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] } |
||
print $t[$i+1] - $t[$i], " "; |
print $t[$i+1] - $t[$i], " "; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
Line 1,323: | Line 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: |
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}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/binomial/; |
||
print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</ |
print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</syntaxhighlight> |
||
The <tt>Math::Pari</tt> module also has a binomial, but isn't as fast and overflows its stack after 3400. |
The <tt>Math::Pari</tt> module also has a binomial, but isn't as fast and overflows its stack after 3400. |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2015.12}} |
|||
<lang perl6>constant @pascal = [1], -> @p { [0, |@p Z+ |@p, 0] } ... *; |
|||
constant @catalan = gather for 2, 4 ... * -> $ix { |
|||
my @row := @pascal[$ix]; |
|||
my $mid = +@row div 2; |
|||
take [-] @row[$mid, $mid+1] |
|||
} |
|||
.say for @catalan[^20];</lang> |
|||
{{out}} |
|||
<pre>1 |
|||
2 |
|||
5 |
|||
14 |
|||
42 |
|||
132 |
|||
429 |
|||
1430 |
|||
4862 |
|||
16796 |
|||
58786 |
|||
208012 |
|||
742900 |
|||
2674440 |
|||
9694845 |
|||
35357670 |
|||
129644790 |
|||
477638700 |
|||
1767263190 |
|||
6564120420</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example |
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>constant N = 15 -- accurate to 30, nan/inf for anything over 514 (bigatom version is below). |
|||
<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> |
|||
sequence catalan = {}, -- (>=1 only) |
|||
<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> |
|||
p = repeat(1,N+1) |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</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> |
|||
atom p1 |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">p1</span> |
|||
for i=1 to N do |
|||
<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> |
|||
p1 = p[1]*2 |
|||
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">2</span> |
|||
catalan = append(catalan,p1-p[2]) |
|||
<span style="color: #000000;">catalan</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalan</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> |
|||
for j=1 to N-i+1 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
p1 += p[j+1] |
|||
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
p[j] = p1 |
|||
<span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p1</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
-- ?p[1..N-i+1] |
|||
<span style="color: #000080;font-style:italic;">-- ?p[1..N-i+1]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
?catalan</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">catalan</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,382: | Line 1,681: | ||
</pre> |
</pre> |
||
Explanatory comments to accompany the above |
Explanatory comments to accompany the above |
||
< |
<syntaxhighlight lang="phix">-- FreeBASIC said: |
||
--' 1 1 1 1 1 1 |
--' 1 1 1 1 1 1 |
||
--' 1 2 3 4 5 6 |
--' 1 2 3 4 5 6 |
||
Line 1,414: | Line 1,713: | ||
-- 10 15 21 |
-- 10 15 21 |
||
-- 35 56 |
-- 35 56 |
||
-- 126 (unused)</ |
-- 126 (unused)</syntaxhighlight> |
||
The following bigatom version is over ten times faster than the equivalent on [[Catalan_numbers#Phix|Catalan_numbers]] |
|||
{{libheader|bigatom}} |
|||
<lang Phix>include builtins\bigatom.e |
|||
=== gmp version === |
|||
function catalanB(integer n) -- very very fast! |
|||
{{libheader|Phix/mpfr}} |
|||
sequence catalan = {}, |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
p = repeat(1,n+1) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
bigatom p1 |
|||
<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> |
|||
if n=0 then return 1 end if |
|||
for i=1 to n do |
|||
p1 = ba_multiply(p[1],2) |
|||
catalan = append(catalan,ba_sub(p1,p[2])) |
|||
for j=1 to n-i+1 do |
|||
p1 = ba_add(p1,p[j+1]) |
|||
p[j] = p1 |
|||
end for |
|||
end for |
|||
return catalan[n] |
|||
end function |
|||
<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> |
|||
atom t0 = time() |
|||
<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> |
|||
string sc100 = ba_sprint(catalanB(100)) |
|||
<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> |
|||
printf(1,"%d: %s (%3.2fs)\n",{100,sc100,time()-t0}) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
atom t0 = time() |
|||
<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> |
|||
string sc250 = ba_sprint(catalanB(250)) |
|||
<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> |
|||
printf(1,"%d: %s (%3.2fs)\n",{250,sc250,time()-t0})</lang> |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalan</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">catalan</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> |
|||
<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\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalanB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</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;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">250</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalanB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">250</span><span style="color: #0000FF;">)))})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
100: 89651994709013149668...20837521538745909320 (57 digits) |
|||
100: 896519947090131496687170070074100632420837521538745909320 (0.08s) |
|||
250: 46511679596923379649...69029457769094808256 (147 digits) |
|||
250: 465116795969233796497747947259667807407291160080922096111953326525143875193659257831340309862635877995262413955019878805418475969029457769094808256 (1.01s) |
|||
</pre> |
|||
The above is significantly faster than the equivalent(s) on [[Catalan_numbers#Phix|Catalan_numbers]], |
|||
a quick comparison showing the latter getting exponentially worse (then again I memoised the slowest recursive version): |
|||
<pre> |
|||
800 2000 4000 8000 |
|||
catalanB: 0.6s 3.5s 14.5s 64s |
|||
catalan2m: 0.7s 7.0s 64.9s 644s |
|||
</pre> |
</pre> |
||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de bino (N K) |
||
(let f |
(let f |
||
'((N) |
'((N) |
||
Line 1,461: | Line 1,766: | ||
(bino (* 2 N) N) |
(bino (* 2 N) N) |
||
(bino (* 2 N) (inc N)) ) ) ) |
(bino (* 2 N) (inc N)) ) ) ) |
||
(bye)</ |
(bye)</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="purebasic">#MAXNUM = 15 |
||
Declare catalan() |
Declare catalan() |
||
Line 1,490: | Line 1,794: | ||
Print(Str(cat)+" ") |
Print(Str(cat)+" ") |
||
Next |
Next |
||
EndProcedure</ |
EndProcedure</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
|||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="python">>>> n = 15 |
||
>>> t = [0] * (n + 2) |
>>> t = [0] * (n + 2) |
||
>>> t[1] = 1 |
>>> t[1] = 1 |
||
Line 1,508: | Line 1,812: | ||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
>>> </ |
>>> </syntaxhighlight> |
||
{{Works with|Python|2.7}} |
{{Works with|Python|2.7}} |
||
< |
<syntaxhighlight lang="python">def catalan_number(n): |
||
nm = dm = 1 |
nm = dm = 1 |
||
for k in range(2, n+1): |
for k in range(2, n+1): |
||
Line 1,519: | Line 1,823: | ||
print [catalan_number(n) for n in range(1, 16)] |
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]</ |
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</syntaxhighlight> |
||
===Composition of pure functions=== |
|||
Note that sequence [[oeis:A000108|A000108]] on OEIS (referenced in the task description) confirms that the first four Catalan numbers are indeed 1, 1, 2, 5 ... |
|||
(Several scripts on this page appear to lose the first 1). |
|||
{{Trans|Haskell}} |
|||
{{Works with|Python|3.7}} |
|||
<syntaxhighlight lang="python">'''Catalan numbers from Pascal's triangle''' |
|||
from itertools import (islice) |
|||
from operator import (add) |
|||
# nCatalans :: Int -> [Int] |
|||
def nCatalans(n): |
|||
'''The first n Catalan numbers, |
|||
derived from Pascal's triangle.''' |
|||
# diff :: [Int] -> Int |
|||
def diff(xs): |
|||
'''Difference between the first two items in the list, |
|||
if its length is more than one. |
|||
Otherwise, the first (only) item in the list.''' |
|||
return ( |
|||
xs[0] - (xs[1] if 1 < len(xs) else 0) |
|||
) if xs else None |
|||
return list(map( |
|||
compose(diff)(uncurry(drop)), |
|||
enumerate(map(fst, take(n)( |
|||
everyOther( |
|||
pascalTriangle() |
|||
) |
|||
))) |
|||
)) |
|||
# pascalTriangle :: Gen [[Int]] |
|||
def pascalTriangle(): |
|||
'''A non-finite stream of |
|||
Pascal's triangle rows.''' |
|||
return iterate(nextPascal)([1]) |
|||
# nextPascal :: [Int] -> [Int] |
|||
def nextPascal(xs): |
|||
'''A row of Pascal's triangle |
|||
derived from a preceding row.''' |
|||
return zipWith(add)([0] + xs)(xs + [0]) |
|||
# TEST ---------------------------------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''First 16 Catalan numbers.''' |
|||
print( |
|||
nCatalans(16) |
|||
) |
|||
# GENERIC ------------------------------------------------- |
|||
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c |
|||
def compose(g): |
|||
'''Right to left function composition.''' |
|||
return lambda f: lambda x: g(f(x)) |
|||
# drop :: Int -> [a] -> [a] |
|||
# drop :: Int -> String -> String |
|||
def drop(n): |
|||
'''The sublist of xs beginning at |
|||
(zero-based) index n.''' |
|||
def go(xs): |
|||
if isinstance(xs, list): |
|||
return xs[n:] |
|||
else: |
|||
take(n)(xs) |
|||
return xs |
|||
return lambda xs: go(xs) |
|||
# everyOther :: Gen [a] -> Gen [a] |
|||
def everyOther(g): |
|||
'''Every other item of a generator stream.''' |
|||
while True: |
|||
yield take(1)(g) |
|||
take(1)(g) # Consumed, not yielded. |
|||
# fst :: (a, b) -> a |
|||
def fst(tpl): |
|||
'''First component of a pair.''' |
|||
return tpl[0] |
|||
# iterate :: (a -> a) -> a -> Gen [a] |
|||
def iterate(f): |
|||
'''An infinite list of repeated applications of f to x.''' |
|||
def go(x): |
|||
v = x |
|||
while True: |
|||
yield v |
|||
v = f(v) |
|||
return lambda x: go(x) |
|||
# take :: Int -> [a] -> [a] |
|||
# take :: Int -> String -> String |
|||
def take(n): |
|||
'''The prefix of xs of length n, |
|||
or xs itself if n > length xs.''' |
|||
return lambda xs: ( |
|||
xs[0:n] |
|||
if isinstance(xs, list) |
|||
else list(islice(xs, n)) |
|||
) |
|||
# uncurry :: (a -> b -> c) -> ((a, b) -> c) |
|||
def uncurry(f): |
|||
'''A function over a tuple |
|||
derived from a curried function.''' |
|||
return lambda xy: f(xy[0])( |
|||
xy[1] |
|||
) |
|||
# zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
def zipWith(f): |
|||
'''A list constructed by zipping with a |
|||
custom function, rather than with the |
|||
default tuple constructor.''' |
|||
return lambda xs: lambda ys: ( |
|||
list(map(f, xs, ys)) |
|||
) |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{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}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
Line 1,534: | Line 2,002: | ||
;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 |
;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 |
||
;; 2674440 9694845) |
;; 2674440 9694845) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2015.12}} |
|||
<syntaxhighlight lang="raku" line>constant @pascal = [1], -> @p { [0, |@p Z+ |@p, 0] } ... *; |
|||
constant @catalan = gather for 2, 4 ... * -> $ix { |
|||
my @row := @pascal[$ix]; |
|||
my $mid = +@row div 2; |
|||
take [-] @row[$mid, $mid+1] |
|||
} |
|||
.say for @catalan[^20];</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 |
|||
2 |
|||
5 |
|||
14 |
|||
42 |
|||
132 |
|||
429 |
|||
1430 |
|||
4862 |
|||
16796 |
|||
58786 |
|||
208012 |
|||
742900 |
|||
2674440 |
|||
9694845 |
|||
35357670 |
|||
129644790 |
|||
477638700 |
|||
1767263190 |
|||
6564120420</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===explicit subscripts=== |
===explicit subscripts=== |
||
All of the REXX program examples can handle arbitrary large numbers. |
All of the REXX program examples can handle arbitrary large numbers. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,549: | Line 2,049: | ||
@.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k*/ |
@.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. */ |
say @.ip - @.i /*display the Ith Catalan number. */ |
||
end /*i*/ /*stick a fork in it, we're all done. */</ |
end /*i*/ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
'''output''' when using the default input: |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
Line 1,570: | Line 2,070: | ||
===implicit subscripts=== |
===implicit subscripts=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,582: | Line 2,082: | ||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
@: parse arg !; return @.! /*return the value of @.[arg(1)] */</ |
@: parse arg !; return @.! /*return the value of @.[arg(1)] */</syntaxhighlight> |
||
'''output''' is the same as the 1<sup>st</sup> version. |
'''output''' is the same as the 1<sup>st</sup> version. |
||
===using binomial coefficients=== |
===using binomial coefficients=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,598: | Line 2,098: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 |
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)</ |
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</syntaxhighlight> |
||
'''output''' is the same as the 1<sup>st</sup> version. |
'''output''' is the same as the 1<sup>st</sup> version. |
||
===binomial coefficients, memoized=== |
===binomial coefficients, memoized=== |
||
This REXX version uses memoization for the calculation of factorials. |
This REXX version uses memoization for the calculation of factorials. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,617: | Line 2,117: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
comb: procedure expose !.; parse arg x,y; if x=y then return 1; if y>x then return 0 |
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)</ |
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</syntaxhighlight> |
||
'''output''' is the same as the 1<sup>st</sup> version. <br><br> |
'''output''' is the same as the 1<sup>st</sup> version. <br><br> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
n=15 |
n=15 |
||
cat = list(n+2) |
cat = list(n+2) |
||
Line 1,635: | Line 2,134: | ||
see "" + (cat[i+1]-cat[i]) + " " |
see "" + (cat[i+1]-cat[i]) + " " |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</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}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="tcl">def catalan(num) |
||
t = [0, 1] #grows as needed |
t = [0, 1] #grows as needed |
||
(1..num).map do |i| |
(1..num).map do |i| |
||
Line 1,652: | Line 2,199: | ||
end |
end |
||
p catalan(15)</ |
p catalan(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,659: | Line 2,206: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic">n = 15 |
||
dim t(n+2) |
dim t(n+2) |
||
t(1) = 1 |
t(1) = 1 |
||
Line 1,667: | Line 2,214: | ||
for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j |
for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j |
||
print t(i+1) - t(i);" "; |
print t(i+1) - t(i);" "; |
||
next i</ |
next i</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
fn main() |
fn main() |
||
Line 1,701: | Line 2,247: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">def catalan(n: Int): Int = |
||
if (n <= 1) 1 |
if (n <= 1) 1 |
||
else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum |
else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum |
||
(1 to 15).map(catalan(_))</ |
(1 to 15).map(catalan(_))</syntaxhighlight> |
||
{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/2ybpRZxCTOyrx3mIy8yIDw Scastie (JVM)]. |
{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/2ybpRZxCTOyrx3mIy8yIDw Scastie (JVM)]. |
||
=={{header|Scilab}}== |
=={{header|Scilab}}== |
||
<lang>n=15 |
<syntaxhighlight lang="text">n=15 |
||
t=zeros(1,n+2) |
t=zeros(1,n+2) |
||
t(1)=1 |
t(1)=1 |
||
Line 1,725: | Line 2,270: | ||
end |
end |
||
disp(t(i+1)-t(i)) |
disp(t(i+1)-t(i)) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:20ex"> 1. |
<pre style="height:20ex"> 1. |
||
Line 1,742: | Line 2,287: | ||
2674440. |
2674440. |
||
9694845. </pre> |
9694845. </pre> |
||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const proc: main is func |
const proc: main is func |
||
Line 1,764: | Line 2,308: | ||
end for; |
end for; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,770: | Line 2,314: | ||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="ruby">func catalan(num) { |
||
var t = [0, 1] |
var t = [0, 1] |
||
(1..num).map { |i| |
(1..num).map { |i| |
||
Line 1,783: | Line 2,326: | ||
} |
} |
||
say catalan(15).join(' ')</ |
say catalan(15).join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|smart BASIC}}== |
=={{header|smart BASIC}}== |
||
< |
<syntaxhighlight lang="qbasic">PRINT "Catalan Numbers from Pascal's Triangle"!PRINT |
||
x = 15 |
x = 15 |
||
DIM t(x+2) |
DIM t(x+2) |
||
Line 1,801: | Line 2,343: | ||
NEXT m |
NEXT m |
||
PRINT n,"#######":t(n+1) - t(n) |
PRINT n,"#######":t(n+1) - t(n) |
||
NEXT n</ |
NEXT n</syntaxhighlight> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">proc catalan n { |
||
set result {} |
set result {} |
||
array set t {0 0 1 1} |
array set t {0 0 1 1} |
||
Line 1,816: | Line 2,357: | ||
} |
} |
||
puts [catalan 15]</ |
puts [catalan 15]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|TI-83 BASIC}}== |
=={{header|TI-83 BASIC}}== |
||
< |
<syntaxhighlight lang="ti83b">"CATALAN |
||
15→N |
15→N |
||
seq(0,I,1,N+2)→L1 |
seq(0,I,1,N+2)→L1 |
||
Line 1,834: | Line 2,374: | ||
End |
End |
||
Disp L1(I+1)-L1(I) |
Disp L1(I+1)-L1(I) |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 |
<pre> 1 |
||
Line 1,852: | Line 2,392: | ||
9694845 |
9694845 |
||
Done </pre> |
Done </pre> |
||
=={{header|Vala}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="vala">void main() { |
|||
const int N = 15; |
|||
uint64[] t = {0, 1}; |
|||
for (int i = 1; i <= N; i++) { |
|||
for (int j = i; j > 1; j--) t[j] = t[j] + t[j - 1]; |
|||
t[i + 1] = t[i]; |
|||
for (int j = i + 1; j > 1; j--) t[j] = t[j] + t[j - 1]; |
|||
print(@"$(t[i + 1] - t[i]) "); |
|||
} |
|||
print("\n"); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
|||
</pre> |
|||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
To run in console mode with cscript. |
To run in console mode with cscript. |
||
< |
<syntaxhighlight lang="vbscript">dim t() |
||
if Wscript.arguments.count=1 then |
if Wscript.arguments.count=1 then |
||
n=Wscript.arguments.item(0) |
n=Wscript.arguments.item(0) |
||
Line 1,874: | Line 2,431: | ||
next 'j |
next 'j |
||
Wscript.echo t(i+1)-t(i) |
Wscript.echo t(i+1)-t(i) |
||
next 'i</ |
next 'i</syntaxhighlight> |
||
=={{header|Visual Basic}}== |
=={{header|Visual Basic}}== |
||
{{trans|Rexx}} |
{{trans|Rexx}} |
||
{{works with|Visual Basic|VB6 Standard}} |
{{works with|Visual Basic|VB6 Standard}} |
||
<syntaxhighlight lang="vb"> |
|||
<lang vb> |
|||
Sub catalan() |
Sub catalan() |
||
Const n = 15 |
Const n = 15 |
||
Line 1,896: | Line 2,452: | ||
Next i |
Next i |
||
End Sub 'catalan |
End Sub 'catalan |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre style="height:20ex"> |
<pre style="height:20ex"> |
||
Line 1,914: | Line 2,470: | ||
2674440 |
2674440 |
||
9694845 |
9694845 |
||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="wren">var n = 15 |
|||
var t = List.filled(n+2, 0) |
|||
t[1] = 1 |
|||
for (i in 1..n) { |
|||
if (i > 1) for (j in i..2) t[j] = t[j] + t[j-1] |
|||
t[i+1] = t[i] |
|||
if (i > 0) for (j in i+1..2) t[j] = t[j] + t[j-1] |
|||
System.write("%(t[i+1]-t[i]) ") |
|||
} |
|||
System.print()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
|||
</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) { |
|||
const row = binomial(n * 2).?; |
|||
try stdout.print("{d:2} {d:8}\n", .{ n, row[n] - row[n + 1] }); |
|||
} |
|||
} |
|||
pub fn binomial(n: u32) ?[]const u64 { |
|||
if (n >= rmax) |
|||
return null |
|||
else { |
|||
const k = n * (n + 1) / 2; |
|||
return pascal[k .. k + n + 1]; |
|||
} |
|||
} |
|||
const rmax = 68; |
|||
// evaluated and created at compile-time |
|||
const pascal = build: { |
|||
@setEvalBranchQuota(100_000); |
|||
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined; |
|||
coefficients[0] = 1; |
|||
var j: u32 = 0; |
|||
var k: u32 = 1; |
|||
var n: u32 = 1; |
|||
while (n < rmax) : (n += 1) { |
|||
var prev = coefficients[j .. j + n]; |
|||
var next = coefficients[k .. k + n + 1]; |
|||
next[0] = 1; |
|||
var i: u32 = 1; |
|||
while (i < n) : (i += 1) |
|||
next[i] = prev[i] + prev[i - 1]; |
|||
next[i] = 1; |
|||
j = k; |
|||
k += n + 1; |
|||
} |
|||
break :build coefficients; |
|||
}; |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
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> |
</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|PARI/GP}} using binomial coefficients. |
{{trans|PARI/GP}} using binomial coefficients. |
||
< |
<syntaxhighlight lang="zkl">fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) } |
||
(1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</ |
(1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
L(1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845) |
L(1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845) |
||
</pre> |
</pre> |
||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="zxbasic">10 LET N=15 |
||
20 DIM t(N+2) |
20 DIM t(N+2) |
||
30 LET t(2)=1 |
30 LET t(2)=1 |
||
Line 1,935: | Line 2,589: | ||
70 FOR j=i+1 TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j |
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);" "; |
80 PRINT t(i+1)-t(i);" "; |
||
90 NEXT i</ |
90 NEXT i</syntaxhighlight> |
Latest revision as of 12:10, 12 November 2023
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Print out the first 15 Catalan numbers by extracting them from Pascal's triangle.
- See
- Catalan Numbers and the Pascal Triangle. This method enables calculation of Catalan Numbers using only addition and subtraction.
- Catalan's Triangle for a Number Triangle that generates Catalan Numbers using only addition.
- Sequence A000108 on OEIS has a lot of information on Catalan Numbers.
- Related Tasks
11l
V n = 15
V t = [0] * (n + 2)
t[1] = 1
L(i) 1 .. n
L(j) (i .< 1).step(-1)
t[j] += t[j - 1]
t[i + 1] = t[i]
L(j) (i + 1 .< 1).step(-1)
t[j] += t[j - 1]
print(t[i + 1] - t[i], end' ‘ ’)
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
360 Assembly
For maximum compatibility, this program uses only the basic instruction set.
CATALAN CSECT
USING CATALAN,R13,R12
SAVEAREA B STM-SAVEAREA(R15)
DC 17F'0'
DC CL8'CATALAN'
STM STM R14,R12,12(R13)
ST R13,4(R15)
ST R15,8(R13)
LR R13,R15
LA R12,4095(R13)
LA R12,1(R12)
* ---- CODE
LA R0,1
ST R0,T t(1)=1
LA R4,0 ix:i=1
LA R6,1 by 1
LH R7,N to n
LOOPI BXH R4,R6,ENDLOOPI loop i
LR R5,R4 ix:j=i+1
LA R5,2(R5) i+2
LA R8,0
BCTR R8,0 by -1
LA R9,1 to 2
LOOP1J BXLE R5,R8,ENLOOP1J loop j
LR R10,R5 j
BCTR R10,0
SLA R10,2
L R2,T(R10) r2=t(j)
LR R1,R10 j
SH R1,=H'4'
L R3,T(R1) r3=t(j-1)
AR R2,R3 r2=r2+r3
ST R2,T(R10) t(j)=t(j)+t(j-1)
B LOOP1J
ENLOOP1J EQU *
LR R1,R4 i
BCTR R1,0
SLA R1,2
L R3,T(R1) t(i)
LA R1,4(R1)
ST R3,T(R1) t(i+1)
LR R5,R4 ix:j=i+2
LA R5,3(R5) i+3
LA R8,0
BCTR R8,0 by -1
LA R9,1 to 2
LOOP2J BXLE R5,R8,ENLOOP2J loop j
LR R10,R5 j
BCTR R10,0
SLA R10,2
L R2,T(R10) r2=t(j)
LR R1,R10 j
SH R1,=H'4'
L R3,T(R1) r3=t(j-1)
AR R2,R3 r2=r2+r3
ST R2,T(R10) t(j)=t(j)+t(j-1)
B LOOP2J
ENLOOP2J EQU *
LR R1,R4 i
BCTR R1,0
SLA R1,2
L R2,T(R1) t(i)
LA R1,4(R1)
L R3,T(R1) t(i+1)
SR R3,R2
CVD R3,P
UNPK Z,P
MVC C,Z
OI C+L'C-1,X'F0'
MVC WTOBUF(8),C+8
WTO MF=(E,WTOMSG)
B LOOPI
ENDLOOPI EQU *
* ---- END CODE
CNOP 0,4
L R13,4(0,R13)
LM R14,R12,12(R13)
XR R15,R15
BR R14
* ---- DATA
N DC H'15'
T DC 17F'0'
P DS PL8
Z DS ZL16
C DS CL16
WTOMSG DS 0F
DC H'80'
DC H'0'
WTOBUF DC CL80' '
YREGS
END
- Output:
00000001 00000002 00000005 00000014 00000042 00000132 00000429 00001430 00004862 00016796 00058786 00208012 00742900 02674440 09694845
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
- Output:
Screenshot from Atari 8-bit computer
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
Ada
Uses package Pascal from the Pascal triangle solution[[1]]
with Ada.Text_IO, Pascal;
procedure Catalan is
Last: Positive := 15;
Row: Pascal.Row := Pascal.First_Row(2*Last+1);
begin
for I in 1 .. Last loop
Row := Pascal.Next_Row(Row);
Row := Pascal.Next_Row(Row);
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2)));
end loop;
end Catalan;
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
ALGOL 68
INT n = 15;
[ 0 : n + 1 ]INT t;
t[0] := 0;
t[1] := 1;
FOR i TO n DO
FOR j FROM i BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD;
t[i+1] := t[i];
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
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
ALGOL W
begin
% print the first 15 Catalan numbers from Pascal's triangle %
integer n;
n := 15;
begin
integer array pascalLine ( 1 :: n + 1 );
% the Catalan numbers are the differences between the middle and middle - 1 numbers of the odd %
% lines of Pascal's triangle (lines with 3 or more numbers) %
% note - we only need to calculate the left side of the triangle %
pascalLine( 1 ) := 1;
for c := 2 until n + 1 do begin
% even line %
for i := c - 1 step -1 until 2 do pascalLine( i ) := pascalLine( i - 1 ) + pascalLine( i );
pascalLine( c ) := pascalLine( c - 1 );
% odd line %
for i := c step -1 until 2 do pascalLine( i ) := pascalLine( i - 1 ) + pascalLine( i );
writeon( i_w := 1, s_w := 0, " ", pascalLine( c ) - pascalLine( c - 1 ) )
end for_c
end
end.
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
APL
⍝ Based heavily on the J solution
CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2}
- Output:
CATALAN 15 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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 ""
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
AutoHotkey
/* Generate Catalan Numbers
//
// smgs: 20th Feb, 2014
*/
Array := [], Array[2,1] := Array[2,2] := 1 ; Array inititated and 2nd row of pascal's triangle assigned
INI := 3 ; starts with calculating the 3rd row and as such the value
Loop, 31 ; every odd row is taken for calculating catalan number as such to obtain 15 we need 2n+1
{
if ( A_index > 2 )
{
Loop, % A_INDEX
{
old := ini-1, index := A_index, index_1 := A_index + 1
Array[ini, index_1] := Array[old, index] + Array[old, index_1]
Array[ini, 1] := Array[ini, ini] := 1
line .= Array[ini, A_index] " "
}
;~ MsgBox % line ; gives rows of pascal's triangle
; calculating every odd row starting from 1st so as to obtain catalan's numbers
if ( mod(ini,2) != 0)
{
StringSplit, res, line, %A_Space%
ans := res0//2, ans_1 := ans++
result := result . res%ans_1% - res%ans% " "
}
line :=
ini++
}
}
MsgBox % result
- Produces:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
AWK
# syntax: GAWK -f CATALAN_NUMBERS_PASCALS_TRIANGLE.AWK
# converted from C
BEGIN {
printf("1")
for (n=2; n<=15; n++) {
num = den = 1
for (k=2; k<=n; k++) {
num *= (n + k)
den *= k
catalan = num / den
}
printf(" %d",catalan)
}
printf("\n")
exit(0)
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
BASIC
Applesoft BASIC
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
Chipmunk Basic
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
GW-BASIC
The GW-BASIC solution works without any changes.
MSX Basic
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
- Output:
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
QBasic
The MSX-BASIC solution works without any changes.
XBasic
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
Yabasic
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
Batch File
@echo off
setlocal ENABLEDELAYEDEXPANSION
set n=15
set /A nn=n+1
for /L %%i in (0,1,%nn%) do set t.%%i=0
set t.1=1
for /L %%i in (1,1,%n%) do (
set /A ip=%%i+1
for /L %%j in (%%i,-1,1) do (
set /A jm=%%j-1
set /A t.%%j=t.%%j+t.!jm!
)
set /A t.!ip!=t.%%i
for /L %%j in (!ip!,-1,1) do (
set /A jm=%%j-1
set /A t.%%j=t.%%j+t.!jm!
)
set /A ci=t.!ip!-t.%%i
echo !ci!
)
)
pause
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
C
//This code implements the print of 15 first Catalan's Numbers
//Formula used:
// __n__
// | | (n + k) / k n>0
// k=2
#include <stdio.h>
#include <stdlib.h>
//the number of Catalan's Numbers to be printed
const int N = 15;
int main()
{
//loop variables (in registers)
register int k, n;
//necessarily ull for reach big values
unsigned long long int num, den;
//the nmmber
int catalan;
//the first is not calculated for the formula
printf("1 ");
//iterating from 2 to 15
for (n=2; n<=N; ++n) {
//initializaing for products
num = den = 1;
//applying the formula
for (k=2; k<=n; ++k) {
num *= (n+k);
den *= k;
catalan = num /den;
}
//output
printf("%d ", catalan);
}
//the end
printf("\n");
return 0;
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
C#
int n = 15;
List<int> t = new List<int>() { 0, 1 };
for (int i = 1; i <= n; i++)
{
for (var j = i; j > 1; j--) t[j] += t[j - 1];
t.Add(t[i]);
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1];
Console.Write(((i == 1) ? "" : ", ") + (t[i + 1] - t[i]));
}
- Produces:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
C++
// Generate Catalan Numbers
//
// Nigel Galloway: June 9th., 2012
//
#include <iostream>
int main() {
const int N = 15;
int t[N+2] = {0,1};
for(int i = 1; i<=N; i++){
for(int j = i; j>1; j--) t[j] = t[j] + t[j-1];
t[i+1] = t[i];
for(int j = i+1; j>1; j--) t[j] = t[j] + t[j-1];
std::cout << t[i+1] - t[i] << " ";
}
return 0;
}
- Produces:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Common Lisp
(defun catalan (n)
"Return the n-th Catalan number"
(if (<= n 1) 1
(let ((result 2))
(dotimes (k (- n 2) result)
(setq result (* result (/ (+ n k 2) (+ k 2)))) ))))
(dotimes (n 15)
(print (catalan (1+ n))) )
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
D
void main() {
import std.stdio;
enum uint N = 15;
uint[N + 2] t;
t[1] = 1;
foreach (immutable i; 1 .. N + 1) {
foreach_reverse (immutable j; 2 .. i + 1)
t[j] += t[j - 1];
t[i + 1] = t[i];
foreach_reverse (immutable j; 2 .. i + 2)
t[j] += t[j - 1];
write(t[i + 1] - t[i], ' ');
}
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Delphi
See Pascal.
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
.
EchoLisp
(define dim 100)
(define-syntax-rule (Tidx i j) (+ i (* dim j)))
;; generates Catalan's triangle
;; T (i , j) = T(i-1,j) + T (i, j-1)
(define (T n)
(define i (modulo n dim))
(define j (quotient n dim))
(cond
((zero? i) 1) ;; left column = 1
((= i j) (T (Tidx (1- i) j))) ;; diagonal value = left value
(else (+ (T (Tidx (1- i) j)) (T (Tidx i (1- j)))))))
(remember 'T #(1))
- Output:
;; 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
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]
..PZ [blank tape and terminator]
T54K [refer to working array with 'C']
P300F [address of working array]
T46K [to call print subroutine with 'G N']
P56F [address of print subroutine]
[Modification of library subroutine P7.
Prints non-negative integer, up to 10 digits, right-justified.
55 locations, load at even address.]
E25KTN
GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@
TFH17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@
T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@
[Main program]
PK T200K GK
[Constants]
[0] PD [short constant 1]
[1] P2F [to inc address by 2]
[2] T#C [used in manufacturing EDSAC orders]
[3] MF [add to T order to make A order with same address]
[4] #F [set figures]
[5] &F [line feed]
[6] @F [carriage return]
[7] P7D [maximum n = 15]
[Variable]
[8] PF [n]
[Enter with acc = 0]
[9] O4@ [set teleprinter to figures]
T4#C T2#C T#C A@ TC [initialize first 3 terms to 1, 0, 0]
T8@ E58@ [set n := 0; jump to inc n and print C_n]
[Outer loop; here with n updated]
[17] TF A8@ [acc := latest n]
L1F A2@ T22@ [make and store order 'T 2n #C']
[22] T#C [sets term := 0; also used to test for end of loop]
A2@ [load 'T#C', initial value of order 31]
[Loop to convert e.g. (20, 15, 6, 1) to (35, 21, 7, 1); works left to right]
[24] U31@ A3@ U29@ A1@ T30@ [set up orders on next line]
[29] A#C A#C T#C [replaced by manufactured orders]
A31@ A1@ S22@ E38@ [inc address in order 31, jump out if done]
A22@ E24@ [not done, loop back]
[38] A22@ T48@ [initialize order 48]
[Loop to convert e.g. (35, 21, 7, 1) to (70, 56, 28, 8, 1); works right to left]
[40] TF A48@ A3@ U46@ S1@ T47@ [set up orders on next line]
[46] A#C A#C T#C [replaced by manufactured orders]
A48@ S1@ T48@ [dec address in order 48]
A2@ S48@ G40@ [test for done, loop back if not]
A#C LD T#C [double first term, e.g. 35 -> 70 (not done in loop)]
[Increment n and print Catalan number C_n]
[58] TD [clear 0D, ensures sandwich bit = 0]
A8@ A@ U8@ TF [inc n; set 0D := n by setting 0F := n]
A63@ GN [print n]
A#C S4#C TD A68@ GN [print Catalan number C_n, e.g. C_5 = 70 - 28 = 42]
O6@ O5@ [print CR, LF]
A8@ S7@ G17@ [test for maximum n, loop back if not]
[75] O4@ ZF [flush printer buffer; stop]
E9Z PF [define entry point; enter with acc = 0]
- Output:
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
Elixir
defmodule Catalan do
def numbers(num) do
{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} ->
t1 = numbers(i, t0)
t2 = numbers(i+1, Tuple.insert_at(t1, i+1, elem(t1, i)))
{[elem(t2, i+1) - elem(t2, i) | list], t2}
end)
Enum.reverse(result)
end
defp numbers(0, t), do: t
defp numbers(n, t), do: numbers(n-1, put_elem(t, n, elem(t, n-1) + elem(t, n)))
end
IO.inspect Catalan.numbers(15)
- Output:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
Erlang
-module(catalin).
-compile(export_all).
mul(N,D,S,S)->
N2=N*(S+S),
D2=D*S,
K = N2 div D2 ;
mul(N,D,S,L)->
N2=N*(S+L),
D2=D*L,
K = mul(N2,D2,S,L+1).
catl(Ans,16) -> Ans;
catl(D,S)->
C=mul(1,1,S,2),
catl([D|C],S+1).
main()->
Ans=catl(1,2).
ERRE
PROGRAM CATALAN
!$DOUBLE
DIM CATALAN[50]
FUNCTION ODD(X)
ODD=FRC(X/2)<>0
END FUNCTION
PROCEDURE GETCATALAN(L)
LOCAL J,K,W
LOCAL DIM PASTRI[100]
L=L*2
PASTRI[0]=1
J=0
WHILE J<L DO
J+=1
K=INT((J+1)/2)
PASTRI[K]=PASTRI[K-1]
FOR W=K TO 1 STEP -1 DO
PASTRI[W]+=PASTRI[W-1]
END FOR
IF NOT(ODD(J)) THEN
K=INT(J/2)
CATALAN[K]=PASTRI[K]-PASTRI[K-1]
END IF
END WHILE
END PROCEDURE
BEGIN
LL=15
GETCATALAN(LL)
FOR I=1 TO LL DO
WRITE("### ####################";I;CATALAN[I])
END FOR
END PROGRAM
- Output:
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
F#
let mutable nm=uint64(1)
let mutable dm=uint64(1)
let mutable a=uint64(1)
printf "1, "
for i = 2 to 15 do
nm<-uint64(1)
dm<-uint64(1)
for k = 2 to i do
nm <-uint64( uint64(nm) * (uint64(i)+uint64(k)))
dm <-uint64( uint64(dm) * uint64(k))
let a = uint64(uint64(nm)/uint64(dm))
printf "%u"a
if(i<>15) then
printf ", "
Factor
USING: arrays grouping io kernel math prettyprint sequences ;
IN: rosetta-code.catalan-pascal
: next-row ( seq -- seq' )
2 clump [ sum ] map 1 prefix 1 suffix ;
: pascal ( n -- seq )
1 - { { 1 } } swap [ dup last next-row suffix ] times ;
15 2 * pascal [ length odd? ] filter [
dup length 1 = [ 1 ]
[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if
pprint bl
] each drop
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
FreeBASIC
' version 15-09-2015
' compile with: fbc -s console
#Define size 31 ' (N * 2 + 1)
Sub pascal_triangle(rows As Integer, Pas_tri() As ULongInt)
Dim As Integer x, y
For x = 1 To rows
Pas_tri(1,x) = 1
Pas_tri(x,1) = 1
Next
For x = 2 To rows
For y = 2 To rows + 1 - x
Pas_tri(x, y) = pas_tri(x - 1 , y) + pas_tri(x, y - 1)
Next
Next
End Sub
' ------=< MAIN >=------
Dim As Integer count, row
Dim As ULongInt triangle(1 To size, 1 To size)
pascal_triangle(size, triangle())
' 1 1 1 1 1 1
' 1 2 3 4 5 6
' 1 3 6 10 15 21
' 1 4 10 20 35 56
' 1 5 15 35 70 126
' 1 6 21 56 126 252
' The Pascal triangle is rotated 45 deg.
' to find the Catalan number we need to follow the diagonal
' for top left to bottom right
' take the number on diagonal and subtract the number in de cell
' one up and one to right
' 1 (2 - 1), 2 (6 - 4), 5 (20 - 15) ...
Print "The first 15 Catalan numbers are" : print
count = 1 : row = 2
Do
Print Using "###: #########"; count; triangle(row, row) - triangle(row +1, row -1)
row = row + 1
count = count + 1
Loop Until count > 15
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
- Output:
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
Go
package main
import "fmt"
func main() {
const n = 15
t := [n + 2]uint64{0, 1}
for i := 1; i <= n; i++ {
for j := i; j > 1; j-- {
t[j] += t[j-1]
}
t[i+1] = t[i]
for j := i + 1; j > 1; j-- {
t[j] += t[j-1]
}
fmt.Printf("%2d : %d\n", i, t[i+1]-t[i])
}
}
- Output:
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
Groovy
class Catalan
{
public static void main(String[] args)
{
BigInteger N = 15;
BigInteger k,n,num,den;
BigInteger catalan;
print(1);
for(n=2;n<=N;n++)
{
num = 1;
den = 1;
for(k=2;k<=n;k++)
{
num = num*(n+k);
den = den*k;
catalan = num/den;
}
print(" " + catalan);
}
}
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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.
import System.Environment (getArgs)
-- Pascal's triangle.
pascal :: [[Integer]]
pascal = [1] : map (\row -> 1 : zipWith (+) row (tail row) ++ [1]) pascal
-- The Catalan numbers from Pascal's triangle. This uses a method from
-- http://www.cut-the-knot.org/arithmetic/algebra/CatalanInPascal.shtml
-- (see "Grimaldi").
catalan :: [Integer]
catalan = map (diff . uncurry drop) $ zip [0..] (alt pascal)
where alt (x:_:zs) = x : alt zs -- every other element of an infinite list
diff (x:y:_) = x - y
diff (x:_) = x
main :: IO ()
main = do
ns <- fmap (map read) getArgs :: IO [Int]
mapM_ (print . flip take catalan) ns
- Output:
./catalan 15 [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
Icon and Unicon
The following works in both languages. It avoids computing elements in Pascal's triangle that aren't used.
link math
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:
->cn 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 ->
J
Catalan=. }:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)
- Example use:
Catalan 15
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
A structured derivation of Catalan follows:
o=. @: NB. Composition of verbs (functions)
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70
( MiddleDiagonal=. (<0 1)&|: ) o PascalTriangle 5
1 2 6 20 70
( AdjacentLeft=. MiddleDiagonal o (2&|.) ) o PascalTriangle 5
1 4 15 1 5
( Catalan=. }: o (}. o MiddleDiagonal - }: o AdjacentLeft) o PascalTriangle o (2&+) f. ) 5
1 2 5 14 42
Catalan
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)
Java
public class Test {
public static void main(String[] args) {
int N = 15;
int[] t = new int[N + 2];
t[1] = 1;
for (int i = 1; i <= N; i++) {
for (int j = i; j > 1; j--)
t[j] = t[j] + t[j - 1];
t[i + 1] = t[i];
for (int j = i + 1; j > 1; j--)
t[j] = t[j] + t[j - 1];
System.out.printf("%d ", t[i + 1] - t[i]);
}
}
}
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
JavaScript
ES5
Iteration
var n = 15;
for (var t = [0, 1], i = 1; i <= n; i++) {
for (var j = i; j > 1; j--) t[j] += t[j - 1];
t[i + 1] = t[i];
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1];
document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]);
}
- Output:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
ES6
Functional composition
(() => {
'use strict';
// CATALAN
// catalanSeries :: Int -> [Int]
let catalanSeries = n => {
let alternate = xs => xs.reduce(
(a, x, i) => i % 2 === 0 ? a.concat([x]) : a, []
),
diff = xs => xs.length > 1 ? xs[0] - xs[1] : xs[0];
return alternate(pascal(n * 2))
.map((xs, i) => diff(drop(i, xs)));
}
// PASCAL
// pascal :: Int -> [[Int]]
let pascal = n => until(
m => m.level <= 1,
m => {
let nxt = zipWith(
(a, b) => a + b, [0].concat(m.row), m.row.concat(0)
);
return {
row: nxt,
triangle: m.triangle.concat([nxt]),
level: m.level - 1
}
}, {
level: n,
row: [1],
triangle: [
[1]
]
}
)
.triangle;
// GENERIC FUNCTIONS
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
let zipWith = (f, xs, ys) =>
xs.length === ys.length ? (
xs.map((x, i) => f(x, ys[i]))
) : undefined;
// until :: (a -> Bool) -> (a -> a) -> a -> a
let until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
}
// drop :: Int -> [a] -> [a]
let drop = (n, xs) => xs.slice(n);
// tail :: [a] -> [a]
let tail = xs => xs.length ? xs.slice(1) : undefined;
return tail(catalanSeries(16));
})();
- Output:
[1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845]
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.
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.
def binomial(n; k):
if k > n / 2 then binomial(n; n-k)
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
end;
# 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]
- Output:
$ jq -n -c -f Catalan_numbers_Pascal.jq
[0,0]
[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]
[30,3814986502092304]
[31,14544636039226880]
[510,5.491717746183512e+302]
[511,null]
Julia
# v0.6
function pascal(n::Int)
r = ones(Int, n, n)
for i in 2:n, j in 2:n
r[i, j] = r[i-1, j] + r[i, j-1]
end
return r
end
function catalan_num(n::Int)
p = pascal(n + 2)
p[n+4:n+3:end-1] - diag(p, 2)
end
@show catalan_num(15)
- Output:
catalan_num(15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
Kotlin
// version 1.1.2
import java.math.BigInteger
val ONE = BigInteger.ONE
fun pascal(n: Int, k: Int): BigInteger {
if (n == 0 || k == 0) return ONE
val num = (k + 1..n).fold(ONE) { acc, i -> acc * BigInteger.valueOf(i.toLong()) }
val den = (2..n - k).fold(ONE) { acc, i -> acc * BigInteger.valueOf(i.toLong()) }
return num / den
}
fun catalanFromPascal(n: Int) {
for (i in 1 until n step 2) {
val mi = i / 2 + 1
val catalan = pascal(i, mi) - pascal(i, mi - 2)
println("${"%2d".format(mi)} : $catalan")
}
}
fun main(args: Array<String>) {
val n = 15
catalanFromPascal(n * 2)
}
- Output:
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
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.
function nextrow (t)
local ret = {}
t[0], t[#t + 1] = 0, 0
for i = 1, #t do ret[i] = t[i - 1] + t[i] end
return ret
end
function catalans (n)
local t, middle = {1}
for i = 1, n do
middle = math.ceil(#t / 2)
io.write(t[middle] - (t[middle + 1] or 0) .. " ")
t = nextrow(nextrow(t))
end
end
catalans(15)
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
M2000 Interpreter
We have to add -1 in For x=2 to rows, because in FreeBasic when x=rows then inner loop never happen because end value for y is 1, so lower than start value 2. In M2000 this should run from 2 to 1, so we have to exclude this situation from outer loop, adding -1, and before loop we have to include en exit from sub if rows are less than 2.
We can define integer variables (16 bit), and we can use integer literals numbers using % as last char.
Inside triangle array we use decimal numbers, using @ for first literals, so all additions next produce decimals too.
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).
Module CatalanNumbers {
Def Integer count, t_row, size=31
Dim triangle(1 to size, 1 to size)
\\ call sub
pascal_triangle(size, &triangle())
Print "The first 15 Catalan numbers are"
count = 1% : t_row = 2%
Do {
Print Format$("{0:0:-3}:{1:0:-15}", count, triangle(t_row, t_row) - triangle(t_row +1, t_row -1))
t_row++
count++
} Until count > 15
End
Sub pascal_triangle(rows As Integer, &Pas_tri())
Local x=0%, y=0%
For x = 1 To rows
Pas_tri( 1%, x ) = 1@
Pas_tri( x, 1% ) = 1@
Next x
if rows<2 then exit sub
For x = 2 To rows-1
For y = 2 To rows + 1 - x
Pas_tri(x, y) = pas_tri(x - 1 , y) + pas_tri(x, y - 1)
Next y
Next x
End Sub
}
CatalanNumbers
- Output:
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
Maple
catalan:=proc(n)
local i,a:=[1],C:=[1];
for i to n do
a:=[0,op(a)]+[op(a),0];
a:=[0,op(a)]+[op(a),0];
C:=[op(C),a[i+1]-a[i]];
od;
C
end:
catalan(10);
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
Mathematica / 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.
nextrow[lastrow_] := Module[{output},
output = ConstantArray[1, Length[lastrow] + 1];
Do[
output[[i + 1]] = lastrow[[i]] + lastrow[[i + 1]];
, {i, 1, Length[lastrow] - 1}];
output
]
pascaltriangle[size_] := NestList[nextrow, {1}, size]
catalannumbers[length_] := Module[{output, basetriangle},
basetriangle = pascaltriangle[2 length];
list1 = basetriangle[[# *2 + 1, # + 1]] & /@ Range[length];
list2 = basetriangle[[# *2 + 1, # + 2]] & /@ Range[length];
list1 - list2
]
(* testing *)
catalannumbers[15]
- Output:
{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}
MATLAB / Octave
n = 15;
p = pascal(n + 2);
p(n + 4 : n + 3 : end - 1)' - diag(p, 2)
- Output:
ans = 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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);
- Output:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
Nim
const n = 15
var t = newSeq[int](n + 2)
t[1] = 1
for i in 1..n:
for j in countdown(i, 1): t[j] += t[j-1]
t[i+1] = t[i]
for j in countdown(i+1, 1): t[j] += t[j-1]
stdout.write t[i+1] - t[i], " "
stdout.write '\n'
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
OCaml
let catalan : int ref = ref 0 in
Printf.printf "%d ," 1 ;
for i = 2 to 9 do
let nm : int ref = ref 1 in
let den : int ref = ref 1 in
for k = 2 to i do
nm := (!nm)*(i+k);
den := (!den)*k;
catalan := (!nm)/(!den) ;
done;
print_int (!catalan); print_string "," ;
done;;
- Output:
OUTPUT: 1 ,2,5,14,42,132,429,1430,4862
Oforth
import: mapping
: pascal( n -- [] )
[ 1 ] n #[ dup [ 0 ] + [ 0 ] rot + zipWith( #+ ) ] times ;
: catalan( n -- m )
n 2 * pascal at( n 1+ ) n 1+ / ;
- Output:
>#catalan 15 seq map . [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
PARI/GP
vector(15,n,binomial(2*n,n)-binomial(2*n,n+1))
- Output:
%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
Pascal
Program CatalanNumbers
type
tElement = Uint64;
var
Catalan : array[0..50] of tElement;
procedure GetCatalan(L:longint);
var
PasTri : array[0..100] of tElement;
j,k: longInt;
begin
l := l*2;
PasTri[0] := 1;
j := 0;
while (j<L) do
begin
inc(j);
k := (j+1) div 2;
PasTri[k] :=PasTri[k-1];
For k := k downto 1 do
inc(PasTri[k],PasTri[k-1]);
IF NOT(Odd(j)) then
begin
k := j div 2;
Catalan[k] :=PasTri[k]-PasTri[k-1];
end;
end;
end;
var
i,l: longint;
Begin
l := 15;
GetCatalan(L);
For i := 1 to L do
Writeln(i:3,Catalan[i]:20);
end.
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
Perl
use constant N => 15;
my @t = (0, 1);
for(my $i = 1; $i <= N; $i++) {
for(my $j = $i; $j > 1; $j--) { $t[$j] += $t[$j-1] }
$t[$i+1] = $t[$i];
for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] }
print $t[$i+1] - $t[$i], " ";
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
After the 28th Catalan number, this overflows 64-bit integers. We could add use bigint; use Math::GMP ":constant"; to make it work, albeit not at a fast pace. However we can use a module to do it much faster:
use ntheory qw/binomial/;
print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";
The Math::Pari module also has a binomial, but isn't as fast and overflows its stack after 3400.
Phix
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example
constant N = 15 -- accurate to 30, nan/inf for anything over 514 (gmp version is below). sequence catalan = {}, -- (>=1 only) p = repeat(1,N+1) atom p1 for i=1 to N do p1 = p[1]*2 catalan = append(catalan,p1-p[2]) for j=1 to N-i+1 do p1 += p[j+1] p[j] = p1 end for -- ?p[1..N-i+1] end for ?catalan
- Output:
{1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845}
Explanatory comments to accompany the above
-- FreeBASIC said:
--' 1 1 1 1 1 1
--' 1 2 3 4 5 6
--' 1 3 6 10 15 21
--' 1 4 10 20 35 56
--' 1 5 15 35 70 126
--' 1 6 21 56 126 252
--' The Pascal triangle is rotated 45 deg.
--' to find the Catalan number we need to follow the diagonal
--' for top left to bottom right
--' take the number on diagonal and subtract the number in de cell
--' one up and one to right
--' 1 (2 - 1), 2 (6 - 4), 5 (20 - 15) ...
--
-- The first thing that struck me was it is twice as big as it needs to be,
-- something like this would do...
-- 1 1 1 1 1 1
-- 2 3 4 5 6
-- 6 10 15 21
-- 20 35 56
-- 70 126
-- 252
-- It is more obvious from the upper square that the diagonal on that, which is
-- that same as column 1 on this, is twice the previous, which on the second
-- diagram is in column 2. Further, once we have calculated the value for column
-- one above, we can use it immediately to calculate the next catalan number and
-- do not need to store it. Lastly we can overwrite row 1 with row 2 etc in situ,
-- and the following shows what we need for subsequent rounds:
-- 1 1 1 1 1
-- 3 4 5 6
-- 10 15 21
-- 35 56
-- 126 (unused)
gmp version
with javascript_semantics include builtins\mpfr.e function catalanB(integer n) -- very very fast! sequence catalan = mpz_inits(n), p = mpz_inits(n+1,1) mpz p1 = mpz_init(1) if n=0 then return p1 end if for i=1 to n do mpz_mul_si(p1,p[1],2) mpz_sub(catalan[i],p1,p[2]) for j=1 to n-i+1 do mpz_add(p1,p1,p[j+1]) mpz_set(p[j],p1) end for end for return catalan[n] end function printf(1,"%d: %s\n",{100,shorten(mpz_get_str(catalanB(100)))}) printf(1,"%d: %s\n",{250,shorten(mpz_get_str(catalanB(250)))})
- Output:
100: 89651994709013149668...20837521538745909320 (57 digits) 250: 46511679596923379649...69029457769094808256 (147 digits)
The above is significantly faster than the equivalent(s) on Catalan_numbers, a quick comparison showing the latter getting exponentially worse (then again I memoised the slowest recursive version):
800 2000 4000 8000 catalanB: 0.6s 3.5s 14.5s 64s catalan2m: 0.7s 7.0s 64.9s 644s
PicoLisp
(de bino (N K)
(let f
'((N)
(if (=0 N) 1 (apply * (range 1 N))) )
(/
(f N)
(* (f (- N K)) (f K)) ) ) )
(for N 15
(println
(-
(bino (* 2 N) N)
(bino (* 2 N) (inc N)) ) ) )
(bye)
PureBasic
#MAXNUM = 15
Declare catalan()
If OpenConsole("Catalan numbers")
catalan()
Input()
End 0
Else
End -1
EndIf
Procedure catalan()
Define k.i, n.i, num.d, den.d, cat.d
Print("1 ")
For n=2 To #MAXNUM
num=1 : den =1
For k=2 To n
num * (n+k)
den * k
cat = num / den
Next
Print(Str(cat)+" ")
Next
EndProcedure
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Python
Procedural
>>> n = 15
>>> t = [0] * (n + 2)
>>> t[1] = 1
>>> for i in range(1, n + 1):
for j in range(i, 1, -1): t[j] += t[j - 1]
t[i + 1] = t[i]
for j in range(i + 1, 1, -1): t[j] += t[j - 1]
print(t[i+1] - t[i], end=' ')
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
>>>
def catalan_number(n):
nm = dm = 1
for k in range(2, n+1):
nm, dm = ( nm*(n+k), dm*k )
return nm/dm
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
Note that sequence A000108 on OEIS (referenced in the task description) confirms that the first four Catalan numbers are indeed 1, 1, 2, 5 ...
(Several scripts on this page appear to lose the first 1).
'''Catalan numbers from Pascal's triangle'''
from itertools import (islice)
from operator import (add)
# nCatalans :: Int -> [Int]
def nCatalans(n):
'''The first n Catalan numbers,
derived from Pascal's triangle.'''
# diff :: [Int] -> Int
def diff(xs):
'''Difference between the first two items in the list,
if its length is more than one.
Otherwise, the first (only) item in the list.'''
return (
xs[0] - (xs[1] if 1 < len(xs) else 0)
) if xs else None
return list(map(
compose(diff)(uncurry(drop)),
enumerate(map(fst, take(n)(
everyOther(
pascalTriangle()
)
)))
))
# pascalTriangle :: Gen [[Int]]
def pascalTriangle():
'''A non-finite stream of
Pascal's triangle rows.'''
return iterate(nextPascal)([1])
# nextPascal :: [Int] -> [Int]
def nextPascal(xs):
'''A row of Pascal's triangle
derived from a preceding row.'''
return zipWith(add)([0] + xs)(xs + [0])
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''First 16 Catalan numbers.'''
print(
nCatalans(16)
)
# GENERIC -------------------------------------------------
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Right to left function composition.'''
return lambda f: lambda x: g(f(x))
# drop :: Int -> [a] -> [a]
# drop :: Int -> String -> String
def drop(n):
'''The sublist of xs beginning at
(zero-based) index n.'''
def go(xs):
if isinstance(xs, list):
return xs[n:]
else:
take(n)(xs)
return xs
return lambda xs: go(xs)
# everyOther :: Gen [a] -> Gen [a]
def everyOther(g):
'''Every other item of a generator stream.'''
while True:
yield take(1)(g)
take(1)(g) # Consumed, not yielded.
# fst :: (a, b) -> a
def fst(tpl):
'''First component of a pair.'''
return tpl[0]
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated applications of f to x.'''
def go(x):
v = x
while True:
yield v
v = f(v)
return lambda x: go(x)
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.'''
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else list(islice(xs, n))
)
# uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
'''A function over a tuple
derived from a curried function.'''
return lambda xy: f(xy[0])(
xy[1]
)
# zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
def zipWith(f):
'''A list constructed by zipping with a
custom function, rather than with the
default tuple constructor.'''
return lambda xs: lambda ys: (
list(map(f, xs, ys))
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
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
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Racket
#lang racket
(define (next-half-row r)
(define r1 (for/list ([x r] [y (cdr r)]) (+ x y)))
`(,(* 2 (car r1)) ,@(for/list ([x r1] [y (cdr r1)]) (+ x y)) 1 0))
(let loop ([n 15] [r '(1 0)])
(cons (- (car r) (cadr r))
(if (zero? n) '() (loop (sub1 n) (next-half-row r)))))
;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900
;; 2674440 9694845)
Raku
(formerly Perl 6)
constant @pascal = [1], -> @p { [0, |@p Z+ |@p, 0] } ... *;
constant @catalan = gather for 2, 4 ... * -> $ix {
my @row := @pascal[$ix];
my $mid = +@row div 2;
take [-] @row[$mid, $mid+1]
}
.say for @catalan[^20];
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 6564120420
REXX
explicit subscripts
All of the REXX program examples can handle arbitrary large numbers.
/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/
@.=0; @.1=1 /*stem array default; define 1st value.*/
do i=1 for N; ip=i+1
do j=i by -1 for N; jm=j-1; @.j=@.j+@.jm; end /*j*/
@.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:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
implicit subscripts
/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/
@.=0; @.1=1 /*stem array default; define 1st value.*/
do i=1 for N; ip=i+1
do j=i by -1 for N; @.j=@.j+@(j-1); end /*j*/
@.ip=@.i; do k=ip by -1 for N; @.k=@.k+@(k-1); end /*k*/
say @.ip - @.i /*display the Ith Catalan number. */
end /*i*/
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 1st version.
using binomial coefficients
/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/
do j=1 for N /* [↓] display N Catalan numbers. */
say comb(j+j, j) % (j+1) /*display the Jth Catalan number. */
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
!: procedure; parse arg z; _=1; do j=1 for arg(1); _=_*j; end; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
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 1st version.
binomial coefficients, memoized
This REXX version uses memoization for the calculation of factorials.
/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */
parse arg N . /*Obtain the optional argument from CL.*/
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/
!.=.
do j=1 for N /* [↓] display N Catalan numbers. */
say comb(j+j, j) % (j+1) /*display the Jth Catalan number. */
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
!: procedure expose !.; parse arg z; if !.z\==. then return !.z; _=1
do j=1 for arg(1); _=_*j; end; !.z=_; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
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 1st version.
Ring
n=15
cat = list(n+2)
cat[1]=1
for i=1 to n
for j=i+1 to 2 step -1
cat[j]=cat[j]+cat[j-1]
next
cat[i+1]=cat[i]
for j=i+2 to 2 step -1
cat[j]=cat[j]+cat[j-1]
next
see "" + (cat[i+1]-cat[i]) + " "
next
Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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.
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] |
- Input:
≪ { } 1 15 FOR j CATLN j + NEXT ≫ EVAL
- Output:
1: { 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 }
Runs in 119 seconds on an HP-28S.
Fast, idiomatic approach
Using the built-in COMB
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.
Ruby
def catalan(num)
t = [0, 1] #grows as needed
(1..num).map do |i|
i.downto(1){|j| t[j] += t[j-1]}
t[i+1] = t[i]
(i+1).downto(1) {|j| t[j] += t[j-1]}
t[i+1] - t[i]
end
end
p catalan(15)
- Output:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
Run BASIC
n = 15
dim t(n+2)
t(1) = 1
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 t(i+1) - t(i);" ";
next i
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Rust
fn main()
{let n=15usize;
let mut t= [0; 17];
t[1]=1;
let mut j:usize;
for i in 1..n+1
{
j=i;
loop{
if j==1{
break;
}
t[j]=t[j] + t[j-1];
j=j-1;
}
t[i+1]= t[i];
j=i+1;
loop{
if j==1{
break;
}
t[j]=t[j] + t[j-1];
j=j-1;
}
print!("{} ", t[i+1]-t[i]);
}
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Scala
def catalan(n: Int): Int =
if (n <= 1) 1
else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum
(1 to 15).map(catalan(_))
- Output:
See it in running in your browser by Scastie (JVM).
Scilab
n=15
t=zeros(1,n+2)
t(1)=1
for i=1:n
for j=i+1:-1:2
t(j)=t(j)+t(j-1)
end
t(i+1)=t(i)
for j=i+2:-1:2
t(j)=t(j)+t(j-1)
end
disp(t(i+1)-t(i))
end
- Output:
1. 2. 5. 14. 42. 132. 429. 1430. 4862. 16796. 58786. 208012. 742900. 2674440. 9694845.
Seed7
$ include "seed7_05.s7i";
const proc: main is func
local
const integer: N is 15;
var array integer: t is [] (1) & N times 0;
var integer: i is 0;
var integer: j is 0;
begin
for i range 1 to N do
for j range i downto 2 do
t[j] +:= t[j - 1];
end for;
t[i + 1] := t[i];
for j range i + 1 downto 2 do
t[j] +:= t[j - 1];
end for;
write(t[i + 1] - t[i] <& " ");
end for;
writeln;
end func;
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Sidef
func catalan(num) {
var t = [0, 1]
(1..num).map { |i|
flip(^i ).each {|j| t[j+1] += t[j] }
t[i+1] = t[i]
flip(^i.inc).each {|j| t[j+1] += t[j] }
t[i+1] - t[i]
}
}
say catalan(15).join(' ')
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
smart BASIC
PRINT "Catalan Numbers from Pascal's Triangle"!PRINT
x = 15
DIM t(x+2)
t(1) = 1
FOR n = 1 TO x
FOR m = n TO 1 STEP -1
t(m) = t(m) + t(m-1)
NEXT m
t(n+1) = t(n)
FOR m = n+1 TO 1 STEP -1
t(m) = t(m) + t(m-1)
NEXT m
PRINT n,"#######":t(n+1) - t(n)
NEXT n
Tcl
proc catalan n {
set result {}
array set t {0 0 1 1}
for {set i 1} {[set k $i] <= $n} {incr i} {
for {set j $i} {$j > 1} {} {incr t($j) $t([incr j -1])}
set t([incr k]) $t($i)
for {set j $k} {$j > 1} {} {incr t($j) $t([incr j -1])}
lappend result [expr {$t($k) - $t($i)}]
}
return $result
}
puts [catalan 15]
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
TI-83 BASIC
"CATALAN
15→N
seq(0,I,1,N+2)→L1
1→L1(1)
For(I,1,N)
For(J,I+1,2,-1)
L1(J)+L1(J-1)→L1(J)
End
L1(I)→L1(I+1)
For(J,I+2,2,-1)
L1(J)+L1(J-1)→L1(J)
End
Disp L1(I+1)-L1(I)
End
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 Done
Vala
void main() {
const int N = 15;
uint64[] t = {0, 1};
for (int i = 1; i <= N; i++) {
for (int j = i; j > 1; j--) t[j] = t[j] + t[j - 1];
t[i + 1] = t[i];
for (int j = i + 1; j > 1; j--) t[j] = t[j] + t[j - 1];
print(@"$(t[i + 1] - t[i]) ");
}
print("\n");
}
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
VBScript
To run in console mode with cscript.
dim t()
if Wscript.arguments.count=1 then
n=Wscript.arguments.item(0)
else
n=15
end if
redim t(n+1)
't(*)=0
t(1)=1
for i=1 to n
ip=i+1
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
Wscript.echo t(i+1)-t(i)
next 'i
Visual Basic
Sub catalan()
Const n = 15
Dim t(n + 2) As Long
Dim i As Integer, j As Integer
t(1) = 1
For i = 1 To n
For j = i + 1 To 2 Step -1
t(j) = t(j) + t(j - 1)
Next j
t(i + 1) = t(i)
For j = i + 2 To 2 Step -1
t(j) = t(j) + t(j - 1)
Next j
Debug.Print i, t(i + 1) - t(i)
Next i
End Sub 'catalan
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Wren
var n = 15
var t = List.filled(n+2, 0)
t[1] = 1
for (i in 1..n) {
if (i > 1) for (j in i..2) t[j] = t[j] + t[j-1]
t[i+1] = t[i]
if (i > 0) for (j in i+1..2) t[j] = t[j] + t[j-1]
System.write("%(t[i+1]-t[i]) ")
}
System.print()
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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, ^ );
];
]
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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 primality task.)
const std = @import("std");
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
var n: u32 = 1;
while (n <= 15) : (n += 1) {
const row = binomial(n * 2).?;
try stdout.print("{d:2} {d:8}\n", .{ n, row[n] - row[n + 1] });
}
}
pub fn binomial(n: u32) ?[]const u64 {
if (n >= rmax)
return null
else {
const k = n * (n + 1) / 2;
return pascal[k .. k + n + 1];
}
}
const rmax = 68;
// evaluated and created at compile-time
const pascal = build: {
@setEvalBranchQuota(100_000);
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined;
coefficients[0] = 1;
var j: u32 = 0;
var k: u32 = 1;
var n: u32 = 1;
while (n < rmax) : (n += 1) {
var prev = coefficients[j .. j + n];
var next = coefficients[k .. k + n + 1];
next[0] = 1;
var i: u32 = 1;
while (i < n) : (i += 1)
next[i] = prev[i] + prev[i - 1];
next[i] = 1;
j = k;
k += n + 1;
}
break :build coefficients;
};
- Output:
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
zkl
using binomial coefficients.
fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) }
(1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })
- Output:
L(1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845)
ZX Spectrum Basic
10 LET N=15
20 DIM t(N+2)
30 LET t(2)=1
40 FOR i=2 TO N+1
50 FOR j=i TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j
60 LET t(i+1)=t(i)
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
- Programming Tasks
- Solutions by Programming Task
- 11l
- 360 Assembly
- Action!
- Action! Tool Kit
- Ada
- ALGOL 68
- ALGOL W
- APL
- Arturo
- AutoHotkey
- AWK
- BASIC
- Applesoft BASIC
- Chipmunk Basic
- GW-BASIC
- MSX Basic
- QBasic
- XBasic
- Yabasic
- Batch File
- C
- C sharp
- C++
- Common Lisp
- D
- Delphi
- EasyLang
- EchoLisp
- EDSAC order code
- Elixir
- Erlang
- ERRE
- F Sharp
- Factor
- FreeBASIC
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- M2000 Interpreter
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- Maxima
- Nim
- OCaml
- Oforth
- PARI/GP
- Pascal
- Perl
- Ntheory
- Phix
- Phix/mpfr
- PicoLisp
- PureBasic
- Python
- Quackery
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Run BASIC
- Rust
- Scala
- Scilab
- Seed7
- Sidef
- Smart BASIC
- Tcl
- TI-83 BASIC
- Vala
- VBScript
- Visual Basic
- Wren
- XPL0
- Zig
- Zkl
- ZX Spectrum Basic