a096304.txt, Kevin Ryde, May 2021

Sequence A096304 is the numbers k for which 3k does not divide

                (6k-4)!
    C(k) = -----------------    = A187358(k-1)  Catalan trisection
           (3n-1)! * (3n-2)!

Ralf Stephan conjectured in a formula that these k written in ternary
have an arbitrary least significant digit and above that only digits
0 or 1.

        high                low
    k = [0,1] ... [0,1]  [0,1,2]     ternary digits permitted

This is true, by considering prime powers in C(k) and 3k.


C(k) is a trisection of the Catalan numbers and its factorials can be
written with a binomial

           B(k)
    C(k) = ----     where B(k) = binomial(6k-4, 3k-2)
           3k-1

3k and 3k-1 have no common factor, so dividing out 3k-1 from B(k) does
not change whether or not 3k divides B(k),

    3k divides C(k) iff 3k divides B(k)
      since gcd(3k, 3k-1) = 1

It's convenient to consider binomial B(k) rather than C(k).


Kummer showed that for a given prime p, the power p^e dividing
binomial(x+y,y) is

    e = number of carries when add x and y in base p

B(k) is x = y = 3k-2 so its prime powers are the number of carries
when doubling 3k-2 in base p.  For example in base p=5, a carry occurs
on doubling digit 3 or 4, and propagates on doubling 2 but does not
begin at 2.

    digit      base 5
    -----      ------
      4        always carry:  4+4 = 3 carry 1
      3        always carry:  3+3 = 1 carry 1
      
      2        carry does not begin:     2+2 = 4 no carry
               but does propagate:   1 + 2+2 = 0 carry 1
      
      1        never carry: 1 + 1+1 = 3 no carry
      0        never carry: 1 + 0+0 = 1 no carry


The prime factors in B(k) can be compared to the prime factors in 3k
to test divisibility.  If 3k has more of a given prime p than B(k)
does then 3k does not divide B(k) and k is a term of the sequence.

Factors of p in 3k are low 0s when 3k is written in base p.
In base p=5, if k has one or more low 0s then

     3k  = ...  w  0 0 0 0        some digit w!=0
    3k-2 = ... w-1 4 4 4 3
                   \-----/

Each of the low 0s in 3k becomes a low digit 3 or 4 in 3k-2 which are
each a carry on doubling, so there are always enough factors of 5 in
B(k) for the factors of 5 in 3k.  The corresponding argument holds for
any prime p > 5 too.


For p=2, if 3k has one or more low 0s then

           h     w
     3k  = 1 ... 1 0 0 0 0      low 0s
    3k-2 = 1 ... 0 1 1 1 0
                   \-----/

Doubling 3k-2 causes a carry out of each 1-bit in 3k-2.  The low 0s of
3k become 1s in 3k-2, except the lowest 0.  But because 3k is not a
power of 2, it has at least one more 1-bit above w, such as its most
significant bit h.  Bits above w in 3k are unchanged in 3k-2 and so
3k-2 has at least as many 1-bits as 3k has low 0s.


For p=3, if 3k has exactly one low 0 then

     3k  = ...  w  0            some digit w!=0
    3k-2 = ... w-1 1

A carry on doubling 3k-2 begins only at a digit 2.  But both w-1 <= 1
and the low 1 shown are not digit 2s.  Digits above w in 3k are
unchanged in 3k-2, and if none of them are digit 2 to make a carry
then 3k does not divide B(k).

If 3k has two or more low 0s then

     3k  = ...  w  0 0 0 0      some digit w!=0
    3k-2 = ... w-1 2 2 2 1
                   \---/

3k-2 has low 2s and they are carries on doubling, but one fewer than
the low 0s of 3k.  If w=2 so that w-1 = 1 then the carry up from the
highest 2 propagates there (1 + 1+1 = 0 carry 1), thus giving the
extra needed.  Or any digit 2 above w in 3k is unchanged in 3k-2 and
is also an extra.  But if 3k has no digit 2 at or above w, then 3k
does not divide B(k).


Combining these cases shows that B(k), and thus C(k), is not divisible
by 3k iff 3k in ternary has only digits 0 or 1 above its second-least
significant digit, and in turn iff k has only digits 0 or 1 above its
least significant digit, as per Ralf Stephan.

In terms of the sequence index n, numbers of this form can be thought
of as writing n in a mixed radix where the least significant digit is
ternary and all above it are binary,

        high                low
    n = [0,1] ... [0,1] [0,1,2]     mixed radix: low ternary
                                    rest binary (per A340051)

Then k = A096304(n) is obtained by interpreting these digits as
ternary.


A generating function for A096304 can be formed as a usual kind of sum
adding digits of the required values at appropriate indices n.  The
low ternary digit is a periodic 0,1,2

    (0 + 1*x + 2*x^2)/(1-x^3)  = periodic 0,1,2      (A010872)

The lowest binary digit is alternately 0 and 1 above the ternary digit,

    (x^3+x^4+x^5)/(1-x^6)  = periodic 0,0,0,1,1,1    (A088911 shifted)

Interpreting the digits as ternary means multiply this binary digit by
3 to become the second-lowest ternary digit.  The next bit is
12-periodic multiplied by 9 for the third ternary digit, and so on.

                 x + 2*x^2                  x^(3*2^i) + ... + x^(3*2^(i+1)-1)
    A096304(x) = --------- + Sum  3^(i+1) * ---------------------------------
                  1 - x^3    i>=0                  1 - x^(3*2^(i+1))

The geometric series in the numerator and some cancelling gives

                  x*(1+2*x)     3         3^i * x^(3*2^i)
    A096304(x) =  ---------  + --- * Sum  ---------------
                   1 - x^3     1-x   i>=1  1 + x^(3*2^i)

In this form, the denominator in the sum gives +1 at the start of each
1-bit run and -1 after the run, and 1/(1-x) is partial sums of those
to make the runs.  The runs would start with 1s at n=0 and numerator
x^(3*2^i) shifts to the desired n positions.

A340051 is these same mixed-radix digits interpreted as decimal rather
than ternary.  Its generating function differs only in having 10 for
the digit placements so 10/(1-x) and 10^i rather than 3/(1-x) and 3^i.

------------------------------------------------------------------------------