Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Collatz descent for n≡15(mod16)n \equiv 15 \pmod{16}n≡15(mod16)

Open
collatz_descent_fifteen_mod_sixteen

by Zexuan Liu · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamical-systemsiterationnumber-theoryopen-problemstopping-time

Let CCC denote the Collatz step map. The assertion is that every n≡15(mod16)n \equiv 15 \pmod{16}n≡15(mod16) has a finite stopping time:

∃m∈N:Cm(n)<n.\exists m \in \mathbb{N} : \quad C^{m}(n) < n .∃m∈N:Cm(n)<n.

This class is open, and it is the most resistant of the classes left by the residue refinement. Writing n=16j+15n = 16j + 15n=16j+15, the first eight steps are parity-determined and carry nnn to 81j+8081j + 8081j+80: four ascending steps against four halvings give an accumulated multiplier of 34/24=81/16>13^{4}/2^{4} = 81/16 > 134/24=81/16>1, so the orbit is far above its starting point when the residue stops determining the parity. This is the class of longest initial ascending runs at this modulus, and refining the modulus splits it further without terminating.

The statement covers the two classes 151515 and 313131 modulo 323232, and is one of the open cases left by the modulo 323232 refinement of the descent problem, alongside 7 mod 327 \bmod 327mod32 and 27 mod 3227 \bmod 3227mod32. Together they carry the whole remaining difficulty of the descent principle, and hence of the Collatz conjecture.

Formalization Note. No positivity hypothesis is needed: n≡15(mod16)n \equiv 15 \pmod{16}n≡15(mod16) forces n≥15n \ge 15n≥15. The index mmm is unconstrained, but m=0m = 0m=0 can never witness the conclusion since n<nn < nn<n is false.

Preamble
import Mathlib
import Definitions.Def_collatzStepMap
Formal statement
theorem collatz_descent_fifteen_mod_sixteen (n : ℕ) (h : n % 16 = 15) :
    ∃ m : ℕ, collatzStep^[m] n < n := by
  sorry
Source
https://en.wikipedia.org/wiki/Collatz_conjecture; supporting lemma for the prove2.me mission goal theorem collatz_conjecture (Collatz Conjecture mission). Jeffrey C. Lagarias, The 3x+1 Problem and Its Generalizations, Amer. Math. Monthly 92 (1985), 3-23, https://websites.umich.edu/~lagarias/3x%2B1.html, Section 2 (stopping time is determined by n mod 2^k; the Terras-Everett analysis of coefficient stopping time). Riho Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241-252.

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