Erdős Problem #413

Erdős Problem 413: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Writing $\omega(m)$ for the number of distinct prime divisors, are there infinitely many integers $N$ such that $m+\omega(m)\le N$ for every positive $m<N$? Does this hold with $\omega(m)$ replaced by $\epsilon\omega(m)$ for some fixed $\epsilon>0$? Source: https://www.erdosproblems.com/413.

The exact-barrier question remains unresolved here. The relaxed question is already answered by Lau's theorem. We state that external input precisely, derive the relaxed conclusion without losing the last offset, and prove that every fixed relaxed-barrier set has density zero. This replaces the earlier GPT-5.2 speculation with proved statements; no novelty is claimed.

Finite windows and a necessary condition

Let $p_j$ be the $j$th prime and put \[ w(X)=\max\{j:p_1\cdots p_j\le X\}. \] Unique factorization shows that $\omega(m)\le w(X)$ for every $m\le X$: the least integer with $j$ distinct prime factors is the product of the first $j$ primes. Consequently the exact-barrier condition at $N$ can be verified by checking only \[ \omega(N-d)\le d\quad (1\le d<w(N-1)). \tag{1} \] All larger offsets are automatic, including equality at $d=w(N-1)$. Empty windows are interpreted as having no conditions. This is an exact finite test for each proposed $N$, not a proof that the test succeeds infinitely often.

For $N>2$, the offset $d=1$ requires $\omega(N-1)\le1$, so $N-1$ must be a prime power. More generally an $\epsilon$-barrier requires \[ \omega(N-1)\le \lfloor1/\epsilon\rfloor. \tag{2} \]

Density zero for every fixed coefficient

For each fixed integer $K\ge0$, the set of integers with at most $K$ distinct prime factors has natural density zero. Here is a short proof. For a fixed prime cutoff $y$, set \[ S_y(m)=\sum_{p\le y}1_{p\mid m},\qquad \mu_y=\sum_{p\le y}1/p. \] On a complete residue system modulo $\prod_{p\le y}p$, the Chinese remainder theorem makes the divisibility indicators independent, with means $1/p$. Therefore the mean of $S_y$ is $\mu_y$ and its variance is at most $\mu_y$. Chebyshev's inequality gives, when $\mu_y>K$, \[ \operatorname{dens}\{m:S_y(m)\le K\} \le\frac{\mu_y}{(\mu_y-K)^2}. \tag{3} \] The density on the left exists because this set is periodic. Since $S_y(m)\le\omega(m)$, $3$ bounds the upper density of $\{m:\omega(m)\le K\}$. Euler's divergence of the prime reciprocal sum makes $\mu_y\to\infty$, proving the assertion. By $2$, the set of $\epsilon$-barriers has density zero for each fixed $\epsilon>0$. In particular existence of infinitely many relaxed barriers is compatible only with a sparse set, not positive density.

The precise external theorem and the endpoint shift

Lau, On the number of prime factors of consecutive integers, Theorem 1.3, version 2 of 24 June 2026, proves that there is an absolute $C>0$ and infinitely many integers $n$ with \[ \omega(n-k)\le\Omega(n-k)\le C\log k \quad\hbox{for every integer }1<k<n. \tag{4} \] Primary source: https://arxiv.org/abs/2604.15042v2. The sieve and concentration argument establishing $4$ is an imported theorem; it is not reproduced or formally verified in this attempt.

The restriction $k>1$ matters. One cannot simply substitute $k=1$ in $4$. Instead put $N=n-1$ and, for $1\le m<N$, write $d=N-m\ge1$. Then $k=n-m=d+1$ is in the valid range of $4$. Since $2^d\ge d+1$ for every positive integer $d$, induction or the binomial theorem gives \[ \omega(m)\le C\log(d+1)\le C(\log2)d. \] Taking $\epsilon=1/(C\log2)$ proves \[ m+\epsilon\omega(m)\le m+d=N \quad(1\le m<N). \] The infinitely many $n$ in $4$ give infinitely many distinct $N$. This proves the second assertion relative to the explicitly stated preprint theorem.

Also choose a fixed $K\ge2$ so large that $C\log k\le k$ for every integer $k\ge K$. At each original endpoint $n$ in $4$, one then has $m+\omega(m)\le n$ for every $1\le m\le n-K$. This verifies the known weakened first assertion. It leaves the final $K-1$ offsets unchecked.

The dynamical implication and remaining gap

If exact barriers were unbounded, every orbit of $T(m)=m+\omega(m)$ starting at $m\ge2$ would meet every barrier above its start. Indeed the orbit strictly increases, while the barrier condition prevents a jump from below the barrier to above it. Hence any two such orbits would eventually merge. The fixed point $1$ must be excluded from this implication.

Neither the density-zero argument nor $4$ supplies the missing exact coefficient at the last few offsets. The relaxed question is reconstructed from an external theorem; infinitely many exact barriers and the unconditional merging conclusion remain unresolved by this attempt.

Completion rate estimate: 50%.

FORMAL RESTATEMENT

Let $\omega(n)$ be the number of distinct prime divisors of $n$ (with $\omega(1)=0$). Call an integer $n\ge2$ a barrier for $\omega$ if \[ m+\omega(m)\le n\qquad\text{for every integer }m<n. \] Questions:

1. Are there infinitely many barriers for $\omega$?
2. Does there exist $\epsilon>0$ such that there are infinitely many $n$ with $$m+\epsilon\,\omega(m)\le n\qquad\text{for all }m<n?$$

QUICK LITERATURE/CONTEXT CHECK

The problem file states that Erdős called such $n$ "barriers" and believed $\omega$ (and also $\Omega$) should have infinitely many. It also notes sieve methods were suggested but not (then) strong enough. No external results are used here.

ATTACK PLAN

Rewrite the barrier condition as constraints on the last few integers before $n$: for $m=n-d$ we require $\omega(n-d)\le d$. Since $\omega(t)\le \log_2 t$, all constraints with $d\ge \log_2 n$ are automatic. Thus only a short interval just below $n$ matters. We will:

• Prove simple necessary conditions (e.g. $n-1$ must be a prime power).
• Prove the "short interval" reduction rigorously.
• Compute barriers up to $10^6$ as a sanity check.

WORK

Lemma 413.1 (A barrier forces $n-1$ to be a prime power). If $n\ge2$ is a barrier for $\omega$, then $\omega(n-1)=1$; equivalently, $n-1=p^a$ for some prime $p$ and integer $a\ge1$.

Proof. Apply the defining inequality with $m=n-1$: $$(n-1)+\omega(n-1)\le n,$$ so $\omega(n-1)\le 1$. Since $n-1\ge1$ and $n\ge2$, we have $n-1\ge1$; moreover $n-1\ge2$ unless $n=2$. For $n>2$, $n-1\ge2$ has at least one prime divisor so $\omega(n-1)\ge1$, hence $\omega(n-1)=1$, i.e. $n-1$ is a prime power. (For $n=2$, $n-1=1$ and the barrier condition holds trivially.) $\square$

Lemma 413.2 (Only a short interval matters). Fix $n\ge2$ and set $L=\lceil \log_2 n\rceil$. If $$m+\omega(m)\le n$$ holds for all integers $m$ with $n-L\le m<n$, then it holds for all $m<n$; i.e. $n$ is a barrier.

Proof. Let $m<n-L$. Then $n-m> L-1 \ge \log_2 n -1$ and in particular $n-m\ge \log_2 n\ge \log_2 m$. Since $\omega(m)$ counts distinct primes dividing $m$, we have the elementary bound $\omega(m)\le \log_2 m$ (because $m$ is at least the product of $\omega(m)$ distinct primes, which is at least $2^{\omega(m)}$). Thus $\omega(m)\le \log_2 m\le \log_2 n\le n-m$, i.e. $m+\omega(m)\le n$. So all constraints with $m<n-L$ are automatic; only $m\in[n-L,n)$ need checking. $\square$

Proposition 413.3 (Running-maximum reformulation). Define $A(m)=m+\omega(m)$ and $M(n)=\max_{1\le m<n} A(m)$. Then $n\ge2$ is a barrier for $\omega$ if and only if $M(n)\le n$ (equivalently $M(n)=n$ for $n>2$).

Proof. The barrier condition is exactly $A(m)\le n$ for all $m<n$, which is equivalent to the maximum of the left-hand side over $m<n$ being $\le n$. For $n>2$, Lemma 413.1 shows $A(n-1)\ge n$, so $M(n)\ge n$; hence $M(n)\le n$ is equivalent to $M(n)=n$. $\square$

FAST REALITY CHECK (exact computations). I computed $\omega(m)$ for $m\le 10^6$ by a prime sieve and checked the barrier condition by maintaining the running maximum of $m+\omega(m)$. Results:

• There are $5943$ barriers $n\le 10^6$.
• The first $30$ are $$2,3,4,5,6,8,9,10,12,14,17,18,20,24,26,28,30,33,38,42,48,50,54,60,65,74,82,84,90,98.$$
• The largest barrier $\le 10^6$ is $999774$.
• For the relaxed condition with $\epsilon=1/2$ (i.e. $m+\omega(m)/2\le n$), among $n\le 200000$ there are $78361$ such "$\epsilon$-barriers", and in fact $n=200000$ itself satisfies the condition in that range.

VERIFICATION

• Lemma 413.1 is a one-line necessary condition; it correctly treats the edge case $n=2$.
• Lemma 413.2 uses only $2^{\omega(m)}\le m$, which is exact and elementary.
• The computation was a direct sieve; no probabilistic assumptions.

FINAL

UNRESOLVED

(i) Strongest proved partial result: A barrier $n>2$ must satisfy that $n-1$ is a prime power (Lemma 413.1), and verifying the barrier property only requires checking the last $L=\lceil \log_2 n\rceil$ integers below $n$ (Lemma 413.2). Computation confirms many barriers exist up to $10^6$ (exactly $5943$).

(ii) First gap: prove (or disprove) that barriers exist for infinitely many $n$; concretely, show there are infinitely many $n$ such that $\omega(n-d)\le d$ for every $1\le d\le \lceil \log_2 n\rceil$.

(iii) Top 3 next moves:

1. Use sieve methods on the short interval $[n-L,n)$ with $L\asymp \log n$ to show that infinitely many prime powers $p^a$ have the property that all of $p^a-1,p^a-2,\dots,p^a-L$ have at most $d$ distinct primes at distance $d$.
2. Experiment computationally with the structure of $n-1$ (prime vs higher prime power) among barriers, and with the distribution of $\omega(n-d)$ near barriers, to guess a constructive infinite family.
3. For the $\epsilon$-variant, try to prove existence for some explicit $\epsilon$ by showing a positive density of $n$ satisfy $m+\epsilon\omega(m)\le n$ for all $m<n$ (using the short-interval reduction).

(iv) Minimal counterexample structure: if only finitely many barriers exist, there is a largest barrier $n_0$; then for every $n>n_0$ there exists some $m<n$ with $m+\omega(m)>n$, and by Lemma 413.2 such a witness $m$ can be chosen within $\lceil \log_2 n\rceil$ of $n$.