Arithmetic properties of Catalan numbers

TheoremParity of Catalan numbers#✓fully proved

For every natural number \(n\), the \(n\)th Catalan number \(C_n\) is odd if and only if \(n = 2^a - 1\) for some natural number \(a\).

theorem catalan_odd_iff (n : ℕ) :
    Odd (catalan n) ↔ ∃ a : ℕ, n = 2 ^ a - 1

Sources

• Alon Regev, "The Central Component of a Triangulation", Journal of Integer Sequences 16 (2013), Article 13.4.1, theorem oddcats, lines 132–147 of https://cs.uwaterloo.ca/journals/JIS/VOL16/Regev/regev4.tex. This entry records the displayed theorem statement. Lines 85–88 define C_n with the standard indexing used by Mathlib's catalan, so no index shift is required. The natural subtraction in 2 ^ a - 1 is safe because 2 ^ a is positive. No parallel Catalan definition is introduced.

TheoremCatalan numbers other than \(1\) are not perfect powers#✓fully proved

For every natural number \(n \ge 2\), the \(n\)-th Catalan number \(C_n\) is not a perfect power: there are no natural numbers \(m\) and \(k\) with \(k \ge 2\) and \(C_n = m^k\).

The proof of Checcoli and D'Adderio checks small cases directly, and for \(n \ge 6\) uses a Ramanujan prime \(p\) with \(n + 2 \le p < 2n\), which divides \(C_n\) exactly once, so \(C_n = m^k\) with \(k \ge 2\) is impossible.

theorem catalan_not_perfect_power
    (n : ℕ) (hn : 2 ≤ n) :
    ¬ ∃ m k : ℕ, 2 ≤ k ∧ catalan n = m ^ k

Sources

• Nathaniel Benjamin, Grant Fickes, Eugene Fiorini, Edgar Jaramillo Rodriguez, Eric Jovinelly, and Tony W. H. Wong, "Primes and Perfect Powers in the Catalan Triangle," Journal of Integer Sequences 22 (2019), Article 19.7.6, Theorem [Checcoli–D'Adderio], lines 148–150, https://cs.uwaterloo.ca/journals/JIS/VOL22/Fiorini/fiorini3.tex

2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.