A263922 Highest exponent in prime factorization of n-th central binomial coefficient.

1, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 2, 2, 3, 2, 3, 3, 4, 2, 4, 3, 4, 4, 4, 4, 5, 2, 3, 4, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 2, 2, 3, 4, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 4, 3, 3, 4, 3, 4, 4, 5

Offset: 1

Author

Robert Israel, Oct 29 2015

Keywords

• nonn
• nice

Comments

a(n) >= 2 for n > 4.

a(n) is the maximum number of carries in base-p addition of n+n for primes p <= 2n.

A000120(n) <= a(n) <= A070939(n).

It appears that a(n) >= 3 for n > 1056. Any further n must be greater than 10^1000. Similarly it appears that a(n) >= 4 for n > 557056 and a(n) >= 5 for n > 1090519552. - Charles R Greathouse IV, Oct 31 2015

Examples

			For n=3, C(6,3) = 20 = 2^2 * 5^1 so a(3) = 2.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• MathOverflow, Divisibility of a binomial coefficient by p^2 — current status
• A. Granville and O. Ramaré, Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients, Mathematika 43 (1996), 73-107, [DOI].

Crossrefs

Cf. A000120, A000984, A051903, A070939, A263924.

Programs

Haskell

a263922 = a051903 . a000984  -- Reinhard Zumkeller, Nov 19 2015

Maple

f:= t -> max(seq(s[2],s=ifactors(t)[2])):
seq(f(binomial(2*n,n)),n=1..100); # Robert Israel, Oct 29 2015

Mathematica

a[n_] := FactorInteger[Binomial[2 n, n]][[All, 2]] // Max; Array[a, 100] (* Jean-François Alcover, Nov 27 2015 *)

PARI

f(n,p)=my(d=Vecrev(digits(n,p)),c); sum(i=1,#d,c=(2*d[i]+c>=p))
a(n)=my(r=hammingweight(n),L=sqrtnint(n,r+1),t); forprime(p=3, L, t=f(n,p); if(t>r, L=sqrtnint(n,1+r=t)); if(p>=L, return(r))); r \\ Charles R Greathouse IV, Oct 29 2015

PARI

vector(200, n, vecmax(factor(binomial(2*n, n))[, 2])) \\ Altug Alkan, Oct 30 2015

Sage

max_exp = lambda n: max([p[1] for p in list(n.factor())])
print([max_exp(binomial(2*n,n)) for n in (1..87)]) # Peter Luschny, Oct 30 2015
def a(n):
    N = 2*n
    r = sum(N.digits(2))
    b = 1+ZZ(N).nth_root(r, truncate_mode=1)[0]
    for p in primes(3, b):
        t, q = 0, N
        while True:
            q //= p
            if q == 0: break
            if (q & 1) == 1: t += 1
        if t > r : r = t
    return r
print([a(n) for n in (1..87)]) # Peter Luschny, Nov 02 2015

Formula

a(n) = A051903(A000984(n)).