cp's OEIS Frontend

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

%I A263922 #36 Mar 06 2020 04:07:54
%S A263922 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 A263922 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 A263922 3,3,4,2,3,3,4,3,4,4,5,4,3,3,4,3,4,4,5
%N A263922 Highest exponent in prime factorization of n-th central binomial coefficient.
%C A263922 a(n) >= 2 for n > 4.
%C A263922 a(n) is the maximum number of carries in base-p addition of n+n for primes p <= 2n.
%C A263922 A000120(n) <= a(n) <= A070939(n).
%C A263922 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 A263922 Robert Israel, <a href="/A263922/b263922.txt">Table of n, a(n) for n = 1..10000</a>
%H A263922 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 A263922 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 A263922 a(n) = A051903(A000984(n)).
%e A263922 For n=3, C(6,3) = 20 = 2^2 * 5^1 so a(3) = 2.
%p A263922 f:= t -> max(seq(s[2],s=ifactors(t)[2])):
%p A263922 seq(f(binomial(2*n,n)),n=1..100); # _Robert Israel_, Oct 29 2015
%t A263922 a[n_] := FactorInteger[Binomial[2 n, n]][[All, 2]] // Max; Array[a, 100] (* _Jean-François Alcover_, Nov 27 2015 *)
%o A263922 (PARI) f(n,p)=my(d=Vecrev(digits(n,p)),c); sum(i=1,#d,c=(2*d[i]+c>=p))
%o A263922 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 A263922 (PARI) vector(200, n, vecmax(factor(binomial(2*n, n))[, 2])) \\ _Altug Alkan_, Oct 30 2015
%o A263922 (Sage)
%o A263922 max_exp = lambda n: max([p[1] for p in list(n.factor())])
%o A263922 print([max_exp(binomial(2*n,n)) for n in (1..87)]) # _Peter Luschny_, Oct 30 2015
%o A263922 def a(n):
%o A263922     N = 2*n
%o A263922     r = sum(N.digits(2))
%o A263922     b = 1+ZZ(N).nth_root(r, truncate_mode=1)[0]
%o A263922     for p in primes(3, b):
%o A263922         t, q = 0, N
%o A263922         while True:
%o A263922             q //= p
%o A263922             if q == 0: break
%o A263922             if (q & 1) == 1: t += 1
%o A263922         if t > r : r = t
%o A263922     return r
%o A263922 print([a(n) for n in (1..87)]) # _Peter Luschny_, Nov 02 2015
%o A263922 (Haskell)
%o A263922 a263922 = a051903 . a000984  -- _Reinhard Zumkeller_, Nov 19 2015
%Y A263922 Cf. A000120, A000984, A051903, A070939, A263924.
%K A263922 nonn,nice
%O A263922 1,3
%A A263922 _Robert Israel_, Oct 29 2015