Exact Computation of the Catalan Number $C(2,050,572,903)$
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917207348346880 |
|---|---|
| author | Ramani, Mahesh |
| author_facet | Ramani, Mahesh |
| contents | This paper presents a two-phase algorithm for computing exact Catalan numbers at an unprecedented scale. The method is demonstrated by computing $C(n)$ for $n = 2,050,572,903$ yielding a result with a targeted $1,234,567,890$ decimal digits. To circumvent the memory limitations associated with evaluating large factorials, the algorithm operates exclusively in the prime-exponent domain. Phase 1 employs a parallel segmented sieve to enumerate primes up to $2n$ and applies Legendre's formula to determine the precise prime factorization of $C(n)$. The primes are grouped by exponent and serialized to disk. Phase 2 reconstructs the final integer using a memory-efficient balanced product tree with chunking. The algorithm runs on a time complexity of $Θ(n(\log n)^2)$ bit-operations and a space complexity of $Θ(n \log n)$ bits. This result represents the largest exact Catalan number computed to date. Performance statistics for a single-machine execution are reported, and verification strategies -- including modular checks and SHA-256 hash validation -- are discussed. The source code and factorization data are provided to ensure reproducibility. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_11621 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Computation of the Catalan Number $C(2,050,572,903)$ Ramani, Mahesh Data Structures and Algorithms Combinatorics 11Y16, 11B75, 05A10 F.2.1; G.2.1 This paper presents a two-phase algorithm for computing exact Catalan numbers at an unprecedented scale. The method is demonstrated by computing $C(n)$ for $n = 2,050,572,903$ yielding a result with a targeted $1,234,567,890$ decimal digits. To circumvent the memory limitations associated with evaluating large factorials, the algorithm operates exclusively in the prime-exponent domain. Phase 1 employs a parallel segmented sieve to enumerate primes up to $2n$ and applies Legendre's formula to determine the precise prime factorization of $C(n)$. The primes are grouped by exponent and serialized to disk. Phase 2 reconstructs the final integer using a memory-efficient balanced product tree with chunking. The algorithm runs on a time complexity of $Θ(n(\log n)^2)$ bit-operations and a space complexity of $Θ(n \log n)$ bits. This result represents the largest exact Catalan number computed to date. Performance statistics for a single-machine execution are reported, and verification strategies -- including modular checks and SHA-256 hash validation -- are discussed. The source code and factorization data are provided to ensure reproducibility. |
| title | Exact Computation of the Catalan Number $C(2,050,572,903)$ |
| topic | Data Structures and Algorithms Combinatorics 11Y16, 11B75, 05A10 F.2.1; G.2.1 |
| url | https://arxiv.org/abs/2601.11621 |