A259788 -id:A259788 - cp's OEIS frontend

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

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, 18, 20, 22, 23, 21, 23, 20, 24, 21, 21, 20, 22, 24, 23, 22, 21, 22, 26, 26, 30, 31, 32, 30, 35, 34, 33, 31, 33, 34, 34, 33, 37, 38, 40, 42, 42, 44, 46, 42, 42, 43, 45

Offset: 0

Vladimir Shevelev, Jul 07 2015

nonn

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.

			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.

Peter J. C. Moses, Table of n, a(n) for n = 0..4999
Wikipedia, Kummer's theorem.

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

seq(padic:-ordp(numtheory:-phi(binomial(2*n,n)),2), n= 0 .. 100); # Robert Israel, Jul 10 2015

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

vector(80, n, n--; valuation(eulerphi(binomial(2*n,n)), 2)) \\ Michel Marcus, Jul 11 2015

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

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
a(n) = A007814(A000010(A000984(n))). - Robert Israel, Jul 10 2015

More terms from Peter J. C. Moses, Jul 07 2015

A259922 a(n)= Sum_{2 < prime p <= n} c_p - Sum_{n < prime p < 2*n} c_p, where 2^c_p is the greatest power of 2 dividing p-1.

Original entry on oeis.org

0, -1, -1, -2, 2, 1, 1, 1, -3, -4, -2, -3, 1, 1, -1, -2, 6, 6, 6, 6, 3, 2, 4, 3, 3, 3, 1, 1, 5, 4, 4, 4, 4, 3, 3, 2, 3, 3, 3, 2, 8, 7, 9, 9, 6, 6, 8, 8, 3, 3, 1, 0, 4, 3, 1, 1, -3, -3, -1, -1, 3, 3, 3, 2, 2, 1, 3, 3, 0, -1, 1, 1, 7, 7, 5, 4, 4, 4, 4, 4, 4, 3

Offset: 1

Vladimir Shevelev, Jul 09 2015

sign

It is known that, for n>10, pi(2*n) < 2*pi(n), where pi(n) is the number of primes not exceeding n (A000720). Thus, for n>10, in the interval (1,n] we have more primes than in the interval (n,2*n).

In connection with this, it is natural to conjecture that there exists a number N such that a(n)>0 for all n >= N.

Peter J. C. Moses, Table of n, a(n) for n = 1..2000

Cf. A007814, A060208, A259788, A259897.

Map[Total[Flatten[Map[IntegerExponent[Select[#,PrimeQ]-1,2]&,{Range[3,#],Range[#+1,2#-1]}]{1,-1}]]&,Range[50]]

More terms from Peter J. C. Moses, Jul 09 2015

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions