A263922 - OEIS

%I #36 Mar 06 2020 04:07:54

%S 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,

%T 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,

%U 3,3,4,2,3,3,4,3,4,4,5,4,3,3,4,3,4,4,5

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

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

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

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

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

%H Robert Israel, <a href="/A263922/b263922.txt">Table of n, a(n) for n = 1..10000</a>

%H MathOverflow, <a href="http://mathoverflow.net/questions/45923/divisibility-of-a-binomial-coefficient-by-p2-current-status">Divisibility of a binomial coefficient by p^2 — current status</a>

%H A. Granville and O. Ramaré, <a href="http://www.dms.umontreal.ca/~andrew/PDF/ramare.pdf">Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients</a>, Mathematika 43 (1996), 73-107, <a href="http://dx.doi.org/10.1112/S0025579300011608">[DOI]</a>.

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

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

%p f:= t -> max(seq(s[2],s=ifactors(t)[2])):

%p seq(f(binomial(2*n,n)),n=1..100); # _Robert Israel_, Oct 29 2015

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

%o (PARI) f(n,p)=my(d=Vecrev(digits(n,p)),c); sum(i=1,#d,c=(2*d[i]+c>=p))

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

%o (PARI) vector(200, n, vecmax(factor(binomial(2*n, n))[, 2])) \\ _Altug Alkan_, Oct 30 2015

%o (Sage)

%o max_exp = lambda n: max([p[1] for p in list(n.factor())])

%o print([max_exp(binomial(2*n,n)) for n in (1..87)]) # _Peter Luschny_, Oct 30 2015

%o def a(n):

%o     N = 2*n

%o     r = sum(N.digits(2))

%o     b = 1+ZZ(N).nth_root(r, truncate_mode=1)[0]

%o     for p in primes(3, b):

%o         t, q = 0, N

%o         while True:

%o             q //= p

%o             if q == 0: break

%o             if (q & 1) == 1: t += 1

%o         if t > r : r = t

%o     return r

%o print([a(n) for n in (1..87)]) # _Peter Luschny_, Nov 02 2015

%o (Haskell)

%o a263922 = a051903 . a000984  -- _Reinhard Zumkeller_, Nov 19 2015

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

%K nonn,nice

%O 1,3

%A _Robert Israel_, Oct 29 2015