/-
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 FormalConjecturesUtilErdős Problem 365
References:
[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 Erdos365Golomb'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 _ (by hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12100 < 12167 norm_num All goals completed! 🐙) (by hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12167 < 12321 norm_num All goals completed! 🐙), hns _ (by hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12100 < 12168 norm_num All goals completed! 🐙) (by hA:Nat.Powerful 12167hB:Nat.Powerful 12168hns:∀ (n : ℕ), 12100 < n → n < 12321 → ¬IsSquare n⊢ 12168 < 12321 norm_num 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) := by ⊢ ¬∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)
intro h h:∀ (n : ℕ), 0 < n → n.Powerful → (n + 1).Powerful → IsSquare n ∨ IsSquare (n + 1)⊢ False
obtain ⟨hA, hB, hnA, hnB⟩ := golomb_pair 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 (by 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 norm_num All goals completed! 🐙) hA hB with hs | hs
· inl 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 exact hnA hs All goals completed! 🐙
· inr 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 exact hnB hs 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 := by ⊢ ∃ C,
0 < C ∧
∃ k, ∀ᶠ (x : ℕ) in Filter.atTop, ↑{n | 0 < n ∧ n ≤ x ∧ n.Powerful ∧ (n + 1).Powerful}.ncard ≤ C * Real.log ↑x ^ k
sorry All goals completed! 🐙end Erdos365