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

[Emmanuel Vantieghem]

I think it should be
binomial(2n-2, n-1) = binomial(2^(m+1)-4, 2^m-2)
instead of
binomial(2n-2, n-1) = binomial(2^(m+1)-4, 2^m-1)


2015-11-15 17:54 GMT+01:00 William Keith <william.keith at gmail.com>:

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