|
%I #17 May 24 2018 10:11:34
%S 0,1,2,4,7,11,21,22,28,37,42,52,69,784
%N Numbers k such that the number of divisors of the k-th central binomial coefficient is a power of 2.
%C Equivalently (as shown below), numbers k such that the number of divisors of the k-th central binomial coefficient is 1 or a prime power p^j, j >= 1.
%C a(15) > 10^8, if it exists.
%C Conjecture: there are no terms beyond 784.
%C The central binomial coefficient of k is C(2*k, k) = (2*k)!/k!^2 = (2*k)*(2*k-1)*(2*k-2)*...*(k+1)/k!, which contains each prime in the interval [k+1, 2*k] with multiplicity 1. Thus, for k >= 1, the number of divisors of C(2*k, k) will be an even number. (For k=0, C(2*k, k) = 1, whose number of divisors is 1 = 2^0.)
%C For each term k, the prime factorization of C(2*k, k) must be of the form Product_{j=1..J} p_j ^ (2^m_j - 1), where J is the number of distinct prime factors and each m_j >= 1, so that the number of divisors will be Product_{j=1..J} 2^m_j = 2^Sum_{j=1..J} m_j.
%C No number k can be a term if there exists any prime p such that k < p^2 <= 2*k and floor(2*k/p) is odd, because the multiplicity of p in C(2*k, k) will be exactly 2, so the number of divisors of C(2*k, k) will be divisible by 3 (and by 2). This criterion is sufficient to rule out every k in the interval [20124, 10^8], and it seems nearly certain that it also applies for all k > 10^8. A proof that it does apply for all k > 10^8 would also prove that 784 is the final term of this sequence.
%e k=2 is a term because C(4,2) = 6 = 2*3, which has 4 = 2^2 divisors.
%e k=3 is not a term because C(6,3) = 20 = 2^2 * 5, which has 6 = 2*3 divisors.
%e k=784 is a term because the number of divisors of C(1568,784) is 2^172. (Its prime factorization is 2^3 times the product of 170 other primes, each of which occurs with a multiplicity of 1.)
%e k=2763 is not a term because the number of divisors of C(5526,2763) is 2^499 * 3^3. (Each of the prime factors of C(5526,2763) has a multiplicity of 2^1 - 1 = 1, 2^2 - 1 = 3, or 2^3 - 1 = 7, with the exception of 59, 71, and 73, each of which occurs with multiplicity 2.
%e k=10^50 cannot be a term, since there exist primes p (such as 14142135623730950488016843) such that the unreduced numerator of C(2*k, k), i.e., (2*k)*(2*k-1)*(2*k-2)*...*(k+1), contains exactly one more factor that is a multiple of p than does the unreduced denominator k*(k-1)*...*3*2*1, and one of those multiples of p that occurs in the unreduced numerator is p^2, with the result that p appears in the prime factorization of C(2*k, k) with multiplicity 2, so its number of divisors is divisible by both 2 and 3.
%o (PARI) ispow2(n) = (n==1) || (n==2) || (ispower(n,,&p) && (p==2));
%o isok(n) = ispow2(numdiv(binomial(2*n,n))); \\ _Michel Marcus_, May 21 2018
%Y Cf. A000984 (Central binomial coefficients).
%K nonn,hard,more
%O 1,3
%A _Jon E. Schoenfield_, May 20 2018
|
