Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Accelerated (Syracuse) map T(n)=(3n+1)/2v2(3n+1)T(n) = (3n+1)/2^{v_2(3n+1)}T(n)=(3n+1)/2v2​(3n+1)

Definition
syracuseStep

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

dynamical-systemsiterationnumber-theorystopping-time

The Syracuse map, also called the accelerated Collatz map, sends

T(n)=3n+12 v2(3n+1),T(n) = \frac{3n+1}{2^{\,v_2(3n+1)}},T(n)=2v2​(3n+1)3n+1​,

where v2v_2v2​ is the 222-adic valuation, so that T(n)T(n)T(n) is the odd part of 3n+13n+13n+1.

On an odd input the classical Collatz map performs one ascending step n↦3n+1n \mapsto 3n+1n↦3n+1 followed by a run of halvings, and TTT collapses that whole run into a single step: TTT carries odd numbers to odd numbers, and its orbit is the subsequence of odd values along the Collatz orbit. This is the setting in which the quantitative theory of the problem is usually developed — the Terras–Everett stopping-time density theorem and Tao's almost-all result are both statements about TTT rather than about the classical map — because the expected multiplicative drift per step of TTT is 3/4<13/4 < 13/4<1, whereas the classical map alternates between growth and contraction.

Formalization Note. The valuation is Mathlib's (3 * n + 1).factorization 2 and the quotient is written with the ordCompl notation, so the definition is total on N\mathbb{N}N and needs no hypothesis on nnn; the intended domain is the odd numbers, and hypotheses of oddness are carried by the theorems that use it rather than by the definition.

Definition code
import Mathlib.Data.Nat.Factorization.Basic

open Nat

/-- One step of the accelerated (Syracuse) map: `n ↦ (3 * n + 1) / 2 ^ v₂(3 * n + 1)`, the odd
part of `3 * n + 1`.  On odd inputs this collapses the ascending step and the ensuing run of
halvings of the Collatz map into a single step. -/
def syracuseStep (n : ℕ) : ℕ := ordCompl[2] (3 * n + 1)
Source
https://en.wikipedia.org/wiki/Collatz_conjecture#Syracuse_function; Jeffrey C. Lagarias, The 3x+1 Problem and Its Generalizations, Amer. Math. Monthly 92 (1985), 3-23, Section 2 (the function T), https://websites.umich.edu/~lagarias/3x%2B1.html; Riho Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241-252; Terence Tao, Almost All Orbits of the Collatz Map Attain Almost Bounded Values, Forum of Mathematics Pi 10 (2022), https://arxiv.org/abs/1909.03562

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