Current status (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.[2]
1Packet records
5 records
Record
Kind
Assessment
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.
Result
Evidence: Reproduced
A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1
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]
Relevance to this problem
For Most divisors of a binomial coefficient with top at most 10^6, record bdr1m-claim-cutoff-lower-bound (“A certified cutoff-scale coefficient gives a 16,113-digit lower bound”) records a bound, answer, status fact, or structural consequence. The record states: 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.
Evidence
ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope.
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.
An exact 100-million-state recurrence sweep gives a 469-digit divisor count.
Result
Evidence: Computational evidence
The record reports a computation within its stated scope. Reproduction requires a separate replay.
claim · Computation 2
An exact 100-million-state recurrence sweep gives a 469-digit divisor count.[2]
Relevance to this problem
For Most divisors of a binomial coefficient with top at most 10^6, record bdr1m-claim-exact-prefix-20000 (“The exact record through n=20,000 occurs at (19,971, 9,949)”) records a bound, answer, status fact, or structural consequence. The record states: An exact 100-million-state recurrence sweep gives a 469-digit divisor count.
Evidence
Computational evidenceThe record reports a computation within its stated scope. Reproduction requires a separate replay.
Using \(k\leq n/2\) by symmetry, the exact prefix record is attained at
\[
(n,k)=(19971,9949).
\]
Its divisor count is
\[
\boxed{2348387885204790879830610540244537680880212204266092283665817947799112331315722388739095226210492168628520272301982570612855049692984247653163656175812378814497351725872902200308583530162859385427897865865873620878587583646796243101440659894852088456115074260792754959770155740574399754249752554204207499681748634739352025413649254209837693841360334377369629570834866128375706364256515169543130470863765460450748221403831366558257535620632378709575168022539059180077056}.
\]
The prime-exponent histogram of \(\binom{19971}{9949}\) is
\[
\#\{p:v_p=1\}=1527,\quad \#\{p:v_p=2\}=9,\quad \#\{p:v_p=3\}=4,
\]
with one exponent 8 and one exponent 10. The factors having exponent above one are
\[
2^{10}3^8 5^3 7^2 11^3 13^3 19^2 23^3 41^2 59^2 79^2 107^2 109^2 127^2 131^2.
\]
Thus the displayed value also equals \(2^{1527}3^9 4^4 9\cdot11\). The ordered full factorization has SHA-256 digest `11d4dc8a9b2dc54225e841546f236a3a9cd5c2f61fe0db6ab2455f28749b9c6c` under the `p^e` convention documented in the certificate artifact.
The sources located do not give the two-parameter bounded record at one million.
Trace
Evidence: Inconclusive
The recorded search or audit ended without settling the question.
attempt · Route 1
The sources located do not give the two-parameter bounded record at one million.[1][2][3]
Relevance to this problem
For Most divisors of a binomial coefficient with top at most 10^6, record bdr1m-attempt-literature-audit (“The literature audit found asymptotic and central-coefficient results”) documents a concrete method, search boundary, or failed route. The record states: The sources located do not give the two-parameter bounded record at one million.
Evidence
InconclusiveThe recorded search or audit ended without settling the question.
Scope
published and public-sequence work on divisor counts and prime exponents of binomial coefficients
OEIS A048784 tabulates \(\tau\binom{2m}{m}\) for central binomial coefficients and cites Fedorov's asymptotic formula for that sequence. Fedorov's separate Mathematical Notes paper studies upper and lower orders of ratios between divisor counts of adjacent binomial coefficients. Erdős and Kolesnik study prime-power divisibility near the middle. These sources concern central values, asymptotics, or individual prime powers.
Searches by the exact objective, divisor-record terminology, and the pair of bounds \(k<n\leq10^6\) found no published table or complete two-parameter sweep. The exact value at the requested cutoff therefore remains unresolved in this record. The prefix theorem and cutoff-scale lower bound above are the certified results supplied here.
C++ updates prime exponents and the arbitrary-precision divisor count using exact small-integer multiplication and division.
Artifact
Evidence: Executable material
Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1
C++ updates prime exponents and the arbitrary-precision divisor count using exact small-integer multiplication and division.[2]
Relevance to this problem
For Most divisors of a binomial coefficient with top at most 10^6, record bdr1m-artifact-exact-prefix-sweep (“Exact 100-million-state binomial recurrence sweep”) supplies evidence or a replay used to check the packet. The record states: C++ updates prime exponents and the arbitrary-precision divisor count using exact small-integer multiplication and division.
Evidence
Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay.
Record state
available
Scope
all 100000000 symmetry-reduced pairs with 2 <= n <= 20000 and 1 <= k <= floor(n/2)
c++ -O3 -std=c++17 sweep.cpp -o sweep && ./sweep 20000
Runtime
C++17 standard library
Details
For each fixed \(n\), the program starts at \(\binom n0=1\) and applies
\[
\binom nk=\binom n{k-1}\frac{n-k+1}{k}.
\]
A smallest-prime-factor sieve decomposes both update terms. When an exponent changes from \(e\) to \(e'\), the program replaces the divisor-count factor \(e+1\) by \(e'+1\). Its base-\(10^9\) integer class performs every division exactly and aborts on a remainder or a negative binomial exponent.
The sweep visits exactly 100,000,000 states and performs 490,041,974 prime-exponent updates. It hashes each row maximum, its location, and its decimal length in increasing row order. The final FNV-1a value is `15944218793165208384`. The one-line standard output has SHA-256 digest `acd2be4af4c40571118fca0c72418c8785bc595949f3d5cecc44bcd02f8f7c69`.
Standard-library Python regenerates both full factorizations and checks their SHA-256 digests.
Artifact
Evidence: Executable material
Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 2
Standard-library Python regenerates both full factorizations and checks their SHA-256 digests.[2]
Relevance to this problem
For Most divisors of a binomial coefficient with top at most 10^6, record bdr1m-artifact-factorization-replay (“Legendre factorization and divisor-count replay”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python regenerates both full factorizations and checks their SHA-256 digests.
Evidence
Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay.
Record state
available
Scope
the complete prime-exponent factorizations at (19971,9949) and (1000000,499985)
join source_lines with newline and run with python3
Runtime
CPython 3.9 or later, standard library only
Details
The verifier sieves every prime through each top parameter. Legendre's factorial valuation gives every binomial exponent as an integer. The code joins the nonzero pairs in ascending prime order using `p^e` and hashes the resulting factorization. It then multiplies every \(e+1\), hashes the exact decimal divisor count, and reports each exponent histogram.
The prefix factorization contains 1,542 terms. The cutoff-scale factorization contains 53,478 terms. Their report payload has SHA-256 digest `fea7d94ea1b9b59e253076f13b8caf82c47db0d875c7e0b71d351554ee7eb723`.
Original intake status. UNKNOWN as of 2026-07-25. An exact 100-million-state recurrence sweep gives a 469-digit divisor count. The checked sources do not settle the full acceptance condition.
The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: An exact 100-million-state recurrence sweep gives a 469-digit divisor count.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. The prefix record occurs at (n,k)=(1992,943).
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.
How the 5 records connectThe overview places each record once. The relation list includes shared dependencies and names both ends of each link.
ProblemMost divisors of a binomial coefficient with top at most 10^6
Contribute to this problemCite this problem statement
Cite the original sources separately.
Plain text
“Most divisors of a binomial coefficient with top at most 10^6.” TheoremDB. P2666. Problem statement; statement text SHA-256 bb94a806480af1f7b9130c58f973f88c5ff6a88c9f8ec9c9a8bc7b76bc66e5f7. https://theoremdb.org/statement/?ref=P2666
BibTeX
@misc{theoremdb-problem-bb94a806480af1f7b9130c58f973f88c5ff6a88c9f8ec9c9a8bc7b76bc66e5f7,
title = {{Most divisors of a binomial coefficient with top at most 10\textasciicircum{}6}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 bb94a806480af1f7b9130c58f973f88c5ff6a88c9f8ec9c9a8bc7b76bc66e5f7},
url = {https://theoremdb.org/statement/?ref=P2666}
}
Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.
1References
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. 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. ↗reference database · reference source · web version checked 2026-07-25 · checked 2026-07-25Source use: original summary.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.The literature audit found asymptotic and central-coefficient results. The sources located do not give the two-parameter bounded record at one million.Also cited at Entry definition, values, comments, programs, and linked references.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.
Packet source. 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. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The literature audit found asymptotic and central-coefficient results. The sources located do not give the two-parameter bounded record at one million.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.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.
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. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The literature audit found asymptotic and central-coefficient results. The sources located do not give the two-parameter bounded record at one million.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.
CC0 bounded divisor-record target with an exact prime-exponent recurrence.
Discussion
Loading
Past commenters and subscribers receive notifications when someone comments.