The Conjecture

The Collatz problem concerns the behavior of iterates of the function `C`, defined on integers by:
`C: {(n-=0(2)|->n/2),(n-=1(2)|->3*n+1):}`

The Collatz Conjecture asserts that, starting from any positive integer `n`, repeated iteration of this function eventually produces the value `1`.
`AAninNN, EEkinNN, C^{(k)}(n)=1`

The definition of `C` implies that every odd step will be followed by an even step. Instead of `C`, we can use the function.
`F: {(n-=0(2)|->n/2),(n-=1(2)|->(3*n+1)/2):}`
The conjecture is equivalent to:
`AAninNN, EEkinNN, F^{(k)}(n)=1`

A third option is to consider merging all feasible divisions by two, and define the function `Q` on odd integers by:
`Q:n|->(3*n+1)/|3*n+1|_2`
Where `|p|_2` being the biggest factor `m` such that `2^m` divides `p`.
In this case, the conjecture is equivalent to:
`AAn-=1(2), EEkinNN, Q^{(k)}(n)=1`

We will mostly use the second form of the conjecture, and its extension to `ZZ`

Notations and Definitions

Trajectory, Steps, Routes and Transformation

The Trajectory of `n`, `hat(T)(n)` is the set of successive iterations of `F` from `n` to 1. It can be represented as:

Each single application of ``F is called a Step, we define Steps by:
Odd Steps:
An Odd Step is an application of the transformation
`U: {(2NN+1->NN),(n|->(3*n+1)/2):}`
We note `o(n)` the number of Odd Steps within `hat(T)(n)`
Even Steps:
An Even Step is an application of the transformation
`D: {(2NN->NN),(n|->n/2):}`
We note `e(n)` the number of Even Steps within `hat(T)(n)`

We will note `hat(T)_[[k]](n)` the restriction of `hat(T)(n)` to the `k` first steps.

We define the Routes of `n`, `obrace(n)^("k")`,as the sets of successive values taken when following `hat(T)_[[k]](n)`:
`obrace(n)^("k")={F^((i))(n), i in [0,k]}`
and by extension `obrace(n)`, the Complete Route of `n` to `1`:
`obrace(n)={n_0=n, n_1=F(n),...,n_i=F^((i))(n),...,1}`

Height

The height is the logarithm of the current value: `u = ln(n)`
The maximum height of `n` is the logarithm of the maximum value of the route of `n`:
`u_max(n)=ln(max_(i in N)(F^((i))(n)))`

Stopping Time

The Stopping Time of `n`, `sigma(n)` is the number of consecutive Steps from `n` to reach a value with a height below the initial height:
`sigma(n)=max_(k in NN)(k, AAi in [1,k], F^((i))(n)>n)`

Total Stopping Time

The Total Stopping Time of `n`, `sigma_(oo)(n)` is the number of Steps from `n` to `1`:
`sigma_(oo)(n)=min_(k in NN)(k, F^((k))(n)=1)`
By definition, the Total Stopping Time is the sum of the number of Odd Steps and Even Steps:
`sigma_(oo)(n)=o(n)+e(n)`

Total Stopping Time Classes

The `k^(th)` Total Stopping Time Class `R_k` is the set of integer having a Total Stopping Time equal to `k`:
`R_k={n in NN, sigma_(oo)(n)=k}`
We define `r_k` as the number of elements in `R_k`
The `o^(th)` Subclass of `R_k`, `R_(k,o)` is the set of integer whose Total Stopping Time is `k` and the number of Odd Steps is `o`:
`R_(k,o)={n in NN, sigma_(oo)(n)=k ^^ o(n)=o}`
We define `r_(k,o)` as the number of elements in `R_(k,o)`
All subclasses are disjoint, so we have:
`R_k=uuu_(i=0)^k(R_(k,o))`
and
`r_k=sum_(i=0)^k(r_(k,o))`

Expansion

We define the expansion of `n`, `s(n)` by the ratio between the maximum height and the initial height:
`s(n)=(u_max(n))/ln(n)`

Finesse

We define the finesse of `n`, `gamma(n)` by the ratio between the Total Stopping Time and the initial height:
`gamma(n)=(sigma_(oo)(n))/ln(n)`

Completeness

We define the completeness of `n`, `c(n)` by the ratio between the Odd Steps and the Total Stopping Time:
`c(n)=(o(n))/(sigma_(oo)(n))`

Impact of different generating functions

Using `C`

The number of odd steps is the same, an additional even step is encountered after each odd step.
`{(o_C(n)=o(n)),(e_C(n)=o(n)+e(n)):}`
The Stopping Time is sometimes called Glide.
The Total Stopping Time is sometimes called Delay.
`{:(Delay(n),=o_C(n)+e_C(n)),(,=2*o(n)+e(n)),(,=sigma_(oo)(n)+o(n)):}`
The completeness is then equal to the ratio between Odd and Even Steps:
`c(n)=(o_C(n))/(e_C(n))`

Using `Q`

The number of odd steps is the same, no even steps, the Total Stopping Time equals the number of odd steps.
`{:(TST_Q(n),=o_Q(n)),(,=o(n)):}`