A066973 -id:A066973 - cp's OEIS frontend

A259788 Greatest prime factor of phi(binomial(2*n,n)).

2, 2, 3, 3, 5, 5, 5, 5, 5, 3, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 7, 23, 23, 23, 23, 23, 23, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 83, 83, 83, 83, 83, 83, 89

Offset: 2

Vladimir Shevelev, Jul 05 2015

nonn

Conjectures:
(1) 7 is a unique term which is not a Sophie Germain prime (A005384);
(2) A Sophie Germain prime p occurs p times if and only if p=2,3,5 and 11; otherwise, it occurs q-p times, where q is the next Sophie Germain prime > p;
(3) a(n) is the greatest prime factor of p-1 for primes p in the interval (n, 2*n).
All these conjectures follow from the following strengthening of the Bertrand postulate for n>=24: the interval (n, 2*n) contains a safe prime (A005385).

Peter J. C. Moses, Table of n, a(n) for n = 2..5001

Cf. A000010, A000984, A005384, A005385, A006530, A066973.

Map[First[Last[FactorInteger[EulerPhi[Binomial[2#,#]]]]]&,Range[2,100]]

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

Original entry on oeis.org

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

A102715 Triangle read by rows: T(n,k) is phi(binomial(n,k)), where phi is Euler's totient function (0 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 4, 4, 4, 4, 1, 1, 2, 8, 8, 8, 2, 1, 1, 6, 12, 24, 24, 12, 6, 1, 1, 4, 12, 24, 24, 24, 12, 4, 1, 1, 6, 12, 24, 36, 36, 24, 12, 6, 1, 1, 4, 24, 32, 48, 72, 48, 32, 24, 4, 1, 1, 10, 40, 80, 80, 120, 120, 80, 80, 40, 10, 1, 1, 4, 20, 80, 240, 240

Offset: 0

Emeric Deutsch, Feb 06 2005

Row n contains n+1 terms. Row sums yield A064450.

			T(6,3)=8 because the positive integers relatively prime to binomial(6,3)=20 and not exceeding 20 are 1,3,7,9,11,13,17 and 19.
Triangle begins:
  1;
  1, 1;
  1, 1, 1;
  1, 2, 2, 1;
  1, 2, 2, 2, 1;
  1, 4, 4, 4, 4, 1;

Cf. A000010 (totient), A007318 (binomial).

Cf. A064450, A066973.

/* As triangle */ [[EulerPhi(Binomial(n,k)): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, May 01 2019

with(numtheory): T:=(n,k)->phi(binomial(n,k)): for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

Flatten[Table[EulerPhi[Binomial[n, k]], {n, 0, 12}, {k, 0, n}]] (* Vincenzo Librandi, May 01 2019 *)

T(n, k) = A000010(A007318(n, k)) (0 <= k <= n).

T(2n,n) = A066973(n).

cp's OEIS Frontend

A259788 Greatest prime factor of phi(binomial(2*n,n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A102715 Triangle read by rows: T(n,k) is phi(binomial(n,k)), where phi is Euler's totient function (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Maple

Mathematica

Formula