Catalan numbers: Difference between revisions
→{{header|langur}}
Langurmonkey (talk | contribs) |
|||
| (32 intermediate revisions by 13 users not shown) | |||
Line 411:
15 9694845
</pre>
=={{header|BASIC}}==
{{works with|FreeBASIC}}
Line 451 ⟶ 452:
14 2674440
15 9694845
==={{header|Applesoft BASIC}}===
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">10 HOME : REM 10 CLS for Chipmunk Basic/QBasic
20 DIM c(15)
30 c(0) = 1
40 PRINT 0, c(0)
50 FOR n = 0 TO 14
60 c(n + 1) = 0
70 FOR i = 0 TO n
80 c(n + 1) = c(n + 1) + c(i) * c(n - i)
90 NEXT i
100 PRINT n + 1, c(n + 1)
110 NEXT n
120 END</syntaxhighlight>
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="freebasic">function factorial(n)
if n = 0 then return 1
return n * factorial(n - 1)
end function
function catalan1(n)
prod = 1
for i = n + 2 to 2 * n
prod *= i
next i
return int(prod / factorial(n))
end function
function catalan2(n)
if n = 0 then return 1
sum = 0
for i = 0 to n - 1
sum += catalan2(i) * catalan2(n - 1 - i)
next i
return sum
end function
function catalan3(n)
if n = 0 then return 1
return catalan3(n - 1) * 2 * (2 * n - 1) \ (n + 1)
end function
print "n", "First", "Second", "Third"
print "-", "-----", "------", "-----"
print
for i = 0 to 15
print i, catalan1(i), catalan2(i), catalan3(i)
next i</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> 10 FOR i% = 1 TO 15
20 PRINT FNcatalan(i%)
30 NEXT
40 END
50 DEF FNcatalan(n%)
60 IF n% = 0 THEN = 1
70 = 2 * (2 * n% - 1) * FNcatalan(n% - 1) / (n% + 1)</syntaxhighlight>
{{out}}
<pre> 1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">10 FOR i = 1 TO 15
20 PRINT i;" ";catalan(i)
30 NEXT
40 END
50 SUB catalan(n)
60 catalan = 1
70 IF n <> 0 THEN catalan = ((2*((2*n)-1))/(n+1))*catalan(n-1)
80 END SUB</syntaxhighlight>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">dim c[16]
let c[0] = 1
for n = 0 to 15
let p = n + 1
let c[p] = 0
for i = 0 to n
let q = n - i
let c[p] = c[p] + c[i] * c[q]
next i
print n, " ", c[n]
next n</syntaxhighlight>
{{out| Output}}<pre>
0 1
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|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Function factorial(n As UInteger) As UInteger
If n = 0 Then Return 1
Return n * factorial(n - 1)
End Function
Function catalan1(n As UInteger) As UInteger
Dim prod As UInteger = 1
For i As UInteger = n + 2 To 2 * n
prod *= i
Next
Return prod / factorial(n)
End Function
Function catalan2(n As UInteger) As UInteger
If n = 0 Then Return 1
Dim sum As UInteger = 0
For i As UInteger = 0 To n - 1
sum += catalan2(i) * catalan2(n - 1 - i)
Next
Return sum
End Function
Function catalan3(n As UInteger) As UInteger
If n = 0 Then Return 1
Return catalan3(n - 1) * 2 * (2 * n - 1) \ (n + 1)
End Function
Print "n", "First", "Second", "Third"
Print "-", "-----", "------", "-----"
Print
For i As UInteger = 0 To 15
Print i, catalan1(i), catalan2(i), catalan3(i)
Next
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
{{out}}
<pre>
n First Second Third
- ----- ------ -----
0 1 1 1
1 1 1 1
2 2 2 2
3 5 5 5
4 14 14 14
5 42 42 42
6 132 132 132
7 429 429 429
8 1430 1430 1430
9 4862 4862 4862
10 16796 16796 16796
11 58786 58786 58786
12 208012 208012 208012
13 742900 742900 742900
14 2674440 2674440 2674440
15 9694845 9694845 9694845
</pre>
==={{header|FutureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
local fn Factorial( n as NSInteger ) as UInt64
UInt64 sum = 0
if n = 0 then sum = 1 : exit fn
sum = n * fn Factorial( n - 1 )
end fn = sum
local fn Catalan1( n as NSInteger ) as UInt64
UInt64 product = 1, result
NSUInteger i
for i = n + 2 to 2 * n
product = product * i
next
result = product / fn Factorial( n )
end fn = result
local fn Catalan2( n as NSInteger ) as UInt64
UInt64 sum = 0
NSUInteger i
if n = 0 then sum = 1 : exit fn
for i = 0 to n - 1
sum += fn Catalan2(i) * fn Catalan2( n - 1 - i )
next
end fn = sum
local fn Catalan3( n as NSInteger ) as UInt64
UInt64 result
if n = 0 then result = 1 : exit fn
result = fn Catalan3( n - 1 ) * 2 * ( 2 * n - 1 ) / ( n + 1 )
end fn = result
NSUInteger i
for i = 0 to 19
if( i < 16 )
NSLog( @"%3d.\t\t%7llu\t\t%12llu\t\t%12llu", i, fn Catalan1( i ), fn Catalan2( i ), fn Catalan3( i ) )
else
NSLog( @"%3d.\t\t%@\t\t%12llu\t\t%12llu", i, @"[-err-]", fn Catalan2( i ), fn Catalan3( i ) )
end if
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
0. 1 1 1
1. 1 1 1
2. 2 2 2
3. 5 5 5
4. 14 14 14
5. 42 42 42
6. 132 132 132
7. 429 429 429
8. 1430 1430 1430
9. 4862 4862 4862
10. 16796 16796 16796
11. 58786 58786 58786
12. 208012 208012 208012
13. 742900 742900 742900
14. 2674440 2674440 2674440
15. 9694845 9694845 9694845
16. [-err-] 35357670 35357670
17. [-err-] 129644790 129644790
18. [-err-] 477638700 477638700
19. [-err-] 1767263190 1767263190
</pre>
==={{header|GW-BASIC}}===
{{works with|BASICA}}
<syntaxhighlight lang="gwbasic">
100 REM Catalan numbers
110 DIM C(15)
130 PRINT 0, C(0)
140 FOR N = 0 TO 14
150 C(N + 1) = 0
160 FOR I = 0 TO N
170 C(N + 1) = C(N + 1) + C(I) * C(N - I)
180 NEXT I
190 PRINT N + 1, C(N + 1)
200 NEXT N
210 END
</syntaxhighlight>
{{out}}
<pre>
0 1
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|Liberty BASIC}}===
{{works with|Just BASIC}}
<syntaxhighlight lang="lb">print "non-recursive version"
print catNonRec(5)
for i = 0 to 15
print i;" = "; catNonRec(i)
next
print
print "recursive version"
print catRec(5)
for i = 0 to 15
print i;" = "; catRec(i)
next
print
print "recursive with memoisation"
redim cats(20) 'clear the array
print catRecMemo(5)
for i = 0 to 15
print i;" = "; catRecMemo(i)
next
print
wait
function catNonRec(n) 'non-recursive version
catNonRec=1
for i=1 to n
catNonRec=((2*((2*i)-1))/(i+1))*catNonRec
next
end function
function catRec(n) 'recursive version
if n=0 then
catRec=1
else
catRec=((2*((2*n)-1))/(n+1))*catRec(n-1)
end if
end function
function catRecMemo(n) 'recursive version with memoisation
if n=0 then
catRecMemo=1
else
if cats(n-1)=0 then 'call it recursively only if not already calculated
prev = catRecMemo(n-1)
else
prev = cats(n-1)
end if
catRecMemo=((2*((2*n)-1))/(n+1))*prev
end if
cats(n) = catRecMemo 'memoisation for future use
end function</syntaxhighlight>
{{out}}
<pre>
non-recursive version
42
0 = 1
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
recursive version
42
0 = 1
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
recursive with memoisation
42
0 = 1
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|Minimal BASIC}}===
Line 481 ⟶ 887:
120 END
</syntaxhighlight>
==={{header|PureBasic}}===
Using the third formula...
<syntaxhighlight lang="purebasic">; saving the division for last ensures we divide the largest
; numerator by the smallest denominator
Procedure.q CatalanNumber(n.q)
If n<0:ProcedureReturn 0:EndIf
If n=0:ProcedureReturn 1:EndIf
ProcedureReturn (2*(2*n-1))*CatalanNumber(n-1)/(n+1)
EndProcedure
ls=25
rs=12
a.s=""
a.s+LSet(RSet("n",rs),ls)+"CatalanNumber(n)"
; cw(a.s)
Debug a.s
For n=0 to 33 ;33 largest correct quad for n
a.s=""
a.s+LSet(RSet(Str(n),rs),ls)+Str(CatalanNumber(n))
; cw(a.s)
Debug a.s
Next</syntaxhighlight>
{{out|Sample Output}}
<pre>
n CatalanNumber(n)
0 1
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
16 35357670
17 129644790
18 477638700
19 1767263190
20 6564120420
21 24466267020
22 91482563640
23 343059613650
24 1289904147324
25 4861946401452
26 18367353072152
27 69533550916004
28 263747951750360
29 1002242216651368
30 3814986502092304
31 14544636039226909
32 55534064877048198
33 212336130412243110
</pre>
==={{header|Run BASIC}}===
<syntaxhighlight lang="runbasic">FOR i = 1 TO 15
PRINT i;" ";catalan(i)
NEXT
FUNCTION catalan(n)
catalan = 1
if n <> 0 then catalan = ((2 * ((2 * n) - 1)) / (n + 1)) * catalan(n - 1)
END FUNCTION</syntaxhighlight>
<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|Sinclair ZX81 BASIC}}===
Line 520 ⟶ 1,015:
13 742900
14 2674440</pre>
==={{header|smart BASIC}}===
<syntaxhighlight lang="qbasic">PRINT "Recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catrec(n)
NEXT n
PRINT!PRINT
PRINT "Non-recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catnonrec(n)
NEXT n
END
DEF catrec(x)
IF x = 0 THEN
temp = 1
ELSE
n = x
temp = ((2*((2*n)-1))/(n+1))*catrec(n-1)
END IF
catrec = temp
END DEF
DEF catnonrec(x)
temp = 1
FOR n = 1 TO x
temp = (2*((2*n)-1))/(n+1)*temp
NEXT n
catnonrec = temp
END DEF</syntaxhighlight>
==={{header|TI-83 BASIC}}===
This problem is perfectly suited for a TI calculator.
<syntaxhighlight lang="ti-83 basic">:For(I,1,15
:Disp (2I)!/((I+1)!I!
:End</syntaxhighlight>
{{out}}
<pre> 1
2
4
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
Done</pre>
==={{Header|Tiny BASIC}}===
Integers are limited to 32767 so only the first ten Catalan numbers can be represented. And even then one has to do some finagling to avoid internal overflows.
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">
10 REM Catalan numbers
30 LET C = 1
40 PRINT N," ",C
50 IF N > 9 THEN END
70 GOSUB 200
80 LET C = (2 * N - 1) * C
90 LET C = 2 * C / (N + 1)
110 GOTO 40
210 IF C <= 0 THEN RETURN
220 LET C = C - (N + 1)
230 LET I = I + 1
240 GOTO 210
250 REM To avoid internal overflow, I subtract something clever from
260 REM C and then add it back at the end.</syntaxhighlight>
{{out}}
<pre>0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796</pre>
==={{header|VBA}}===
<syntaxhighlight lang="vb">Public Sub Catalan1(n As Integer)
'Computes the first n Catalan numbers according to the first recursion given
Dim Cat() As Long
Dim sum As Long
ReDim Cat(n)
Cat(0) = 1
For i = 0 To n - 1
sum = 0
For j = 0 To i
sum = sum + Cat(j) * Cat(i - j)
Next j
Cat(i + 1) = sum
Next i
Debug.Print
For i = 0 To n
Debug.Print i, Cat(i)
Next
End Sub
Public Sub Catalan2(n As Integer)
'Computes the first n Catalan numbers according to the second recursion given
Dim Cat() As Long
ReDim Cat(n)
Cat(0) = 1
For i = 1 To n
Cat(i) = 2 * Cat(i - 1) * (2 * i - 1) / (i + 1)
Next i
Debug.Print
For i = 0 To n
Debug.Print i, Cat(i)
Next
End Sub</syntaxhighlight>
{{out|Result}}
<pre>
Catalan1 15
0 1
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>
(Expect same result with "Catalan2 15")
==={{header|VBScript}}===
<syntaxhighlight lang="vb">
Function catalan(n)
catalan = factorial(2*n)/(factorial(n+1)*factorial(n))
End Function
Function factorial(n)
If n = 0 Then
Factorial = 1
Else
For i = n To 1 Step -1
If i = n Then
factorial = n
Else
factorial = factorial * i
End If
Next
End If
End Function
'Find the first 15 Catalan numbers.
For j = 1 To 15
WScript.StdOut.Write j & " = " & catalan(j)
WScript.StdOut.WriteLine
Next
</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|Visual Basic .NET}}===
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function Factorial(n As Double) As Double
If n < 1 Then
Return 1
End If
Dim result = 1.0
For i = 1 To n
result = result * i
Next
Return result
End Function
Function FirstOption(n As Double) As Double
Return Factorial(2 * n) / (Factorial(n + 1) * Factorial(n))
End Function
Function SecondOption(n As Double) As Double
If n = 0 Then
Return 1
End If
Dim sum = 0
For i = 0 To n - 1
sum = sum + SecondOption(i) * SecondOption((n - 1) - i)
Next
Return sum
End Function
Function ThirdOption(n As Double) As Double
If n = 0 Then
Return 1
End If
Return ((2 * (2 * n - 1)) / (n + 1)) * ThirdOption(n - 1)
End Function
Sub Main()
Const MaxCatalanNumber = 15
Dim initial As DateTime
Dim final As DateTime
Dim ts As TimeSpan
initial = DateTime.Now
For i = 0 To MaxCatalanNumber
Console.WriteLine("CatalanNumber({0}:{1})", i, FirstOption(i))
Next
final = DateTime.Now
ts = final - initial
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
Console.WriteLine()
initial = DateTime.Now
For i = 0 To MaxCatalanNumber
Console.WriteLine("CatalanNumber({0}:{1})", i, SecondOption(i))
Next
final = DateTime.Now
ts = final - initial
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
Console.WriteLine()
initial = DateTime.Now
For i = 0 To MaxCatalanNumber
Console.WriteLine("CatalanNumber({0}:{1})", i, ThirdOption(i))
Next
final = DateTime.Now
ts = final - initial
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.19 to execute
CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.831 to execute
CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.8 to execute</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="
print " - ----- ------ -----"
print
for i = 0 to 15
print i using "###", catalan1(i) using "########", catalan2(i) using "########", catalan3(i) using "########"
next i
end
sub factorial(n)
if n = 0 return 1
return n * factorial(n - 1)
end
sub catalan1(n)
local proc, i
prod = 1
for i = n + 2 to 2 * n
prod
next i
return int(prod / factorial(n))
end
local sum, i
if n = 0 return 1
sum = 0
for i = 0 to n - 1
sum
next i
return sum
end
if n = 0
return
end sub</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|Befunge}}==
{{trans|Ada}}
<syntaxhighlight lang="befunge">0>:.:000p1>\:00g-#v_v
Line 1,336 ⟶ 2,107:
user> (take 15 (catalan-numbers-recursive))
(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)</syntaxhighlight>
=={{header|CLU}}==
<syntaxhighlight lang="clu">catalan = iter (amount: int) yields (int)
c: int := 1
for n: int in int$from_to(1, amount) do
yield(c)
c := (4*n-2)*c/(n+1)
end
end catalan
start_up = proc ()
po: stream := stream$primary_output()
for n: int in catalan(15) do
stream$putl(po, int$unparse(n))
end
end start_up</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
=={{header|Common Lisp}}==
With all three methods defined.
Line 1,366 ⟶ 2,169:
(format t "~%Method ~d:~%" i)
(dotimes (i 16) (format t "C(~2d) = ~d~%" i (funcall f i))))</syntaxhighlight>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub catalan(n: uint32): (c: uint32) is
c := 1;
var i: uint32 := 1;
while i <= n loop
c := (4*i-2)*c/(i+1);
i := i+1;
end loop;
end sub;
var i: uint8 := 0;
while i < 15 loop
print("catalan(");
print_i8(i);
print(") = ");
print_i32(catalan(i as uint32));
print_nl();
i := i+1;
end loop;</syntaxhighlight>
{{out}}
<pre>catalan(0) = 1
catalan(1) = 1
catalan(2) = 2
catalan(3) = 5
catalan(4) = 14
catalan(5) = 42
catalan(6) = 132
catalan(7) = 429
catalan(8) = 1430
catalan(9) = 4862
catalan(10) = 16796
catalan(11) = 58786
catalan(12) = 208012
catalan(13) = 742900
catalan(14) = 2674440</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
Line 1,438 ⟶ 2,280:
15 : 9694845 9694845 9694845
</pre>
=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.bigint, std.functional, std.range;
Line 1,467 ⟶ 2,310:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
func catalan n
if n = 0
return
.
for i = 0 to 14
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 2,074 ⟶ 2,896:
14 2674440
===============
</pre>
=={{header|Frink}}==
Line 2,191 ⟶ 2,951:
</pre>
=={{header|
{{FormulaeEntry|page=https://formulae.org/?script=examples/Catalan_numbers}}
'''Solution'''
'''Direct definition'''
[[File:Fōrmulæ - Catalan numbers 01.png]]
[[File:Fōrmulæ - Catalan numbers 02.png]]
'''Direct definition (alternative)'''
The expression <math>\frac{(2n)!}{(n+1)!\,n!}</math> turns out to be equals to <math>\prod_{k=2}^{n}\frac{n + k}{k}</math>
[[File:Fōrmulæ - Catalan numbers 03.png]]
(same result)
'''No directly defined'''
Recursive definitions are easy to write, but extremely inefficient (specially the first one).
Because a list is intended to be get, the list of previous values can be used as a form of memoization, avoiding recursion.
The next function make use of the "second" form of recursive definition (without recursion):
[[File:Fōrmulæ - Catalan numbers 04.png]]
[[File:Fōrmulæ - Catalan numbers 05.png]]
(same result)
=={{header|GAP}}==
<syntaxhighlight lang="gap">Catalan1 := n -> Binomial(2*n, n) - Binomial(2*n, n - 1);
Line 2,653 ⟶ 3,361:
</pre>
=={{header|JavaScript}}==
===Procedural===
<syntaxhighlight lang="javascript"><html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
Line 2,700 ⟶ 3,410:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
===Functional===
Defining an infinite list:
<syntaxhighlight lang="javascript">(() => {
"use strict";
// ----------------- CATALAN NUMBERS -----------------
// catalansDefinitionThree :: [Int]
const catalansDefinitionThree = () =>
// An infinite sequence of Catalan numbers.
scanlGen(
c => n => Math.floor(
(2 * c * pred(2 * n)) / succ(n)
)
)(1)(
enumFrom(1)
);
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () =>
take(15)(
catalansDefinitionThree()
);
// --------------------- GENERIC ---------------------
// enumFrom :: Enum a => a -> [a]
const enumFrom = function* (n) {
// An infinite sequence of integers,
// starting with n.
let v = n;
while (true) {
yield v;
v = 1 + v;
}
};
// pred :: Int -> Int
const pred = x =>
x - 1;
// scanlGen :: (b -> a -> b) -> b -> Gen [a] -> [b]
const scanlGen = f =>
// The series of interim values arising
// from a catamorphism over an infinite list.
startValue => function* (gen) {
let
a = startValue,
x = gen.next();
yield a;
while (!x.done) {
a = f(a)(x.value);
yield a;
x = gen.next();
}
};
// succ :: Int -> Int
const succ = x =>
1 + x;
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}).flat();
// MAIN ---
return JSON.stringify(main(), null, 2);
})();</syntaxhighlight>
{{Out}}
<pre>[
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440
]</pre>
=={{header|jq}}==
{{ works with|jq|1.4 }}
Line 2,847 ⟶ 3,666:
2674440 2674440 2674440
9694845 9694845 9694845</pre>
=={{header|Lambdatalk}}==
{{trans|Javascript}}
<h3>1) catalan1</h3>
<syntaxhighlight lang="scheme">
{def catalan1
{def fac {lambda {:n} {* {S.serie 1 :n}}}}
{lambda {:n}
{floor {+ {/ {fac {* 2 :n}} {fac {+ :n 1}} {fac :n}} 0.5}}}}
-> catalan1
{S.map catalan1 {S.serie 1 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
<h3>2) catalan2</h3>
<syntaxhighlight lang="scheme">
{def catalan2
{def catalan2.sum
{lambda {:n :a :s :i}
{if {= :i :n}
then {A.set! :n :s :a}
else {catalan2.sum :n
:a
{+ :s {* {catalan2.loop :i :a}
{catalan2.loop {- :n :i 1} :a}}}
{+ :i 1}} }}}
{def catalan2.loop
{lambda {:n :a}
{if {= :n 0}
then 1
else {if {W.equal? {A.get :n :a} undefined}
then {A.get :n {catalan2.sum :n :a 0 0}}
else {A.get :n :a} }}}}
{lambda {:n}
{catalan2.loop :n {A.new}} }}
-> catalan2
{S.map catalan2 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
<h3>3) catalan3</h3>
<syntaxhighlight lang="scheme">
{def catalan3
{def catalan3.loop
{lambda {:n :a}
{if {= :n 0}
then 1
else {if {W.equal? {A.get :n :a} undefined}
then {A.get :n
{A.set! :n
{/ {* {- {* 4 :n} 2}
{catalan3.loop {- :n 1} :a}}
{+ :n 1}}
:a}}
else {A.get :n :a}
}}}}
{lambda {:n}
{catalan3.loop :n {A.new}}}}
-> catalan3
{S.map catalan3 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
<h3>4) Alternative for a vertical diplay</h3>
<syntaxhighlight lang="scheme">
{style
td { text-align:right;
font-family:monospace;
}
}
{table
{tr {td} {td cat1} {td cat2} {td cat3}}
{S.map {lambda {:i} {tr {td :i}
{td {catalan1 :i}}
{td {catalan2 :i}}
{td {catalan3 :i}}}}
{S.serie 0 15}}
}
cat1 cat2 cat3
0 1 1 1
1 1 1 1
2 2 2 2
3 5 5 5
4 14 14 14
5 42 42 42
6 132 132 132
7 429 429 429
8 1430 1430 1430
9 4862 4862 4862
10 16796 16796 16796
11 58786 58786 58786
12 208012 208012 208012
13 742900 742900 742900
14 2674440 2674440 2674440
15 9694845 9694845 9694845
</syntaxhighlight>
=={{header|langur}}==
{{trans|Perl}}
<syntaxhighlight lang="langur">val .factorial =
val .catalan = fn(.n) { .factorial(2 x .n) / .factorial(.n+1) / .factorial(.n) }
for .i in 0..15 {
Line 2,877 ⟶ 3,807:
10000: 224537812493385215633593584257360578701103586219365887773293713835854436588700534490998102719114320210209905393799589701149327326500953702713977513001838761306936534407802585494454599941773729984591764542782202886796997833276495496514760245912220654267091568311812071300891219894022165175451441066691435091975969499731921675488934120638046514134965974069039677192984714638704528752769863567952620334847707274529741976558104236293861846622622783294667505268651205024766408784881872997404042356319626323351089169906635603513309014645157443570842822082866699012415455339518777770781742052837799476906230350785959040487158118992753484022865373274100095762968510625236915280143408460651206678398725681703811505423791566261735329550627967717189932855983913468867794806585863794483869239933179341394259456515091026456652770409848702116046445406995085092488210998732255656992243441519938747425554228724734242623566663631968254490897214106655375215196762710825001305055093871863518797311135688370964194817463890187212845332422257193414201244344808864449873736345425670715824582633802476282521798739438044652622163657359012681653473214512797365047989922327391063907061792126264420963262176161781711086630089636828211837643128677915076724947168653050318426339007489738275045346257959685376480042860870398232333705506506342394485443047987642390287346746539674780326188825579548593281319807827279403944008553690033855132088140116099772393778770685018936338194366302053586633406848404622048675525765095697363909787189635178694239275237185046710057476484117945279786897787624602379494797322427251542758312638233073625857897083435831841717971137851874666094337671443717108457737153283641719103639784923520519013700030680553564442331411313831920775983175313709250333784211385811480015293165463406576311626295629412110652218717603537723650144357966952842696678735624157616428716812764985074925414219421312810089785108621126934245959900367104035334200067714905754827856122801987429837706493130435832752072139392743006620396370486473952500144779413596417260472218266529167783118015414918168260722824885550181735638670588682513610805160133611349864194033776132438535863120087679096358696928233598996870302136347936567444208209125300149683552369341937471817860835774359234009557030148123353114950735217736514617017504851011193104728986836180908987352236659629183725016607437110422583156042941955830763092095074443334625318588569114114087985404048889671202396824806275701581378689568449507132793603852731445602923990458926101180821029108808623323378547869169352237448925371763574346501610378415722137519019474474794069155118626291447578558908522430436148987521551911541787974276591708584289036595642180860178815462862735993859177180582760389253540408842580225467216988321950591728369194164290645992782274919561096308372635908842325870580231011459216934235078490764707633348336131667313582584404397290232519769625777374165187949140092779343812345117947306771376053099536367169631889642304360871187460737580808157222861127968703067542270175460553478533349238111434409526724363429611803844595968793121871649699680963646793415774160274520010905236593324062464542927011227158945796188186430711399250096518886617184049325827319276468018789191520522185358895653192882843061349706085770767046601045697944646638311930027354235643643713545212361580694059553720806659066661496416423676930095857438882302891350789287291844752601744462789158506243012088536936184422120232369244564444689340142897415432231452353338115944183447986470689449043710051589958391273681116292415738776171575775695905846247205522469202801517417551374761549677412720803623129527503286287755308576386461385928958587649159872019202866614901547860974883963007792442796064165417207167072370586790722366932349325253877744621251386864069101337572557790214048760202008337611577675840153696735860276810033694744314488435390547908483357054897387317002405793108554524629034558098886977538473481750772616164313845337139245688079995996839933620829828339492800825536599964878893947278408890351634126931068657027524005795713514365098086505030570362785115155293306343520969872400876180105031975302255898787642403303027682634969586730202117121076117629457710028105378124677420093990476071697970354661002217702623344454780740808459286778553016318604430682610618871098652904537323336381304469735192868285840882036271136058499391069436145426450229039329475974178236465920534171895204155964515055983303017823692138977622016292722019365841360360274557488926673754175222061483328914099598663902320310143583379354121664996173733086613692927391384486261610892314450463841637667054196985332620403539011932606618414419229492637564924726411270720189611019154677281846409387514072618176832310721327819277699943226895919915049652045449281057471199978267843961724883768772155477073354744908923995448752333726740642292872107500458349718026322755698226793850983280706045951407323891263270928264657562125955511946782954645656015480418543664557515041692091317941000997342935512311493290722434384401250133402934163457264794261787386862382738330195237770190998115114193014769006071380834085352290585937952429981509893303796306071520571655936820282768086579891336876000368502562579738337809071051261343359121744773055264455701014137255399929760233753812017596045145926791136761130783810840502248142803073720015451941006030172192834375431286154255159659778817089767964922549014569972777126726537787896968876337799235679125368824867754881036161730805613471278633981478858113141202728303435218970292775366288829203013873713349923690394124920402725698544786016048685431525811047414746045227535216327530901827040588505255466803793791888002231571686068617764292584075135236237044383334893874602177596602979234717936820827427229615827657960492946059695301906791494260652411424538532836730097985187522379068364429583532675896349363295120431429006688249818006722311568902288350452581968418068616818268667067741994472455501649753611708445979082338902214467454627107888156489438584617793175431865532382711812960546611287516640
</pre>
=={{header|Logo}}==
<syntaxhighlight lang="logo">to factorial :n
Line 3,018 ⟶ 3,837:
742900
2674440</pre>
=={{header|Logtalk}}==
For this task it is instructive to show a more general-purpose interface for sequences and an implementation of it for Catalan numbers.
First, <code>loader.lgt</code>:
<syntaxhighlight lang="logtalk">
:- initialization((
% libraries
logtalk_load(dates(loader)),
logtalk_load(meta(loader)),
logtalk_load(types(loader)),
% application
logtalk_load(seqp),
logtalk_load(catalan),
logtalk_load(catalan_test)
)).
</syntaxhighlight>
The interface is defined in <code>seqp.lgt</code> as a protocol:
<syntaxhighlight lang="logtalk">
:- protocol(seqp).
:- public(init/0). % reset to a beginning state if meaningful
:- public(nth/2). % get the nth value of the sequence
:- public(to_nth/2). % get from the start to the nth value of the sequence as a list
:- end_protocol.
</syntaxhighlight>
The implementation of a Catalan sequence generator is in <code>catalan.lgt</code>:
<syntaxhighlight lang="logtalk">
:- object(catalan, implements(seqp)).
:- private(catalan/2).
:- dynamic(catalan/2).
% Public interface.
init :- retractall(catalan(_,_)). % flush any memoized results
nth(N, V) :- \+ catalan(N, V), catalan_(N, V), !. % generate iff it's not been memoized
nth(N, V) :- catalan(N, V), !. % otherwise use the memoized version
to_nth(N, L) :-
integer::sequence(0, N, S), % generate a list of 0 to N
meta::map(nth, S, L). % map the nth/2 predicate to the list for all Catalan numbers up to N
% Local helper predicates.
catalan_(N, V) :-
N > 0, % calculate
N1 is N - 1,
N2 is N + 1,
catalan_(N1, V1), % via a recursive call
V is V1 * 2 * (2 * N - 1) // N2,
assertz(catalan(N, V)). % and memoize the result
catalan_(0, 1).
:- end_object.
</syntaxhighlight>
This is a memoizing implementation whose impact we will check in the test. The <code>init/0</code> predicate flushes any memoized results.
The test driver is a simple one that generates the first fifteen Catalan numbers four times, comparing times with and without memoization. From <code>catalan_test.lgt</code>:
<syntaxhighlight lang="logtalk">
:- object(catalan_test).
:- public(run/0).
run :-
% put the object into a known initial state
catalan::init,
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C1), D1),
% first 15 Catalan numbers again, twice, recording duration.
time_operation(catalan::to_nth(15, C2), D2),
time_operation(catalan::to_nth(15, C3), D3),
% reset the object again
catalan::init,
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C4), D4),
% ensure the results were the same each time
C1 = C2, C2 = C3, C3 = C4,
% write the results and durations of each run
write(C1), write(' '), write(D1), nl,
write(C2), write(' '), write(D2), nl,
write(C3), write(' '), write(D3), nl,
write(C4), write(' '), write(D4), nl.
% visual inspection should show all results the same
% first and final durations should be much larger
:- meta_predicate(time_operation(0, *)).
time_operation(Goal, Duration) :-
time::cpu_time(Before),
call(Goal),
time::cpu_time(After),
Duration is After - Before.
:- end_object.
</syntaxhighlight>
{{Out}}
The session at the top-level looks like this:
<pre>
?- {loader}.
% ... messages elided ...
% (0 warnings)
true.
?- catalan_test::run.
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001603
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.000306
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.00026
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001346
true.
</pre>
This test shows:
# The <code>nth/2</code> predicate works (since <code>to_nth/2</code> is implemented in terms of it).
# The <code>to_nth/2</code> predicate works.
# Memoization generates a speedup of between ~4.5× to ~6.2× over generating from scratch.
=={{header|Lua}}==
<syntaxhighlight lang="lua">-- recursive with memoization
Line 3,180 ⟶ 4,137:
/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */</syntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map (show . catalan) [0..14]))]
catalan :: num->num
catalan 0 = 1
catalan n = (4*n - 2) * catalan (n - 1) div (n + 1)</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CatalanNumbers;
Line 3,246 ⟶ 4,227:
ReadChar
END CatalanNumbers.</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math
Line 3,857 ⟶ 4,839:
13 => 742900 742900 742900
14 => 2674440 2674440 2674440</pre>
=={{header|PL/0}}==
{{trans|Tiny BASIC}}
Integers are limited to 32767 so only the first ten Catalan numbers can be represented. To avoid internal overflow, the program subtracts something clever from <code>c</code> and then adds it back at the end.
<syntaxhighlight lang="pascal">
var n, c, i;
begin
n := 0; c := 1;
! c;
while n <= 9 do
begin
n := n + 1;
i := 0;
while c > 0 do
begin
c := c - (n + 1);
i := i + 1
end;
c := 2 * (2 * n - 1) * c / (n + 1);
c := c + 2 * i * (2 * n - 1);
! c
end;
end.
</syntaxhighlight>
{{out}}
<pre>
1
1
2
5
14
42
132
429
1430
4862
16796
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">catalan: procedure options (main); /* 23 February 2012 */
Line 4,099 ⟶ 5,120:
true .
</pre>
=={{header|Python}}==
Three algorithms including explicit memoization. (Pythons [http://svn.python.org/view/python/branches/release31-maint/Modules/mathmodule.c?revision=82224&view=markup factorial built-in function] is not memoized internally).
Line 4,595 ⟶ 5,554:
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def factorial(n)
(1..n).reduce(1, :*)
Line 4,610 ⟶ 5,568:
def catalan_rec1(n)
return 1 if n == 0
(0...n).
end
Line 4,662 ⟶ 5,620:
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn c_n(n: u64) -> u64 {
Line 4,839 ⟶ 5,773:
14 2674440
</pre>
=={{header|Standard ML}}==
<syntaxhighlight lang="sml">(*
Line 5,018 ⟶ 5,921:
C_49 = 509552245179617138054608572
</pre>
== {{header|TypeScript}} ==
Line 5,073 ⟶ 5,954:
15 9694845
</pre>
=={{header|Ursala}}==
<syntaxhighlight lang="ursala">#import std
Line 5,246 ⟶ 6,128:
Time Elapsed: 76 μs
</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
Line 5,490 ⟶ 6,141:
}
}</syntaxhighlight>
{{out}}
<pre>
Line 5,520 ⟶ 6,170:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="
import "./math" for Int
var catalan = Fn.new { |n|
Line 5,583 ⟶ 6,233:
15 9694845
</pre>
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun catalan (n)
Line 5,625 ⟶ 6,276:
2674440
</pre>
=={{header|zkl}}==
Uses GMP to calculate big factorials.
| |||