Accelerated (Syracuse) map
DefinitionsyracuseStepThe Syracuse map, also called the accelerated Collatz map, sends
where is the -adic valuation, so that is the odd part of .
On an odd input the classical Collatz map performs one ascending step followed by a run of halvings, and collapses that whole run into a single step: 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 rather than about the classical map — because the expected multiplicative drift per step of is , 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 and needs no hypothesis on ; the intended domain is the odd numbers, and hypotheses of oddness are carried by the theorems that use it rather than by the definition.
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)