Erdős Problem #929

Erdős Problem 929 --- collection record

PROVENANCE AND STATUS

TeX syntax corrected for display; mathematical content unchanged. Official problem: https://www.erdosproblems.com/929

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below with TeX syntax corrections for display.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/929.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Let k$\ge$ 2 be an integer. For x$\ge$ 2, define the property (*)_{k,x}(n): \[(\*)_{k,x}(n)\quad\text{means: for each } i\in\{1,2,\dots,k\},\; n+i \text{ is divisible by at least one prime } p\le x.\] Equivalently, each of the k consecutive integers n+1,…,n+k has a prime factor $\le$ x.

Let A_{k,x}:={n$\in\mathbb N$: (*)_{k,x}(n) holds}. Define S(k) to be the minimal real x such that A_{k,x} has positive (natural) density, i.e. \[ \limsup_{N\to\infty} \frac{|A_{k,x}\cap[1,N]|}{N} > 0. \] (For fixed k, the intended meaning of “positive density set of n” in the problem statement is: the asymptotic density exists and is >0, or at least that the upper density is >0; for our purposes we will show that once A_{k,x} is nonempty it already contains an arithmetic progression and hence has positive density.)

Question: Estimate S(k) as k$\to\infty$. In particular, is S(k)$\ge$ k^{1-o$1$}?

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records: - A lower bound from Rosser’s sieve: S(k) > k^{1/2-o$1$}. - A trivial upper bound: $S(k)\le k+1$ (e.g. take $n\equiv 1 \pmod{(k+1)!}$). - An improved upper bound from large prime gaps (Ford–Green–Konyagin–Maynard–Tao): $S(k) \ll k \frac{\log\log\log k}{\log\log k\,\log\log\log\log k}.$

I do not use or assert any additional external results beyond what is stated in the problem file.

3) ATTACK PLAN

Proof-track ideas (lower bounds on S(k)): - Translate the condition into a covering problem modulo the primorial $P(x)=\prod_{p\le x} p$ and apply sieve lower bounds to show one cannot cover an interval of length k using only primes $\le$ x when x is too small.

Construction-track ideas (upper bounds on S(k)): - Use Chinese remainder / covering congruences to force each of n+1,…,n+k to be divisible by a chosen small prime, yielding explicit arithmetic progressions.

Best path here: I can prove exact equivalences and the trivial upper bound rigorously, and I can compute small values of S(k) exactly for small k by exhaustive search modulo primorials. The asymptotic lower bound S(k)$\ge$ k^{1-o$1$} remains open.

4) WORK

Lemma 929.1 (nonempty $\Rightarrow$ positive density). Fix k$\ge$ 2 and x$\ge$ 2. Let M(x):=$\prod_{p\le x}$ p (the product of all primes $\le$ x). If there exists n_0 such that (*)_{k,x}$n_0$ holds, then A_{k,x} contains the entire arithmetic progression {n_0 + t M(x): t$\in\mathbb Z_{\ge 0}$}. In particular, A_{k,x} has natural density at least 1/M(x), hence positive.

Proof. Assume (*)_{k,x}$n_0$ holds. Fix i$\in${1,…,k}. By definition, there exists a prime p_i$\le$ x such that p_i divides n_0+i. Since p_i$\le$ x, the prime p_i is one of the factors of M(x), so p_i divides M(x). Therefore for any t$\ge$ 0, \[ n_0 + tM(x) + i \equiv n_0 + i \pmod{p_i}, \] so p_i divides n_0+tM(x)+i. Thus for each i, the integer n_0+tM(x)+i is divisible by a prime $\le$ x. Hence (*)_{k,x}(n_0+tM(x)) holds for every t$\ge$ 0. So the full arithmetic progression is contained in A_{k,x}. The progression has density exactly 1/M(x), so A_{k,x} has density at least 1/M(x)>0. $\square$

Corollary 929.1a. For fixed k, S(k) equals the minimal x such that there exists at least one integer n with (*)_{k,x}(n).

Proof. If A_{k,x} is nonempty then by Lemma 929.1 it has positive density, so such x is admissible for S(k). Conversely, if A_{k,x} has positive density then it is certainly nonempty. Thus “positive density” and “nonempty” are equivalent for A_{k,x}, and taking minima over x gives the corollary. $\square$

Lemma 929.2 (trivial upper bound S(k)$\le$ k+1). For every integer k$\ge$ 2, we have S(k)$\le$ k+1.

Proof. Let x:=k+1 and take n satisfying \[ n \equiv 1 \pmod{(k+1)!}. \] Then for each i$\in${1,…,k}, we have \[ n+i = 1 + i + t (k+1)! = (i+1) + t (k+1)! \] for some integer t, hence $i+1$ divides n+i because $i+1$ divides $k+1$!. Therefore n+i is divisible by a prime factor of $i+1$, and every prime factor of $i+1$ is $\le$ i+1$\le$ k+1=x. So (*)_{k,x}(n) holds. By Corollary 929.1a, this implies S(k)$\le$ x=k+1. $\square$

FAST REALITY CHECK (exact small-k computation). Using Corollary 929.1a, I computed S(k) for k$\le$ 30 by brute force search modulo primorials. I also computed, for each x, the maximum length L(x) of a run of consecutive integers all having a prime factor $\le$ x. Exact values found: - L$2$=1, L$3$=3, L$5$=5, L$7$=9, L$11$=13, L$13$=21, L$17$=25, L$19$=33. From these, the exact S(k) for k$\le$ 30 is: S$1$=2, S$2$=3, S$3$=3, S$4$=5, S$5$=5, S$6$=7, S$7$=7, S$8$=7, S$9$=7, S$10$=11, S$11$=11, S$12$=11, S$13$=11, S$14$=13, S$15$=13, S$16$=13, S$17$=13, S$18$=13, S$19$=13, S$20$=13, S$21$=13, S$22$=17, S$23$=17, S$24$=17, S$25$=17, S$26$=19, S$27$=19, S$28$=19, S$29$=19, S$30$=19.

An explicit witness for k=33 and x=19 is n=60043, since each of 60044,60045,…,60076 has a prime factor $\le$ 19; by Lemma 929.1 this yields a positive-density arithmetic progression of solutions.

5) VERIFICATION

- Lemma 929.1: Checked that using M(x)=$\prod_{p\le x}$p ensures every prime p$\le$ x divides M(x), so divisibility persists under translation by M(x). - Lemma 929.2: Checked that for each i, i+1 divides $k+1$!, hence divides n+i. - Computational check: Verified the run length L$19$=33 by direct gcd computation against the primorial 2$\cdot$3$\cdot$5$\cdot$7$\cdot$11$\cdot$13$\cdot$17$\cdot$19=9699690.

6) FINAL

UNRESOLVED (i) Strongest proved partial result: For each fixed (k,x), existence of a single n with the property implies a positive-density infinite arithmetic progression of such n (Lemma 929.1), and in particular S(k) can be characterized as the minimal x for which at least one such n exists (Corollary 929.1a). Also S(k)$\le$ k+1 holds by an explicit congruence construction (Lemma 929.2). Exact values of S(k) were computed for k$\le$ 30. (ii) First gap (crisp): Prove a near-linear lower bound $S(k)\ge k^{1-o(1)}$ (or exhibit a family of coverings showing $S(k)\le k^{1-\delta}$ for some fixed $\delta>0$ infinitely often). (iii) Top 3 next moves: 1. Reformulate the problem as a covering congruence problem: choose for each prime $p\le x$ one residue class a_p (mod p) so that {1,…,k} is covered by $\bigcup_{p\le x}\{i: i\equiv a_p\ (\mathrm{mod}\ p)\}$. Use this to search algorithmically for better constructions and to attempt lower bounds. 2. Attempt to prove a sieve lower bound on the Jacobsthal-type function for primorials: show the maximum run of integers not coprime to $\prod_{p\le x} p$ is $\le x^{1+o(1)}$ (or similar), then translate to S(k) lower bounds. 3. Extend brute force computations of S(k) to larger k (within feasible primorial sizes) to guess the true order of growth and test the plausibility of $S(k)\ge k^{1-o(1)}$. (iv) Minimal counterexample structure: A counterexample to $S(k)\ge k^{1-o(1)}$ would provide a sequence $k_j\to\infty$ and primes bounded by $x_j\le k_j^{1-\delta}$ together with residue classes mod those primes that cover all indices 1..k_j; equivalently, runs of length k_j in the sequence of integers all having a prime factor $\le$ x_j with x_j substantially smaller than k_j.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT

Let k$\ge$ 2 be an integer. For x$\ge$ 2, define the property (*)_{k,x}(n): \[(\*)_{k,x}(n)\quad\text{means: for each } i\in\{1,2,\dots,k\},\; n+i \text{ is divisible by at least one prime } p\le x.\] Equivalently, each of the k consecutive integers n+1,…,n+k has a prime factor $\le$ x.

Let A_{k,x}:={n$\in\mathbb N$: (*)_{k,x}(n) holds}. Define S(k) to be the minimal real x such that A_{k,x} has positive (natural) density, i.e. \[ \limsup_{N\to\infty} \frac{|A_{k,x}\cap[1,N]|}{N} > 0. \] (For fixed k, the intended meaning of “positive density set of n” in the problem statement is: the asymptotic density exists and is >0, or at least that the upper density is >0; for our purposes we will show that once A_{k,x} is nonempty it already contains an arithmetic progression and hence has positive density.)

Question: Estimate S(k) as k$\to\infty$. In particular, is S(k)$\ge$ k^{1-o$1$}?

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records: - A lower bound from Rosser’s sieve: S(k) > k^{1/2-o$1$}. - A trivial upper bound: $S(k)\le k+1$ (e.g. take $n\equiv 1 \pmod{(k+1)!}$). - An improved upper bound from large prime gaps (Ford–Green–Konyagin–Maynard–Tao): $S(k) \ll k \frac{\log\log\log k}{\log\log k\,\log\log\log\log k}.$

I do not use or assert any additional external results beyond what is stated in the problem file.

3) ATTACK PLAN

Proof-track ideas (lower bounds on S(k)): - Translate the condition into a covering problem modulo the primorial $P(x)=\prod_{p\le x} p$ and apply sieve lower bounds to show one cannot cover an interval of length k using only primes $\le$ x when x is too small.

Construction-track ideas (upper bounds on S(k)): - Use Chinese remainder / covering congruences to force each of n+1,…,n+k to be divisible by a chosen small prime, yielding explicit arithmetic progressions.

Best path here: I can prove exact equivalences and the trivial upper bound rigorously, and I can compute small values of S(k) exactly for small k by exhaustive search modulo primorials. The asymptotic lower bound S(k)$\ge$ k^{1-o$1$} remains open.

4) WORK

Lemma 929.1 (nonempty $\Rightarrow$ positive density). Fix k$\ge$ 2 and x$\ge$ 2. Let M(x):=$\prod_{p\le x}$ p (the product of all primes $\le$ x). If there exists n_0 such that (*)_{k,x}$n_0$ holds, then A_{k,x} contains the entire arithmetic progression {n_0 + t M(x): t$\in\mathbb Z_{\ge 0}$}. In particular, A_{k,x} has natural density at least 1/M(x), hence positive.

Proof. Assume (*)_{k,x}$n_0$ holds. Fix i$\in${1,…,k}. By definition, there exists a prime p_i$\le$ x such that p_i divides n_0+i. Since p_i$\le$ x, the prime p_i is one of the factors of M(x), so p_i divides M(x). Therefore for any t$\ge$ 0, \[ n_0 + tM(x) + i \equiv n_0 + i \pmod{p_i}, \] so p_i divides n_0+tM(x)+i. Thus for each i, the integer n_0+tM(x)+i is divisible by a prime $\le$ x. Hence (*)_{k,x}(n_0+tM(x)) holds for every t$\ge$ 0. So the full arithmetic progression is contained in A_{k,x}. The progression has density exactly 1/M(x), so A_{k,x} has density at least 1/M(x)>0. $\square$

Corollary 929.1a. For fixed k, S(k) equals the minimal x such that there exists at least one integer n with (*)_{k,x}(n).

Proof. If A_{k,x} is nonempty then by Lemma 929.1 it has positive density, so such x is admissible for S(k). Conversely, if A_{k,x} has positive density then it is certainly nonempty. Thus “positive density” and “nonempty” are equivalent for A_{k,x}, and taking minima over x gives the corollary. $\square$

Lemma 929.2 (trivial upper bound S(k)$\le$ k+1). For every integer k$\ge$ 2, we have S(k)$\le$ k+1.

Proof. Let x:=k+1 and take n satisfying \[ n \equiv 1 \pmod{(k+1)!}. \] Then for each i$\in${1,…,k}, we have \[ n+i = 1 + i + t (k+1)! = (i+1) + t (k+1)! \] for some integer t, hence $i+1$ divides n+i because $i+1$ divides $k+1$!. Therefore n+i is divisible by a prime factor of $i+1$, and every prime factor of $i+1$ is $\le$ i+1$\le$ k+1=x. So (*)_{k,x}(n) holds. By Corollary 929.1a, this implies S(k)$\le$ x=k+1. $\square$

FAST REALITY CHECK (exact small-k computation). Using Corollary 929.1a, I computed S(k) for k$\le$ 30 by brute force search modulo primorials. I also computed, for each x, the maximum length L(x) of a run of consecutive integers all having a prime factor $\le$ x. Exact values found: - L$2$=1, L$3$=3, L$5$=5, L$7$=9, L$11$=13, L$13$=21, L$17$=25, L$19$=33. From these, the exact S(k) for k$\le$ 30 is: S$1$=2, S$2$=3, S$3$=3, S$4$=5, S$5$=5, S$6$=7, S$7$=7, S$8$=7, S$9$=7, S$10$=11, S$11$=11, S$12$=11, S$13$=11, S$14$=13, S$15$=13, S$16$=13, S$17$=13, S$18$=13, S$19$=13, S$20$=13, S$21$=13, S$22$=17, S$23$=17, S$24$=17, S$25$=17, S$26$=19, S$27$=19, S$28$=19, S$29$=19, S$30$=19.

An explicit witness for k=33 and x=19 is n=60043, since each of 60044,60045,…,60076 has a prime factor $\le$ 19; by Lemma 929.1 this yields a positive-density arithmetic progression of solutions.

5) VERIFICATION

- Lemma 929.1: Checked that using M(x)=$\prod_{p\le x}$p ensures every prime p$\le$ x divides M(x), so divisibility persists under translation by M(x). - Lemma 929.2: Checked that for each i, i+1 divides $k+1$!, hence divides n+i. - Computational check: Verified the run length L$19$=33 by direct gcd computation against the primorial 2$\cdot$3$\cdot$5$\cdot$7$\cdot$11$\cdot$13$\cdot$17$\cdot$19=9699690.

6) FINAL

UNRESOLVED (i) Strongest proved partial result: For each fixed (k,x), existence of a single n with the property implies a positive-density infinite arithmetic progression of such n (Lemma 929.1), and in particular S(k) can be characterized as the minimal x for which at least one such n exists (Corollary 929.1a). Also S(k)$\le$ k+1 holds by an explicit congruence construction (Lemma 929.2). Exact values of S(k) were computed for k$\le$ 30. (ii) First gap (crisp): Prove a near-linear lower bound $S(k)\ge k^{1-o(1)}$ (or exhibit a family of coverings showing $S(k)\le k^{1-\delta}$ for some fixed $\delta>0$ infinitely often). (iii) Top 3 next moves: 1. Reformulate the problem as a covering congruence problem: choose for each prime $p\le x$ one residue class a_p (mod p) so that {1,…,k} is covered by $\bigcup_{p\le x}\{i: i\equiv a_p\ (\mathrm{mod}\ p)\}$. Use this to search algorithmically for better constructions and to attempt lower bounds. 2. Attempt to prove a sieve lower bound on the Jacobsthal-type function for primorials: show the maximum run of integers not coprime to $\prod_{p\le x} p$ is $\le x^{1+o(1)}$ (or similar), then translate to S(k) lower bounds. 3. Extend brute force computations of S(k) to larger k (within feasible primorial sizes) to guess the true order of growth and test the plausibility of $S(k)\ge k^{1-o(1)}$. (iv) Minimal counterexample structure: A counterexample to $S(k)\ge k^{1-o(1)}$ would provide a sequence $k_j\to\infty$ and primes bounded by $x_j\le k_j^{1-\delta}$ together with residue classes mod those primes that cover all indices 1..k_j; equivalently, runs of length k_j in the sequence of integers all having a prime factor $\le$ x_j with x_j substantially smaller than k_j.