Erdős problem #1181 — live audit, exact reduction, and exhaustive finite data

Access/search date: 2026-07-28 UTC.

Result in one paragraph

The mandatory collision gate did not fire: the live page is OPEN, has 0 claimed proofs, and lists no current worker or interested collaborator. I did not prove the requested uniform constant saving. I obtained two verifiable pieces of progress:

1. [a] an exact reduction

\[ q(n,k)\ge y \quad\Longleftrightarrow\quad \prod_{\substack{k<p<y\\p\ {\rm prime}}}p \ \bigm|\ {n+k\choose k}, \tag{1} \] together with the resulting sharper exact capacity inequality \[ \sum_{k<p<q(n,k)}\log p\le \log {n+k\choose k}; \tag{2} \]

1. [d] an exhaustive determination of

\(\max q(n,\lfloor\log n\rfloor)\) in every logarithmic band \(1\le\lfloor\log n\rfloor\le20\). This covers all \(1,318,815,732\) integers \[ 3\le n\le1,318,815,734<e^{21}. \] The largest value in the whole range is \(113\), attained uniquely at \(n=999,852,511\).

The exact unresolved step is not prime counting: below \((1-c)(\log n)^2\), the forced squarefree prime product is exponentially smaller than the binomial coefficient by \(\exp((c+o(1))(\log n)^2)\). One needs a uniform theorem saying that enough of the binomial coefficient is forced into repeated, small, or very large prime factors. The standard primorial estimate and Gallagher larger sieve do not supply such a theorem.

Claim labels

• [a] elementary-rigorous: proved below from elementary arithmetic, or a

direct observation from a checked source.

• [b] rigorous-modulo-named-theorem: the deduction is complete after the

explicitly named published theorem is accepted.

• [c] plausible/structural-unverified: a heuristic, diagnosis, or possible

route, not a theorem.

• [d] computational-only: exhaustively checked only in the stated finite

range.

Nothing below claims that problem #1181 is solved.

0. Mandatory live-page gate

Retrieval and collision check

[a, direct source observation] I fetched the rendered DOM of <https://www.erdosproblems.com/1181> through the Bright Data residential browser path. Direct datacenter fetching was not used as authority. The live page displayed:

• status OPEN;
• 0 comments on this problem;
• 0 claimed proofs for this problem;
• Interested in collaborating None;
• Currently working on this problem None;
• This problem looks difficult None;
• This problem looks tractable None;
• last edited 07 March 2026.

Thus neither stop condition applied.

Verbatim live statement

Let \(q(n,k)\) denote the least prime which does not divide \(\prod_{1\leq i\leq k}(n+i)\). Is it true that there exists some \(c>0\) such that, for all large \(n\), \[ > q(n,\log n)<(1-c)(\log n)^2? > \]

The source marker is [Er79d,p.78]; the only tag is number theory.

Everything mathematical listed on the page

[a, tracker transcription] The page records the elementary bound

from comparison of the primorial with the product of the consecutive integers.

[c, tracker-reported heuristic] It reports Tao's heuristic from the comments on problem #457:

[a, tracker transcription] It points to #457 for lower bounds. The current #457 page reports the complementary construction

for infinitely many \(n\), based on an elaboration sketched by Tao in that page's comments. This is tracker material, not a claim independently promoted here to a published theorem.

For the integer-valued second argument, I use the original source's explicit convention \(k=\lfloor\log n\rfloor\), and every logarithm below is natural.

1. Primary-source and literature audit

Original source

[a, source-verified] The cited paper exists:

Paul Erdős, “Some unconventional problems in number theory,” Acta Mathematica Academiae Scientiarum Hungaricae 33 (1979), 71–80, DOI <https://doi.org/10.1007/BF01903382>.

I downloaded the scan from the Erdős publication archive and extracted page 78. Erdős defines \(A(n,k)=\prod_{1\le i\le k}(n+i)\), defines \(q(n,k)\) as above, gives the crude \(q(n,k)<(1+o(1))k\log n\), and then asks the stronger

for all sufficiently large \(n\). He immediately says that he and Pomerance could not even prove the weaker constant saving from \((\log n)^2\). Thus the live problem is an exact extraction of the explicitly stated 1979 barrier.

Searches actually performed

[a, search observation; not a theorem] I searched exact phrases and notation including "q(n,k)", "q(n,[log n])", `"least prime which does not divide"`, the title of the 1979 paper, and combinations with consecutive integers and Pomerance. I also queried Crossref and the OpenAlex citation graph for DOI 10.1007/BF01903382 and inspected titles and abstracts/full text when relevant. No paper found in those searches states the uniform upper bound in #1181 or a constant-factor improvement over \((\log n)^2\). Search misses are not evidence that no such paper exists.

The closest apparently relevant citing paper was M. A. Bennett, M. Filaseta, and O. Trifonov, “On the factorization of consecutive integers”, J. Reine Angew. Math. 629 (2009), 171–200, DOI <https://doi.org/10.1515/CRELLE.2009.030>. [a, source-verified] Its introduction and main theorems concern the small-prime and large-prime parts of binomial coefficients, especially fixed small \(k\) and explicit Diophantine exceptions. It does not state a bound for \(k=\lfloor\log n\rfloor\) that fills the gap below.

The live problem itself was only split off from #457 on 7 March 2026. No claimed proof or discussion had appeared on its page by the access date.

2. Exact arithmetic reduction

Let

Lemma 1: one-prime residue test

[a] If \(p>k\) is prime, then

Indeed, the least positive distance from \(n\) to the next multiple of \(p\) must be one of \(1,\ldots,k\). If \(n\bmod p=0\), that distance is \(p>k\), so residue zero is correctly excluded.

Lemma 2: binomial divisibility equivalence

[a] For any real \(y>k\),

Proof. Every prime \(p\le k\) divides a block of \(k\) consecutive integers. For \(p>k\), \(v_p(k!)=0\), hence

The condition \(q(n,k)\ge y\) says exactly that every prime \(p<y\) divides the block product. The primes in \(R(k,y)\) are distinct, so their individual divisibilities are equivalent to their product dividing \(B(n,k)\).

\(\square\)

This gives a particularly compact reformulation of #1181: prove that for some \(c>0\), with \(k=\lfloor\log n\rfloor\),

for every sufficiently large \(n\).

Exact capacity bound

Write

Taking \(y=q(n,k)\) in (4) gives

This is [a] and is a strict refinement of comparing the primorial with the unnormalised product: division by \(k!\) is legitimate for all forced primes \(p>k\).

The standard estimate \({N\choose k}\le(eN/k)^k\) gives the completely explicit inequality

For \(k=\lfloor\log n\rfloor\), Stirling's formula gives

Consequently, the prime number theorem \(\vartheta(x)\sim x\) yields

This deduction is [b, prime number theorem]. Importantly, the unknown \(o(1)\) in (8) may swamp the displayed \(k\log k\) term, so (8) does not constitute a second-order bound on \(q\), much less a constant saving. Equation (5), not an overinterpreted expansion of (8), is the useful rigorous reduction.

3. Exact finite computation

Exhaustive algorithm

[a] For fixed \(k\), the relevant integer band is

The checker proves each claimed ceiling exactly with rational Taylor bounds: it computes

and bounds the tail by

Both comparisons with the adjacent integers are then exact Fraction comparisons; no floating-point logarithm decides a band endpoint.

[a] Within a band, before testing a prime \(p>k\), the candidate vector contains exactly those \(n\) for which every earlier prime divides \(P(n,k)\). Equation (3) says to retain exactly the candidates satisfying n % p >= p-k. Deleted entries have \(q(n,k)=p\). When the candidate vector is empty, that entire chunk has been classified. Chunking changes memory use but not the search space.

[d] NumPy performs only exact signed 64-bit remainder and comparison operations here; the largest \(n\) is below \(2^{31}\). The standalone checker additionally:

1. cross-checks the Eratosthenes prime list against trial division;
2. compares the residue algorithm with a literal big-integer product

implementation for every \(n\le10,000\) in the bands;

1. recomputes every reported maximizer from the literal product definition;
2. verifies \(R(k,q)\mid {n+k\choose k}\) for every maximizer;
3. verifies the explicit \(k=20\) residue certificate below.

Complete table

[d] The following maxima and complete maximizer lists were obtained by exhausting every integer in every displayed band.

Thus:

[d, exact finite theorem] For every integer \(3\le n<e^{21}\), \(q(n,\lfloor\log n\rfloor)\le113\), with equality only at \(n=999,852,511\). The much more informative bandwise sharp bounds are in the table. This is finite evidence, not evidence of a uniform asymptotic constant by itself.

Compact certificate for the top value

Take \(n=999,852,511\), \(k=20\). Every prime \(p\le20\) automatically divides one of 20 consecutive integers. For the remaining primes below 113, the following table gives an \(i\) for which \(p\mid n+i\):

On the other hand,

so the next multiple of 113 is \(113-35=78>20\) places away. Hence \(q(n,20)=113\). Every entry is directly checked by the standalone script.

4. Why the standard machinery stops

The exact exponential capacity gap

Let \(k=\lfloor\log n\rfloor\) and \(y=(1-c)(\log n)^2=(1-c+o(1))k^2\). By the prime number theorem,

whereas (7) gives

Thus \(R(k,y)\) is smaller than \(B(n,k)\) by

This calculation is [b, prime number theorem]. It explains precisely why no refinement of the size comparison by only polynomial or \(\exp(O(k\log k))\) factors can prove a fixed \(c>0\).

A concrete sufficient missing lemma

Define the squarefree medium-prime part

The factor \(E\) contains all small-prime mass, all repeated copies of medium primes, and all prime factors exceeding \(k^2\).

[a, reduction] The following lemma would solve #1181:

There is a fixed \(\delta>0\) such that, whenever \(k=\lfloor\log n\rfloor\) and \(n\) is sufficiently large, \[ > \log E(n,k)\ge\delta k^2. > \tag{11} > \]

Indeed, if \(q(n,k)\ge(1-c)k^2\), then \(R(k,(1-c)k^2)\) is a subproduct of \(H\), so

Taking logarithms and using the prime number theorem gives

which is impossible for \(c<\delta\). This implication is [b, prime number theorem].

I found no theorem giving (11). Results asserting one large prime factor, one repeated prime, or an \(\exp(O(k\log k))\) complementary factor are quantitatively insufficient because of (9). A theorem of the scale (11), or another mechanism exploiting the aligned residues in (3), is the exact missing input for this route.

Larger-sieve barrier

Let \(\mathcal A\) be the set of \(n\) in an interval of length \(X\) for which \(q(n,k)>y\). By (3), modulo every prime \(k<p\le y\), the set \(\mathcal A\) occupies at most \(k\) residue classes.

Gallagher's larger sieve (P. X. Gallagher, “A larger sieve,” Acta Arith. 18 (1971), 77–81) would give

but only when the denominator is positive. For a logarithmic band, \(\log X=k+O(1)\), so at \(y=(1-c)k^2\) the denominator is

Therefore (12) supplies no bound at the target scale. This is [b, Gallagher's theorem + prime number theorem]. Improving it here requires using the special fact that the \(k\) occupied classes are the aligned interval \(\{-1,\ldots,-k\}\), not merely that there are \(k\) of them.

Why smooth-number estimates do not immediately substitute

[c] Condition (4) says that a block of only \(k\asymp\log n\) integers collectively contains every prime below \(y\); it does not say that every integer in the block is \(y\)-smooth. Average estimates for smooth numbers therefore do not directly address it. A usable result would need uniform control in every interval of length \(\log n\), plus enough quantitative mass outside the one-copy medium-prime product to reach (11). That is much stronger than the average-density statements located in the search.

Cost of extending the brute-force table

[d] The complete checker scanned 1.319 billion integers in 79.7 seconds on one VM core, with the \(k=20\) band taking 49.5 seconds. The next band contains exactly 2,266,097,112 integers. At the measured rate it would cost about \(0.04\) core-hours; I did not run it because it would add several CPU minutes for no new asymptotic mechanism.

[c, measured-rate extrapolation] Exponential band growth quickly defeats this method: the \(k=25\) band has 123,724,710,091 integers (roughly 2 core-hours at the observed rate), and the \(k=30\) band has 18,362,375,083,723 integers (roughly 300 core-hours, likely optimistic). No finite extension can supply the required all-large-\(n\) step.

5. Reproduction

The standalone checker is runs/erdos1181_wave8i_reverify.py. It requires Python 3 and NumPy and is otherwise self-contained.

Run:

python3 runs/erdos1181_wave8i_reverify.py

The completed verification printed:

20  485165196    1318815734    833650539     113     1 (999852511,)  [49.506s]
VERIFIED: scanned 1,318,815,732 integers, 3 <= n <= 1,318,815,734, in 79.711s

SHA-256 of the checker used for that run:

a9049328dfdd631d0c9cde45f64932e6c395534455570bdbaa50f686763d2a0c

The core exhaustive step, reproduced from the standalone source, is:

def scan_band(k, lo, hi, primes, chunk_size):
    q_counts = defaultdict(int)
    terminal_candidates = []
    for start in range(lo, hi + 1, chunk_size):
        stop = min(hi + 1, start + chunk_size)
        candidates = np.arange(start, stop, dtype=np.int64)
        for p in primes:
            if p <= k:
                continue
            before = candidates
            candidates = before[(before % p) >= p - k]
            q_counts[p] += int(before.size - candidates.size)
            if candidates.size == 0:
                terminal_candidates.append((p, tuple(map(int, before))))
                break
        else:
            raise AssertionError("prime limit too small during scan")
    assert sum(q_counts.values()) == hi - lo + 1
    maximum = max(p for p, count in q_counts.items() if count)
    maximizers = []
    for terminal_prime, values in terminal_candidates:
        if terminal_prime == maximum:
            maximizers.extend(values)
    assert len(maximizers) == q_counts[maximum]
    return maximum, tuple(maximizers), dict(sorted(q_counts.items()))

PARTIAL: exact binomial-divisibility reduction proved and q(n,floor log n) exhaustively maximized for every 3<=n<e^21 (unique global maximum q=113), but no uniform constant saving is proved.