[seqfan] A051404

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


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

More information about the SeqFan mailing list