cp's OEIS Frontend

Let C(m) denote the m-th Catalan number (A000108). Let == denote congruence and =!= its negation. Vladimir Reshetnikov asked (see link) how many n exist such that C(n) == 1 (mod 6). It was pointed out by Robert Israel that the only known n are in {1,3,31,255}. Since C(n) is odd if and only if n = 2^m - 1, for some m, Emmanuel Vantieghem (see links) stated the stronger conjecture that C(2^n-1) == 0 (mod 3), for all n>8. This is the motivation for the following.

If n is an integer such that the congruences C(n) == 0 (mod 3) and C(n-1) =!= 0 (mod 3) hold simultaneously, then we call n a "block number." A sequence {n, n+1, ..., n+k-1} of consecutive numbers is called a "block" (of order k), if C(n+i) == 0 (mod 3), for all i such that 0 <= i < k, and if C(n-1) =!= 0 (mod 3) (i.e., if n is a block number) and C(n+k) =!= 0 (mod 3).

If m is an integer such that the congruences C(m) =!= 0 (mod 3) and C(m-1) == 0 (mod 3) hold simultaneously, then we call m a "gap number." A sequence {m, m+1, ..., m+j-1} of consecutive numbers is called a "gap" (of order j), if C(m+i) =!= 0 (mod 3), for all i such that 0 <= i < j, and if C(m-1) == 0 (mod 3) (i.e., if m is a gap number) and C(m+j) == 0 (mod 3). (The sequence A265104 is conjectured to contain all possible gap numbers.) If C(n) == 0 (mod 3), then we say that n is "gap-avoiding."

It follows that if {n, n+1, ..., n+k-1} is a block with block number n, then n+k is a gap number, and if {m, m+1, ..., m+j-1} is a gap with gap number m, then m+j is a block number.

Conjecture 1: The sequence contains all possible block numbers.

Conjecture 2: If m is a block number, then 3*m - 1 is a block number.

Conjecture 3: If C(n) == 0 (mod 3), then C(3*n-1) == 0 (mod 3) or, what is the same thing, if n lies in a block, then 3*n - 1 lies in a block.

Conjecture 4: Assuming that A265104 contains all possible gap numbers, let B(n) denote the block with block number a(n), n >= 1, so that B(n) = {a(n), a(n)+1, ..., A265104(n)-1}. The (flattened) sequence {B(1), B(2), ...} of blocks contains all numbers m such that the base 3 representations of m and m+1 both contain at least one 2 and is identical to A111018.

Conjecture 5: C(n) == 0 (mod 3) if and only if the base 3 representations of n and n + 1 both contain at least one 2. [This conjecture has been proved by Robert Israel (see link for the proof)].

Theorem 1: The following statements are equivalent to Vantieghem's conjecture stated above: (i) For all m>8, 2^m-1 is gap-avoiding; (ii) C(2^n-1) == 0 (mod 3) if and only if the base 3 representations of 2^n - 1 and 2^n both contain at least one 2.

Proof: For (i), the statement obviously follows from the definitions, and (ii) follows from the proof of Conjecture 5.