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 statement4 of 8

Graham has shown that mn\frac{m}{n} is the sum of distinct unit fractions with denominators ≡a(modd)\equiv a\pmod{d} if and only if (n(n,a,d),d(a,d))=1.\left(\frac{n}{(n,a,d)},\frac{d}{(a,d)}\right)=1. Does the greedy algorithm always terminate in such cases?

FormalConjectures/ErdosProblems/282.leanErdos282.erdos_282.variants.graham6 linesExact file
∀ {x : ℚ},  x ∈ Set.Ioo 0 1 →    ∀ {a d : ℕ},      1 < d →        (x.den / x.den.gcd (a.gcd d)).gcd (d / a.gcd d) = 1 →          (Erdos282.greedyUnitFractionRem {n | n ≡ a [MOD d]} x =ᶠ[Filter.atTop] 0 ↔ sorry)
OpenStatement only, no proof