# P2666: Most divisors of a binomial coefficient with top at most 10^6

- ID: `P2666`
- Reference: `binomial-divisor-record-1e6`
- Page: https://theoremdb.org/statements/P2666
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(\tau(m)\) denote the number of positive divisors of \(m\). Determine \(\max_{1\le k<n\le10^6}\tau\!\binom{n}{k}\).

### Context

This finite arithmetic problem asks for the largest divisor count attained by any nontrivial binomial coefficient in the stated range.

### Problem setup

- **Definition (divisor function).** The divisor function \(\tau(m)\) is the number of positive divisors of \(m\).
- **Convention.** By the symmetry \(\binom nk=\binom n{n-k}\), a search may restrict to \(k\le n/2\).

### What counts as a solution

- Give an attaining pair (n,k), its prime-exponent certificate, and a complete exact sweep through n=10^6.

## Status

The exact factorization of \(\binom{1000000}{499985}\) gives a 16,113-digit divisor-count lower bound; no matching upper bound or complete sweep over \(1\le k<n\le10^6\) is recorded, so the exact maximum remains open. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (A certified cutoff-scale coefficient gives a 16,113-digit lower bound).** The exact factorization of \(\binom{1000000}{499985}\) gives a 16,113-digit divisor-count lower bound; no matching upper bound or complete sweep over \(1\le k<n\le10^6\) is recorded, so the exact maximum remains open.

At the admissible pair
\[
(n,k)=(1000000,499985),
\]
the coefficient has 53,478 distinct prime factors. Its exponent histogram is
\[
(1:53413),(2:56),(3:3),(4:2),(5:2),(8:1),(12:1).
\]
Consequently
\[
\max_{1\leq k<n\leq10^6}\tau\binom nk
\geq 2^{53413}3^{56}4^3 5^2 6^2\cdot9\cdot13.
\]
This exact integer has 16,113 decimal digits. Its first 64 digits are `2901061995181429015403180177031159054152063659198892515558624106`, its final 64 digits are `0248962087137382083803874069801496392268550388351507391473254400`, and its SHA-256 digest is `37e6b0aec8c146fa82e6e8d0eb776dbb1504fb2fff80e5fa74bff8eaddfee951`.

For complete factorization data, the artifact computes
\[
v_p\binom nk=\sum_{j\geq1}\left(\left\lfloor\frac n{p^j}\right\rfloor-\left\lfloor\frac k{p^j}\right\rfloor-\left\lfloor\frac{n-k}{p^j}\right\rfloor\right)
\]
for every prime \(p\leq10^6\). Joining the 53,478 nonzero pairs as ascending `p^e` terms gives SHA-256 digest `fb3db7328c0c940f68d88e873c6554c9ec65616c825f5b933fd2e55e492e1be2`. This certifies the lower bound without asserting that this pair is globally optimal.

### Background and intake notes

- Original intake status: Status remains unverified. Divisor records for binomial coefficients may appear in sequence tables, while this two-parameter cutoff needs a direct check.
- For each n, update the prime-exponent vector by C(n,k)=C(n,k-1)(n-k+1)/k and update tau multiplicatively. Partition by n intervals with boundary-free checkpoints.
- Trap: computing the binomial integer first creates avoidable huge values. Floating logarithms can rank candidates but cannot certify equal or adjacent divisor counts.

- Recorded example: The prefix record occurs at (n,k)=(1992,943).

### Other known results

- **Computation 2** (reproduced): An exact 100-million-state recurrence sweep gives a 469-digit divisor count. [2](#reference-2)

### Prior approaches

- **Route 1** (inconclusive): The sources located do not give the two-parameter bounded record at one million. [3](#reference-3) [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): C++ updates prime exponents and the arbitrary-precision divisor count using exact small-integer multiplication and division. [2](#reference-2)
- **Artifact 2** (reproduced): Standard-library Python regenerates both full factorizations and checks their SHA-256 digests. [2](#reference-2)

### Computational notes

- A smallest-prime-factor table and exact exponent updates checked every 1<=k<n<=2000, using k<=n/2 by symmetry. The largest divisor count was 38875045166713492745911146937917405680217134825593324271610888192 at C(1992,943); all exponent updates ended integral and nonnegative.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `binomial-divisor-record-1e6`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Paul Erdös and Grigori Kolesnik, “Prime power divisors of binomial coefficients”. Discrete Mathematics 200(1-3) (1999), 101-117. DOI 10.1016/S0012-365X(98)00326-4. OEIS A048784; G. V. Fedorov, On the number of divisors of binomial coefficients, Mathematical Notes 93 (2013), 308-316, DOI 10.1134/S0001434613010331; Paul Erdős and Grigori Kolesnik, Prime power divisors of binomial coefficients, Discrete Mathematics 200 (1999), 101-117, DOI 10.1016/S0012-365X(98)00326-4 https://doi.org/10.1016/S0012-365X(98)00326-4
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Most divisors of a binomial coefficient with top at most 10^6: The literature audit found asymptotic and central-coefficient results. The sources located do not give the two-parameter bounded record at one million.
2. <a id="reference-2"></a>G. V. Fedorov, “On the number of divisors of binomial coefficients”. Mathematical Notes 93(1-2) (2013), 308-316. DOI 10.1134/S0001434613010331. OEIS A048784; G. V. Fedorov, On the number of divisors of binomial coefficients, Mathematical Notes 93 (2013), 308-316, DOI 10.1134/S0001434613010331; Paul Erdős and Grigori Kolesnik, Prime power divisors of binomial coefficients, Discrete Mathematics 200 (1999), 101-117, DOI 10.1016/S0012-365X(98)00326-4 https://doi.org/10.1134/S0001434613010331
   - Also cited at Exact Legendre-valuation replay in bdr1m-artifact-factorization-replay
   - Also cited at Exact recurrence sweep in bdr1m-artifact-exact-prefix-sweep and Legendre certificate in bdr1m-artifact-factorization-replay
   - Also cited at Inline C++17 computation executed on 2026-07-25
   - Also cited at Inline CPython standard-library computation reproduced on 2026-07-25
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Most divisors of a binomial coefficient with top at most 10^6: The literature audit found asymptotic and central-coefficient results. The sources located do not give the two-parameter bounded record at one million.
   - Source named by the research packet.
3. <a id="reference-3"></a>David Johnson-Davies, “A048784: a(n) = tau(binomial(2*n,n)), where tau is the number of divisors,” The On-Line Encyclopedia of Integer Sequences, checked 2026-08-01. Entry definition, values, comments, programs, and linked references https://oeis.org/A048784
   - reference_database; reference source; web version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - Reused material: Entry definition, values, comments, programs, and linked references
   - Reuse basis: fair_use_reviewed; rights holder: The OEIS Foundation Inc. and the credited contributors; checked 2026-08-01; by Philip Weiss, TheoremDB staff
   - Required attribution: David Johnson-Davies, “A048784: a(n) = tau(binomial(2*n,n)), where tau is the number of divisors,” The On-Line Encyclopedia of Integer Sequences, checked 2026-08-01.
   - For Most divisors of a binomial coefficient with top at most 10^6, this source records the divisor count for central binomial coefficients without claiming the packet’s two-parameter bounded record.