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