Erdős Problem #942

Erdős Problem 942 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Let $h(n)$ count the number of powerful (if $p\mid m$ then $p^2\mid m$) integers in $[n^2,(n+1)^2)$. Estimate $h(n)$. In particular is there some constant $c>0$ such that\[h(n) < (\log n)^{c+o(1)}\]and, for infinitely many $n$,\[h(n) >(\log n)^{c-o(1)}?\] Erdős writes it is not hard to prove that $\limsup h(n)=\infty$, and that the density $\delta_l$ of integers for which $h(n)=l$ exists and $\sum \delta_l=1$. A proof that $h(n)$ is unbounded is provided by van Doorn in the comments. De Koninck and Luca [DeLu04] have proved, for infinitely many $n$,\[h(n) \gg \left(\frac{\log n}{\log\log n}\right)^{1/3}.\]They also give the density ($\approx 0.275$) of those $n$ such that $h(n)=1$. References [DeLu04] De Koninck, Jean-Marie and Luca, Florian, Sur la proximité des nombres puissants . Acta Arith. $2004$, 149--157.

FORMAL RESTATEMENT

Fix $n\in\mathbb{N}$ with $n\ge 1$. Call an integer $m\ge 1$ powerful if for every prime $p$, $p\mid m\Rightarrow p^2\mid m$. Define \[ h(n) := \#\{m\in\mathbb{Z}: n^2\le m < (n+1)^2 \ \text{and $m$ is powerful}\}. \] The problem asks for asymptotics/upper-lower bounds for $h(n)$ as $n\to\infty$. In particular it asks whether there exists a constant $c>0$ such that \[ h(n) < (\log n)^{c+o(1)} \quad (n\to\infty) \] (i.e. $\log h(n) \le (c+o(1))\log\log n$), and whether for infinitely many $n$ we have \[ h(n) > (\log n)^{c-o(1)}. \] Edge case conventions: $\log$ is natural logarithm; $o(1)$ means a quantity tending to $0$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not use any external results beyond what is stated in the problem text. The problem text asserts: $1$ $\limsup_{n\to\infty} h(n)=\infty$ (unboundedness), $2$ the densities $\delta_\ell := \lim_{N\to\infty} \#\{1\le n\le N: h(n)=\ell\}/N$ exist and sum to $1$, $3$ for infinitely many $n$, $h(n) \gg (\log n/\log\log n)^{1/3}$.

ATTACK PLAN

Proof-track ideas.

• Use the structural parametrization of powerful numbers $m=a^2b^3$ with $b$ squarefree to reduce counting to lattice points $(a,b)$ lying in a thin region defined by $n^2\le a^2b^3<(n+1)^2$.
• Derive global bounds for the counting function $P(x):=\#\{m\le x: m\text{ powerful}\}$ and convert them into average bounds on $h(n)$ via telescoping sums.
• (Hard) Improve global bounds to local bounds in short intervals of length $\asymp n$, aiming for polylogarithmic control.

Disproof/construction-track ideas.

• Try to construct $n$ for which many distinct pairs $(a,b)$ yield $a^2b^3$ in $[n^2,(n+1)^2)$, perhaps by forcing $a^2b^3$ to cluster near a square via congruences/CRT.
• If polylog bounds are false, search computationally for unusually large $h(n)$ and attempt to reverse-engineer structural reasons.

WORK

Fast reality check (explicit computation).

I computed $h(n)$ by enumerating powerful numbers $m\le (N+1)^2$ using the representation $m=a^2b^3$ with $b$ squarefree, then counting how many fall in each interval $[n^2,(n+1)^2)$. Exact outputs:

• $h(1),\dots,h(20) = [1,2,1,1,3,1,1,2,1,2,3,1,1,3,2,2,1,2,2,2]$.
• For $1\le n\le 5000$, $\max h(n)=7$, first attained at $n=3611$.
• For $1\le n\le 100000$, $\max h(n)=8$, attained at $n\in\{17329,57476,66154,83860,88402\}$.
• Empirical distribution up to $n\le 100000$ (counts of $h(n)=\ell$ for $\ell\le 8$): \[ \#\{n\le 100000: h(n)=1\}=28273,\ \#\{h=2\}=40348,\ \#\{h=3\}=22417,\ \#\{h=4\}=7190,\ \#\{h=5\}=1524,\ \#\{h=6\}=219,\ \#\{h=7\}=24,\ \#\{h=8\}=5. \]

These computations are only sanity checks; they are not proofs.

Lemma 942.1 (structure of powerful integers).

An integer $m\ge 1$ is powerful if and only if there exist integers $a\ge 1$ and squarefree $b\ge 1$ such that \[ m=a^2b^3. \] Moreover, $b$ is uniquely determined as the product of primes dividing $m$ to an odd exponent.

Proof. Write the prime factorization $m=\prod_p p^{e_p}$ with $e_p\ge 0$ and $e_p=0$ for all but finitely many primes.

($\Rightarrow$) If $m$ is powerful then every $e_p\in\{0\}\cup\{2,3,4,\dots\}$. Define \[ b:=\prod_{p: e_p\text{ odd}} p \] (the product over primes where $e_p$ is odd). Then $b$ is squarefree by construction. Now define $a$ by specifying the exponent of each prime $p$ in $a$: \[ \nu_p(a):= \begin{cases} e_p/2 & \text{if $e_p$ is even},\\ (e_p-3)/2 & \text{if $e_p$ is odd}. \end{cases} \] This is an integer because if $e_p$ is odd then $e_p\ge 3$ and $e_p-3$ is even. Then the exponent of $p$ in $a^2b^3$ equals \[ 2\nu_p(a)+3\nu_p(b)= \begin{cases} 2\cdot(e_p/2)+0=e_p & \text{if $e_p$ is even},\\ 2\cdot((e_p-3)/2)+3\cdot 1=e_p & \text{if $e_p$ is odd}, \end{cases} \] so $m=a^2b^3$.

($\Leftarrow$) If $m=a^2b^3$ with $b$ squarefree, then in the prime factorization of $m$ every prime exponent is either $2\nu_p(a)$ (if $p\nmid b$) or $2\nu_p(a)+3$ (if $p\mid b$). In either case it is at least $2$ whenever $p\mid m$, so $m$ is powerful.

Uniqueness of $b$: if $m=\prod p^{e_p}$, then $e_p$ is odd if and only if the $p$-exponent in $b^3$ contributes an odd amount (namely $3$), which happens iff $p\mid b$. Thus $b$ is uniquely determined as the product of primes with odd exponent in $m$. $\Box$

Lemma 942.2 (global counting bound).

Let \[ P(X):=\#\{m\le X: m\text{ powerful}\}. \] Then for all $X\ge 1$, \[ P(X) \le \Big(\sum_{b=1}^{\infty} b^{-3/2}\Big)\, X^{1/2}. \] In particular $P(X)=O(X^{1/2})$.

Proof. By Lemma 942.1, each powerful $m\le X$ has a (unique) representation $m=a^2b^3$ with $b$ squarefree. Ignoring the squarefree restriction only increases the count, so \[ P(X) \le \#\{(a,b)\in\mathbb{N}^2: a^2b^3\le X\}. \] Fix $b\ge 1$. The inequality $a^2b^3\le X$ is equivalent to $a\le \sqrt{X}/b^{3/2}$, so the number of admissible $a$ is at most $\sqrt{X}/b^{3/2}$. Therefore \[ P(X) \le \sum_{b=1}^{\lfloor X^{1/3}\rfloor} \frac{\sqrt{X}}{b^{3/2}} \le \sqrt{X}\sum_{b=1}^{\infty} \frac{1}{b^{3/2}}. \] The series $\sum_{b\ge 1} b^{-3/2}$ converges (a $p$-series with $p=3/2>1$), giving the stated bound. $\Box$

Proposition 942.3 (bounded average of $h(n)$).

For every $N\ge 1$, \[ \frac{1}{N}\sum_{n=1}^N h(n) \le \Big(\sum_{b=1}^{\infty} b^{-3/2}\Big)\,\Big(1+\frac{1}{N}\Big). \] In particular, the average value of $h(n)$ over $1\le n\le N$ is $O(1)$.

Proof. The intervals $[n^2,(n+1)^2)$ for $n=1,2,\dots,N$ partition $[1,(N+1)^2)$, hence \[ \sum_{n=1}^N h(n)=\#\{m\in\mathbb{Z}:1\le m<(N+1)^2\ \text{and $m$ powerful}\}=P((N+1)^2-1)\le P((N+1)^2). \] Apply Lemma 942.2 with $X=(N+1)^2$ to get \[ \sum_{n=1}^N h(n)\le \Big(\sum_{b\ge 1} b^{-3/2}\Big)\,(N+1), \] and divide by $N$. $\Box$

Lemma 942.4 (trivial pointwise lower bound).

For all $n\ge 1$, $h(n)\ge 1$.

Proof. The integer $n^2$ lies in $[n^2,(n+1)^2)$ and is a perfect square, hence powerful. So the interval contains at least one powerful integer. $\Box$

VERIFICATION

• Lemma 942.1: checked parity cases for exponents $e_p=2,3,4,5,6,7$ explicitly; the construction gives $e_p=2u$ if even and $e_p=2u+3$ if odd.
• Lemma 942.2: the relaxation removing the squarefree restriction only increases the count, so the upper bound is valid.
• Proposition 942.3: verified that the intervals $[n^2,(n+1)^2)$ are disjoint and cover $[1,(N+1)^2)$.
• Computation sanity: for $n=1$, interval $[1,4)$ contains powerful $1,4$? Actually $4$ is excluded; so only $1$, giving $h(1)=1$, matching the computed list.

FINAL

UNRESOLVED (i) Strongest proved partial result: the global counting bound $P(X)=O(X^{1/2})$ (Lemma 942.2) implies the bounded-average statement $\frac1N\sum_{n\le N} h(n)=O(1)$ (Proposition 942.3) and the trivial pointwise lower bound $h(n)\ge 1$ (Lemma 942.4). (ii) First gap: obtain any nontrivial pointwise upper bound $h(n)\le (\log n)^{C}$ (or even $h(n)=n^{o(1)}$) valid for all large $n$. (iii) Top 3 next moves:

1. Study the Diophantine inequality $n^2\le a^2b^3<(n+1)^2$ with $b$ squarefree via lattice-point counting and try to prove a pointwise bound uniform in $n$.
2. Attempt to control powerful numbers in intervals of length $\asymp \sqrt{x}$ using a square-sieve: if $m$ is powerful then its squarefree kernel $\mathrm{rad}(m)$ satisfies $\mathrm{rad}(m)^2\mid m$; try to bound how often many such kernels can occur in $[n^2,(n+1)^2)$.
3. Extend the computation to much larger $n$ and record the maximizing $n$ and the specific powerful numbers in the maximizing interval; attempt to detect a structural pattern enabling a constructive lower bound.

(iv) Minimal counterexample structure (to a conjectured polylog upper bound): an $n$ for which there exist many pairs $(a,b)$ with $b$ squarefree such that $a^2b^3$ are all squeezed into a length-$2n+1$ window; heuristically this would likely require $n$ to have many small prime factors so that many nearby integers have large square divisors.

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.

Let $h(n)$ count the number of powerful (if $p\mid m$ then $p^2\mid m$) integers in $[n^2,(n+1)^2)$. Estimate $h(n)$. In particular is there some constant $c>0$ such that\[h(n) < (\log n)^{c+o(1)}\]and, for infinitely many $n$,\[h(n) >(\log n)^{c-o(1)}?\] Erdős writes it is not hard to prove that $\limsup h(n)=\infty$, and that the density $\delta_l$ of integers for which $h(n)=l$ exists and $\sum \delta_l=1$. A proof that $h(n)$ is unbounded is provided by van Doorn in the comments. De Koninck and Luca [DeLu04] have proved, for infinitely many $n$,\[h(n) \gg \left(\frac{\log n}{\log\log n}\right)^{1/3}.\]They also give the density ($\approx 0.275$) of those $n$ such that $h(n)=1$. References [DeLu04] De Koninck, Jean-Marie and Luca, Florian, Sur la proximité des nombres puissants . Acta Arith. $2004$, 149--157.

FORMAL RESTATEMENT

Fix $n\in\mathbb{N}$ with $n\ge 1$. Call an integer $m\ge 1$ powerful if for every prime $p$, $p\mid m\Rightarrow p^2\mid m$. Define \[ h(n) := \#\{m\in\mathbb{Z}: n^2\le m < (n+1)^2 \ \text{and $m$ is powerful}\}. \] The problem asks for asymptotics/upper-lower bounds for $h(n)$ as $n\to\infty$. In particular it asks whether there exists a constant $c>0$ such that \[ h(n) < (\log n)^{c+o(1)} \quad (n\to\infty) \] (i.e. $\log h(n) \le (c+o(1))\log\log n$), and whether for infinitely many $n$ we have \[ h(n) > (\log n)^{c-o(1)}. \] Edge case conventions: $\log$ is natural logarithm; $o(1)$ means a quantity tending to $0$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not use any external results beyond what is stated in the problem text. The problem text asserts: $1$ $\limsup_{n\to\infty} h(n)=\infty$ (unboundedness), $2$ the densities $\delta_\ell := \lim_{N\to\infty} \#\{1\le n\le N: h(n)=\ell\}/N$ exist and sum to $1$, $3$ for infinitely many $n$, $h(n) \gg (\log n/\log\log n)^{1/3}$.

ATTACK PLAN

Proof-track ideas.

• Use the structural parametrization of powerful numbers $m=a^2b^3$ with $b$ squarefree to reduce counting to lattice points $(a,b)$ lying in a thin region defined by $n^2\le a^2b^3<(n+1)^2$.
• Derive global bounds for the counting function $P(x):=\#\{m\le x: m\text{ powerful}\}$ and convert them into average bounds on $h(n)$ via telescoping sums.
• (Hard) Improve global bounds to local bounds in short intervals of length $\asymp n$, aiming for polylogarithmic control.

Disproof/construction-track ideas.

• Try to construct $n$ for which many distinct pairs $(a,b)$ yield $a^2b^3$ in $[n^2,(n+1)^2)$, perhaps by forcing $a^2b^3$ to cluster near a square via congruences/CRT.
• If polylog bounds are false, search computationally for unusually large $h(n)$ and attempt to reverse-engineer structural reasons.

WORK

Fast reality check (explicit computation).

I computed $h(n)$ by enumerating powerful numbers $m\le (N+1)^2$ using the representation $m=a^2b^3$ with $b$ squarefree, then counting how many fall in each interval $[n^2,(n+1)^2)$. Exact outputs:

• $h(1),\dots,h(20) = [1,2,1,1,3,1,1,2,1,2,3,1,1,3,2,2,1,2,2,2]$.
• For $1\le n\le 5000$, $\max h(n)=7$, first attained at $n=3611$.
• For $1\le n\le 100000$, $\max h(n)=8$, attained at $n\in\{17329,57476,66154,83860,88402\}$.
• Empirical distribution up to $n\le 100000$ (counts of $h(n)=\ell$ for $\ell\le 8$): \[ \#\{n\le 100000: h(n)=1\}=28273,\ \#\{h=2\}=40348,\ \#\{h=3\}=22417,\ \#\{h=4\}=7190,\ \#\{h=5\}=1524,\ \#\{h=6\}=219,\ \#\{h=7\}=24,\ \#\{h=8\}=5. \]

These computations are only sanity checks; they are not proofs.

Lemma 942.1 (structure of powerful integers).

An integer $m\ge 1$ is powerful if and only if there exist integers $a\ge 1$ and squarefree $b\ge 1$ such that \[ m=a^2b^3. \] Moreover, $b$ is uniquely determined as the product of primes dividing $m$ to an odd exponent.

Proof. Write the prime factorization $m=\prod_p p^{e_p}$ with $e_p\ge 0$ and $e_p=0$ for all but finitely many primes.

($\Rightarrow$) If $m$ is powerful then every $e_p\in\{0\}\cup\{2,3,4,\dots\}$. Define \[ b:=\prod_{p: e_p\text{ odd}} p \] (the product over primes where $e_p$ is odd). Then $b$ is squarefree by construction. Now define $a$ by specifying the exponent of each prime $p$ in $a$: \[ \nu_p(a):= \begin{cases} e_p/2 & \text{if $e_p$ is even},\\ (e_p-3)/2 & \text{if $e_p$ is odd}. \end{cases} \] This is an integer because if $e_p$ is odd then $e_p\ge 3$ and $e_p-3$ is even. Then the exponent of $p$ in $a^2b^3$ equals \[ 2\nu_p(a)+3\nu_p(b)= \begin{cases} 2\cdot(e_p/2)+0=e_p & \text{if $e_p$ is even},\\ 2\cdot((e_p-3)/2)+3\cdot 1=e_p & \text{if $e_p$ is odd}, \end{cases} \] so $m=a^2b^3$.

($\Leftarrow$) If $m=a^2b^3$ with $b$ squarefree, then in the prime factorization of $m$ every prime exponent is either $2\nu_p(a)$ (if $p\nmid b$) or $2\nu_p(a)+3$ (if $p\mid b$). In either case it is at least $2$ whenever $p\mid m$, so $m$ is powerful.

Uniqueness of $b$: if $m=\prod p^{e_p}$, then $e_p$ is odd if and only if the $p$-exponent in $b^3$ contributes an odd amount (namely $3$), which happens iff $p\mid b$. Thus $b$ is uniquely determined as the product of primes with odd exponent in $m$. $\Box$

Lemma 942.2 (global counting bound).

Let \[ P(X):=\#\{m\le X: m\text{ powerful}\}. \] Then for all $X\ge 1$, \[ P(X) \le \Big(\sum_{b=1}^{\infty} b^{-3/2}\Big)\, X^{1/2}. \] In particular $P(X)=O(X^{1/2})$.

Proof. By Lemma 942.1, each powerful $m\le X$ has a (unique) representation $m=a^2b^3$ with $b$ squarefree. Ignoring the squarefree restriction only increases the count, so \[ P(X) \le \#\{(a,b)\in\mathbb{N}^2: a^2b^3\le X\}. \] Fix $b\ge 1$. The inequality $a^2b^3\le X$ is equivalent to $a\le \sqrt{X}/b^{3/2}$, so the number of admissible $a$ is at most $\sqrt{X}/b^{3/2}$. Therefore \[ P(X) \le \sum_{b=1}^{\lfloor X^{1/3}\rfloor} \frac{\sqrt{X}}{b^{3/2}} \le \sqrt{X}\sum_{b=1}^{\infty} \frac{1}{b^{3/2}}. \] The series $\sum_{b\ge 1} b^{-3/2}$ converges (a $p$-series with $p=3/2>1$), giving the stated bound. $\Box$

Proposition 942.3 (bounded average of $h(n)$).

For every $N\ge 1$, \[ \frac{1}{N}\sum_{n=1}^N h(n) \le \Big(\sum_{b=1}^{\infty} b^{-3/2}\Big)\,\Big(1+\frac{1}{N}\Big). \] In particular, the average value of $h(n)$ over $1\le n\le N$ is $O(1)$.

Proof. The intervals $[n^2,(n+1)^2)$ for $n=1,2,\dots,N$ partition $[1,(N+1)^2)$, hence \[ \sum_{n=1}^N h(n)=\#\{m\in\mathbb{Z}:1\le m<(N+1)^2\ \text{and $m$ powerful}\}=P((N+1)^2-1)\le P((N+1)^2). \] Apply Lemma 942.2 with $X=(N+1)^2$ to get \[ \sum_{n=1}^N h(n)\le \Big(\sum_{b\ge 1} b^{-3/2}\Big)\,(N+1), \] and divide by $N$. $\Box$

Lemma 942.4 (trivial pointwise lower bound).

For all $n\ge 1$, $h(n)\ge 1$.

Proof. The integer $n^2$ lies in $[n^2,(n+1)^2)$ and is a perfect square, hence powerful. So the interval contains at least one powerful integer. $\Box$

VERIFICATION

• Lemma 942.1: checked parity cases for exponents $e_p=2,3,4,5,6,7$ explicitly; the construction gives $e_p=2u$ if even and $e_p=2u+3$ if odd.
• Lemma 942.2: the relaxation removing the squarefree restriction only increases the count, so the upper bound is valid.
• Proposition 942.3: verified that the intervals $[n^2,(n+1)^2)$ are disjoint and cover $[1,(N+1)^2)$.
• Computation sanity: for $n=1$, interval $[1,4)$ contains powerful $1,4$? Actually $4$ is excluded; so only $1$, giving $h(1)=1$, matching the computed list.

FINAL

UNRESOLVED (i) Strongest proved partial result: the global counting bound $P(X)=O(X^{1/2})$ (Lemma 942.2) implies the bounded-average statement $\frac1N\sum_{n\le N} h(n)=O(1)$ (Proposition 942.3) and the trivial pointwise lower bound $h(n)\ge 1$ (Lemma 942.4). (ii) First gap: obtain any nontrivial pointwise upper bound $h(n)\le (\log n)^{C}$ (or even $h(n)=n^{o(1)}$) valid for all large $n$. (iii) Top 3 next moves:

1. Study the Diophantine inequality $n^2\le a^2b^3<(n+1)^2$ with $b$ squarefree via lattice-point counting and try to prove a pointwise bound uniform in $n$.
2. Attempt to control powerful numbers in intervals of length $\asymp \sqrt{x}$ using a square-sieve: if $m$ is powerful then its squarefree kernel $\mathrm{rad}(m)$ satisfies $\mathrm{rad}(m)^2\mid m$; try to bound how often many such kernels can occur in $[n^2,(n+1)^2)$.
3. Extend the computation to much larger $n$ and record the maximizing $n$ and the specific powerful numbers in the maximizing interval; attempt to detect a structural pattern enabling a constructive lower bound.

(iv) Minimal counterexample structure (to a conjectured polylog upper bound): an $n$ for which there exist many pairs $(a,b)$ with $b$ squarefree such that $a^2b^3$ are all squeezed into a length-$2n+1$ window; heuristically this would likely require $n$ to have many small prime factors so that many nearby integers have large square divisors.