[seqfan] Re: A051404

[Vladimir Shevelev]

Dear Don Reble and SeqFans,
 
A.-M. Legendre poved that the exponent of the highest power of prime p which divides n! equals (n - s_p(n))/(p-1), where
s_p(n) is the number of digits of n in base p. From this it is easy to obtain that the exponent of the highest power of prime p which divides C(2*n-1, n) is (s_p(n)  +  s_p(n-1) - s_p(2*n-1))/(p-1). [By the way, if to write this for C(a+b, a), we obtain
s_p(a) + s_p(b) - s_p(a+b)  and since it is always>= 0, then for s_p we have a "triangle inequality"]
If p=2 and s_2(n)=k(n) 1-bits, then we have  k(n) + k(n-1) - k(2*n-1). But from the equality 2*n-1 = 2*(n-1) +1 we immediately obtain  k(n-1) - k(2*n-1) = -1. Thus the exponent of the highest power of 2 which divides C(2*n-1, n) is indeed 
equals k(n) - 1.  This means that number n is in  A051404 if and only if  s_2(n) <=2 and s_3(n)  +  s_3(n-1) - s_3(2*n-1) <= 2. 
The second your result is beautiful for computer check. It is interesting that it is directly obtained from a remarkable general result of  another classic mathematician E. E. Kummer: the exponent of the highest power of prime p which divides C(N, x) equals to the number of carries which appear in adding x and N-x in base p, or in the considered case - in adding n-1 and n in base 3. 
 
Best regards,
Vladimir


----- Original Message -----
From: Don Reble <djr at nk.ca>
Date: Sunday, October 27, 2013 11:50
Subject: [seqfan] A051404
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> Seqfans:
> 
> > %I A051404
> > %S 
> 1,2,3,4,6,9,10,12,18,33,34,36,40,64,66,192,256,264,272,513,514,516,>    576,768,1026,1056,2304,16392,65664,81920,532480,545259520
> > %N Neither 4 nor 9 divides C(2n-1,n) (almost certainly finite).
> > %A David W. Wilson (davidwwilson(AT)comcast.net)
> > %E Complete up to 2^64 = 18446744073709551616.
> 
>     What a nice sequence. (Thanks, David.)
> 
>     Testing whether 4 divides f(n)=C(2n-1,n) is 
> surprisingly easy.
>     Write n in base 2. If there are k 1-bits, then
>         2^k does not divide 
> f(n), but
>         2^{k-1} does divide f(n).
>     (You'll enjoy proving this.)
> 
>     The sequence therefore contains only numbers 
> with one or two 1-bits.
> 
>     The rule for divisibility by 3^k is more 
> complicated.    Write n in base three. Find each 
> maximal substring which does not
>     contain a '0' and ends with a '2'. The sum of 
> the lengths of those
>     substrings equals the exponent of the highest 
> power of 3 which
>     divides f(n). (You'll _hate_ proving this. Ecch!)
> 
>     Example: 328979 is "121201021102" in base 3. 
> The maximal substrings
>         are "1212", "2" (from 
> 211), and "2". There are 6 digits in the
>         substrings, so 3^6 
> divides f(328979), but 3^7 doesn't.
>     Example: 68800 is "10111101011" in base 3. 
> There are no substrings
>         which end in '2', so 
> 3 does not divide f(68800).
> 
>     The sequence therefore contains only numbers 
> with no 2-trits,
>     or a single 2-trit immediately following a 0-
> trit or at the start.
> 
> 
>     So it's easy to check up to, say, 2^30000. As 
> expected, there are
>     no more terms in that range.
> 
> 
>     P.S. Just kidding: you'll enjoy finding both 
> proofs.
> -- 
> Don Reble  djr at nk.ca
> 
> 
> -- 
> This message has been scanned for viruses and
> dangerous content by MailScanner, and is
> believed to be clean.
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎