Erdős Problem #380

FORMAL RESTATEMENT

Erdős #380; structural lemmas and reconstruction from Tao's error estimates, 2026-09-24. An integer interval $I=[u,v]$ is bad if the largest prime dividing $\prod_{m\in I}m$ divides this product at least twice. Let $B(x)$ count positive integers at most $x$ lying in some bad interval, and let \[ A(x)=\#\{2\leq n\leq x:P(n)^2\mid n\}. \] Prove $B(x)\sim A(x)$. The companion assertion asks for the count of integers lying in intervals whose product is powerful. The harmless convention at $n=1$ affects all counts by at most one.

QUICK LITERATURE AND CONTEXT CHECK

Tao's Products of consecutive integers with unusual anatomy proves both assertions. Below the decisive error bounds from that paper are explicitly imported. The interval structure, the exact singleton counting formula, and the asymptotic for powerful integers are proved here.

OBJECTIVE AND ATTACK PLAN

Locate a singleton witness inside every bad interval, then distinguish that structural fact from the harder estimate for all the additional integers covered by such intervals. Use the published estimates to complete the comparison.

WORK

Prime-free intervals. If an interval $[u,v]$ contains a prime, it contains a prime $q>v/2$. Indeed this is automatic if $u>v/2$; otherwise Bertrand's postulate supplies a prime between $\lfloor v/2\rfloor$ and $2\lfloor v/2\rfloor$, with $v=2,3$ checked directly. Take the largest prime in the interval. It occurs just once in the product, and no larger prime can divide any term: a prime larger than $v/2$ can only occur as the term itself. Hence an interval containing a prime is not bad. In particular, a bad interval with $u\geq2$ has $v<2u-1$, since Bertrand supplies a prime between $u$ and $2u$.

Let $H=v-u+1$. Then $H<u$. The standard Sylvester--Schur theorem says that the product of $H$ consecutive integers, all exceeding $H$, has a prime factor exceeding $H$. Thus the largest prime $p$ in a bad interval satisfies $p>H$. It divides just one of its $H$ terms, say $a$, so the required repeated occurrence forces $p^2\mid a$ and $P(a)=p$. Every bad interval therefore contains a singleton-bad integer. This does not by itself bound how many other integers all such intervals cover.

An exact formula for the singleton count. Let $\Psi(y,z)$ count positive integers at most $y$ all of whose prime factors are at most $z$, including $1$. Classifying an integer counted by $A(x)$ by its largest prime gives the disjoint identity \[ A(x)=\sum_{p\leq\sqrt x}\Psi(x/p^2,p). \tag{1} \] Indeed it is uniquely $p^2a$ with $P(a)\leq p$. Every such integer belongs to its singleton bad interval, so $A(x)\leq B(x)$.

The declared analytic input for bad intervals. Tao's Theorem 1.7 states that the number of additional covered integers is \[ 0\leq B(x)-A(x)\ll\frac{A(x)}{(\log x)^{1-o(1)}}. \tag{2} \] The anti-sieve and smooth-number correlation estimates proving $2$ are not reconstructed here. Since the denominator tends to infinity, division by $A(x)$ proves $B(x)/A(x)\to1$. There is no loss from the possibility that a witnessing interval extends past $x$: $2$ is a theorem about membership in the full union of intervals, subsequently intersected with $[1,x]$.

Powerful integers and very bad intervals. Every powerful integer has a unique representation $a^2b^3$ with $b$ squarefree. At a prime with exponent $e\geq2$, choose exponent $0$ in $b$ if $e$ is even and exponent $1$ if $e$ is odd; the remaining exponent is nonnegative and even. Therefore their counting function $F(x)$ satisfies \[ F(x)=\sum_{b\leq x^{1/3}}\mu(b)^2\left\lfloor\sqrt{x/b^3}\right\rfloor =\frac{\zeta(3/2)}{\zeta(3)}\sqrt x+O(x^{1/3}). \tag{3} \] The floor errors total $O(x^{1/3})$, and the omitted tail of $\sum b^{-3/2}$ contributes $O(x^{1/3})$ after multiplication by $\sqrt x$. Its squarefree Euler product is $\prod_p(1+p^{-3/2})=\zeta(3/2)/\zeta(3)$.

If $V(x)$ counts membership in very bad intervals, singleton intervals give $V(x)\geq F(x)+O(1)$. The second declared analytic input, Tao's Theorem 1.8, is \[ V(x)-F(x)=O(x^{2/5+o(1)}). \] Together with $3$, this yields $V(x)\sim\zeta(3/2)\sqrt x/\zeta(3)$ and in particular $V(x)\ll\sqrt x$.

RESULT AND LIMITATIONS

Attempt status: solved relative to Tao's two explicitly stated error estimates. The elementary structure and counting arguments are complete; the difficult estimates $2$ and its very-bad counterpart remain published external dependencies. No proof that every member of a very bad interval is itself powerful is asserted, and no such stronger statement is needed.

SOURCES

https://www.erdosproblems.com/380; Tao, Products of consecutive integers with unusual anatomy, Theorems 1.7 and 1.8: https://arxiv.org/html/2603.27990.

Completion rate estimate: 100% relative to the stated external estimates.

Problem #380 (Round 2)

1) ROUND-2 OBJECTIVE

Path C (obstruction / structural reduction). In Round 1 the main unresolved gap was the lack of a rigid description of a bad interval beyond "it contains no primes". The new goal is to prove a sharper internal structure theorem for bad intervals, then use it to isolate exactly what would have to happen in any counterexample to the conjectural behaviour of very bad intervals.

2) Round-1 FOUNDATION USED

I use only the following Round-1 results.

1. If $[u,v]$ is bad, then it contains no primes.
2. Consequently, every bad interval satisfies $v<2u$.
3. Hence if $n\le x$ lies in a bad interval, then the whole interval lies below $2x$.
4. For singletons, $[n,n]$ is bad if and only if $P(n)^2\mid n$, and $[n,n]$ is very bad if and only if $n$ is powerful.

I do not re-prove these.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is the following "anchor-smooth reduction".

Anchor-smooth reduction. If $[u,v]$ is bad, write \[ L=v-u,\qquad N(u,v)=\prod_{m=u}^{v}m,\qquad Q=P(N(u,v)). \] Then:

1. $Q>L$;
2. there is a unique $t\in [u,v]$ divisible by $Q$, and in fact $Q^2\mid t$;
3. every element of $[u,v]$ is $Q$-smooth.

So every bad interval is a run of consecutive $Q$-smooth integers of length $L+1<Q+1$ containing an "anchor" $t$ with $P(t)=Q$ and $Q^2\mid t$.

This is strictly stronger than the Round-1 information "bad $\Rightarrow$ prime-free".

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was this: even though bad intervals contain no primes, that alone did not explain how they are tied to the set \[ \{n:\ P(n)^2\mid n\}. \]

The new plan is:

1. prove the anchor-smooth reduction;
2. deduce a covering lemma showing that every integer counted by $B(x)$ lies within distance $<P(t)$ of an anchor $t$ with $P(t)^2\mid t$;
3. analyse the first genuinely new case for very bad intervals, namely intervals of length $1$ and $2$, to isolate the precise obstruction to proving $V(x)\sim$ (powerful numbers).

5) WORK (ROUND-2)

Theorem 1 (anchor-smooth reduction).

Let $[u,v]$ be bad. Put $L=v-u$ and $Q=P\!\left(\prod_{m=u}^{v}m\right)$. Then for $L\ge 1$ one has:

1. $Q>L$;
2. exactly one element $t\in [u,v]$ is divisible by $Q$;
3. $Q^2\mid t$;
4. every $m\in [u,v]$ has all prime factors at most $Q$.

Proof.

By the Round-1 lemma, $[u,v]$ contains no primes, hence $v<2u$. Therefore \[ L=v-u<u, \] so every integer in the block \[ u,u+1,\dots,v-1 \] is strictly greater than $L$.

Now $u(u+1)\cdots (v-1)$ is a product of $L$ consecutive integers, each greater than $L$. By the Sylvester--Schur theorem, this product has a prime divisor exceeding $L$. Since $Q$ is the largest prime divisor of the larger product $\prod_{m=u}^{v}m$, we get \[ Q>L. \]

Because the interval length is $L$, two distinct multiples of $Q$ cannot both lie in $[u,v]$: their difference would be at least $Q>L$. Thus at most one element of $[u,v]$ is divisible by $Q$.

On the other hand, the interval is bad, so the exponent of $Q$ in $\prod_{m=u}^{v}m$ is at least $2$. Hence the unique multiple $t$ of $Q$ in the interval must actually satisfy \[ Q^2\mid t. \]

Finally, $Q=P\!\left(\prod_{m=u}^{v}m\right)$ by definition, so no element of the interval can have a prime factor exceeding $Q$. Thus every element of $[u,v]$ is $Q$-smooth. This proves the theorem.

The degenerate case $L=0$ is even easier: then $[u,v]=[n,n]$, and badness means exactly $P(n)^2\mid n$.

Corollary 2 (covering by anchor neighbourhoods).

Let $n\le x$ lie in some bad interval. Then there exists an integer $t\le 2x$ such that \[ P(t)^2\mid t ,\qquad |n-t|<P(t). \]

Proof.

Choose a bad interval $[u,v]$ containing $n$, and let $t$ be the anchor supplied by Theorem 1. Then \[ P(t)=Q,\qquad P(t)^2\mid t,\qquad |n-t|\le v-u=L<Q=P(t). \] Also, by the Round-1 bound $v<2u$ and the fact that $u\le n\le v$, \[ t\le v<2u\le 2n\le 2x. \] So $t\le 2x$, as claimed. This proves the corollary.

Corollary 3 (set-theoretic reduction of Problem #380(a)).

For every $x\ge 1$, \[ \{n\le x:\ n \mbox{ lies in a bad interval}\} \subseteq \bigcup_{t\le 2x,\ P(t)^2\mid t} \{m:\ |m-t|<P(t)\}. \]

Equivalently, every integer counted by $B(x)$ is captured by a neighbourhood of radius $P(t)-1$ around an anchor $t$ counted by the singleton set from Round 1.

Short very-bad intervals.

The anchor-smooth theorem does not settle the powerful case, but it does sharply reduce the first unsolved lengths.

Length $1$ (two consecutive integers). If $[n,n+1]$ is very bad, then \[ n(n+1) \] is powerful and $\gcd(n,n+1)=1$. Therefore every prime divisor of the product comes from exactly one factor, with the same exponent as in that factor. Hence both $n$ and $n+1$ are powerful.

So a very bad interval of length $1$ is exactly a pair of consecutive powerful numbers.

Length $2$ (three consecutive integers), odd start. If $[n,n+2]$ is very bad and $n$ is odd, then $n,n+1,n+2$ are pairwise coprime. Therefore the same reasoning shows that each of \[ n,\ n+1,\ n+2 \] must itself be powerful.

Thus any odd-start very bad interval of length $2$ produces three consecutive powerful numbers.

Length $2$ (three consecutive integers), even start. Write the interval as \[ [2a,2a+2]. \] Then \[ (2a)(2a+1)(2a+2)=2^{2+\alpha+\beta}AB(2a+1), \] where \[ a=2^{\alpha}A,\qquad a+1=2^{\beta}B, \] with $A,B$ odd. The odd integers $A$, $B$, and $2a+1$ are pairwise coprime. Therefore, if the product is powerful, then each of \[ A,\ B,\ 2a+1 \] must be powerful.

So any even-start very bad interval of length $2$ forces a very restricted configuration: the odd part of $a$ is powerful, the odd part of $a+1$ is powerful, and $2a+1$ is powerful.

This is the first place where the Round-1 heuristic "maybe every very bad interval consists only of powerful numbers" meets a genuinely arithmetic obstruction.

6) ADVERSARIAL VERIFICATION

I checked the following possible failure points.

1. Does Theorem 1 accidentally use a Round-1 proof again? No. It only cites the Round-1 conclusion $v<2u$ and then adds a genuinely new Sylvester--Schur step.
2. Could the anchor be non-unique? No, because $Q>L$ and two multiples of $Q$ differ by at least $Q$.
3. Does the theorem claim the interval contains $Q^2$ itself? No. It only claims that the unique multiple of $Q$ in the interval is divisible by $Q^2$. This distinction matters: for example, $[242,243]$ is bad with $Q=11$, and the unique multiple is $242=2\cdot 11^2$, not $11^2$ itself.
4. In the even-start very-bad case, do we really get that $a$ and $a+1$ are powerful? No, and I have deliberately not claimed that. The extra factor $4$ can repair the $2$-adic defect. The correct statement is only about the odd parts of $a$ and $a+1$.
5. Boundary case $L=0$. This was separated off explicitly.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The new Round-2 progress is:

1. a rigorous anchor-smooth reduction for every bad interval;
2. a covering lemma reducing Problem #380(a) to neighbourhoods of singleton anchors $t$ with $P(t)^2\mid t$;
3. an exact classification of very bad intervals of length $1$;
4. a sharp reduction of the first new three-term cases to highly constrained powerful-number configurations.

This is a real advance over Round 1, but it does not yet prove either \[ B(x)\sim \#\{n\le x:\ P(n)^2\mid n\} \] or \[ V(x)\sim \#\{n\le x:\ n \mbox{ is powerful}\}. \]

8) COMPLETION ESTIMATE

COMPLETION: 45%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #380, accessed 2026-03-08, https://www.erdosproblems.com/380.
2. T. N. Shorey and R. Tijdeman, Arithmetic properties of blocks of consecutive integers, especially the discussion of Sylvester's theorem in Section 3.1.

Problem #380

1) FORMAL RESTATEMENT

For integers $1\le u\le v$, define \[ N(u,v)\ :=\ \prod_{m=u}^{v} m. \] Write $P(n)$ for the largest prime factor of an integer $n\ge 2$, and set $P(1):=1$ for convenience. For a prime $p$, write $\nu_p(n)$ for the exponent of $p$ in the prime factorisation of $n$.

• The interval $[u,v]$ is bad if the largest prime factor of $N(u,v)$ occurs with exponent $>1$, i.e. \[ \text{if }\, P\left(N(u,v)\right)=:Q \text{ then } \nu_Q\left(N(u,v)\right)\ge 2. \]
• Define \[ B(x)\ :=\ \#\{\,n\in\{1,2,\dots,\lfloor x\rfloor\}:\ \exists\,u\le n\le v \text{ with } [u,v]\text{ bad}\,\}. \]
• Define the comparison counting function \[ A(x)\ :=\ \#\{\,n\le x:\ P(n)^2\mid n\,\}. \]

Question 380(a). Is it true that $B(x)\sim A(x)$ as $x\to\infty$?

Next, call $[u,v]$ very bad if $N(u,v)$ is a powerful (a.k.a. squareful) integer, meaning that every prime divisor occurs with exponent at least $2$: \[ (\forall \text{ primes }p\mid N(u,v))\quad \nu_p\left(N(u,v)\right)\ge 2. \] Let \[ V(x)\ :=\ \#\{\,n\le x:\ \exists\,u\le n\le v \text{ with } [u,v]\text{ very bad}\,\}. \] Let \[ \mathrm{Pow}(x)\ :=\ \#\{\,n\le x:\ n\text{ is powerful}\,\}. \]

Question 380(b). Is it true that $V(x)\ll x^{1/2}$, and in fact $V(x)\sim \mathrm{Pow}(x)$?

2) QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems website lists Problem #380 as open and records (from Erdős--Graham, 1980) that $B(x)>x^{1-o(1)}$, and that \[ A(x)=\frac{x}{\exp\!\left((c+o(1))\sqrt{\log x\log\log x}\right)} \] for some constant $c>0$.(https://www.erdosproblems.com/380 (accessed 2026-01-17).)

The same page attributes to Terence Tao the observation that if $[u,v]$ is bad then it contains no primes, hence $v<2u$.(Same source as above.)

For powerful numbers, a classical asymptotic (going back at least to Bateman--Grosswald) is \[ \mathrm{Pow}(x)=\frac{\zeta(3/2)}{\zeta(3)}\,x^{1/2}+\frac{\zeta(2/3)}{\zeta(2)}\,x^{1/3}+O(x^{1/6}), \] as recorded for example on OEIS A001694.(https://oeis.org/A001694 (see the "FORMULA" section; accessed 2026-01-17).)

3) ATTACK PLAN

1. Prove the easy structural lemma "bad intervals contain no primes" and derive the strong geometric restriction $v<2u$.
2. Use this restriction to justify finite computations of $B(x)$ and $V(x)$ up to moderate $x$ by searching only intervals with $v<2u\le 2x$.
3. Establish trivial but useful inclusions: \[ A(x)\le B(x)\quad\text{and}\quad \mathrm{Pow}(x)\le V(x), \] coming from singleton intervals.
4. Try to upper bound the "extra" contribution $B(x)-A(x)$ by relating any bad interval to nearby integers $n$ with $P(n)^2\mid n$. (Here lies the main gap: badness can come from two distinct multiples of a large prime, not necessarily a square.)

4) WORK

Finite computations (sanity checks).

Using the corollary $v<2u$, if $n\le x$ lies in a bad interval $[u,v]$, then \[ u\le n\le v<2u\le 2n\le 2x. \] So to decide whether $n\le x$ is counted by $B(x)$, it suffices to search for bad intervals with endpoints $\le 2x$ (and satisfying $v<2u$). The following table was computed exactly by enumerating all $[u,v]$ with $1\le u\le x$ and $u\le v<\min(2u,2x]$ and checking badness/very-badness.

Observations:

• In this range, $B(x)$ is only about $5$--$15\%$ larger than $A(x)$, consistent with the conjecture $B(x)\sim A(x)$ (but of course far from proving it).
• In this range, the set of integers $\le x$ that lie in a very bad interval coincides with the set of powerful numbers $\le x$ (hence $V(x)=\mathrm{Pow}(x)$ for these $x$). This suggests (but does not prove) the stronger statement that every very bad interval consists entirely of powerful numbers.

5) VERIFICATION

• The lemma "bad intervals contain no primes" was checked against brute force search up to $v\le 200$ (no counterexamples found), and the proof uses only Bertrand's postulate plus a maximality argument.
• Edge cases: if $[u,v]$ contains a prime $p=2$, then $v<4$ by the proof, and indeed no such interval is bad. Singleton intervals work as claimed: $[n,n]$ is bad iff $P(n)^2\mid n$; $[n,n]$ is very bad iff $n$ is powerful.
• The computational reduction $v\le 2x$ for membership in $B(x)$ relies on $v<2u$; this is logically sound.

6) FINAL

UNRESOLVED.

1. (i) Strongest partial result obtained. Every bad interval contains no primes, hence satisfies $v<2u$. Consequently $A(x)\le B(x)$ for all $x$, and $B(x)$ can be computed for a given $x$ by searching only intervals with endpoints $\le 2x$ and $v<2u$. Similarly, $\mathrm{Pow}(x)\le V(x)$.
2. (ii) First hard gap. To prove $B(x)\sim A(x)$ one needs a near-complete classification of integers lying in some bad interval. The obstruction is that badness can come from the largest prime factor $Q$ dividing two distinct integers in $[u,v]$ (so that $\nu_Q(N(u,v))\ge 2$) without any single integer $n$ in the interval satisfying $Q^2\mid n$.
3. (iii) Top 3 next moves.
   1. Prove an upper bound on the length of bad intervals that is $v^{o(1)}$ (or even $v^{\varepsilon}$ for all $\varepsilon>0$); then one could attempt a union bound over "anchors" $n$ with $P(n)^2\mid n$.
   2. Show that every bad interval must contain many integers $m$ whose largest prime factor equals the interval's maximal prime; quantify how often this can happen without forcing a square (or forcing nearby squares).
   3. Develop a local model around primes $q$ and intervals near $q^2$ (where $q^2$ supplies $\nu_q\ge 2$) to estimate the measure of the set covered by bad intervals and compare it to $A(x)$.
4. (iv) Why it might be true. Heuristically, the only "robust" way to make the maximal prime appear with exponent $\ge 2$ is to have a square of that maximal prime present (or a very short interval containing two multiples), which suggests the coverage set should look like integers with $P(n)^2\mid n$ plus a thin halo.

7) COMPLETION ESTIMATE

Estimated probability of a full resolution from these notes alone: 25%.