A059097 -id:A059097 - cp's OEIS frontend

A110493 Largest prime p such that p^2 divides binomial(2n,n), or 0 if binomial(2n,n) is squarefree.

0, 0, 0, 2, 0, 3, 2, 2, 3, 2, 2, 2, 2, 5, 5, 3, 3, 3, 5, 5, 3, 2, 2, 5, 5, 7, 7, 7, 2, 2, 2, 2, 7, 7, 7, 3, 2, 2, 5, 7, 7, 7, 3, 5, 5, 3, 7, 7, 7, 5, 3, 3, 3, 3, 2, 2, 3, 2, 2, 3, 3, 11, 11, 11, 11, 11, 5, 5, 5, 5, 5, 5, 11, 11, 11, 11, 11, 3, 5, 5, 3, 7, 7, 11, 11, 13, 13, 13, 13, 13, 13, 5, 5, 5, 11, 11

Offset: 0

T. D. Noe, Jul 22 2005

Binomial(2n,n) is squarefree for only n = 0, 1, 2, 4. Sequence A059097 lists n such that a(n) = 0 or 2. The plot shows the quadratic nature of this sequence. Sequence A110494 makes the quadratic behavior clearer.

Granville and Ramaré show that if n >= 2082 then a(n) >= sqrt(n/5). - Robert Israel, Sep 04 2019

			a(5) = 3 because binomial(10,5) = 252 = (2^2)(3^2)(7).

T. D. Noe, Table of n, a(n) for n = 0..10000
T. D. Noe, Plot of A110493
A. Granville and O. Ramaré, Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients, Mathematika 43 (1996), 73-107, [DOI].

Cf. A110494 (least k such that prime(n)^2 divides binomial(2k, k)).

Cf. A059097, A110494.

f:= proc(n) local F;
  F:= select(t -> t[2]>=2, ifactors(binomial(2*n,n))[2]);
  if F = [] then 0 else max(map(t -> t[1],F)) fi
end proc:
map(f, [$0..100]); # Robert Israel, Sep 04 2019

Table[f=FactorInteger[Binomial[2n, n]]; s=Select[f, #[[2]]>1&]; If[s=={}, 0, s[[-1,1]]], {n, 0, 100}]

a(0) prepended by T. D. Noe, Mar 27 2014

A356637 a(n) = A000265(A263931(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 9, 3, 3, 45, 5, 1, 21, 7, 175, 675, 45, 45, 1485, 5775, 5775, 45045, 2145, 195, 8775, 2925, 5733, 22491, 833, 6545, 373065, 24871, 24871, 1566873, 3086265, 181545, 357903, 39767, 39767, 156975, 309925, 61985, 5020785, 239085, 20322225, 160730325

Offset: 0

Peter Luschny, Sep 07 2022

nonn

Let n >= 5. If a(n) is squarefree, then 2 divides binomial(2*n, n) more than once and is the only prime that does so. There is only a finite number of such cases (see A059097).
An efficient algorithm for the calculation is available, which is based on prime factorization. See the SageMath implementation. The main application is the efficient calculation of the central binomial coefficient, which is the product of this sequence, the Glaisher/Gould sequence, and the upper primorial function (see the formula section).
Since the central binomial coefficient is a bisection of the swinging factorial A056040, and the swinging factorial, in turn, is the building block for an efficient algorithm for the computation of the factorial function, the terms of this sequence occur as factors in all these computations. See the links for details.

			Let n = 22 and consider the prime factorization of m = binomial(2*n, n):
2^3 * [3 * 5 * 13] * 23 * 29 * 31 * 37 * 41 * 43. Then a(22) = 3 * 5 * 13. This is what is left after the 'prime tail' A261130(n) and the 'prime head' A006519(m) = A001316(n) have been cut off.

Peter Luschny, Swing, divide and conquer the factorial, (excerpt).
Peter Luschny, Fast Factorial Functions, a code repository.
Eric Weisstein's World of Mathematics, Erdős Squarefree Conjecture.

Cf. A000265, A263931, A261130, A006519, A000984, A001316, A059097, A056040.

A263931 := n -> binomial(2*n, n) / convert(select(isprime, {$n+1..2*n}), `*`):
A000265 := n -> n / 2^padic[ordp](n, 2):
seq(A000265(A263931(n)), n = 0..45);

def A356637(n: int) -> int:
    m = 2 * n
    if m < 5: return 1
    sqrtm = isqrt(m) + 1
    R = prime_range(sqrtm, m // 3 + 1)
    factors = [x for x in R if is_odd(m // x)]
    for prime in prime_range(3, sqrtm):
        p: int = 1
        q: int = m
        while True:
            q //= prime
            if q == 0:
                break
            if q & 1 == 1:
                p *= prime
        if p > 1:
            factors.append(p)
    return product(factors)
print([A356637(n) for n in range(45)])

A000984(n) = a(n) * A001316(n) * A261130(n) for n >= 2.

A111869 Least number k such that C(2k,k) is divisible by n^2.

Original entry on oeis.org

1, 3, 5, 15, 13, 5, 25, 63, 41, 13, 61, 15, 85, 25, 14, 255, 145, 41, 181, 23, 25, 61, 265, 95, 313, 85, 365, 27, 421, 14, 481, 1023, 61, 145, 39, 53, 685, 181, 86, 63, 841, 25, 925, 61, 44, 265, 1105, 383, 1201, 313, 145, 85, 1405, 365, 63, 95, 181, 421, 1741, 23, 1861

Offset: 1

Robert G. Wilson v, Nov 23 2005

nonn

From David A. Corneth, Aug 15 2025: (Start)
Conjecture 1: a(n) = (n^2 - 1)/2 + 1 for odd prime n.
Conjecture 2: Let q be the largest prime factor of n. Let e be the multiplicity of q in the factorization of n. Then a(n) >= (q^(2*e) - 1)/2 + 1. for n != 2.
These conjectures hold for n = 1..4002.
Conjecture 3: a(2^k) = 4^k - 1 for k >= 1.
This conjecture holds for k = 1..11. (End)

			From _David A. Corneth_, Aug 15 2025: (Start)
a(4) = 15 as 4^2 = 16 | binomial(2*15, 15) = binomial(30, 15) and for any k < 15 we have 16 does not divide binomial(2*k, k). We don't really need to compute binomial(30, 15) and not the previous binomial(2*k, k) but just find how many factors 2 they have. binomial(30, 15) = 30! / (15!)^2.
We find the 2-adic valuation of 30! as follows: let b(0) = 30 and let b(n + 1) = floor(b(n) / 2). Then the 2-adic valuation of 30! is Sum{k = 1..floor(log(30)/log(2))} b(k) = b(1) + b(2) + b(3) + b(4) = 15 + 7 + 3 + 1 = 26.
Similar for 15! it is 7 + 3 + 1 = 11. 26 - 2*11 = 4 >= 4 so a(4) <= 15 and checking the others gives a(4) = 15. (End)

David A. Corneth, Table of n, a(n) for n = 1..4002 (first 500 terms from Seiichi Manyama, terms n = 501..840 from Chai Wah Wu)
David A. Corneth, PARI program
David A. Corneth, Upper bounds on a(n) for n = 1..10000

Cf. A000984, A059097, A073078, A370980.

f[n_] := Block[{k = 1, m = n^2}, While[ Mod[ Binomial[2k, k], m] != 0, k++ ]; k]; Array[f, 61]

PARI
```
See Corneth link
```

a(n) = A073078(n^2).

A239622 Conjecturally, the irregular triangle of numbers k such that prime(n)^2 is the largest squared prime divisor of binomial(2k,k).

Original entry on oeis.org

0, 1, 2, 4, 3, 6, 7, 9, 10, 11, 12, 21, 22, 28, 29, 30, 31, 36, 37, 54, 55, 57, 58, 110, 171, 784, 786, 5, 8, 15, 16, 17, 20, 35, 42, 45, 50, 51, 52, 53, 56, 59, 60, 77, 80, 133, 134, 135, 136, 156, 157, 158, 159, 160, 161, 170, 210, 211, 212, 400, 401, 402, 651, 652, 785

Offset: 0

T. D. Noe, Mar 27 2014

Row 0 lists the numbers k such that binomial(2k,k) is squarefree. Sequence A110494 lists the first term of each row; A239623 lists the conjectured last term; A239624 lists the conjectured length of each row.

			The irregular triangle begins:
0, 1, 2, 4
3, 6, 7, 9,..., 784, 786
5, 8, 15, 16,..., 652, 785
13, 14, 18, 19,..., 445, 2080
25, 26, 27, 32,..., 783, 902
61, 62, 63, 64,..., 2033, 2034

T. D. Noe, Rows n = 0..40 of irregular triangle, flattened

Cf. A059097 (union of first two rows), A110493, A110494, A239623, A239624.

b = 1; t = Table[b = b*(4 - 2/n); last = 0; Do[If[Mod[b, p^2] == 0, last = p], {p, Prime[Range[PrimePi[Sqrt[2*n]]]]}]; last, {n, 20000}]; t = Join[{0}, t]; Table[Flatten[Position[t, p]] - 1, {p, Join[{0}, Prime[Range[20]]]}]

A118562 Least number k such that binomial(2k,k) is divisible by all squares to n squared but not (n+1) squared, or 0 if impossible.

Original entry on oeis.org

1, 3, 5, 15, 0, 23, 89, 95, 0, 123, 0, 215, 0, 0, 1117, 943, 0, 2003, 0, 0, 0, 3455, 0, 1439, 0, 7846, 0, 7916, 0, 14735, 13103, 0, 0, 0, 0, 23711, 0, 0, 0, 24049, 0, 44857, 0, 0, 0, 44711, 0, 47594, 0, 0, 0, 77021, 0, 0, 0, 0, 0, 195765, 0, 381398, 0, 0, 374435, 0, 0

Offset: 1

Robert G. Wilson v, Nov 23 2005

nonn

a(5)=0 because any number squared which would divide binomial(2k,k) would also be divided by 6^2 since 6=2*3.

			a(3)=5 because binomial(10,5)=252 which is divisible by the squares of 1, 2 & 3 but not 4 squared.
a(70)=385823.

Chai Wah Wu, Table of n, a(n) for n = 1..250

Cf. A059097, A111869, A080765, A024619.

f[n_] := Block[{k = 1, b = Binomial[2n, n]}, While[Mod[b, k^2] == 0, k++ ]; k - 1]; t = Table[0, {100}]; Do[ a = f[n]; If[a < 101 &t[[a]] == 0, t[[a]] = n; Print[{a, n}]], {n, 38000}] (* or *)
expoPF[k_, n_] := Module[{s = 0, x = n}, While[x > 0, x = Floor[x/k]; s += x]; s]; expoCF[k_, n_] := Min[expoPF[ #[[1]], n]/#[[2]] & /@ FactorInteger@k]; f[n_] := Module[{k = 2}, While[ expoCF[k, 2n] >= 2(1 + expoCF[k, n]), k++ ]; k-1]; t = Table[0, {100}]; Do[ a = f[n]; If[a < 101 &t[[a]] == 0, t[[a]] = n; Print[{a, n}]], {n, 400000}]; t

a(n)=0 iff n is a member of A080765: m such that m+1 divides lcm(1..m).

a(n-1)=0 iff n-1 is a member of A024619: Numbers that are not powers of primes.

A108795 Conjectured greatest number k such that C(2k,k) is not divisible by any odd prime to the n-th power.

Original entry on oeis.org

1, 786, 538279, 1430148153

Offset: 1

R. K. Guy and Robert G. Wilson v, Nov 29 2005

nonn

Checked by Jack Brennen to 5.93*10^10 and in fact every number beyond 14384056005 was divisible by at least two odd-prime-fourth-powers. C(2*14384056005,14384056005) seems to be the last such number which is only divisible by a single odd-prime-fourth-power, being divisible by 5^9 but by no other prime more than 3 times.

			a(1)=1 because for all k's>1 C(2k,k) is divisible by an odd prime.
a(2)=786 because it is the last entry in A059097, i.e., C(1572,786) has no prime factor squared.

R. K. Guy, Unsolved Problems in Number Theory, C33.

Cf. A059097.

expoPF[k_, n_] := Module[{s = 0, x = n}, While[x > 0, x = Floor[x/k]; s += x]; s]; goodQ[n_] := Module[{i = 2, p}, While[p = Prime[i]; p <= n && expoPF[p, 2n] < 3 + 2expoPF[p, n], i++ ]; p > n]; Do[ If[ goodQ[n], Print[n]], {n, 5500000}]

a(4) from Jack Brennen, Nov 30 2005

cp's OEIS Frontend

A110493 Largest prime p such that p^2 divides binomial(2n,n), or 0 if binomial(2n,n) is squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A356637 a(n) = A000265(A263931(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

SageMath

Formula

A111869 Least number k such that C(2k,k) is divisible by n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A239622 Conjecturally, the irregular triangle of numbers k such that prime(n)^2 is the largest squared prime divisor of binomial(2k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A118562 Least number k such that binomial(2k,k) is divisible by all squares to n squared but not (n+1) squared, or 0 if impossible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A108795 Conjectured greatest number k such that C(2k,k) is not divisible by any odd prime to the n-th power.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Extensions