OFFSET
0,4
COMMENTS
The 2-adic valuation (or 2-adic order) of n>=1 is the highest exponent k such that 2^k divides n. Below we also write 2^k||n.
Since the number of primes in the interval (n, 2*n) tends to infinity as n goes to infinity, a(n) also tends to infinity (see formula).
By Kummer's theorem (link [Wikipedia]), a prime p divides binomial(2*n,n) if and only if there is a carry in adding n+n in base p.
LINKS
Peter J. C. Moses, Table of n, a(n) for n = 0..4999
Wikipedia, Kummer's theorem.
FORMULA
c(n)-1 + Sum_{n < prime p < 2*n)c_p <= a(n) <= Sum_{2 < prime p < 2 *n)c_p, n>1, where 2^c(n)|| binomial(2*n,n) (note that c(n) = A000120(n)) and 2^c_p || p-1.
a(n) = (number of carries in binary addition of n+n) - 1 + Sum(p in S, A007814(p-1)) where S is the set of odd primes p < 2n such that at least one of the base-p digits of n is greater than (p-1)/2. - Robert Israel, Jul 10 2015
EXAMPLE
Let n=9, binomial(18,9) = 48620. Here
c(n)=2, Sum_{9 < prime p < 18)c_p = 7,
Sum_{2 < prime p < 18)c_p = 11. So 8<=a(9) <= 11.
MAPLE
seq(padic:-ordp(numtheory:-phi(binomial(2*n, n)), 2), n= 0 .. 100); # Robert Israel, Jul 10 2015
MATHEMATICA
Map[IntegerExponent[EulerPhi[Binomial[2#, #]], 2]&, Range[0, 100]]
PROG
(PARI) vector(80, n, n--; valuation(eulerphi(binomial(2*n, n)), 2)) \\ Michel Marcus, Jul 11 2015
(Python)
from math import comb
from sympy import totient
def A259897(n): return (~(m:=totient(comb(2*n, n)))& m-1).bit_length() # Chai Wah Wu, Jul 07 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, Jul 07 2015
EXTENSIONS
More terms from Peter J. C. Moses, Jul 07 2015
STATUS
approved