Bound the number of consecutive powerful pairs up to $x$: is it $(\log x)^{O(1)}$? (Erdős #365)
Statement
A positive integer $n$ is *powerful* (equivalently $2$-full) if every prime $p$ dividing $n$ satisfies $p^2\mid n$. A *consecutive powerful pair* is an $n$ such that both $n$ and $n+1$ are powerful; the smallest is $(8,9)$, and these $n$ are catalogued as OEIS A060355. Erdős asked two questions. First, must every consecutive powerful pair arise from a Pell-type equation — equivalently, must one of $n$, $n+1$ be a perfect square? Second, and the part that remains open: is the number of $n\leq x$ with $n$ and $n+1$ both powerful bounded by $(\log x)^{O(1)}$? That is, does there exist a constant $C$ with $$\#\{\,n\leq x : n\text{ and }n+1\text{ both powerful}\,\}\leq (\log x)^{C}$$ for all sufficiently large $x$? The first question is now known to have a negative answer (Golomb; Walker), so the live problem is this counting bound.
Acceptance. FULLY RESOLVES: either (a) a complete proof that $\#\{n\leq x : n, n+1\text{ both powerful}\}\leq (\log x)^{C}$ for some explicit constant $C$ and all sufficiently large $x$ — a machine-checkable (Lean/Coq) proof is preferred, otherwise a full written proof with every step — or (b) a disproof showing the counting function exceeds $(\log x)^{C}$ for every fixed $C$ (again with a complete proof). ADVANCES (each independently checkable): prove an unconditional upper bound on the counting function strictly sharper than any stated in the background, with proof; OR establish the $(\log x)^{O(1)}$ bound conditional on a clearly stated hypothesis (e.g. the abc conjecture) with a complete conditional proof; OR extend the exhaustive enumeration of consecutive powerful pairs (OEIS A060355) to a new record height with the search program and a reproducible certificate that the search was exhaustive up to that bound, reporting the empirical growth of the counting function. Deliver the proof file, the conditional proof, or the search code plus the attained bound and the enumerated pairs.
Background
Posed by Erdős and discussed by Erdős [Er76d, p.31] and Erdős–Graham [ErGr80, p.68]; listed as open on erdosproblems.com/365 (fetched 2026-07-13, status 'open', tagged 'number theory | powerful'). Origin: Erdős asked Mahler whether infinitely many consecutive powerful pairs exist, and Mahler observed the answer is yes via the Pell equation $x^2 = 2^3 y^2 + 1$, which produces pairs with one member a square (e.g. $(8,9)$). Erdős then asked whether *every* such pair must come from a Pell equation — equivalently whether one of $n$, $n+1$ is always a perfect square. This was disproved: Golomb [Go70] noted that $12167 = 23^3$ and $12168 = 2^3\cdot 3^2\cdot 13^2$ are consecutive, both powerful, and neither a square, and Walker [Wa76] showed that $7^3 x^2 = 3^3 y^2 + 1$ has infinitely many solutions, yielding infinitely many non-square consecutive powerful pairs. What remains open is the density/counting question: the consecutive powerful pairs form OEIS A060355, and Erdős conjectured their counting function up to $x$ is at most $(\log x)^{O(1)}$. The problem appears as B16 in Guy's *Unsolved Problems in Number Theory* [Gu04], and is a close cousin of the venue problems on three consecutive powerful numbers (Erdős #364) and on a $2$-full $n$ with $3$-full successor (Erdős #366). The attacker's tool: exhaustive enumeration of powerful numbers via the parametrisation $n = a^2 b^3$ to extend A060355 and empirically fit the growth of its counting function, combined with abc-conditional or Pell-structure arguments to bound the count analytically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #365 (T. F. Bloom) | website |
| REF-02 | OEIS A060355 — n such that n and n+1 are both powerful | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.