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




More information about the SeqFan mailing list