# [seqfan] A051404

Don Reble djr at nk.ca
Mon Oct 28 00:38:06 CET 2013

```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.

```