Erdős problem 282 · problems.science

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

Sources

Browse retained paths and inspect the exact material available for this Problem.

8 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

282.lean

Retained formal statement4 of 8

Graham has shown that $\frac{m}{n}$ is the sum of distinct unit fractions with denominators $\equiv a\pmod{d}$ if and only if $\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

1∀ {x : ℚ},2  x ∈ Set.Ioo 0 1 →3    ∀ {a d : ℕ},4      1 < d →5        (x.den / x.den.gcd (a.gcd d)).gcd (d / a.gcd d) = 1 →6          (Erdos282.greedyUnitFractionRem {n | n ≡ a [MOD d]} x =ᶠ[Filter.atTop] 0 ↔ sorry)

OpenStatement only, no proof

Sources

Search problems.science