Reused writeup on Math-5643 (gpt pro 5.2)

Erdős Problem 430 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/430

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, without editing their text.

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/430.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/430.tex.

FORMAL RESTATEMENT Fix an integer $n\ge 2$. Define a decreasing sequence $(a_k)$ of integers in $[1,n)$ by \[ a_1:=n-1, \] and for $k\ge 2$ define $a_k$ (if it exists) to be the greatest integer $m$ with $1\le m<a_{k-1}$ such that every prime factor $p$ of $m$ satisfies \[ p>n-m. \] (If no such $m$ exists, the sequence terminates.)

Question: Is it true that for all sufficiently large $n$, the sequence $(a_k)$ cannot consist solely of primes (aside from the terminal $1$)? Equivalently: for all sufficiently large $n$, does there exist a composite $m$ with $1<m<n$ whose prime factors all exceed $n-m$?

Conventions: $1$ has no prime factors, so it vacuously satisfies the “all prime factors” condition.

QUICK LITERATURE/CONTEXT CHECK The problem statement reports computational evidence (Selfridge) but no proof, and notes an equivalence to another problem. No external results are used here.

ATTACK PLAN Proof track ideas. 1) Translate the condition in terms of the least prime factor $p(m)$: the constraint is $p(m)>n-m$. 2) Show that for large $n$ there must exist a composite $m$ close to $n$ whose least prime factor exceeds $n-m$ (a “rough composite” in a short interval), possibly by sieve/large-prime-factor arguments.

Disproof track ideas. 1) Look for an infinite family of $n$ for which every $m$ satisfying $p(m)>n-m$ is automatically prime; i.e. $Q_n:=\{m<n: p(m)>n-m\}$ contains no composites. 2) Use computation to guess structural conditions on such $n$ and attempt a constructive proof.

WORK Fast reality check (explicit computation). For each $n$ one can compute the set \[ Q_n:=\{m\in\{1,2,\dots,n-1\}: \text{every prime factor of }m\text{ is } > n-m\}, \] and the greedy sequence $(a_k)$ is exactly the elements of $Q_n$ listed in decreasing order. A computation for $n\le 5000$ finds $93$ values of $n$ for which $Q_n\setminus\{1\}$ consists entirely of primes (so the greedy sequence is “all primes” before terminating at $1$). The largest such $n\le 5000$ is $n=4974$. The last $20$ such $n\le 5000$ are: \[ 1500,1572,2004,2114,2352,2394,2400,2622,2688,2690,2694,2700,2862,2970,2972,3042,3540,3542,4290,4974. \] For example, for $n=54$ the greedy sequence begins \[ 53,49,47,\dots \] and contains the composite $49$ (since $49$ has prime factor $7>54-49=5$), while for $n=200$ the greedy sequence is exactly the list of all primes in $(100,200)$ in decreasing order followed by $1$.

Lemma 430.1 (range restriction). If $m$ is an integer with $1<m<n$ satisfying the condition “all prime factors of $m$ are $>n-m$”, then necessarily \[ m>\frac n2. \]

Proof. Assume for contradiction that $1<m\le n/2$ satisfies the condition. Let $p$ be any prime divisor of $m$. Then $p\le m\le n/2$. Since $m\le n/2$, we have $n-m\ge n/2\ge p$. Thus $p\le n-m$, contradicting the required strict inequality $p>n-m$. Therefore no such $m$ can lie at or below $n/2$. $\square$

Lemma 430.2 (even numbers cannot qualify for even $n$). If $n$ is even, then no even integer $m$ with $2\le m<n$ satisfies the prime-factor condition.

Proof. Let $n$ be even and suppose $m$ is even with $2\le m<n$. Then $2$ is a prime factor of $m$. The condition requires $2>n-m$, i.e. $n-m\le 1$. But $n-m$ is a positive integer (since $m<n$), so $n-m=1$. This implies $m=n-1$, which is odd because $n$ is even. This contradicts that $m$ is even. Hence no such even $m$ exists. $\square$

Lemma 430.3 (all large primes qualify). If $p$ is prime with $n/2<p<n$, then $p\in Q_n$.

Proof. The only prime factor of $p$ is $p$ itself. The condition for $p$ to lie in $Q_n$ is therefore $p>n-p$, which is equivalent to $p>n/2$. By hypothesis this holds, so $p\in Q_n$. $\square$

VERIFICATION - Lemma 430.1: the contradiction uses only $p\le m$ for a prime divisor $p$ of $m$ and the inequality $n-m\ge n/2$ when $m\le n/2$. - Lemma 430.2: the strict inequality $2>n-m$ forces $n-m=1$; the parity contradiction is immediate. - Lemma 430.3: checks the condition explicitly for primes. - Computations: examples (e.g. $n=54$ contains $49$; $n=4974$ yields exactly the primes in $(n/2,n)$ plus $1$) were verified directly from the defining condition.

FINAL UNRESOLVED (i) Strongest proved partial result: any qualifying integer $m>1$ must lie in $(n/2,n)$ (Lemma 430.1), and if $n$ is even then any qualifying $m>1$ must be odd (Lemma 430.2). Moreover, all primes in $(n/2,n)$ always qualify (Lemma 430.3). (ii) First gap (crisp): decide whether for all sufficiently large $n$ there must exist a composite $m$ with $n/2<m<n$ and least prime factor $>n-m$ (equivalently, whether $Q_n$ must contain composites for all large $n$). (iii) Top 3 next moves: 1. Sieve in short intervals: for a given $n$, study the interval $[n-y,n)$ and show (or refute) the existence of a composite $m$ in this interval avoiding all primes $\le y$ (i.e. $y$-rough), with $y=n-m$. 2. Structural search for “all-prime” $n$: characterise $n$ for which $Q_n\setminus\{1\}$ is exactly the set of primes in $(n/2,n)$; the computations up to $5000$ give many such $n$ (e.g. $n=200,4974$). 3. Extend computation with certification: compute all-prime instances much further and attempt to detect a congruence or factorial/primorial-type construction that guarantees absence of qualifying composites. (iv) Minimal counterexample structure: if the conjectured “eventual composite” property is true, a minimal counterexample would be a large $n$ for which every composite $m\in(n/2,n)$ has least prime factor $\le n-m$ (so no composite qualifies). If the conjecture is false, a minimal infinite counterexample family would be an unbounded sequence of such $n$ (as suggested by the existence of many examples up to $5000$), forcing a uniform explanation of why each composite in $(n/2,n)$ always has a very small prime factor compared to its distance from $n$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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