Reused writeup on Math-5814 (gpt pro 5.2)

Erdős Problem 676 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

1) FORMAL RESTATEMENT

An integer $N\ge 1$ is called representable if there exist a prime $p$, an integer $a\ge 1$, and an integer $b$ with $0\le b<p$ such that \[ N=ap^2+b. \] Question: Is every sufficiently large integer representable?

Variant questions (from the problem text): - What if the condition that $p$ is prime is omitted (i.e. $p$ is any integer $\ge 2$)? - Define $c_N$ as the minimal constant such that $N=ap^2+b$ with $0\le b<c_N p$ for some prime $p\le\sqrt N$. Is it true that $c_N$ is eventually $\le 1$ (the main question), or perhaps $\limsup c_N=\infty$? Is $c_N<N^{o(1)}$?

2) QUICK LITERATURE/CONTEXT CHECK

As stated in the problem text: - The sieve of Eratosthenes implies almost all integers are of the form $ap^2+b$ with $0\le b<p$. - The Brun--Selberg sieve implies the number of exceptions in $[1,x]$ is $\ll x/(\log x)^c$ for some $c>0$. - Erdős believed it is unlikely that all sufficiently large integers are representable. - Selfridge and Wagstaff's preliminary computation suggested infinitely many exceptions even when $p$ is not required to be prime.

I do not use any other external results here.

3) ATTACK PLAN

- Convert the representation condition into an explicit modular condition $N\bmod p^2<p$. - Run a sieve-style computation to list exceptions for small $N$ and estimate the exception density. - Prove basic structural lemmas about the sets covered by a fixed prime $p$.

4) WORK

FAST REALITY CHECK (exceptions by computation)

Define $N$ to be representable if there exists a prime $p\le\sqrt N$ with $N\bmod p^2<p$.

- Up to $10{,}000$: there are $1327$ exceptions. The first exceptions are \[ 1,2,3,6,7,14,15,22,23,30,31,34,35,39,42,43,\dots \] and the largest exception $\le 10{,}000$ is $9995$.

- Up to $1{,}000{,}000$: there are $83{,}812$ exceptions (about $8.3812\%$ of integers $\le 10^6$).

Lemma 676.1 (equivalent modular condition)

An integer $N\ge 1$ is representable if and only if there exists a prime $p\le\sqrt N$ such that \[ N\bmod p^2 \in \{0,1,\dots,p-1\}. \]

Proof. ($\Rightarrow$) If $N=ap^2+b$ with $a\ge 1$ and $0\le b<p$, then by the division algorithm, $b$ is exactly the remainder of $N$ upon division by $p^2$. Hence $N\bmod p^2=b<p$. Also $a\ge 1$ implies $N\ge p^2$, hence $p\le\sqrt N$.

($\Leftarrow$) Conversely, suppose there exists a prime $p\le\sqrt N$ such that the remainder $b:=N\bmod p^2$ satisfies $0\le b<p$. Write $N=qp^2+b$ with $q=\lfloor N/p^2\rfloor$. Since $p\le\sqrt N$, we have $q\ge 1$. Setting $a:=q$ gives $N=ap^2+b$ with $a\ge 1$ and $0\le b<p$.

Lemma 676.2 (structure and density for fixed $p$)

Fix a prime $p$. Let \[ S_p:=\{N\ge 1: \exists a\ge 1,\ 0\le b<p\text{ with }N=ap^2+b\}. \] Then $S_p$ consists exactly of those integers whose residue modulo $p^2$ lies in $\{0,1,\dots,p-1\}$. Equivalently, for each integer $a\ge 1$, \[ [ap^2,\ ap^2+p-1]\subset S_p, \] and $S_p$ contains no other integers in the block $[ap^2,\ (a+1)p^2-1]$. Moreover, $S_p$ has natural density $1/p$.

Proof. The residue description is immediate from Lemma 676.1 (with $p$ fixed) and the uniqueness of the remainder modulo $p^2$. For each $a\ge 1$, the integers in the interval $[ap^2,ap^2+p-1]$ are exactly those congruent to $0,1,\dots,p-1$ modulo $p^2$, so they lie in $S_p$, and no other integer in that length-$p^2$ block has such a residue.

For density: in each full residue class block of size $p^2$, exactly $p$ residues are allowed. Hence among $\{1,2,\dots,Ap^2\}$ there are exactly $A\cdot p$ elements of $S_p$. Dividing by $Ap^2$ gives proportion $p/(p^2)=1/p$. Letting $A\to\infty$ yields natural density $1/p$.

5) VERIFICATION

- Lemma 676.1: checks that $a\ge 1$ forces $p\le\sqrt N$, so the restriction $p\le\sqrt N$ is not extra. - Lemma 676.2: the density computation uses periodicity modulo $p^2$ and is correct. - Computation consistency: $N=4$ is representable via $p=2$, $a=1$, $b=0$; $N=6$ is not representable because for $p=2$ we have $6\bmod 4=2\not<2$ and no other prime $p$ has $p^2\le 6$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result:

Representability is equivalent to the modular condition $N\bmod p^2<p$ for some prime $p\le\sqrt N$ (Lemma 676.1). For each fixed prime $p$, the covered set has density $1/p$ and consists of the first $p$ integers in each block of length $p^2$ (Lemma 676.2). Computations show that exceptions are common for small $N$ (about $8.38\%$ up to $10^6$) but coverage increases with $N$.

(ii) First gap (crisp):

I cannot decide whether the set of exceptions is finite or infinite; in particular I cannot prove that every sufficiently large $N$ has some prime $p\le\sqrt N$ with $N\bmod p^2<p$, nor can I construct an infinite family of exceptions.

(iii) Top 3 next moves:

1. Attempt an explicit infinite construction of exceptions by forcing $N\bmod p^2\in\{p,\dots,p^2-1\}$ simultaneously for many small primes $p$ via CRT. 2. Quantitatively sharpen sieve upper bounds for the exception set using only the modular structure of $S_p$. 3. Extend computation to larger ranges and look for structured families of exceptions (e.g. in certain congruence classes) that might guide a CRT construction.

(iv) Minimal counterexample structure:

An infinite counterexample family would likely be built by choosing $N$ in a residue class modulo $\prod_{p\le y} p^2$ that avoids the first $p$ residues mod $p^2$ for every small prime $p\le y$, and then showing that for such $N$ no larger prime $p>y$ can work either (e.g. because $p^2$ is too large or because the remaining residues are still excluded).

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.