[seqfan] Re: A000108(n) ≡ 1 (mod 6)

israel at math.ubc.ca israel at math.ubc.ca
Mon Nov 9 01:50:21 CET 2015

```In fact I suspect that the only Catalan numbers coprime to 6 are
A000108(1), A000108(3), A000108(31) and A000108(255).  I can confirm there
are no others up to A000108(2^10000).

A000108(n) is odd iff n = 2^k - 1.  The question is then, which of these
have A000108(n) coprime to 3.

By Kummer's theorem, the 3-adic order of C(2n, n) is the number of carries
in the addition of n + n in base 3. The 3-adic order of A00108(n) is that
minus the 3-adic order of n+1. The only way this can be 0 is that there are
no 2's in the base-3 expansion of n except possibly at the end, and the
digit (if any) immediately preceding the 2's at the end must be 0. Thus 94
= 10111_3 and 107 = 10222_3 qualify but not 95 = 10112_3 or 96 = 10120_3. I
tried all numbers of the form 2^k-1 with k <= 10000.

Now the base-3 digits of 2^k - 1 seem to be fairly random and there are
about k*log_3(2) of them; heuristically the probability of a number with m
base-3 digits qualifying should decrease exponentially with \$k\$. Since a
series with exponentially decreasing terms converges, we should expect only
finitely many 2^k - 1 to qualify. Of course this is only heuristic, not a
proof.

Cheers,
Robert

On Nov 8 2015, Vladimir Reshetnikov wrote:

>Dear Seqfans,
>
> Is it true that there are only 2 Catalan numbers
> <http://oeis.org/A000108> of the form 6*k+1 (i.e. congruent to 1 modulo
> 6), namely A000108(1) = 1 and A000108(31) = 14544636039226909?
>
>--
>Thanks