login
a(n) is the 2-adic valuation of phi(binomial(2*n,n)).
2

%I #30 Jul 07 2022 19:02:24

%S 0,0,1,3,3,3,4,6,6,10,9,11,10,11,11,14,12,10,11,13,14,17,17,17,16,16,

%T 18,20,22,23,21,23,20,24,21,21,20,22,24,23,22,21,22,26,26,30,31,32,30,

%U 35,34,33,31,33,34,34,33,37,38,40,42,42,44,46,42,42,43,45

%N a(n) is the 2-adic valuation of phi(binomial(2*n,n)).

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

%C 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).

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

%H Peter J. C. Moses, <a href="/A259897/b259897.txt">Table of n, a(n) for n = 0..4999</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Kummer%27s_theorem">Kummer's theorem</a>.

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

%F 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

%F a(n) = A007814(A000010(A000984(n))). - _Robert Israel_, Jul 10 2015

%e Let n=9, binomial(18,9) = 48620. Here

%e c(n)=2, Sum_{9 < prime p < 18)c_p = 7,

%e Sum_{2 < prime p < 18)c_p = 11. So 8<=a(9) <= 11.

%p seq(padic:-ordp(numtheory:-phi(binomial(2*n,n)),2), n= 0 .. 100); # _Robert Israel_, Jul 10 2015

%t Map[IntegerExponent[EulerPhi[Binomial[2#,#]],2]&,Range[0,100]]

%o (PARI) vector(80, n, n--; valuation(eulerphi(binomial(2*n,n)), 2)) \\ _Michel Marcus_, Jul 11 2015

%o (Python)

%o from math import comb

%o from sympy import totient

%o def A259897(n): return (~(m:=totient(comb(2*n,n)))& m-1).bit_length() # _Chai Wah Wu_, Jul 07 2022

%Y Cf. A000010, A000120, A000984, A007814, A066973, A259788.

%K nonn

%O 0,4

%A _Vladimir Shevelev_, Jul 07 2015

%E More terms from _Peter J. C. Moses_, Jul 07 2015