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

[israel at math.ubc.ca]

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
>Vladimir
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>