Skip to content

Erdős problem 282

Start work

Let A⊆NA\subseteq \mathbb{N} be an infinite set and consider the following greedy algorithm for a rational x∈(0,1)x\in (0,1): choose the minimal n∈An\in A such that n≥1/xn\geq 1/x and repeat with xx replaced by x−1nx-\frac{1}{n}. If this terminates after finitely many steps then this produces a representation of xx as the sum of distinct unit fractions with denominators from AA.

Sources

The source's own material, retained exactly.

8 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

282.lean

Retained formal statement5 of 8

Graham has also shown that xx is the sum of distinct unit fractions with square denominators if and only if x∈[0,π2/6−1)∪[1,π2/6)x\in [0,\pi^2/6-1)\cup [1,\pi^2/6). Does the greedy algorithm for this always terminate? Erdős and Graham believe not - indeed, perhaps it fails to terminate almost always.

FormalConjectures/ErdosProblems/282.leanErdos282.erdos_282.variants.sq4 linesExact file
sorry ↔  ∀ (x : ℚ),    ↑x ∈ Set.Ico 0 (Real.pi ^ 2 / 6 - 1) ∪ Set.Ico 1 (Real.pi ^ 2 / 6) →      Erdos282.greedyUnitFractionRem {n | IsSquare n} x =ᶠ[Filter.atTop] 0
OpenStatement only, no proof