Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

A non-terminating Erdős 261 greedy orbit has no limiting carry ratio

Proved
Erdos261.ratio_not_tendsto

by Ethan Cheung Wang · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

erdos-problemsnumber-theory

Let gjg_jgj​ be the greedy carry for Erdős Problem 261 started at (n,n)(n,n)(n,n): g0=ng_0=ng0​=n, and gj+1=2gj−(n+j+1)g_{j+1}=2g_j-(n+j+1)gj+1​=2gj​−(n+j+1) if 2gj≥n+j+12g_j\ge n+j+12gj​≥n+j+1 (a subtracting step), otherwise gj+1=2gjg_{j+1}=2g_jgj+1​=2gj​ (a doubling step). Equivalently (N,R)↦(N+1, 2R mod (N+1))(N,R)\mapsto(N+1,\,2R\bmod(N+1))(N,R)↦(N+1,2Rmod(N+1)) with Nj=n+jN_j=n+jNj​=n+j, Rj=gjR_j=g_jRj​=gj​; the greedy algorithm terminates iff some gj=0g_j=0gj​=0. Theorem. If gk≠0g_k\ne0gk​=0 for all kkk, then gj/(n+j)g_j/(n+j)gj​/(n+j) does not converge.

With xj=gj/(n+j)x_j=g_j/(n+j)xj​=gj​/(n+j) and qj∈{0,1}q_j\in\{0,1\}qj​∈{0,1} the decision at step jjj, qj=2gj−gj+1n+j+1=2xjn+jn+j+1−xj+1q_j=\frac{2g_j-g_{j+1}}{n+j+1}=2x_j\frac{n+j}{n+j+1}-x_{j+1}qj​=n+j+12gj​−gj+1​​=2xj​n+j+1n+j​−xj+1​. If xj→Lx_j\to Lxj​→L then qj→Lq_j\to Lqj​→L, so qjq_jqj​ is eventually constant, contradicting that both decisions occur infinitely often (Erdos261.greedy_phase_types_infinite).

Preamble
import Mathlib
import Definitions.Def_Erdos261_defs
open Finset
Formal statement
namespace Erdos261

theorem ratio_not_tendsto (n : ℕ) (hnt : ∀ k, greedy n k ≠ 0) :
    ¬ ∃ L : ℝ, Filter.Tendsto (fun j : ℕ => (greedy n j : ℝ) / ((n : ℝ) + j)) Filter.atTop (nhds L) := by sorry

end Erdos261
Source
Erdős Problem 261 (https://www.erdosproblems.com/261); greedy carry as in Borwein–Loring 1990 / Tengely–Ulas–Zygadło 2020 (platform def Def_Erdos261_defs); Claim A1 of claim from a GPT answer relayed by Ethan Cheung (third round, Oct 23 2026), Lean-verified by Grok Bot for Ethan Cheung (Oct 23 2026) (their displayed identity has 1+1/Nj1+1/N_j1+1/Nj​ where Nj/(Nj+1)N_j/(N_j+1)Nj​/(Nj​+1) is correct; the limit argument is unaffected)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me