ERDŐS/DAILY ▸

← back to the ledger

ERDőS #663 · PARTIAL

Erdős problem #663 — wave w007

Date: 2026-07-28 (UTC)

Claim labels used below:

proof using only elementary arithmetic/CRT.

negative, or an extrapolation.

asymptotic theorem.

0. Mandatory live-page gate

(a, direct-source check) I loaded the live page erdosproblems.com/663 through the Bright Data browser path on 2026-07-28, then separately loaded its discussion thread and LaTeX view. The live snapshot said:

Thus the mandatory stop condition did not trigger.

Verbatim live statement

Let $k\geq 2$ and $q(n,k)$ denote the least prime which does not divide $\prod_{1\leq i\leq k}(n+i)$. Is it true that, if $k$ is fixed and $n$ is sufficiently large, we have\[q(n,k)<(1+o(1))\log n?\]

Everything else stated on the live page

(a, direct-source check) The page calls this a problem of Erdős and Pomerance and states the known bound

\[ q(n,k)<(1+o(1))k\log n. \]

It says the proposed improvement may even hold for \(k=o(\log n)\), and points to problem 457.

(c) Tao's sole comment gives the following heuristic, explicitly not a proof. For fixed \(k\), allocating the primes up to roughly \(\log x\) among \(n+1,\ldots,n+k\) gives

\[ k^{(1+o(1))\log x/\log\log x} =x^{(\log k+o(1))/\log\log x} \]

possible allocations. CRT determines one residue for each. Requiring the additional primes up to \((1+\epsilon)\log x\) to hit the same \(k\) numbers has heuristic probability

\[ \left(\frac{k}{(1+O(\epsilon))\log x}\right)^{ (1+o(1))\epsilon\log x/\log\log x} =x^{-\epsilon+o(1)}. \]

This should dominate the subpower allocation count and leave only finitely many exceptions. Tao says making this rigorous looks hard, and notes that the difficulty is monotone in \(k\), so \(k=2\) is the first case to attack. The site warns that comments are unverified.

1. Literature check

(a, primary-source check) Erdős's paper “Many old and on some new problems of mine in number theory,” Congressus Numerantium 30 (1981), 3–27, printed pages 17–18, defines the same \(q(n,k)\) as the smallest prime not dividing \(\prod_{i=1}^k(n+i)\), then asks a related variable-\(k\) question. This verifies that the quantity itself occurs in an original Erdős source. It does not supply the fixed-\(k\) estimate asked here.

(a, bibliographic check only) The live page cites Erdős, “Some of my favourite unsolved problems,” Mathematica Japonica 46(3) (1997), 527–537. The journal's official contents page confirms the title, author, issue, month, and pages. I did not find an open full scan from the publisher, so I did not attribute any finer claim to that article.

(a, primary-source miss) The other live citation is Burr–Erdős–Graham–Li, “Complete sequences of sets of integer powers,” Acta Arithmetica 77 (1996), 133–138, DOI 10.4064/aa-77-2-133-138. I inspected all six pages. The paper concerns completeness of sums of distinct powers. It uses primes only as divisors of an auxiliary modulus in one proof; I found no \(q(n,k)\), no least missing prime, and no product of consecutive integers. I could not find support for problem 663 in it and therefore did not use it.

(c, explicitly non-exhaustive search negative) Exact-phrase and formula searches for "least prime which does not divide", "q(n,k)" together with Erdős/Pomerance, "least number coprime to all numbers in [n+1,n+k]", and "Erdős problem 663" found the live page, the new secondary OEIS entry A391668, and the old sources above, but no later primary paper proving a fixed-\(k\) improvement. Searches also returned papers on large prime factors, Pillai-type coprimality, and long sieved gaps; their statements are different. This is a report of the search, not proof that no relevant paper exists.

2. Rigorous reductions

2.1 The easy bound

(b, Prime Number Theorem) If \(q=q(n,k)\), every prime \(p<q\) divides \(\prod_{i=1}^k(n+i)\). Hence

\[ \prod_{p<q}p\leq\prod_{i=1}^k(n+i)\leq(n+k)^k. \]

The Prime Number Theorem in the equivalent form \(\sum_{p\leq x}\log p=(1+o(1))x\) gives, for fixed \(k\),

\[ (1+o(1))q\leq k\log(n+k)=(k+o(1))\log n. \]

This recovers the live page's \(q(n,k)<(1+o(1))k\log n\).

2.2 Exact CRT form for fixed \(k\)

For a prime \(Q\), define

\[ M_k(Q):=\min\{n\geq1:q(n,k)\geq Q\}. \]

(a) Every prime \(p\leq k\) divides at least one of any \(k\) consecutive integers. If \(k<p<Q\), at most one of \(n+1,\ldots,n+k\) is divisible by \(p\). Therefore, writing

\[ \mathcal P_{k,Q}=\{p\text{ prime}:k<p<Q\},\qquad P_{k,Q}=\prod_{p\in\mathcal P_{k,Q}}p, \]

the condition \(q(n,k)\geq Q\) is equivalent to choosing, for every \(p\in\mathcal P_{k,Q}\), one index \(i_p\in\{1,\ldots,k\}\) and imposing

\[ n\equiv-i_p\pmod p. \]

CRT gives one residue modulo \(P_{k,Q}\) for each allocation. The allocations are distinct because \(p>k\). Consequently \(M_k(Q)\) is exactly the least positive representative among

\[ k^{\,\pi(Q-1)-\pi(k)} \]

explicit CRT residues.

(a) The original conjecture is equivalent to

\[ \boxed{\log M_k(Q)\geq(1-o(1))Q} \tag{1} \]

as \(Q\) tends to infinity through the primes. Indeed, if (1) holds and \(q(n,k)=Q\), then \(n\geq M_k(Q)\), giving \(Q\leq(1+o(1))\log n\); bounded \(Q\) is harmless. Conversely, apply the conjectured bound at \(n=M_k(Q)\). Also \(M_k(Q)\to\infty\), since a finite set of \(n\)'s has a finite maximum value of \(q(n,k)\).

This is a clean finite-to-asymptotic reduction: the only missing part is a uniform lower bound for the smallest of these structured CRT residues.

2.3 Specialization to \(k=2\)

For a real cutoff \(y\), put

\[ P_y=\prod_{p\leq y}p,\qquad R_2(y)=\min\{n\geq1:q(n,2)>y\}. \]

Let \(x=n+1\).

(a) Since \(\gcd(x,x+1)=1\), the condition \(q(n,2)>y\) partitions the primes \(p\leq y\) into two sets. With

\[ A=\prod_{p\mid x,\ p\leq y}p,\qquad B=P_y/A, \]

it is equivalent to

\[ x\equiv0\pmod A,\qquad x\equiv-1\pmod B. \tag{2} \]

Conversely, every factorization \(P_y=AB\) with \((A,B)=1\) and (2) gives such an \(n\). Thus there are exactly \(2^{\pi(y)}\) cases.

For each prime \(p\leq y\), define the CRT idempotent

\[ E_p=\frac{P_y}{p}\left(\frac{P_y}{p}\right)^{-1}\pmod p \quad(\bmod P_y). \]

It is \(1\bmod p\) and \(0\) modulo every other prime dividing \(P_y\). If \(T\) is the set of primes assigned to \(x+1\), then

\[ x_T\equiv-\sum_{p\in T}E_p\pmod{P_y}. \tag{3} \]

Hence \(R_2(y)\) is obtained by finding the least admissible positive representative among all modular subset sums (3), then subtracting one.

(a) Equivalently, every candidate is a positive solution of

\[ Bv-Au=1,\qquad AB=P_y,\qquad x=Au,\quad x+1=Bv. \tag{4} \]

The desired asymptotic in the \(k=2\) case is exactly the assertion that the least \(Au\) occurring in (4) is \(\exp((1-o(1))y)\).

3. Exact finite result

(d, complete deterministic enumeration) The checker proves

\[ \boxed{ R_2(199)= 68979941211663467981891685180356798343731381481900118460455756739438. } \tag{5} \]

Call the integer in (5) \(N\). It also directly computes

\[ \boxed{q(N,2)=211.} \tag{6} \]

Therefore the sharp concrete statement is:

\[ 1\leq n<N\Longrightarrow q(n,2)\leq199, \qquad q(N,2)=211. \tag{7} \]

This is a finite computer-assisted theorem, not a solution of the asymptotic problem.

3.1 Explicit witness

(a, exact integer identities; allocation minimality remains (d)) The minimizing partition returned by the exhaustive search is

\[ \begin{aligned} A={}&108759791111951636978029476381590341452321,\\ B={}&71716964164216075185088687074201951585610,\\ u={}&634241207218383920900252559,\\ v={}&961835766691330846118927704. \end{aligned} \]

The prime allocations are

\[ \begin{aligned} A:\;&3,13,17,19,29,31,41,47,53,59,67,71,83,89,97,103,\\ &149,157,163,173,181,193,197,\\ B:\;&2,5,7,11,23,37,43,61,73,79,101,107,109,113,127,\\ &131,137,139,151,167,179,191,199. \end{aligned} \]

They partition all 46 primes at most 199, and direct multiplication gives

\[ \begin{aligned} Au&=N+1\\ &=68979941211663467981891685180356798343731381481900118460455756739439,\\ Bv&=N+2\\ &=68979941211663467981891685180356798343731381481900118460455756739440. \end{aligned} \]

Thus every prime through 199 divides \((N+1)(N+2)\). The next prime is 211, and

\[ N+1\equiv44\pmod{211},\qquad N+2\equiv45\pmod{211}, \]

so 211 is missing.

3.2 Checkpoints

(d) The same code independently recomputes these complete thresholds:

| \(y\) | \(\pi(y)\) | allocations | exact \(R_2(y)\) | \(q(R_2(y),2)\) | \(q/\log R_2(y)\) | |---:|---:|---:|---:|---:|---:| | 97 | 25 | 33,554,432 | 161426380685234430031618378948 | 101 | 1.501772834599 | | 151 | 36 | 68,719,476,736 | 4609323640415818597292154101076585409117204302643 | 157 | 1.401133116593 | | 199 | 46 | 70,368,744,177,664 | 68979941211663467981891685180356798343731381481900118460455756739438 | 211 | 1.350793939987 |

These ratios are data only; three decreasing values are not evidence of a proved limiting trend.

4. Why the enumeration proves the finite minimum

The standalone verifier is erdos663_wavew007_verify.py. It uses only the Python standard library.

(a, algorithmic coverage proof) For \(y=199\), formula (3) gives 46 binary choices. The program splits the weights into two groups of 23, generates all \(2^{23}\) subset sums in each group by Gray code, sorts one complete list, and streams the other. For every left sum \(s\), binary search finds the closest right sum to \(-s\bmod P_y\), on both sides of the circular wrap. This examines the minimum of every one of the \(2^{23}2^{23}=2^{46}\) allocations. It is a meet-in-the-middle reorganization of exhaustive search, not pruning or random sampling.

(a) Distinct subsets have distinct CRT coordinate vectors, so the half-list residues are unique. The code checks this, checks every idempotent coordinate, reconstructs \(A,B\) from the minimizing mask, checks \(AB=P_y\), checks the two divisibilities in (2), and recomputes \(q(N,2)\) by an independent trial-division prime stream. A separate naive scan checks the small case \(R_2(13)=713\), \(q(713,2)=19\).

Run the full verification with:

python runs/erdos663_wavew007_verify.py

The quick checkpoint is:

python runs/erdos663_wavew007_verify.py --quick

The full run uses two \(2^{23}\)-sized logical halves while storing only the sorted right list. A clean invocation completed in 53.3 seconds with peak resident memory 705,744 KiB and printed:

y= 97 pi=25 allocations=33554432 R_2(y)=161426380685234430031618378948 q=101 q/log(R)=1.501772834599
y=151 pi=36 allocations=68719476736 R_2(y)=4609323640415818597292154101076585409117204302643 q=157 q/log(R)=1.401133116593
y=199 pi=46 allocations=70368744177664 R_2(y)=68979941211663467981891685180356798343731381481900118460455756739438 q=211 q/log(R)=1.350793939987
PASS

The verifier also prints the witness factors and allocated prime sets; any mismatch with the recorded integers raises an assertion.

5. Exact remaining wall

(b, Prime Number Theorem) In the general reduction,

\[ \log P_{k,Q}=(1+o(1))Q,\qquad k^{\pi(Q)-\pi(k)}=\exp(o(Q)). \]

Thus the average spacing of the CRT residues has the desired scale \(\exp(Q-o(Q))\).

(a) Cardinality alone gives no lower bound on the smallest residue: one highly structured residue could be tiny while all the others have large gaps. The elementary product inequality only gives

\[ P_y\mid(n+1)(n+2)\Longrightarrow n+2\geq\sqrt{P_y}, \]

which is the constant-2 bound \(q(n,2)\leq(2+o(1))\log n\). Equation (4) does not become a standard fixed-\(S\) unit equation because the cofactors \(u,v\) are unrestricted.

(c, precise missing lemma) What would close the problem is a deterministic lower-tail anti-concentration theorem for the CRT choice sums: for every fixed \(k\) and every \(\delta>0\), eventually no allocation satisfies

\[ 1\leq \left\langle-\sum_{k<p<Q} i_pE_p\right\rangle_{P_{k,Q}} \leq \exp((1-\delta)Q). \tag{8} \]

Statement (8) is exactly (1) in CRT coordinates. Tao's model predicts it, but neither the product bound, the number of allocations, nor an average-case equidistribution statement rules out the single exceptional allocation that matters.

(c, computational cost estimate) The exact method costs \(O(2^{\pi(y)/2}\log 2^{\pi(y)/2})\) time and \(O(2^{\pi(y)/2})\) memory for \(k=2\). Extending from \(y=199\) (\(2^{23}\) per half) to \(y=229\) (\(2^{25}\) per half) is estimated at roughly 4–6 CPU-minutes and 1.5–2.5 GiB in this Python implementation, so I did not run it under the stated budget. At \(y=1000\), \(\pi(y)=168\), so each half has \(2^{84}\approx1.93\times10^{25}\) entries; even an optimistic \(10^7\) entries/second would require about \(5.4\times10^{14}\) core-hours. Finite enumeration therefore cannot supply the uniformity needed for the conjecture.

PARTIAL: exact CRT reduction plus a complete k=2 enumeration proves the sharp cutoff q(n,2)<=199 for every 1<=n<68979941211663467981891685180356798343731381481900118460455756739438, with q(N,2)=211 at equality; the unresolved step is uniform lower-tail anti-concentration of the CRT allocation residues.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger