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

[William Keith]

Ah, right.  I think Emmanuel has got the crux of it.  I haven't filled out
the details but I think the carry rule solves the problem and proves
divisibility by 3 for m>8.

If n = 2^m -1, then binomial(2n-2, n-1) = binomial(2^(m+1)-4, 2^m-1).
Observe that 2^m-1 is divisible by 3 iff m is even, and is divisible by 3^1
strictly, unless m is 2 (mod 3), at which point the exponent of 3 is an
extended ruler sequence (2,2, 3, 2,2, 3, 2,2, 4, 2,2, 3, 2,2, 3, 2,2, 4,
2,2, 3, 2,2, 3, 2,2, 5, etc.).  The factor 1/(n+1) isn't pulling out any
powers of 3 since it's going to be 1/2^m, so I think divisibility by 3 is
guaranteed.

Cordially,
William Keith

On Sun, Nov 15, 2015 at 5:18 AM, Emmanuel Vantieghem <
emmanuelvantieghem at gmail.com> wrote:

> Using Lucas' congruence for binomials I tested the conjecture up to  m =
> 10000 (that is  n = 2^10000 -1) and found it's true.
> By Lucas' congruence I mean that, modulo a prime number p, Binomial(a,b)
> === Product(Binomial(a(i),b(i))  where a(i) and b(i) are the 'digits' of  a
>  resp. b  in number base p).  The test is very fast (it took less than a
> minute on my PC).
>
> 2015-11-15 7:35 GMT+01:00 L. Edson Jeffery <lejeffery2 at gmail.com>:
>
> > >I have tested the conjecture up to 250000 and found no other terms
> except
> > for 0, 1 & 31. Bob
> >
> >
> > Hello Bob,
> >
> > Are you saying that you tested the conjecture by checking each C(n)
> modulo
> > 6, for n=0..250000? If so, then there are only 17 odd C(n) within that
> > range (unless I miscounted), so the sample size is too small to draw any
> > conclusions.
> >
> > We know that C(n) is odd if and only if n = 2^m - 1, where m >= 0 is an
> > integer. Using that, we could test the conjecture only for those C(2^m -
> > 1), m=0,1,... . But the number of digits of C(2^(m+1) - 1) appears to be
> > roughly twice that of C(2^m - 1) which causes obvious problems with
> > computations. The number of digits of C(2^m - 1), for m >= 0 (as counted
> by
> > Mathematica), is the sequence starting
> >
> > {1, 1, 1, 3, 7, 17, 35, 74, 150, 304, 612, 1228, 2460, 4926, 9857, 19721,
> > 39449, 78905, 157818, 315644, 631296, 1262601, 2525212, 5050435,
> 10100879,
> > 20201769, 40403550, 80807112, ...}
> >
> > I tested the conjecture for C(2^m - 1) up to the still very small m = 31,
> > or n = 2147483647, using Mathematica, but got an overflow error (or
> > something like that) because C(2147483647) is already so large: I guess
> > that C(2^31 - 1) has a little more than 1292913800 digits. So is there a
> > better way to test these numbers?
> >
> > Finally, note that if C(n) is odd, then C(n) == 1 (mod 3) implies that
> C(n)
> > == 1 (mod 6) (or 1 (mod 12)) because also C(n) == 1 (mod 4).
> >
> > Ed Jeffery
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>