Erdős Problem #461

Erdős Problem 461 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

1) FORMAL RESTATEMENT

For integers $t\ge 1$ and $m\ge 1$, define the $t$-smooth component $s_t(m)$ to be the product of all prime powers $p^{v_p(m)}$ dividing $m$ with primes $p<t$ (equivalently, remove from the prime factorisation of $m$ all primes $\ge t$).

For integers $n\ge 0$ and $t\ge 1$, define \[f(n,t):=\left|\{s_t(m): m\in\{n+1,n+2,\dots,n+t\}\}\right|. \] The conjecture asks whether there exists an absolute constant $c>0$ such that for all $n,t$, \[f(n,t)\ge c t\qquad\text{(equivalently, }f(n,t)\gg t\text{ uniformly).} \] The extracted text reports a weaker proven bound $f(n,t)\gg t/\log t$.

2) QUICK LITERATURE/CONTEXT CHECK

The extracted statement reports a bound of order $t/\log t$ due to Erdős and Graham, but no proof is included. I do not rely on external results beyond the elementary lemmas proved below.

3) ATTACK PLAN

• Use basic divisibility properties of intervals of length $t$ (every modulus $d\le t$ has a multiple in the interval).
• Try to force many distinct values of $s_t(m)$ by looking at numbers in the interval with a "distinguishing" large prime factor $p$ with $p<t$.
• Search computationally for small $(n,t)$ where $f(n,t)$ is unusually small relative to $t$.

4) WORK

Fast reality check (computations).

I computed $f(n,t)$ exactly for $2\le t\le 50$ and $0\le n\le 500$. The smallest observed ratios $f(n,t)/t$ in this search were:

• $t=2$: minimum $f=1$ at $n=0$ (ratio $0.5$);
• $t=7$: minimum $f=4$ at $n=176$ (ratio $\approx 0.571$);
• for $t\le 50$ and $n\le 500$, all other minima had ratio $\ge 0.586$.

This small search shows no evidence of $f(n,t)$ being sublinear in $t$.

Lemma 461.1 (every modulus $d\le t$ appears). Let $n\ge 0$ and $t\ge 1$ be integers. For every integer $d$ with $1\le d\le t$, the interval $\{n+1,\dots,n+t\}$ contains at least one multiple of $d$.

Proof. Consider the residues of the $t$ consecutive integers $n+1,\dots,n+t$ modulo $d$. Since $t\ge d$, among these $t$ residues there is a complete set of residues modulo $d$ (in particular, residue $0$ occurs). Concretely, the map $i\mapsto (n+i)\bmod d$ takes $d$ consecutive values $i$ to all residues, so some $i\in\{1,\dots,d\}\subseteq\{1,\dots,t\}$ satisfies $n+i\equiv 0\pmod d$. $\square$

Lemma 461.2 (large primes $p\in(t/2,t)$ yield distinguishable smooth components when their multiples are distinct). Assume $t\ge 3$ and let $p$ be a prime with $\tfrac{t}{2}<p<t$. Then the interval $\{n+1,\dots,n+t\}$ contains exactly one multiple of $p$; call it $m_p$. Then:

1. $p\mid s_t(m_p)$.
2. If $p,q$ are distinct primes in $(t/2,t)$ and $m_p\neq m_q$, then $s_t(m_p)\neq s_t(m_q)$.

Proof. Because $p\le t$, Lemma 461.1 guarantees at least one multiple of $p$ in the interval. For uniqueness: if two distinct numbers in the interval were multiples of $p$, their difference would be a nonzero multiple of $p$ of absolute value $<t$, hence at least $p$, which contradicts $p>t/2$ (since then $2p>t$ implies there is at most one multiple in any length-$t$ interval).

$1$ Since $p<t$ and $p\mid m_p$, the prime $p$ appears in the prime factorisation of $m_p$ with some positive exponent $v_p(m_p)\ge 1$, and by definition $s_t(m_p)$ includes the factor $p^{v_p(m_p)}$. Hence $p\mid s_t(m_p)$.

$2$ If $m_p\neq m_q$, then $q\nmid m_p$: otherwise $m_p$ would be a multiple of $q$ in the interval, and by uniqueness it would have to equal $m_q$. Therefore $q\nmid s_t(m_p)$ (since $q<t$ and if $q$ divided $s_t(m_p)$ it would divide $m_p$). Similarly $p\nmid s_t(m_q)$. Thus $s_t(m_p)$ is divisible by $p$ but not by $q$, while $s_t(m_q)$ is divisible by $q$ but not by $p$, forcing $s_t(m_p)\neq s_t(m_q)$. $\square$

5) VERIFICATION

• Lemma 461.1: checked extreme case $d=t$; the interval of length $t$ always contains a multiple of $t$ (namely $n+t$ if $t\mid n$; more generally by residues).
• Lemma 461.2: uniqueness uses only $2p>t$. The restriction $p>t/2$ is essential.
• Computation: checked by brute-force factorisation for all $t\le 50, n\le 500$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: The interval $[n+1,n+t]$ contains a multiple of every $d\le t$ (Lemma 461.1), and primes $p\in(t/2,t)$ contribute divisibly to the smooth component of their unique multiple, yielding distinct $s_t$ values whenever these multiples are distinct (Lemma 461.2). Computations for $t\le 50$ and $n\le 500$ show $f(n,t)/t$ is never below $0.5$ in this range.

(ii) First gap (crisp): Prove a uniform constant $c>0$ such that for all $n,t$ the set $\{s_t(n+1),\dots,s_t(n+t)\}$ has size at least $ct$. Equivalently, bound from above how many of the $t$ integers can share the same $t$-smooth component.

(iii) Top 3 next moves:

1. Prove a uniform bound on multiplicities: for a fixed value $S$, bound the number of $m\in[n+1,n+t]$ with $s_t(m)=S$.
2. Develop a counting argument based on representing $m=s_t(m)\cdot r$ where $r$ is $t$-rough (all prime factors $\ge t$), and control how many such $r$ can occur in an interval of length $t$.
3. Search computationally for larger $t$ and specially constructed large $n$ (e.g. aligning many primes) to see how small $f(n,t)/t$ can get.

(iv) Minimal counterexample structure: If the conjecture fails badly, a minimal counterexample would be an interval $[n+1,n+t]$ in which many integers share the same small-prime pattern, i.e. can be written as $m=S\cdot r$ with a fixed $S$ composed of primes $<t$ and varying $t$-rough factors $r$, but with only $o(t)$ distinct $S$ values appearing.

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.

1) FORMAL RESTATEMENT

For integers $t\ge 1$ and $m\ge 1$, define the $t$-smooth component $s_t(m)$ to be the product of all prime powers $p^{v_p(m)}$ dividing $m$ with primes $p<t$ (equivalently, remove from the prime factorisation of $m$ all primes $\ge t$).

For integers $n\ge 0$ and $t\ge 1$, define \[f(n,t):=\left|\{s_t(m): m\in\{n+1,n+2,\dots,n+t\}\}\right|. \] The conjecture asks whether there exists an absolute constant $c>0$ such that for all $n,t$, \[f(n,t)\ge c t\qquad\text{(equivalently, }f(n,t)\gg t\text{ uniformly).} \] The extracted text reports a weaker proven bound $f(n,t)\gg t/\log t$.

2) QUICK LITERATURE/CONTEXT CHECK

The extracted statement reports a bound of order $t/\log t$ due to Erdős and Graham, but no proof is included. I do not rely on external results beyond the elementary lemmas proved below.

3) ATTACK PLAN

• Use basic divisibility properties of intervals of length $t$ (every modulus $d\le t$ has a multiple in the interval).
• Try to force many distinct values of $s_t(m)$ by looking at numbers in the interval with a "distinguishing" large prime factor $p$ with $p<t$.
• Search computationally for small $(n,t)$ where $f(n,t)$ is unusually small relative to $t$.

4) WORK

Fast reality check (computations).

I computed $f(n,t)$ exactly for $2\le t\le 50$ and $0\le n\le 500$. The smallest observed ratios $f(n,t)/t$ in this search were:

• $t=2$: minimum $f=1$ at $n=0$ (ratio $0.5$);
• $t=7$: minimum $f=4$ at $n=176$ (ratio $\approx 0.571$);
• for $t\le 50$ and $n\le 500$, all other minima had ratio $\ge 0.586$.

This small search shows no evidence of $f(n,t)$ being sublinear in $t$.

Lemma 461.1 (every modulus $d\le t$ appears). Let $n\ge 0$ and $t\ge 1$ be integers. For every integer $d$ with $1\le d\le t$, the interval $\{n+1,\dots,n+t\}$ contains at least one multiple of $d$.

Proof. Consider the residues of the $t$ consecutive integers $n+1,\dots,n+t$ modulo $d$. Since $t\ge d$, among these $t$ residues there is a complete set of residues modulo $d$ (in particular, residue $0$ occurs). Concretely, the map $i\mapsto (n+i)\bmod d$ takes $d$ consecutive values $i$ to all residues, so some $i\in\{1,\dots,d\}\subseteq\{1,\dots,t\}$ satisfies $n+i\equiv 0\pmod d$. $\square$

Lemma 461.2 (large primes $p\in(t/2,t)$ yield distinguishable smooth components when their multiples are distinct). Assume $t\ge 3$ and let $p$ be a prime with $\tfrac{t}{2}<p<t$. Then the interval $\{n+1,\dots,n+t\}$ contains exactly one multiple of $p$; call it $m_p$. Then:

1. $p\mid s_t(m_p)$.
2. If $p,q$ are distinct primes in $(t/2,t)$ and $m_p\neq m_q$, then $s_t(m_p)\neq s_t(m_q)$.

Proof. Because $p\le t$, Lemma 461.1 guarantees at least one multiple of $p$ in the interval. For uniqueness: if two distinct numbers in the interval were multiples of $p$, their difference would be a nonzero multiple of $p$ of absolute value $<t$, hence at least $p$, which contradicts $p>t/2$ (since then $2p>t$ implies there is at most one multiple in any length-$t$ interval).

$1$ Since $p<t$ and $p\mid m_p$, the prime $p$ appears in the prime factorisation of $m_p$ with some positive exponent $v_p(m_p)\ge 1$, and by definition $s_t(m_p)$ includes the factor $p^{v_p(m_p)}$. Hence $p\mid s_t(m_p)$.

$2$ If $m_p\neq m_q$, then $q\nmid m_p$: otherwise $m_p$ would be a multiple of $q$ in the interval, and by uniqueness it would have to equal $m_q$. Therefore $q\nmid s_t(m_p)$ (since $q<t$ and if $q$ divided $s_t(m_p)$ it would divide $m_p$). Similarly $p\nmid s_t(m_q)$. Thus $s_t(m_p)$ is divisible by $p$ but not by $q$, while $s_t(m_q)$ is divisible by $q$ but not by $p$, forcing $s_t(m_p)\neq s_t(m_q)$. $\square$

5) VERIFICATION

• Lemma 461.1: checked extreme case $d=t$; the interval of length $t$ always contains a multiple of $t$ (namely $n+t$ if $t\mid n$; more generally by residues).
• Lemma 461.2: uniqueness uses only $2p>t$. The restriction $p>t/2$ is essential.
• Computation: checked by brute-force factorisation for all $t\le 50, n\le 500$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: The interval $[n+1,n+t]$ contains a multiple of every $d\le t$ (Lemma 461.1), and primes $p\in(t/2,t)$ contribute divisibly to the smooth component of their unique multiple, yielding distinct $s_t$ values whenever these multiples are distinct (Lemma 461.2). Computations for $t\le 50$ and $n\le 500$ show $f(n,t)/t$ is never below $0.5$ in this range.

(ii) First gap (crisp): Prove a uniform constant $c>0$ such that for all $n,t$ the set $\{s_t(n+1),\dots,s_t(n+t)\}$ has size at least $ct$. Equivalently, bound from above how many of the $t$ integers can share the same $t$-smooth component.

(iii) Top 3 next moves:

1. Prove a uniform bound on multiplicities: for a fixed value $S$, bound the number of $m\in[n+1,n+t]$ with $s_t(m)=S$.
2. Develop a counting argument based on representing $m=s_t(m)\cdot r$ where $r$ is $t$-rough (all prime factors $\ge t$), and control how many such $r$ can occur in an interval of length $t$.
3. Search computationally for larger $t$ and specially constructed large $n$ (e.g. aligning many primes) to see how small $f(n,t)/t$ can get.

(iv) Minimal counterexample structure: If the conjecture fails badly, a minimal counterexample would be an interval $[n+1,n+t]$ in which many integers share the same small-prime pattern, i.e. can be written as $m=S\cdot r$ with a fixed $S$ composed of primes $<t$ and varying $t$-rough factors $r$, but with only $o(t)$ distinct $S$ values appearing.