/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 365

References:

    erdosproblems.com/365

    [Go70] Golomb, S. W., Powerful numbers. Amer. Math. Monthly (1970), 848-855.

    [Gu04] Guy, R. K., Unsolved problems in number theory (2004), Problem B16.

    [Wa76] Walker, D. T., Consecutive integer pairs of powerful numbers and related Diophantine equations. Fibonacci Quart. (1976), 111-116.

@[expose] public sectionnamespace Erdos365

Golomb's consecutive powerful pair $12167=23^3$ and $12168=2^3 3^2 13^2$. Neither number is a square [Go70].

hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ Nat.Powerful 12167 ∧ Nat.Powerful 12168 ∧ ¬IsSquare 12167 ∧ ¬IsSquare 12168 exact ⟨hA, hB, hns _ (hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12100 < 12167 All goals completed! 🐙) (hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12167 < 12321 All goals completed! 🐙), hns _ (hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12100 < 12168 All goals completed! 🐙) (hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12168 < 12321 All goals completed! 🐙)⟩

Do all pairs of consecutive powerful numbers $n$ and $n+1$ come from solutions to Pell equations? In other words, must either $n$ or $n+1$ be a square?

The answer to the first question is no: Golomb [Go70] observed that both $12167=23^3$ and $12168=2^3 3^2 13^2$ are powerful.

We require $n>0$ since Nat.Powerful also includes $0$.

@[category research solved, question, AMS 11] theorem erdos_365.parts.i : ¬ ∀ n : ℕ, 0 < n → Nat.Powerful n → Nat.Powerful (n + 1) → IsSquare n ∨ IsSquare (n + 1) := ⊢ ¬∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1) h:∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)⊢ False h:∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)hA:Nat.Powerful 12167hB:Nat.Powerful 12168hnA:¬IsSquare 12167hnB:¬IsSquare 12168⊢ False rcases h 12167 (h:∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)hA:Nat.Powerful 12167hB:Nat.Powerful 12168hnA:¬IsSquare 12167hnB:¬IsSquare 12168⊢ 0 < 12167 All goals completed! 🐙) hA hB with hs | hs h:∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)hA:Nat.Powerful 12167hB:Nat.Powerful 12168hnA:¬IsSquare 12167hnB:¬IsSquare 12168hs:IsSquare 12167⊢ False All goals completed! 🐙 h:∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)hA:Nat.Powerful 12167hB:Nat.Powerful 12168hnA:¬IsSquare 12167hnB:¬IsSquare 12168hs:IsSquare (12167 + 1)⊢ False All goals completed! 🐙

Is the number of positive $n\leq x$ such that $n$ and $n+1$ are both powerful bounded by $(\log x)^{O(1)}$?

@[category research open, question, AMS 11] theorem erdos_365.parts.ii : ∃ C : ℝ, 0 < C ∧ ∃ k : ℕ, ∀ᶠ x : ℕ in Filter.atTop, ({n : ℕ | 0 < n ∧ n ≤ x ∧ Nat.Powerful n ∧ Nat.Powerful (n + 1)}.ncard : ℝ) ≤ C * (Real.log x) ^ k := ⊢ ∃ C, 0 < C ∧ ∃ k, ∀ᶠ (x : ℕ) in Filter.atTop, ↑{n | 0 < n ∧ n ≤ x ∧ n.Powerful ∧ (n + 1).Powerful}.ncard ≤ C * Real.log ↑x ^ k All goals completed! 🐙end Erdos365