Catalan numbers: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 21:
*[[Evaluate binomial coefficients]]
<br><br>
=={{header|11l}}==
<syntaxhighlight lang="11l">V c = 1
L(n) 1..15
print(c)
Line 45 ⟶ 44:
2674440
</pre>
=={{header|360 Assembly}}==
Very compact version.
<syntaxhighlight lang="360asm">CATALAN CSECT 08/09/2015
USING CATALAN,R15
LA R7,1 c=1
Line 88 ⟶ 86:
15 9694845
</pre>
=={{header|ABAP}}==
This works for ABAP Version 7.40 and above
<syntaxhighlight lang=
report z_catalan_numbers.
Line 146 ⟶ 143:
C(14) = 2674440
</pre>
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<syntaxhighlight lang=
PROC Main()
Line 188 ⟶ 184:
C(15)=9694845
</pre>
=={{header|Ada}}==
<syntaxhighlight lang=
procedure Test_Catalan is
Line 225 ⟶ 220:
15 = 9694845
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68"># calculate the first few catalan numbers, using LONG INT values #
# (64-bit quantities in Algol 68G which can handle up to C23) #
Line 278 ⟶ 272:
15: 9694845
</pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw">begin
% print the catalan numbers up to C15 %
integer Cprev;
Line 309 ⟶ 302:
15: 9694845
</pre>
=={{header|APL}}==
<syntaxhighlight lang="apl"> {(!2×⍵)÷(!⍵+1)×!⍵}(⍳15)-1</syntaxhighlight>
{{out}}
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">catalan: function [n][
if? n=0 -> 1
else -> div (catalan n-1) * (4*n)-2 n+1
Line 346 ⟶ 337:
14 2674440
15 9694845</pre>
=={{header|AutoHotkey}}==
As AutoHotkey has no BigInt, the formula had to be tweaked to prevent overflow. It still fails after n=22
<syntaxhighlight lang=
out .= "`n" Catalan(A_Index)
Msgbox % clipboard := SubStr(out, 2)
Line 385 ⟶ 375:
2674440
9694845</pre>
=={{header|AWK}}==
<syntaxhighlight lang=
BEGIN {
for (i=0; i<=15; i++) {
Line 422 ⟶ 411:
15 9694845
</pre>
=={{header|BASIC}}==
{{works with|FreeBASIC}}
Line 429 ⟶ 417:
Use of <code>REDIM PRESERVE</code> means this will not work in QBasic (although that could be worked around if desired).
<syntaxhighlight lang="qbasic">DECLARE FUNCTION catalan (n as INTEGER) AS SINGLE
REDIM SHARED results(0) AS SINGLE
Line 465 ⟶ 453:
==={{header|GW-BASIC}}===
<syntaxhighlight lang="gwbasic">10 DIM C(15)
20 C(0) = 1
30 PRINT 0, C(0)
Line 479 ⟶ 467:
==={{header|Minimal BASIC}}===
{{trans|GW-BASIC}}
<syntaxhighlight lang="gwbasic">
10 REM Catalan numbers
20 DIM C(15)
Line 499 ⟶ 487:
The specification asks for the first 15 Catalan numbers. A lot of the other implementations produce either C(0) to C(15), which is 16 numbers, or else C(1) to C(15)—which is 15 numbers, but I'm not convinced they're the first 15. This program produces C(0) to C(14).
<syntaxhighlight lang="basic"> 10 FOR N=0 TO 14
20 LET X=N
30 GOSUB 130
Line 535 ⟶ 523:
==={{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.
<syntaxhighlight lang=
10 LET N = 0
20 LET C = 1
Line 562 ⟶ 550:
9 4862
10 16796</pre>
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="freebasic">function factorial(n)
if n = 0 then return 1
return n * factorial(n - 1)
Line 600 ⟶ 587:
{{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
Line 626 ⟶ 612:
742900
2674440</pre>
=={{header|Befunge}}==
{{trans|Ada}}
<syntaxhighlight lang="befunge">0>:.:000p1>\:00g-#v_v
v 2-1*2p00 :+1g00\< $
> **00g1+/^v,*84,"="<
Line 652 ⟶ 637:
14 = 2674440
15 = 9694845</pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">Cat←{ 0⊸<◶⟨1, (𝕊-⟜1)×(¯2+4×⊢)÷1+⊢⟩ 𝕩 }
Fact ← ×´1+↕
Cat1 ← { # direct formula
⌊0.5 + (Fact 2×𝕩) ÷ (Fact 𝕩+1) × Fact 𝕩
}
Cat2 ← { # header based recursion
0: 1;
(𝕊 𝕩-1)×2×(1-˜2×𝕩)÷𝕩+1
}
Cat¨ ↕15
Cat1¨ ↕15
Cat2¨ ↕15</syntaxhighlight>
{{out}}
<pre>⟨ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 ⟩</pre>
=={{header|Bracmat}}==
<syntaxhighlight lang="bracmat">( out$straight
& ( C
=
Line 712:
);</syntaxhighlight>
{{out}}
<syntaxhighlight lang="bracmat">straight
C0 = 1
C1 = 1
Line 781:
+ 9694845*X^15
</syntaxhighlight>
=={{header|Brat}}==
<syntaxhighlight lang="brat">catalan = { n |
true? n == 0
{ 1 }
Line 810 ⟶ 809:
15 - 9694845
</pre>
=={{header|C}}==
All three methods mentioned in the task:
<syntaxhighlight lang="c">#include <stdio.h>
typedef unsigned long long ull;
Line 894 ⟶ 875:
14 2674440 2674440 2674440
15 9694845 9694845 9694845
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">namespace CatalanNumbers
{
/// <summary>
Line 1,066 ⟶ 1,046:
It took 0.3 to execute
</pre>
=={{header|C++}}==
===4 Classes===
We declare 4 classes representing the four different algorithms for calculating Catalan numbers as given in the description of the task. In addition, we declare two supporting classes for the calculation of factorials and binomial coefficients. Because these two are only internal supporting code they are hidden in namespace 'detail'. Overloading the function call operator to execute the calculation is an obvious decision when using C++. (algorithms.h)
<syntaxhighlight lang="cpp">#if !defined __ALGORITHMS_H__
#define __ALGORITHMS_H__
Line 1,131 ⟶ 1,110:
#endif //!defined __ALGORITHMS_H__</syntaxhighlight>
Here is the implementation of the algorithms. The c'tor of each class tells us the algorithm which will be used. (algorithms.cpp)
<syntaxhighlight lang="cpp">#include <iostream>
using std::cout;
using std::endl;
Line 1,233 ⟶ 1,212:
}</syntaxhighlight>
In order to test what we have done, a class Test is created. Using the template parameters N (number of Catalan numbers to be calculated) and A (the kind of algorithm to be used) the compiler will create code for all the test cases we need. What would C++ be without templates ;-) (tester.h)
<syntaxhighlight lang="cpp">#if !defined __TESTER_H__
#define __TESTER_H__
Line 1,260 ⟶ 1,239:
#endif //!defined __TESTER_H__</syntaxhighlight>
Finally, we test the four different algorithms. Note that the first one (direct calculation using the factorial) only works up to N = 10 because some intermediate result (namely (2n)! with n = 11) exceeds the boundaries of an unsigned 64 bit integer. (catalanNumbersTest.cpp)
<syntaxhighlight lang="cpp">#include "algorithms.h"
#include "tester.h"
using namespace rosetta::catalanNumbers;
Line 1,339 ⟶ 1,318:
C(15) = 9694845
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang=
(defn catalan-numbers-direct []
Line 1,358 ⟶ 1,336:
user> (take 15 (catalan-numbers-recursive))
(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)</syntaxhighlight>
=={{header|Common Lisp}}==
With all three methods defined.
<syntaxhighlight lang="lisp">(defun catalan1 (n)
;; factorial. CLISP actually has "!" defined for this
(labels ((! (x) (if (zerop x) 1 (* x (! (1- x))))))
Line 1,389 ⟶ 1,366:
(format t "~%Method ~d:~%" i)
(dotimes (i 16) (format t "C(~2d) = ~d~%" i (funcall f i))))</syntaxhighlight>
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">require "big"
require "benchmark"
Line 1,462 ⟶ 1,438:
15 : 9694845 9694845 9694845
</pre>
=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.bigint, std.functional, std.range;
auto product(R)(R r) { return reduce!q{a * b}(1.BigInt, r); }
Line 1,488 ⟶ 1,463:
[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>
=={{header|Delphi}}==
See [https://www.rosettacode.org/wiki/Catalan_numbers#Pascal Pascal].
=={{header|EasyLang}}==
<syntaxhighlight lang="text">func catalan n . ans .
if n = 0
ans = 1
Line 1,522 ⟶ 1,496:
2674440
</pre>
=={{header|EchoLisp}}==
{{incorrect|Echolisp|series starts 1, 1, 2, ...}}
<syntaxhighlight lang="scheme">
(lib 'sequences)
(lib 'bigint)
Line 1,564 ⟶ 1,537:
→ 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
=={{header|EDSAC order code}}==
The Catalan numbers are here computed by the second method, as a sum of products.
Line 1,573 ⟶ 1,545:
But if we multiply two 35-bit integers A and B, the result is really A*B*(2^-68),
and needs to be multiplied by 2^34 to get the same scaling as for A and B.
<syntaxhighlight lang="edsac">
[Calculation of Catalan numbers.
EDSAC program, Initial Orders 2.]
Line 1,693 ⟶ 1,665:
15 9694845
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang=
class
APPLICATION
Line 1,752 ⟶ 1,723:
2674440
</pre>
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule Catalan do
def cat(n), do: div( factorial(2*n), factorial(n+1) * factorial(n) )
Line 1,788 ⟶ 1,758:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">-module(catalan).
-export([test/0]).
Line 1,829 ⟶ 1,798:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
=={{header|ERRE}}==
<syntaxhighlight lang="text">PROGRAM CATALAN
PROCEDURE CATALAN(N->RES)
Line 1,866 ⟶ 1,834:
15 = 9694845
</pre>
=={{header|Euphoria}}==
<syntaxhighlight lang=
--User:Lnettnay
Line 1,910 ⟶ 1,877:
9694845
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
Seq.unfold(fun (c,n) -> let cc = 2*(2*n-1)*c/(n+1) in Some(c,(cc,n+1))) (1,1) |> Seq.take 15 |> Seq.iter (printf "%i, ")
</syntaxhighlight>
Line 1,919 ⟶ 1,885:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
</pre>
=={{header|Factor}}==
The first method:
<syntaxhighlight lang="factor">USING: kernel math math.combinatorics prettyprint ;
: catalan ( n -- n ) [ 1 + recip ] [ 2 * ] [ nCk * ] tri ;
Line 1,947 ⟶ 1,912:
The last method, memoized by using arrays.
<syntaxhighlight lang="factor">USING: kernel math prettyprint sequences ;
: next ( seq -- newseq )
Line 1,959 ⟶ 1,924:
{{out}}
Similar to above.
=={{header|Fantom}}==
{{incorrect|Fantom|series starts 1, 1, 2, ...}}
<syntaxhighlight lang="fantom">class Main
{
static Int factorial (Int n)
Line 2,032 ⟶ 1,996:
15 -2 9694845 9694845
</pre>
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">Func Catalan(n)=(2*n)!/((n+1)!*n!).;
for i=1 to 15 do !Catalan(i);!' ' od;</syntaxhighlight>
{{out}}<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|Forth}}==
<syntaxhighlight lang="forth">: catalan ( n -- ) 1 swap 1+ 1 do dup cr . i 2* 1- 2* i 1+ */ loop drop ;</syntaxhighlight>
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<syntaxhighlight lang="fortran">program main
!=======================================================================================
implicit none
Line 2,111 ⟶ 2,072:
===============
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Function factorial(n As UInteger) As UInteger
Line 2,174 ⟶ 2,134:
15 9694845 9694845 9694845
</pre>
=={{header|Frink}}==
Frink includes efficient algorithms for calculating arbitrarily-large binomial coefficients and automatically caches factorials.
<syntaxhighlight lang="frink">catalan[n] := binomial[2n,n]/(n+1)
for n = 0 to 15
println[catalan[n]]</syntaxhighlight>
=={{header|FunL}}==
<syntaxhighlight lang="funl">import integers.choose
import util.TextTable
Line 2,229 ⟶ 2,187:
+----+------------+---------+-----------+
</pre>
=={{header|Fōrmulæ}}==
Line 2,237 ⟶ 2,194:
In '''[https://formulae.org/?example=Catalan_numbers this]''' page you can see the program(s) related to this task and their results.
=={{header|GAP}}==
<syntaxhighlight lang="gap">Catalan1 := n -> Binomial(2*n, n) - Binomial(2*n, n - 1);
Catalan2 := n -> Binomial(2*n, n)/(n + 1);
Line 2,270 ⟶ 2,226:
# Same output for all four:
# [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440 ]</syntaxhighlight>
=={{header|Go}}==
Direct:
<syntaxhighlight lang="go">package main
import (
Line 2,305 ⟶ 2,260:
</pre>
Recursive (alternative):
<syntaxhighlight lang="go">
package main
Line 2,352 ⟶ 2,307:
9694845
</pre>
=={{header|Groovy}}==
<syntaxhighlight lang=
class Catalan
{
Line 2,397 ⟶ 2,351:
9694845
</pre>
=={{header|Harbour}}==
<syntaxhighlight lang="visualfoxpro">
PROCEDURE Main()
LOCAL i
Line 2,437 ⟶ 2,390:
5: 9694845
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">-- Three infinite lists, corresponding to the three
-- definitions in the problem statement.
Line 2,467 ⟶ 2,419:
[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>
=={{header|Icon}} and {{header|Unicon}}==
<syntaxhighlight lang=
every writes(catalan(0 to 14)," ")
end
Line 2,483 ⟶ 2,434:
{{out}}
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre>
=={{header|J}}==
<syntaxhighlight lang="j"> ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</syntaxhighlight>
=={{header|Java}}==
Replace double inexact computations with BigInteger implementation.
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
Line 2,620 ⟶ 2,569:
C(15) = 9,694,845 9,694,845 9,694,845
</pre>
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript"><html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
Line 2,669 ⟶ 2,617:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
=={{header|jq}}==
{{ works with|jq|1.4 }}
Line 2,676 ⟶ 2,623:
that formula is used (a) to define a function for computing a single Catalan number; (b) to define a function for generating a sequence of Catalan numbers; and (c) to write a single expression for generating a sequence of Catalan numbers using jq's builtin "recurse/1" filter.
==== Compute a single Catalan number====
<syntaxhighlight lang="jq">def catalan:
if . == 0 then 1
elif . < 0 then error("catalan is not defined on \(.)")
Line 2,682 ⟶ 2,629:
end;</syntaxhighlight>
'''Example 1'''
<syntaxhighlight lang="jq">(range(0; 16), 100) as $i | $i | catalan | [$i, .]</syntaxhighlight>
{{Out}}
<div style="overflow:scroll; height:150px;">
<syntaxhighlight lang="sh">$ jq -M -n -c -f Catalan_numbers.jq
[0,1]
[1,1]
Line 2,706 ⟶ 2,653:
==== Generate a sequence of Catalan numbers ====
<syntaxhighlight lang="jq">def catalan_series(max):
def _catalan: # state: [n, catalan(n)]
if .[0] > max then empty
Line 2,716 ⟶ 2,663:
</syntaxhighlight>
'''Example 2''':
<syntaxhighlight lang="jq">catalan_series(15)</syntaxhighlight>
{{Out}}
As above for 0 to 15.
==== An expression to generate Catalan numbers ====
<syntaxhighlight lang="jq">
[0,1]
| recurse( if .[0] == 15 then empty
Line 2,727 ⟶ 2,674:
{{out}}
As above for 0 to 15.
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">catalannum(n::Integer) = binomial(2n, n) ÷ (n + 1)
@show catalannum.(1:15)
Line 2,741 ⟶ 2,687:
(In the second example, we have used arbitrary-precision integers to avoid overflow for large Catalan numbers.)
=={{header|K}}==
<syntaxhighlight lang="k"> catalan: {_{*/(x-i)%1+i:!y-1}[2*x;x+1]%x+1}
catalan'!:15
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</syntaxhighlight>
=={{header|Kotlin}}==
{{works with|Java|1.7.0}}
{{works with|Kotlin|1.1.4}}
<syntaxhighlight lang="scala">abstract class Catalan {
abstract operator fun invoke(n: Int) : Double
Line 2,820 ⟶ 2,764:
2674440 2674440 2674440
9694845 9694845 9694845</pre>
=={{header|langur}}==
{{trans|Perl}}
<syntaxhighlight lang="langur">val .factorial = f if(.x < 2: 1; .x x self(.x - 1))
val .catalan = f(.n) .factorial(2 x .n) / .factorial(.n+1) / .factorial(.n)
Line 2,851 ⟶ 2,794:
10000: 224537812493385215633593584257360578701103586219365887773293713835854436588700534490998102719114320210209905393799589701149327326500953702713977513001838761306936534407802585494454599941773729984591764542782202886796997833276495496514760245912220654267091568311812071300891219894022165175451441066691435091975969499731921675488934120638046514134965974069039677192984714638704528752769863567952620334847707274529741976558104236293861846622622783294667505268651205024766408784881872997404042356319626323351089169906635603513309014645157443570842822082866699012415455339518777770781742052837799476906230350785959040487158118992753484022865373274100095762968510625236915280143408460651206678398725681703811505423791566261735329550627967717189932855983913468867794806585863794483869239933179341394259456515091026456652770409848702116046445406995085092488210998732255656992243441519938747425554228724734242623566663631968254490897214106655375215196762710825001305055093871863518797311135688370964194817463890187212845332422257193414201244344808864449873736345425670715824582633802476282521798739438044652622163657359012681653473214512797365047989922327391063907061792126264420963262176161781711086630089636828211837643128677915076724947168653050318426339007489738275045346257959685376480042860870398232333705506506342394485443047987642390287346746539674780326188825579548593281319807827279403944008553690033855132088140116099772393778770685018936338194366302053586633406848404622048675525765095697363909787189635178694239275237185046710057476484117945279786897787624602379494797322427251542758312638233073625857897083435831841717971137851874666094337671443717108457737153283641719103639784923520519013700030680553564442331411313831920775983175313709250333784211385811480015293165463406576311626295629412110652218717603537723650144357966952842696678735624157616428716812764985074925414219421312810089785108621126934245959900367104035334200067714905754827856122801987429837706493130435832752072139392743006620396370486473952500144779413596417260472218266529167783118015414918168260722824885550181735638670588682513610805160133611349864194033776132438535863120087679096358696928233598996870302136347936567444208209125300149683552369341937471817860835774359234009557030148123353114950735217736514617017504851011193104728986836180908987352236659629183725016607437110422583156042941955830763092095074443334625318588569114114087985404048889671202396824806275701581378689568449507132793603852731445602923990458926101180821029108808623323378547869169352237448925371763574346501610378415722137519019474474794069155118626291447578558908522430436148987521551911541787974276591708584289036595642180860178815462862735993859177180582760389253540408842580225467216988321950591728369194164290645992782274919561096308372635908842325870580231011459216934235078490764707633348336131667313582584404397290232519769625777374165187949140092779343812345117947306771376053099536367169631889642304360871187460737580808157222861127968703067542270175460553478533349238111434409526724363429611803844595968793121871649699680963646793415774160274520010905236593324062464542927011227158945796188186430711399250096518886617184049325827319276468018789191520522185358895653192882843061349706085770767046601045697944646638311930027354235643643713545212361580694059553720806659066661496416423676930095857438882302891350789287291844752601744462789158506243012088536936184422120232369244564444689340142897415432231452353338115944183447986470689449043710051589958391273681116292415738776171575775695905846247205522469202801517417551374761549677412720803623129527503286287755308576386461385928958587649159872019202866614901547860974883963007792442796064165417207167072370586790722366932349325253877744621251386864069101337572557790214048760202008337611577675840153696735860276810033694744314488435390547908483357054897387317002405793108554524629034558098886977538473481750772616164313845337139245688079995996839933620829828339492800825536599964878893947278408890351634126931068657027524005795713514365098086505030570362785115155293306343520969872400876180105031975302255898787642403303027682634969586730202117121076117629457710028105378124677420093990476071697970354661002217702623344454780740808459286778553016318604430682610618871098652904537323336381304469735192868285840882036271136058499391069436145426450229039329475974178236465920534171895204155964515055983303017823692138977622016292722019365841360360274557488926673754175222061483328914099598663902320310143583379354121664996173733086613692927391384486261610892314450463841637667054196985332620403539011932606618414419229492637564924726411270720189611019154677281846409387514072618176832310721327819277699943226895919915049652045449281057471199978267843961724883768772155477073354744908923995448752333726740642292872107500458349718026322755698226793850983280706045951407323891263270928264657562125955511946782954645656015480418543664557515041692091317941000997342935512311493290722434384401250133402934163457264794261787386862382738330195237770190998115114193014769006071380834085352290585937952429981509893303796306071520571655936820282768086579891336876000368502562579738337809071051261343359121744773055264455701014137255399929760233753812017596045145926791136761130783810840502248142803073720015451941006030172192834375431286154255159659778817089767964922549014569972777126726537787896968876337799235679125368824867754881036161730805613471278633981478858113141202728303435218970292775366288829203013873713349923690394124920402725698544786016048685431525811047414746045227535216327530901827040588505255466803793791888002231571686068617764292584075135236237044383334893874602177596602979234717936820827427229615827657960492946059695301906791494260652411424538532836730097985187522379068364429583532675896349363295120431429006688249818006722311568902288350452581968418068616818268667067741994472455501649753611708445979082338902214467454627107888156489438584617793175431865532382711812960546611287516640
</pre>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">print "non-recursive version"
print catNonRec(5)
for i = 0 to 15
Line 2,964 ⟶ 2,906:
14 = 2674440
15 = 9694845</pre>
=={{header|Logo}}==
<syntaxhighlight lang="logo">to factorial :n
output ifelse [less? :n 1] 1 [product :n factorial difference :n 1]
end
Line 2,994 ⟶ 2,935:
742900
2674440</pre>
=={{header|Lua}}==
<syntaxhighlight lang=
catalan = {[0] = 1}
setmetatable(catalan, {
Line 3,026 ⟶ 2,966:
742900
2674440</pre>
=={{header|MAD}}==
<syntaxhighlight lang=
DIMENSION C(15)
Line 3,059 ⟶ 2,998:
C(13) = 742900
C(14) = 2674440</pre>
=={{header|Maple}}==
<syntaxhighlight lang=
return seq( (2*i)!/((i + 1)!*i!), i = 0 .. n - 1 );
end proc:
Line 3,070 ⟶ 3,008:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang=
{{out|Sample Output}}
<syntaxhighlight lang=
//TableForm=
1
Line 3,092 ⟶ 3,029:
2674440
9694845</syntaxhighlight>
=={{header|MATLAB}} / {{header|Octave}}==
<syntaxhighlight lang=
for i = (1:length(n))
n(i) = (1/(n(i)+1))*nchoosek(2*n(i),n(i));
Line 3,100 ⟶ 3,036:
end</syntaxhighlight>
The following version computes at the same time the n first Catalan numbers (including C0).
<syntaxhighlight lang=
n = [1 cumprod((2:4:4*n-6) ./ (2:n))];
end</syntaxhighlight>
{{out|Sample Output}}
<syntaxhighlight lang=
ans =
Line 3,134 ⟶ 3,070:
The following version uses the identity Ln(x!)=Gammaln(x+1) and prod(1:x)=sum(ln(1:x))
<syntaxhighlight lang=
CatalanNumber=@(n) round(exp(gammaln(2*n+1)-sum(gammaln([n+2 n+1]))));
</syntaxhighlight>
{{out|Sample Output}}
<syntaxhighlight lang=
ans =
Line 3,151 ⟶ 3,087:
</syntaxhighlight>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">/* The following is an array function, hence the square brackets. It uses memoization automatically */
cata[n] := sum(cata[i]*cata[n - 1 - i], i, 0, n - 1)$
cata[0]: 1$
Line 3,162 ⟶ 3,098:
/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */</syntaxhighlight>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CatalanNumbers;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 3,229 ⟶ 3,164:
ReadChar
END CatalanNumbers.</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math
import strformat
Line 3,267 ⟶ 3,201:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
=={{header|OCaml}}==
<syntaxhighlight lang=
let return = ref 1 in
for i = 1 to n do
Line 3,354 ⟶ 3,287:
memoized (10000000 runs) : 0.167
...</pre>
=={{header|Oforth}}==
<syntaxhighlight lang=
n ifZero: [ 1 ] else: [ catalan( n 1- ) 2 n * 1- * 2 * n 1+ / ] ;</syntaxhighlight>
Line 3,366 ⟶ 3,298:
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
</pre>
=={{header|ooRexx}}==
Three versions of this.
<syntaxhighlight lang=
say "catI("i") =" .catalan~catI(i)
say "catR1("i") =" .catalan~catR1(i)
Line 3,499 ⟶ 3,430:
catR1(15) = 9694845
catR2(15) = 9694845</pre>
=={{header|PARI/GP}}==
Memoization is not worthwhile; PARI has fast built-in facilities for calculating binomial coefficients and factorials.
<syntaxhighlight lang="parigp">catalan(n)=binomial(2*n,n+1)/n</syntaxhighlight>
A second version:
<syntaxhighlight lang="parigp">catalan(n)=(2*n)!/(n+1)!/n!</syntaxhighlight>
Naive version with binary splitting:
<syntaxhighlight lang="parigp">catalan(n)=prod(k=n+2,2*n,k)/prod(k=2,n,k)</syntaxhighlight>
Naive version:
<syntaxhighlight lang="parigp">catalan(n)={
my(t=1);
for(k=n+2,2*n,t*=k);
Line 3,515 ⟶ 3,445:
};</syntaxhighlight>
The first version takes about 1.5 seconds to compute the millionth Catalan number, while the second takes 3.9 seconds. The naive implementations, for comparison, take 21 and 45 minutes. In any case, printing the first 15 is simple:
<syntaxhighlight lang="parigp">vector(15,n,catalan(n))</syntaxhighlight>
=={{header|Pascal}}==
<syntaxhighlight lang="pascal">Program CatalanNumbers(output);
function catalanNumber1(n: integer): double;
Line 3,558 ⟶ 3,487:
14 2674440
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">sub factorial { my $f = 1; $f *= $_ for 2 .. $_[0]; $f; }
sub catalan {
my $n = shift;
Line 3,568 ⟶ 3,496:
print "$_\t@{[ catalan($_) ]}\n" for 0 .. 20;</syntaxhighlight>
For computing up to 20 ish, memoization is not needed. For much bigger numbers, this is faster:
<syntaxhighlight lang="perl">my @c = (1);
sub catalan {
use bigint;
Line 3,579 ⟶ 3,507:
That has two downsides: high memory use and slow access to an isolated large value. Using a fast binomial function can solve both these issues. The downside here is if the platform doesn't have the GMP library then binomials won't be fast.
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use ntheory qw/binomial/;
sub catalan {
my $n = shift;
Line 3,585 ⟶ 3,513:
}
print "$_\t", catalan($_), "\n" for 0 .. 10000;</syntaxhighlight>
=={{header|Phix}}==
See also [[Catalan_numbers/Pascal%27s_triangle#Phix]] which may be faster.
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">-- returns inf/-nan for n>85, and needs the rounding for n>=14, accurate to n=29</span>
Line 3,652 ⟶ 3,579:
=== memoized recursive gmp version ===
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
Line 3,689 ⟶ 3,616:
100: 896519947090131496687170070074100632420837521538745909320
</pre>
=={{header|PHP}}==
<syntaxhighlight lang="php"><?php
class CatalanNumbersSerie
Line 3,743 ⟶ 3,669:
15 = 9694845
</pre>
<syntaxhighlight lang="php">
<?php
$n = 15;
Line 3,762 ⟶ 3,688:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670
</pre>
=={{header|Picat}}==
{{works with|Picat}}
<syntaxhighlight lang=
table
factorial(0) = 1.
Line 3,800 ⟶ 3,725:
14. 2674440 = 2674440
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang=
(de fact (N)
(if (=0 N)
Line 3,851 ⟶ 3,775:
13 => 742900 742900 742900
14 => 2674440 2674440 2674440</pre>
=={{header|PL/I}}==
<syntaxhighlight lang=
declare (i, n) fixed;
Line 3,898 ⟶ 3,821:
6564120420
</pre>
=={{header|PlainTeX}}==
<syntaxhighlight lang="tex">\newcount\n
\newcount\r
\newcount\x
Line 3,922 ⟶ 3,844:
\bye</syntaxhighlight>
=={{header|PowerShell}}==
<syntaxhighlight lang=
function Catalan([uint64]$m) {
function fact([bigint]$n) {
Line 3,958 ⟶ 3,879:
===An Alternate Version===
This version could easily be modified to work with big integers.
<syntaxhighlight lang=
function Get-CatalanNumber
{
Line 4,012 ⟶ 3,933:
</syntaxhighlight>
Get the first fifteen Catalan numbers as a PSCustomObject:
<syntaxhighlight lang=
0..14 | Get-CatalanNumber
</syntaxhighlight>
Line 4,036 ⟶ 3,957:
</pre>
To return only the array of Catalan numbers:
<syntaxhighlight lang=
(0..14 | Get-CatalanNumber).CatalanNumber
</syntaxhighlight>
Line 4,057 ⟶ 3,978:
2674440
</pre>
=={{header|Prolog}}==
{{Works with|SWI-Prolog}}
<syntaxhighlight lang=
length(L1, N),
L = [1 | L1],
Line 4,097 ⟶ 4,017:
true .
</pre>
=={{header|PureBasic}}==
Using the third formula...
<syntaxhighlight lang=
; numerator by the smallest denominator
Line 4,161 ⟶ 4,080:
33 212336130412243110
</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,168 ⟶ 4,086:
{{Works with|Python|3}}
<syntaxhighlight lang="python">from math import factorial
import functools
Line 4,238 ⟶ 4,156:
The third definition is directly expressible, as an infinite series, in terms of '''itertools.accumulate''':
<syntaxhighlight lang="python">'''Catalan numbers'''
from itertools import accumulate, chain, count, islice
Line 4,303 ⟶ 4,221:
742900
2674440</pre>
=={{header|Quackery}}==
<syntaxhighlight lang=
[ times [ i 1+ / ] ] is /n! ( n --> n )
Line 4,332 ⟶ 4,249:
14 : 2674440
</pre>
=={{header|R}}==
<syntaxhighlight lang="r">catalan <- function(n) choose(2*n, n)/(n + 1)
catalan(0:15)
[1] 1 1 2 5 14 42 132 429 1430
[10] 4862 16796 58786 208012 742900 2674440 9694845</syntaxhighlight>
=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket
(require planet2)
; (install "this-and-that") ; uncomment to install
Line 4,356 ⟶ 4,271:
'(1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)
</pre>
=={{header|Raku}}==
(formerly Perl 6)
Line 4,362 ⟶ 4,276:
The recursive formulas are easily written into a constant array, either:
<syntaxhighlight lang="raku" line>constant Catalan = 1, { [+] @_ Z* @_.reverse } ... *;</syntaxhighlight>
or
<syntaxhighlight lang="raku" line>constant Catalan = 1, |[\*] (2, 6 ... *) Z/ 2 .. *;
Line 4,387 ⟶ 4,301:
742900
2674440</pre>
=={{header|REXX}}==
===version 1===
Line 4,397 ⟶ 4,310:
has been rearranged to:
:::::::: <big> (n+1) * [fact(n) **2] </big>
<syntaxhighlight lang="rexx">/*REXX program calculates and displays Catalan numbers using four different methods. */
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then do; HI=15; LO=0; end /*No args? Then use a range of 0 ──► 15*/
Line 4,464 ⟶ 4,377:
===version 2===
Implements the 3 methods shown in the task description
<syntaxhighlight lang="rexx">/* REXX ---------------------------------------------------------------
* 01.07.2014 Walter Pachl
*--------------------------------------------------------------------*/
Line 4,539 ⟶ 4,452:
20 6564120420 6564120420 6564120420
n c1.n c2.n c3.n</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
for n = 1 to 15
see catalan(n) + nl
Line 4,569 ⟶ 4,481:
9694845
</pre>
=={{header|Ruby}}==
{{libheader|RubyGems}}
<syntaxhighlight lang="ruby">def factorial(n)
(1..n).reduce(1, :*)
end
Line 4,637 ⟶ 4,548:
15 : 9694845 9694845 9694845
</pre>
=={{header|Run BASIC}}==
<syntaxhighlight lang=
PRINT i;" ";catalan(i)
NEXT
Line 4,662 ⟶ 4,572:
14 2674440
15 9694845</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn c_n(n: u64) -> u64 {
match n {
0 => 1,
Line 4,694 ⟶ 4,603:
c(14) = 2674440
c(15) = 9694845</pre>
=={{header|Scala}}==
Simple and straightforward. Noticeably out of steam without memoizing at about 5000.
<syntaxhighlight lang="scala">
object CatalanNumbers {
def main(args: Array[String]): Unit = {
Line 4,730 ⟶ 4,638:
catalan(15) = 9694845
</pre>
=={{header|Scheme}}==
Tail recursive implementation.
<syntaxhighlight lang="scheme">(define (catalan m)
(let loop ((c 1)(n 0))
(if (not (eqv? n m))
Line 4,757 ⟶ 4,664:
13: 742900
14: 2674440</pre>
=={{header|Seed7}}==
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
Line 4,789 ⟶ 4,695:
9694845
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func f(i) { i==0 ? 1 : (i * f(i-1)) }
func c(n) { f(2*n) / f(n) / f(n+1) }</syntaxhighlight>
With memoization:
<syntaxhighlight lang="ruby">func c(n) is cached {
n == 0 ? 1 : (c(n-1) * (4 * n - 2) / (n + 1))
}</syntaxhighlight>
Calling the function:
<syntaxhighlight lang="ruby">15.times { |i|
say "#{i}\t#{c(i)}"
}</syntaxhighlight>
Line 4,820 ⟶ 4,725:
14 2674440
</pre>
=={{header|smart BASIC}}==
<syntaxhighlight lang="qbasic">PRINT "Recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catrec(n)
Line 4,853 ⟶ 4,757:
catnonrec = temp
END DEF</syntaxhighlight>
=={{header|Standard ML}}==
<syntaxhighlight lang="sml">(*
* val catalan : int -> int
* Returns the nth Catalan number.
Line 4,887 ⟶ 4,790:
* 9694845
*)</syntaxhighlight>
=={{header|Stata}}==
<syntaxhighlight lang="stata">clear
set obs 15
gen catalan=1 in 1
Line 4,917 ⟶ 4,819:
| 2674440 |
+---------+</pre>
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">func catalan(_ n: Int) -> Int {
switch n {
case 0:
Line 4,953 ⟶ 4,854:
catalan(15) => 9694845
</pre>
=={{header|Tcl}}==
<syntaxhighlight lang="tcl">package require Tcl 8.5
# Memoization wrapper
Line 4,975 ⟶ 4,875:
}</syntaxhighlight>
Demonstration:
<syntaxhighlight lang="tcl">for {set i 0} {$i < 15} {incr i} {
puts "C_$i = [expr {catalan($i)}]"
}</syntaxhighlight>
Line 5,004 ⟶ 4,904:
C_49 = 509552245179617138054608572
</pre>
=={{header|TI-83 BASIC}}==
This problem is perfectly suited for a TI calculator.
<syntaxhighlight lang=
:Disp (2I)!/((I+1)!I!
:End</syntaxhighlight>
Line 5,030 ⟶ 4,929:
== {{header|TypeScript}} ==
{{trans|GW-BASIC}}
<syntaxhighlight lang="javascript">
// Catalan numbers
var c: number[] = [1];
Line 5,060 ⟶ 4,959:
15 9694845
</pre>
=={{header|Ursala}}==
<syntaxhighlight lang="ursala">#import std
#import nat
Line 5,088 ⟶ 4,986:
2674440,
9694845></pre>
=={{header|Vala}}==
<syntaxhighlight lang="vala">namespace CatalanNumbers {
public class CatalanNumberGenerator {
private static double factorial(double n) {
Line 5,235 ⟶ 5,132:
Time Elapsed: 76 μs
</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
Line 5,293 ⟶ 5,189:
</pre>
(Expect same result with "Catalan2 15")
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Function catalan(n)
catalan = factorial(2*n)/(factorial(n+1)*factorial(n))
Line 5,339 ⟶ 5,234:
15 = 9694845
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function Factorial(n As Double) As Double
Line 5,470 ⟶ 5,364:
CatalanNumber(15:9694845)
It took 0.8 to execute</pre>
=={{header|Vlang}}==
{{trans|Go}}
<syntaxhighlight lang="vlang">import math.big
fn main() {
Line 5,502 ⟶ 5,395:
2674440
</pre>
=={{header|Wortel}}==
<syntaxhighlight lang="wortel">; the following number expression calculcates the nth Catalan number
#~ddiFSFmSoFSn
; which stands for: dup dup inc fac swap fac mult swap double fac swap divide
Line 5,510 ⟶ 5,402:
!*#~ddiFSFmSoFSn @til 15
; returns [1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674439.9999999995]</syntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt
import "/math" for Int
Line 5,577 ⟶ 5,468:
15 9694845
</pre>
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun catalan (n)
(if (= n 0)
1
(* (/ (* 2 (- (* 2 n) 1)) (+ n 1)) (catalan (- n 1))) ) )
(defun range (x y)
(cons x
(if (< x y)
(range (+ x 1) y) ) ) )
(print (mapcar catalan (range 0 14)))</syntaxhighlight>
{{out}}
<pre>(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">code CrLf=9, IntOut=11;
int C, N;
[C:= 1;
IntOut(0, C); CrLf(0);
for N:= 1 to 14 do
[C:= C*2*(2*N-1)/(N+1);
IntOut(0, C); CrLf(0);
];
]</syntaxhighlight>
{{out}}
<pre>
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
</pre>
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">print " n First Second Third"
print " - ----- ------ -----"
print
Line 5,621 ⟶ 5,552:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|zkl}}==
Uses GMP to calculate big factorials.
<syntaxhighlight lang="zkl">var BN=Import("zklBigNum");
fcn catalan(n){
BN(2*n).factorial() / BN(n+1).factorial() / BN(n).factorial();
Line 5,678 ⟶ 5,564:
println("%2d --> %,d".fmt(100, catalan(100)));</syntaxhighlight>
And an iterative solution at works up to the limit of 64 bit ints (n=33). Would be 35 but need to avoid factional intermediate results.
<syntaxhighlight lang="zkl">fcn catalan(n){ (1).reduce(n,fcn(p,n){ 2*(2*n-1)*p/(n+1) },1) }</syntaxhighlight>
{{out}}
<pre>
Line 5,699 ⟶ 5,585:
100 --> 896,519,947,090,131,496,687,170,070,074,100,632,420,837,521,538,745,909,320
</pre>
=={{header|ZX Spectrum Basic}}==
{{trans|C}}
<syntaxhighlight lang="zxbasic">10 FOR i=0 TO 15
20 LET n=i: LET m=2*n
30 LET r=1: LET d=m-n
| |||