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

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

Author

Robert G. Wilson v, Nov 23 2005

Keywords

• nonn

Comments

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)

Examples

			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)
		

Links

• 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

Crossrefs

Cf. A000984, A059097, A073078, A370980.

Programs

Mathematica

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

PARI

See Corneth link

Formula

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