On the Link between Stopping Time and Non-Trivial Cycles in the Collatz Problem

Lionel Laurore

LuxCarta Technology, Department of Computer Science & Artificial Intelligence, Sophia-Antipolis, France.

DOI: 10.4236/apm.2025.156018                

Abstract

The Collatz Conjecture asserts that for all positive integers $s$ , every Syracuse integer sequence defined by $T\left(s\right)=s/2$ if $s$ is even, and $T\left(s\right)=\left(3s+1\right)/2$ otherwise, eventually reaches 1 after a finite number of iterations. The stopping time of an integer is the smallest number of iterations required for the sequence to fall below its starting value, while the total stopping time measures the iterations needed to reach 1. In this paper, we revisit the notion of stopping time by introducing the coefficient stopping time, defined as the smallest value of n such that the coefficient of $s$ in $T^n\left(s\right)$ , expressed as $3^r/2^n$ , is less than 1. Building on foundational results by Lynn E. Garner (1981), we leverage recent computational results by David Barina to extend Garner’s estimation regarding the minimal length of non-trivial cycles. Specifically, we demonstrate the non-existence of non-trivial cycles of length $n<19478780533$ , thus improving upon the previous result by Shalom Eliahou (2021). We subsequently show that this result can be generalized to all integers $n$ . We also introduce new properties concerning the behavior of Syracuse sequences modulo $2^n$ , which play a central role in our approach. Inspired by the work of Mike Winkler (2017), we provide an exact formulation of the stopping time counting function, which calculates the number of integers $s<2^n$ whose stopping time $\sigma \left(s\right)=n$ . From this formulation, we demonstrate that the density of integers with stopping time greater than $n$ tends to zero as $n$ approaches infinity. Furthermore, if divergent sequences exist, the set of such sequences is of zero density in $\mathbb{N}$ . Our results offer a deeper understanding of how stopping time behavior relates to the elusive search for non-trivial cycles in the Collatz problem.

Keywords

Collatz Problem, Stopping Time, Coefficient Stopping Time, Non-Trivial Cycles, Garner’s Main Theorem

1. Preamble

The 3x + 1 problem, introduced by the mathematician Lothar Collatz in 1937, is the study of integer sequences defined by the arithmetic function $C$ :

$C\left(s\right)=\{\begin{array}{ll}3s+1\hfill & \text{if}s\equiv 1\left(\mathrm{mod}2\right),\hfill \\ \frac{s}{2}\hfill & \text{otherwise}.\hfill \end{array}$

We define $C_{\infty }\left(s\right)$ as the sequence of all iterates of $s$ under the function $C$ : $C_{\infty }\left(s\right)=\left\{C^i\left(s\right):i\in N\right\}$ .

Lothar Collatz conjectured that for any starting number $s$ , the integer sequence $C_{\infty }\left(s\right)$ eventually reaches 1. Another equivalent formulation of the conjecture states that for any starting number $s$ , the integer sequence $C_{\infty }\left(s\right)$ has an iterate below $s$ .

In the following, we will mainly use two alternative formulations of the arithmetic function $C$ :

$T\left(s\right)=\{\begin{array}{ll}\frac{3s+1}{2}\hfill & \text{if}s\equiv 1\left(\mathrm{mod}2\right),\hfill \\ \frac{s}{2}\hfill & \text{otherwise}.\hfill \end{array}$

We define $T_{\infty }\left(s\right)$ as the sequence of all iterates of $s$ under the function $T$ : $T_{\infty }\left(s\right)=\left\{T^i\left(s\right):i\in N\right\}$ .

Additionally, we define:

$N\left(s\right)=\{\begin{array}{ll}\frac{3s+1}{2^{\alpha }}\hfill & \text{if}s\equiv 1\left(\mathrm{mod}2\right),\hfill \\ \frac{s}{2^{\alpha }}\hfill & \text{otherwise},\hfill \end{array}$

where $\alpha \left(s\right)$ is the largest integer such that $\frac{3s+1}{2^{\alpha }}$ or $\frac{s}{2^{\alpha }}$ is odd. We define $N_{\infty }\left(s\right)$ as the sequence of all iterates of $s$ under the function $N$ : $N_{\infty }\left(s\right)=\left\{N^i\left(s\right):i\in N\right\}$ .

We define the subsequences:

$C_m\left(s\right)=\left\{C^i\left(s\right):i<m\right\},T_n\left(s\right)=\left\{T^j\left(s\right):j<n\right\},N_r\left(s\right)=\left\{N^k\left(s\right):k<r\right\}$

Which are linked for the odd terms of these sequences by the relationship:

$C^{n+r}\left(s\right)=T^n\left(s\right)=N^r\left(s\right).$

For example:

$C_{\infty }\left(7\right)=\left\{7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,\cdots \right\}$ has 16 iterates to reach 1.

$T_{\infty }\left(7\right)=\left\{7,11,17,26,13,20,10,5,8,4,2,1,2,1,\cdots \right\}$ has 11 iterates to reach 1.

$N_{\infty }\left(7\right)=\left\{7,11,17,13,5,1,1,\cdots \right\}$ has 5 iterates, containing only odd terms.

And $C^{11}\left(7\right)=T^7\left(7\right)=N^4\left(7\right)=5$ and $C^7\left(7\right)=T^4\left(7\right)=N^3\left(7\right)=13$ .

Another important formulation that we will extensively use later is the following:

If $n$ is the number of iterates of $T$ and $r$ is the number of odd iterates in $T_n\left(s\right)$ , the $n$ -th iterate of $T$ can be represented by the Diophantine equation:

$T^n\left(s\right)=\frac{3^r}{2^n}\cdot s+\frac{1}{2^n}{\displaystyle \sum }_{i=1}^r{3}^{r-i}\cdot 2^{n-\left({\alpha }_i+\cdots +{{\alpha }^{\prime }}_r\right)},$ (1)

where $n={\displaystyle {\sum }_{i=1}^{r-1}{\alpha }_i}+{{\alpha }^{\prime }}_r$ and $1\le {{\alpha }^{\prime }}_r\le {\alpha }_r$ .

The coefficient of $s$ in (1) is $\frac{3^r}{2^n}$ . As long as this coefficient is greater than 1, $T^n\left(s\right)$ will remain greater than $s$ .

We will also use the following equivalent formulation of (1):

$T^n\left(s\right)=\frac{3^{r\left(n\right)}}{2^n}\cdot s+\frac{c_n\left(s\right)}{2^n},$ (2)

where

$c_n\left(s\right)={\displaystyle \sum }_{i=1}^r{3}^{r-i}\cdot 2^{n-\left({\alpha }_i+\cdots +{{\alpha }^{\prime }}_r\right)}$

and $n={\displaystyle {\sum }_{i=1}^{r-1}{\alpha }_i}+{{\alpha }^{\prime }}_r$ .

For example, $T^2\left(5\right)=\frac{3}{2^2}\cdot 5+\frac{1}{2^2}$ , with $n=2={{\alpha }^{\prime }}_1$ and ${{\alpha }^{\prime }}_1\ne {\alpha }_1=4$ as defined in the function $N\left(s\right)$ .

Definition 1.1. (Stopping Time) The Stopping Time $\sigma \left(s\right)$ is the number of iterates required for the sequence to drop below the starting value:

$\sigma \left(s\right)=Min\left\{p\in N:T^p\left(s\right)<s\right\}.$

Definition 1.2. (Coefficient Stopping Time) The Coefficient Stopping Time $\omega \left(s\right)$ is the first iterate where the coefficient of $s$ in (1) is less than 1:

$\omega \left(s\right)=Min\left\{p\in N:\frac{3^{r\left(p\right)}}{2^p}<1\right\}.$

Definition 1.3. (Non-Trivial Cycle) Under the Collatz conjecture, every Syracuse sequence is conjectured to eventually reach the trivial cycle $\left\{2,1\right\}$ under repeated application of the function $T$ . A non-trivial cycle is defined as a periodic sequence of $n$ integers, all strictly greater than 2, that remains invariant under the iteration of $T$ . The Collatz conjecture asserts that no such non-trivial cycles exist.

Definition 1.4. (Coefficient of s in the diophantine equation) The coefficient of s in the diophantine equation 2 is the value $\frac{3^{r\left(n\right)}}{2^n}$ and will be noted:

$Coef\left(T^n\left(s\right)\right)=\frac{3^{r\left(n\right)}}{2^n}$

2. Major Steps of Our Work

In the first part of this document, we will build upon the work of Lynn E. Garner [1] to present the following series of properties regarding stopping time:

• There exists an integer $N=19478780533$ which is the largest stopping time resulting from Lynn E. Garner’s approach, based on the fact that David Barina has verified that the Collatz Conjecture holds for all integers $s<702\times 2^{60}\approx 2^{69.455327}$ . For all $s<2^N$ and $\sigma \left(s\right)\le N$ , the stopping time of s is equal to the coefficient stopping time of $s$ .

• Two Syracuse sequences with starting numbers $s$ and $s^{\prime }$ , positive integers in $\mathbb{N}$ , such that $s\equiv s^{\prime }\left(\mathrm{mod}{2}^n\right)$ , have the same variations and sequences of coefficients of $s$ in Equation (2) for all iterates up to the $n$ -th iterate.

• The density in $\mathbb{N}$ of the set of positive integers with stopping time $\sigma \left(s\right)=n$ is entirely determined by the number of integers modulo $2^n$ having a stopping time equal to $n$ , as long as $n\le 19478780533$ .

• Finally, we will show by strong induction that if, for all $p<n$ and for all integers $s<2^p$ with stopping time $\sigma \left(s\right)=p$ , the stopping time is equal to the Coefficient stopping time $\sigma \left(s\right)=\omega \left(s\right)$ , then this also holds for all integers $s<2^n$ with stopping time $\sigma \left(s\right)=n$ . This approach allows us to extend Lynn E. Garner’s results to all stopping time values.

In a second part, building on the work of Mike Winkler [2], we will develop the following results:

• An exact formulation of the counting function giving the number of integers $s<2^n$ for which the Stopping Time $\sigma \left(s\right)=n$ , for every positive integer $n$ such that all positive integers $s<2^n$ with stopping time $\sigma \left(s\right)=n$ satisfy the condition $\sigma \left(s\right)=\omega \left(s\right)$ .

• We will show that the density function of the positive integers, starting numbers of Syracuse sequences, having a stopping time higher than $n$ , tends to 0 when $n$ grows to infinity, as long as, for every positive integer $n$ such that all positive integers $s<2^n$ with stopping time $\sigma \left(s\right)=n$ satisfy the condition $\sigma \left(s\right)=\omega \left(s\right)$ .

• We will give the exact structure of the highest and lowest trajectory of Syracuse sequences before stopping time iterate.

3. No Non-Trivial Cycle of Lenght Lower than 19,478,780,533

In 1981, Lynn E. Garner published a paper in which he highlighted that the behavior of a Collatz sequence is closely related to the distribution of powers of 2 among the powers of 3. He stated that the powers of 2 appear to be bounded away from the powers of 3 by a lower bound that grows almost as rapidly as the powers of 3. Garner demonstrated that $\sigma \left(s\right)=\omega \left(s\right)=n$ for all $n<64300$ and proved that no non-trivial cycles of length less than $n=64300$ exist.

In this section, we adopt the approach developed by Lynn E. Garner to extend his result to show the non-existence of non-trivial cycles for all stopping times $n\le 19478780533$ . This will also serve as a crucial step in applying the strong induction approach to extend the result to all stopping times.

Our notations differ slightly from those of Garner, as we use the function $T$ introduced earlier, whereas Lynn E. Garner’s proof relies on the function $C$ .

Lemma 3.1. For all positive integers $n\le 19478780533$ and all $s<2^n$ , the stopping time $\sigma \left(s\right)$ corresponds exactly to the coefficient stopping time $\omega \left(s\right)$ . This implies that for all $s<2^{19478780533}$ such that $\sigma \left(s\right)\le 19478780533$ , the stopping time $\sigma \left(s\right)$ of a Syracuse sequence with starting number $s$ corresponds to the coefficient stopping time, in other words, to the first iterate of $T$ such that the coefficient of $s$ in (2) satisfies $\frac{3^{r\left(n\right)}}{2^n}<1$ .

Proof. Let $M\in N$ and let:

$b\left(M\right):=\underset{r<M}{\text{max}}\left\{-{\text{log}}_3\left(1-\frac{2^{n-1}}{3^r}\right)\right\}\text{and}B\left(M\right):=\underset{r<M}{\text{max}}\left\{-{\text{log}}_3\left(\frac{2^n}{3^r}-1\right)\right\}$ (3)

Which implies:

for all $r<M,3^r-2^{n-1}>3^{r-b\left(M\right)}$ (4)

for all $r<M,2^n-3^r>3^{r-B\left(M\right)}$ (5)

The values of M at which b(M) and B(M) increase are given in the below table.

The Main Garner’s Theorem states:

$\text{For}\text{all}s,\text{if}\omega \left(s\right)=n\text{and}r<\text{min}\left\{M,\frac{s}{2}\cdot \frac{3^{1-B\left(M\right)}}{1-3^{-b\left(M\right)}}\right\},\text{then}\sigma \left(s\right)=\omega \left(s\right)$ (6)

This implies that if all Syracuse sequences have a number of odd iterates not too large, the stopping time is equal to the coefficient stopping time. In other words, the stopping time is the first iterate for which the coefficient of $s$ in (1) is less than 1.

If the Coefficient Stopping Time $\omega \left(s\right)=n$ , then: $\frac{3^r}{2^{n\left(r\right)}}<1$ and for $i<r$ , $\frac{3^i}{2^{n\left(i\right)}}>1$ .

And since $n=\alpha \left(1\right)+\cdots +\alpha \left(r\right)$ , we have the following inequality: $\frac{3^{r-i}}{2^{\alpha \left(i\right)+\cdots +\alpha \left(r\right)}}\cdot \frac{3^i}{2^{\alpha \left(1\right)+\cdots +\alpha \left(i-1\right)}}<1$ .

By inequality 4 for any $i<r$ , we have the following upper bound:

$\frac{3^{r-i}}{2^{\alpha \left(i\right)+\cdots +\alpha \left(r\right)}}<\frac{2^{\alpha \left(1\right)+\cdots +\alpha \left(i-1\right)}}{3^i}\le \frac{2^{n\left(i-1\right)}}{3^i}<\frac{1}{3}\cdot \left(1-3^{-b\left(M\right)}\right).$

Then:

$T^n\left(s\right)=\frac{3^r}{2^n}\cdot s+\frac{1}{2^n}{\displaystyle \sum }_{i=1}^r{3}^{r-i}\cdot 2^{n-\left(\alpha \left(i\right)+\cdots +\alpha \left(r\right)\right)}<\frac{3^r}{2^n}\cdot s+\frac{r}{3}\cdot \left(1-3^{-b\left(M\right)}\right).$

If we suppose that $\sigma \left(s\right)>\omega \left(s\right)$ , which implies $T^n\left(s\right)>s$ , we reach a contradiction:

$\begin{array}{c}s<T^n\left(s\right)<\frac{3^r}{2^n}\cdot s+\frac{r}{3}\cdot \left(1-3^{-b\left(M\right)}\right)\\ <\frac{3^r}{2^n}\cdot s+\frac{\frac{s}{2}\cdot \frac{3^{1-B\left(M\right)}}{1-3^{-b\left(M\right)}}}{3}\cdot \left(1-3^{-b\left(M\right)}\right)\\ <\frac{3^r}{2^n}\cdot s+\frac{s}{2}\cdot 3^{-B\left(M\right)}.\end{array}$

Using inequality 5 and the fact that $2^{n-1}<3^r<2^n$ , we have $2^n-3^r>3^{r-B\left(M\right)}>2^{n-1}\cdot 3^{-B\left(M\right)}$ , yielding:

$s<\frac{3^r}{2^n}\cdot s+\frac{s}{2}\cdot 3^{-B\left(M\right)}<\left(\frac{3^r}{2^n}+\frac{2^{n-1}\cdot 3^{-B\left(M\right)}}{2^n}\right)\cdot s<\left(\frac{3^r}{2^n}+\frac{3^{r-B\left(M\right)}}{2^n}\right)\cdot s<s.$

This proves the contradiction.

Thanks to the recent work of David Barina [3] (2021), who computationally verified the Collatz conjecture up to $702\cdot 2^{60}\simeq 2^{69.4553}$ , significantly improving the previous record held by Thomas Oliveira e Silva [4], and due to the increased computational power now available compared to Garner’s time, we have computed all values of $b\left(M\right)$ and $B\left(M\right)$ for all $M<200000000000$ . The results are presented in Table 1. We observe that the values of $M$ and $n\left(M\right)$ correspond to the numerators and denominators of the successive convergents in the continued fraction expansion of $\text{log}\left(2\right)/\text{log}\left(3\right)$ .

Table 1. Highest values of b(M) and B(M).

$M_i$	$n\left(M_i\right)$	$n\left(M_i\right)-n\left(M_{i-1}\right)$	$b\left(M_i\right)$	$B\left(M_i\right)$	$M_i$	$n\left(M_i\right)$	$n\left(M_i\right)-n\left(M_{i-1}\right)$	$b\left(M_i\right)$	$B\left(M_i\right)$
1	2		0.821692	1.134066	4,684,090	7,424108	190,537	11.921111
2	4	1	1.946921		4,874,627	7,726,102	190,537	11.950185
3	5	1		1.613445	5,065,164	8,028,096	190,537	11.980218
5	8	2		2.689105	5,255,701	8,330,090	190,537	12.011276
7	12	2	2.478725		5,446,238	8,632,084	190,537	12.043431
12	20	5	3.915205		5,636,775	8,934,078	190,537	12.076763
17	27	5		2.963203	5,827,312	9,236,072	190,537	12.111363
29	46	12		3.357256	6,017,849	9,538,066	190,537	12.147331
41	65	12		4.067531	6,208,386	9,840,060	190,537	12.184778
53	85	12	5.617528		6,398,923	10,142,054	190,537	12.223832
94	149	41		4.250575	6,589,460	10,444,048	190,537	12.264637
147	233	53		4.479936	6,779,997	10,746,042	190,537	12.307357
200	317	53		4.787298	6,970,534	11,048,036	190,537	12.352182
253	401	53		5.254823	7,161,071	11,350,030	190,537	12.399329
306	485	53		6.267689	7,351,608	11,652,024	190,537	12.449052
359	570	53	6.229625		7,542,145	11,954,018	190,537	12.501649
665	1055	306	9.138086		7,732,682	12,256,012	190,537	12.557472
971	1539	306		6.307414	7,923,219	12,558,006	190,537	12.616944
1636	2593	665		6.348953	8,113,756	12,860,000	190,537	12.680575
2301	3647	665		6.392479	8,304,293	13,161,994	190,537	12.748991
2966	4701	665		6.438190	8,494,830	13,463,988	190,537	12.822970
3631	5755	665		6.486320	8,685,367	13,765,982	190,537	12.903498
4296	6809	665		6.537136	8,875,904	14,067,976	190,537	12.991848
4961	7863	665		6.590959	9,066,441	14,369,970	190,537	13.089704
5626	8917	665		6.648165	9,256,978	14,671,964	190,537	13.199362
6291	9971	665		6.709209	9,447,515	14,973,958	190,537	13.324063
6956	11,025	665		6.774643	9,638,052	15,275,952	190,537	13.468602
7621	12,079	665		6.845148	9,828,589	15,577,946	190,537	13.640506
8286	13,133	665		6.921576	10,019,126	15,879,940	190,537	13.852616
8951	14,187	665		7.005014	10,209,663	16,181,934	190,537	14.129668
9616	15,241	665		7.096879	10,400,200	16,483,928	190,537	14.529907
10,281	16,295	665		7.199068	10,590,737	16,785,922	190,537	15.261307
10,946	17,349	665		7.314197	10,781,274	17,087,915	190,537		16.585704
11,611	18,403	665		7.446026	21,372,011	33,873,837	10,590,737	15.503241
12,276	19,457	665		7.600233	32,153,285	50,961,752	10,781,274	15.833722
12,941	20,511	665		7.786004	42,934,559	68,049,667	10,781,274	16.357825
13,606	21,565	665		8.019673	53,715,833	85,137,582	10,781,274	17.729972
14,271	22,619	665		8.334854	64,497,107	102,225,496	10,781,274		16.890397
14,936	23,673	665		8.820964	118,212,940	187,363,077	53,715,833		17.351701
15,601	24,727	665		9.934703	171,928,773	272,500,658	53,715,833		18.333573
16,266	25,782	665	9.628894		225,644,606	357,638,240	53,715,833	18.389077
31,867	50,509	15,601	10.770361		397,573,379	630,138,897	171928,773		20.907339
47,468	75,235	15,601		10.398601	623,217,985	987,777,137	225,644,606	18.448188
79,335	125,743	31,867		11.393245	1,020,791,364	1,617,916,034	397,573,379	18.511405
111,202	176,252	31,867	11.409410		1,418,364,743	2,248,054,931	397,573,379	18.579343
190,537	301,994	79,335		15.070361	1,815,938,122	2,878,193,828	397,573,379	18.652763
301,739	478,246	111,202	11.425867		2,213,511,501	3,508,332,725	397,573,379	18.732630
492,276	780,240	190,537	11.442627		2,611,084,880	4,138,471,622	397,573,379	18.820183
682,813	1,082,234	190,537	11.459702		3,008,658,259	4,768,610,519	397,573,379	18.917064
873,350	1,384,228	190,537	11.477103		3,406,231,638	5,398,749,416	397,573,379	19.025498
1,063,887	1,686,222	190,537	11.494843		3,803,805,017	6,028,888,313	397,573,379	19.148618
1,254,424	1,988,216	190,537	11.512936		4,201,378,396	6,659,027,210	397,573,379	19.291036
1,444,961	2,290,210	190,537	11.531396		4,598,951,775	7,289,166,107	397,573,379	19.459946
1,635,498	2,592,204	190,537	11.550238		4,996,525,154	7,919,305,004	397,573,379	19.667508
1,826,035	2,894,198	190,537	11.569478		5,394,098,533	8,549,443,901	397,573,379	19.936831
2,016,572	3,196,192	190,537	11.589134		5,791,671,912	9,179,582,798	397,573,379	20.321013
2,207,109	3,498,186	190,537	11.609224		6,189,245,291	9,809,721,695	397,573,379	20.998846
2,397,646	3,800,180	190,537	11.629767		6,586,818,670	10,439,860,591	397,573,379		23.043797
2,588,183	4,102,174	190,537	11.650784		12,776,063,961	20,249,582,286	6,189,245,291	21.100591
2,778,720	4,404,168	190,537	11.672298		19,362,882,631	30,689,442,877	6,586,818,670	21.215156
2,969,257	4,706,162	190,537	11.694333		25,949,701,301	41,129,303,468	6,586,818,670	21.346246
3,159,794	5,008,156	190,537	11.716915		32,536,519,971	51,569,164,059	6,586,818,670	21.499444
3,350,331	5,310,150	190,537	11.740071		39,123,338,641	62,009,024,650	6,586,818,670	21.683750
3,540,868	5,612,144	190,537	11.763832		45,710,157,311	72,448,885,241	6,586,818,670	21.915100
3,731,405	5,914,138	190,537	11.788230		52,296,975,981	82,888,745,832	6,586,818,670	22.226059
3,921,942	6,216,132	190,537	11.813299		58,883,794,651	93,328,606,423	6,586,818,670	22.702068
4,112,479	6,518,126	190,537	11.839079		65,470,613,321	103,768,467,014	6,586,818,670	23.759345
4,303,016	6,820,120	190,537	11.865610		72,057,431,991	114,208,327,605	6,547,0613,321		23.597310
4,493,553	7,122,114	190,537	11.892938		137,528,045,312	217,976,794,617	6,547,0613,321		25.248104

This allows us to estimate, based on the highest values of $B\left(M\right)$ and $b\left(M\right)$ , the maximum $M$ (i.e., the number of odd iterates of $T$ ) before the stopping time, in accordance with Garner’s Main Theorem. It is known that the Collatz conjecture has been computationally verified for all integers $s\le {702.2}^{60}$ . We have computed the condition of Garner’s Main Theorem for all $M$ and identified the highest value of $r$ , corresponding to the largest $s$ for which the Collatz conjecture holds. The highest value of $r$ is obtained for $M=12289742202$ .

$r<\min \left(12776063961,\frac{702\cdot 2^{60}}{2}.\frac{3^{1-23.043797}}{1-3^{-21.100591}}\right)=12289742202$

Thus $\sigma \left(s\right)=\omega \left(s\right)$ for all $s<2^n$ such that $n\left(r\right)<n\left(12289742202\right)=19478780533$ .

According to Lynn E. Garner’s conclusions, this implies that there is no non-trivial cycle of length less than $N=19478780533$ , and consequently that no integer $s<2^n$ can be a solution of the Diophantine equation $T^n\left(s\right)=s$ . This improves on the lower bound $n>17026679261$ found by Shalom Eliahou [5] in 2021 for the length of non-trivial cycles. However, we would likely obtain the same result using the approach developed by Shalom Eliahou if we utilized the computational record obtained by David Barina instead of the one by Oliveira e Silva. The main advantage of Garner’s approach is that it links the nonexistence of non-trivial cycles to the equality between the Stopping Time and the Coefficient Stopping Time.

4. Remarkable Properties of the Stopping Times

Before presenting, in Section 4, our approach to build the stopping time counting function, we are going to state some preliminary definitions and lemmas useful for the following parts of this work.

Definition 4.1. (Stopping time Histogram on Z/2ⁿZ) For every positive integer n,

$H_n=\left\{h_n\left(p\right),p\in N\right\}$

where $h_n\left(p\right)=card\left\{s<2^n,\sigma \left(s\right)=p\right\}$ is the number of residue classes mod $2^n$ of Syracuse sequences of starting number $s$ such that $\sigma \left(s\right)=p$ .

By convention, we will write $h_n\left(\infty \right)$ the number of Syracuse sequences of the starting number $s$ that has no finite stopping time. It concerns the Syracuse sequences, which eventually tend to infinity or reach a non-trivial cycle.

Definition 4.2. (Counting Function of Stopping Time lower or equal to n in Z/2ⁿZ) For every positive integer n,

$\pi \left(2^n\right)=card\left\{s<2^n,\sigma \left(s\right)\le n\right\}$

is the number of residue classes mod $2^n$ of Syracuse sequences of starting number $s$ such that $\sigma \left(s\right)\le n$ .

Definition 4.3. (Counting Function of Stopping Time higher than n in Z/2ⁿZ) For every positive integer n,

$S\left(n\right)=card\left\{s<2^n,\sigma \left(s\right)>n\right\}$

is the number of residue classes mod $2^n$ of Syracuse sequences of starting number $s$ such that $\sigma \left(s\right)>n$

By definition, we have the following equalities:

$\pi \left(2^n\right):={\displaystyle \sum }_{r=0}^n{h}_n\left(p\right),S\left(n\right):={\displaystyle \sum }_{n+1}^{\infty }{h}_n\left(p\right),2^n:={\displaystyle \sum }_{p=0}^{\infty }{h}_n\left(p\right),2^n:=\pi \left(2^n\right)+S\left(n\right)$

We shall see in lemma (5.5), that $h_n\left(p\right)=0$ for all p which don’t satisfy to the relation $p\left(r\right)=\lfloor r\cdot {\log }_2\left(3\right)+1\rfloor$ for $r\in N$ .

Lemma 4.1. For all $s\in 2N+1$ , for all $n$ and $m\in N+1$ , and for all $p\le n$ , we have:

$\begin{array}{l}{T}^p\left(2^n\cdot m+s\right)=\frac{3^{r_p}}{2^p}\cdot 2^n\cdot m+T^p\left(s\right)\text{and}{c}_p\left(2^n\cdot m+s\right)=c_p\left(s\right)\\ \text{and}{r}_p\left(2^n\cdot m+s\right)=r_p\left(s\right)=r_p.\end{array}$ (7)

Proof. The goal of this lemma is to show that for all iterates $p\le n$ of the function $T$ , the expressions $T^p\left(2^n\cdot m+s\right)$ , $\frac{3^{r\left(p\right)}}{2^p}$ , and $T^p\left(s\right)$ have the same variations up to the $n$ -th iteration of $T$ . Using Equation (2), we know:

$T^p\left(s\right)=\frac{3^{r_p}}{2^p}\cdot s+\frac{c_p\left(s\right)}{2^p},$

and $T^{p+1}\left(s\right)$ can be expressed in one of the following forms:

**Case 1:** If $T^p\left(s\right)$ is even, then:

$T^{p+1}\left(s\right)=\frac{T^p\left(s\right)}{2}=\frac{3^{r_p}}{2^{p+1}}\cdot s+\frac{c_p\left(s\right)}{2^{p+1}},$

which implies that $c_{p+1}\left(s\right)=c_p\left(s\right)$ and $r_{p+1}=r_p$ .

**Case 2:** If $T^p\left(s\right)$ is odd, then:

$T^{p+1}\left(s\right)=\frac{3T^p\left(s\right)+1}{2}=\frac{3^{r_p+1}}{2^{p+1}}\cdot s+\frac{3c_p\left(s\right)+2^p}{2^{p+1}},$

which implies that $c_{p+1}\left(s\right)=3c_p\left(s\right)+2^p$ and $r_{p+1}=r_p+1$ .

We will now prove by induction that:

$\begin{array}{l}{T}^p\left(2^n\cdot m+s\right)=\frac{3^{r_p}}{2^p}\cdot 2^n\cdot m+T^p\left(s\right)\text{and}{c}_p\left(2^n\cdot m+s\right)=c_p\left(s\right)\\ \text{and}{r}_p\left(2^n\cdot m+s\right)=r_p\left(s\right)=r_p.\end{array}$

**Base Case:** For $p=1$ , since $s$ is odd:

$\begin{array}{c}T\left(2^n\cdot m+s\right)=\frac{3\left(2^n\cdot m+s\right)+1}{2}=\frac{3}{2}\cdot \left(2^n\cdot m+s\right)+\frac{1}{2}\\ =\frac{3}{2}\cdot 2^n\cdot m+\frac{3s+1}{2}=\frac{3}{2}\cdot 2^n\cdot m+T\left(s\right),\end{array}$

with $c_1\left(2^n\cdot m+s\right)=1=c_1\left(s\right)$ and $r_1\left(2^n\cdot m+s\right)=r_1\left(s\right)=1$ .

**Inductive Step: ** Assume that for some $p<n$ :

$\begin{array}{l}{T}^p\left(2^n\cdot m+s\right)=\frac{3^{r_p}}{2^p}\cdot 2^n\cdot m+T^p\left(s\right)\text{and}{c}_p\left(2^n\cdot m+s\right)=c_p\left(s\right)\\ \text{and}{r}_p\left(2^n\cdot m+s\right)=r_p\left(s\right)=r_p.\end{array}$

**Case 1:** If $T^p\left(2^n\cdot m+s\right)$ is even, then $T^p\left(s\right)$ is necessarily even because $n>p$ , so:

$T^{p+1}\left(2^n\cdot m+s\right)=\frac{T^p\left(2^n\cdot m+s\right)}{2}=\frac{3^{r_p}}{2^{p+1}}\cdot \left(2^n\cdot m+s\right)+\frac{c_p\left(2^n\cdot m+s\right)}{2^{p+1}},$

As by hypothesis $c_p\left(2^n\cdot m+s\right)=c_p\left(s\right)$ , we can simplify:

$T^{p+1}\left(2^n\cdot m+s\right)=\frac{3^{r_p}}{2^{p+1}}\cdot 2^n\cdot m+T^{p+1}\left(s\right)$

and we have

$\begin{array}{l}{c}_{p+1}\left(2^n\cdot m+s\right)=c_p\left(2^n\cdot m+s\right)=c_p\left(s\right)=c_{p+1}\left(s\right)\\ \text{and}{r}_{p+1}\left(2^n\cdot m+s\right)=r_{p+1}\left(s\right)=r_p\end{array}$

**Case 2:** If $T^p\left(2^n\cdot m+s\right)$ is odd, then $T^p\left(s\right)$ is necessarily odd, so:

$T^{p+1}\left(2^n\cdot m+s\right)=\frac{3T^p\left(2^n\cdot m+s\right)+1}{2}=\frac{3^{r\left(p\right)+1}}{2^{p+1}}\cdot \left(2^n\cdot m+s\right)+\frac{3c_p\left(2^n\cdot m+s\right)+2^p}{2^{p+1}},$

which simplifies to:

$T^{p+1}\left(2^n\cdot m+s\right)=\frac{3^{r\left(p\right)+1}}{2^{p+1}}\cdot 2^n\cdot m+T^{p+1}\left(s\right),$

and we have:

$\begin{array}{l}{c}_{p+1}\left(2^n\cdot m+s\right)=3c_p\left(2^n\cdot m+s\right)+2^p=3c_p\left(s\right)+2^p=c_{p+1}\left(s\right)\\ \text{and}{r}_{p+1}\left(2^n\cdot m+s\right)=r_{p+1}\left(s\right)=r_p+1\end{array}$

This completes the proof.

Note: This property is very important because it shows that the variations of the two Syracuse sequences of starting numberd $s$ and $2^n\cdot m+s$ are identical for the first $n$ -iterations, and the sequences corresponding to the coefficients of $s$ and $2^n\cdot m+s$ in (1) are also identical. In his work entitled “Empirical Verification of the 3x + 1 and Related Conjectures”, published in the book The Ultimate Challenge: The 3x + 1 Problem edited by Jeffrey C. Lagarias [6], Thomas Oliveira e Silva [4] observed that the two sequences starting from 15 and 143 exhibit the same behavior up to the stopping time iterate. We have now proven the reason why this observation holds.

Corollary 4.2. For all odd integers $s\in \mathbb{N}$ , and for all $n,m\in {\mathbb{N}}^{+}$ such that $\omega \left(s\right)=n$ , we have:

$\omega \left(s\right)=\omega \left(2^n\cdot m+s\right).$

Proof. Lemma 4.1 shows that the iterates of $T$ starting from $s$ and $2^n\cdot m+s$ follow the same sequence of parities up to step $n$ . In particular, for all $p\le n$ , the coefficient of $s$ in the associated expression (2) is the same:

${\text{Coef}}_s\left(T^p\left(s\right)\right)={\text{Coef}}_s\left(T^p\left(2^n\cdot m+s\right)\right)=\frac{3^{r\left(p\right)}}{2^p}.$

Now, if $n$ is the smallest index for which $\frac{3^{r\left(n\right)}}{2^n}<1$ , then by definition $\omega \left(s\right)=n$ , and we also obtain $\omega \left(2^n\cdot m+s\right)=n$ , completing the proof.

Lemma 4.3. For all odd integers $s<2^n$ such that $\sigma \left(s\right)=\omega \left(s\right)=n$ , all integers $s^{\prime }=2^n\cdot m+s$ , with $m\in N+1$ also have a finite stopping time $\sigma \left(s^{\prime }\right)=n$ .

Proof. The proof follows directly from the previous corollary. Indeed, we have shown that if $\omega \left(s\right)=n$ , then for any $m\in {\mathbb{N}}^{+}$ , we have:

$\omega \left(2^n\cdot m+s\right)=\omega \left(s\right)=n.$

Therefore, if $\omega \left(s\right)=\sigma \left(s\right)$ , the same equality holds for $2^n\cdot m+s$ , and we may conclude that $s$ and $2^n\cdot m+s$ have the same stopping time:

$\sigma \left(2^n\cdot m+s\right)=\sigma \left(s\right).$

An immediate and noteworthy consequence of this result is that, for all $n<N$ , $h_n\left(n+1\right)=2\cdot h_n\left(n\right)$ . More generally, for all $p>n$ , $h_p\left(n\right)=2^{p-n}\cdot h_n\left(n\right)$ . This result implies that all integers in $N$ with a stopping time equal to $n$ are completely determined by the positive integers less than $2^n$ that have a stopping time equal to $n$ , for all $n$ satisfying Garner’s main theorem.

Lemma 4.4. If there exist positive integers $s>4$ and $n>19478780533$ such that $T^n\left(s\right)=s$ and $T^k\left(s\right)>s$ for all $0<k<n$ , meaning that the starting number $s$ in the Syracuse sequence is the smallest term of a non-trivial cycle of length $n$ , then $s$ is the only integer in the residue class modulo $2^n$ that satisfies $T^n\left(s\right)=s$ . Furthermore, all integers of the form $2^n\cdot m+s$ with $m>0$ have a finite stopping time $\sigma \left(2^n\cdot m+s\right)\le n$ .

Proof. According to lemma 4.1, No Non-trivial cycle may exist for $n>19478780533$ . From equation (2), the $n$ -th iterate of $s$ can be expressed as:

$T^n\left(s\right)=\frac{3^r}{2^n}\cdot s+\frac{c_n\left(s\right)}{2^n}.$

If $s$ and $n$ satisfy $T^n\left(s\right)=s$ and $T^k\left(s\right)>s$ for $0<k<n$ , it follows that:

$\begin{array}{l}s=\frac{3^r}{2^n}\cdot s+\frac{c_n\left(s\right)}{2^n}\\ \Rightarrow s-\frac{3^r}{2^n}\cdot s=\frac{c_n\left(s\right)}{2^n}>0\text{which}\text{implies}{3}^r<2^n\text{and}\omega \left(s\right)=n\end{array}$ (8)

By Lemma 4.1, for all integers $m>0$ :

$T^n\left(2^n\cdot m+s\right)=\frac{3^r}{2^n}\cdot \left(2^n\cdot m+s\right)+\frac{c_n\left(2^n\cdot m+s\right)}{2^n}=\frac{3^r}{2^n}\cdot \left(2^n\cdot m+s\right)+\frac{c_n\left(s\right)}{2^n}.$

Simplifying, we get:

$T^n\left(2^n\cdot m+s\right)=3^r\cdot m+\frac{3^r}{2^n}\cdot s+\frac{c_n\left(s\right)}{2^n}=3^r\cdot m+T^n\left(s\right)<2^n\cdot m+s.$

Thus, $\sigma \left(s\right)=\infty$ , and for all $m>0$ , $\sigma \left(2^n\cdot m+s\right)=\omega \left(2^n\cdot m+s\right)=\omega \left(s\right)=n$ .

We can conclude that if $s$ is the starting number of a Syracuse sequence and belongs to a non-trivial cycle of length $n$ , then for all positive integers $m>0$ and $n>0$ , $2^n\cdot m+s$ has a finite stopping time. This implies that $s$ is the only positive integer in the residue class modulo $2^n$ belonging to a non-trivial cycle. All other integers $s^{\prime }\equiv s\mathrm{mod}{2}^n$ in this residue class have a finite stopping time that is equal to or less than $n$ .

Lemma 4.5. A positive integer $n\le 19478780533$ is a stopping time value if and only if $n\left(r\right)=\lfloor r{\log }_{2}3+1\rfloor$ , where $r\in \mathbb{N}$ .

Proof. According to the relation for the $n$ -th iterate of a Syracuse sequence with starting number $s$ , as expressed in (1):

$T^n\left(s\right)=\frac{3^{r_n}}{2^n}s+\frac{c_n\left(s\right)}{2^n},\text{with}{r}_n=\lfloor \frac{n}{{\log }_{2}3}\rfloor .$

As shown in the previous section, for all $n\le 19478780533$ , the stopping time is equal to the coefficient stopping time. If $\sigma \left(s\right)=n$ , the coefficient of $s$ in (1), $\frac{3^{r_n}}{2^n}$ , is less than 1.

If $n$ is such that:

$2^{n-1}<3^{r_n}<2^n<2^{n+1}<3^{r_n+1},$

and we assume that the first iterate with a coefficient of $s$ less than 1 is $n+1$ , then $\frac{3^{r_{n+1}}}{2^{n+1}}<1$ , and for all $p<n+1$ , we have $\frac{3^{r_p}}{2^p}>1$ .

We distinguish two cases:

• If the previous iterate was odd, then $r_n=r_{n+1}-1$ , and $\frac{3^{r_n}}{2^n}<\frac{3^{r_{n+1}}}{2^{n+1}}<1$ .

• If the previous iterate was even, then $r_n=r_{n+1}$ , and $\frac{3^{r_n}}{2^n}<1$ , since by our hypothesis $3^{r_n}<2^n<2^{n+1}$ .

This contradicts the hypothesis $\sigma \left(s\right)=n+1$ .

Thus, we have justified why certain integer values cannot correspond to stopping times. Now, we can express the arithmetic function that generates all stopping time values:

$2^{n-1}<3^r<2^n\iff \left(n-1\right)\ln 2<r\ln 3<n\ln 2\iff n=\lfloor r{\log }_{2}3+1\rfloor$

We can also deduce that if $n$ is a stopping time value, the number of odd iterates $r$ satisfies $r=\lfloor \frac{n}{{\log }_{2}3}\rfloor$ .

Lemma 4.6. The density function $\frac{\pi \left(2^n\right)}{2^n}$ is an increasing function of $n$ and satisfies for all $n\le 19478780533$ :

${\displaystyle \sum }_{r=0}^{r\left(n\right)}\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}=\frac{\pi \left(2^n\right)}{2^n}<1,$

where $z_{p\left(r\right)}=h_{p\left(r\right)}\left(p\left(r\right)\right)$ . Moreover, the density function $\frac{S\left(n\right)}{2^n}$ is a decreasing function and satisfies:

$0<\frac{S\left(n\right)}{2^n}=1-{\displaystyle \sum }_{r=0}^{r\left(n\right)}\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}<1.$

Proof. We can express ${\displaystyle {\sum }_{r=0}^{\infty }{h}_n\left(p\left(r\right)\right)}$ since this power series has at most $2^n$ strictly positive terms.

By Lemma (4.3), we have established that for all $p<n$ :

$h_n\left(p\right)\ge 2^{n-p}{h}_p\left(p\right),$

which implies:

$2^n\ge \pi \left(2^n\right)={\displaystyle \sum }_{r=0}^{r\left(n\right)}{h}_n\left(p\left(r\right)\right)={\displaystyle \sum }_{r=0}^{r\left(n\right)}{2}^{n-p}{h}_p\left(p\right)>0\iff 1>\frac{\pi \left(2^n\right)}{2^n}={\displaystyle \sum }_{r=0}^{r\left(n\right)}\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}>0.$ (9)

This equation means that $\pi \left(2^n\right)$ is fully determined by the numbers $h_p\left(p\right)$ of integers s modulo [2^p] such that $\sigma \left(s\right)=p$ for all $p\le n$

Additionally, we have:

$0<S\left(n\right)=2^n-\pi \left(2^n\right)=2^n-{\displaystyle \sum }_{r=0}^{r\left(n\right)}\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}$

which leads to:

$0<\frac{S\left(n\right)}{2^n}=1-{\displaystyle \sum }_{r=0}^{r\left(n\right)}\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}.$ (10)

Therefore, $\frac{\pi \left(2^n\right)}{2^n}$ is an increasing function bounded by 1, and $\frac{S\left(n\right)}{2^n}$ is a decreasing function bounded by 0.

In the next section, we are going to build an exact formulation of $z_n$ for all $n\le 19478780533$ .

Definition 4.4 Let $P\left(N\right)$ be the property:

$P\left(N\right)$ : For all integers $n\le N$ and all $s<2^n$ such that $\sigma \left(s\right)=n$ , we have $\sigma \left(s\right)=\omega \left(s\right)$ .

Remark This property is true for all $N\le 19478780533$ thanks to our results in section 3.

Theorem 4.7. The property $P\left(N\right)$ holds for all $N\in {\mathbb{N}}^{+}$ .

Proof. Although Section 3 establishes that the equality $\sigma \left(s\right)=\omega \left(s\right)$ holds for all $s<2^n$ with $n\le 19478780533$ , our goal here is to show that this is not a strict upper bound. We first explicitly verify the case $n=19478780534$ , then generalize the result to all $n$ using strong induction.

We proceed by contradiction. Assume that there exists a positive integer $s<2^{N+1}$ such that $\sigma \left(s\right)=N+1$ and $\omega \left(s\right)=n<N+1$ .

If $s<2^n$ , then by assumption—valid for all $n\le N=19478780533$ —we must have $\sigma \left(s\right)=\omega \left(s\right)=n$ , which contradicts the assumption $\sigma \left(s\right)=N+1$ .

If $s>2^n$ , there exists an integer $m$ such that:

$s=2^n\cdot m+s^{\prime },\text{with}{s}^{\prime }<2^n.$

According to Lemma (4.1) and Corollary 4.2, we have shown that the two Syracuse sequences with starting numbers $s^{\prime }$ and $s=2^n\cdot m+s^{\prime }$ exhibit the same variations and follow the same sequence of coefficients in (2). This implies that:

$\omega \left(s^{\prime }\right)=\omega \left(s\right)=n.$

By assumption, since $s^{\prime }<2^n$ and $\sigma \left(s^{\prime }\right)=\omega \left(s^{\prime }\right)=n$ , and by applying Lemma (4.3), it follows that:

$\sigma \left(2^n\cdot m+s^{\prime }\right)=\sigma \left(s^{\prime }\right)=n.$

This leads to a contradiction. Therefore, property $\sigma \left(s\right)=\omega \left(s\right)$ also holds for $n=N+1$ . We therefore have extended the validity of the condition to all $n\le 19478780534$ . This reasoning can be iterated indefinitely for all subsequent values of $N$ , which corresponds to applying a strong (or total) induction argument, as presented below.

To begin the proof with strong induction, we know that the condition is true for small values of $N$ , due to the result of Section 3. And we will assume that it is true for all $n\le N$ , in other terms, for all $n\le N$ and for all integers $s<2^n$ such that $\sigma \left(s\right)=n$ , $\sigma \left(s\right)=\omega \left(s\right)$ . We will prove that it is true for $n=N+1$ .

We proceed by contradiction. Assume that there exists a positive integer $s<2^{N+1}$ such that $\sigma \left(s\right)=N+1$ and $\omega \left(s\right)=n<N+1$ .

If $s<2^n$ , then by assumption—valid for all $n\le N$ —we must have $\sigma \left(s\right)=\omega \left(s\right)=n$ , which contradicts the assumption $\sigma \left(s\right)=N+1$ .

If $s>2^n$ , there exists an integer $m$ such that:

$s=2^n\cdot m+s^{\prime },\text{with}{s}^{\prime }<2^n.$

According to Lemma (4.1) and Corollary 4.2, we have shown that the two Syracuse sequences with starting numbers $s^{\prime }$ and $s=2^n\cdot m+s^{\prime }$ exhibit the same variations and follow the same sequence of coefficients in (2). This implies that:

$\omega \left(s^{\prime }\right)=\omega \left(s\right)=n.$

By assumption, since $s^{\prime }<2^n$ and $\sigma \left(s^{\prime }\right)=\omega \left(s^{\prime }\right)=n$ , and by applying Lemma (4.3), it follows that:

$\sigma \left(2^n\cdot m+s^{\prime }\right)=\sigma \left(s^{\prime }\right)=n.$

This leads to a contradiction. Finally, property $\sigma \left(s\right)=\omega \left(s\right)=N$ also holds for all integers $s\in {\mathbb{N}}^{+}$ .

We have finally proven that the stopping time is equal to the stopping time coefficient for all positive integers.

We now establish a key logical consequence of the equality between stopping time and coefficient stopping time, showing that it implies the non-existence of non-trivial cycles.

Theorem 4.8. If, for all positive integers $s$ , the Stopping Time is equal to the Coefficient Stopping Time, $\sigma \left(s\right)=\omega \left(s\right)$ , then No Non-Trivial Cycles exist.

Proof. We now revisit the reasoning of Lynn E. Garner in his foundational 1981 work. He shows that if a non-trivial cycle of length $N$ exists, then it is necessarily the case that there exists at least one element in the cycle for which the stopping time cannot be equal to the coefficient stopping time.

Indeed, let us consider the integer $s$ representing the minimum value in the cycle. Since the cycle has length $N$ , we have $T^N\left(s\right)=s$ , which implies $\omega \left(s\right)=N$ .

If $\sigma \left(s\right)$ exists, it must by definition satisfy $\sigma \left(s\right)>\omega \left(s\right)$ , since the sequence returns to $s$ only after $N$ steps, without reaching 1 in fewer steps. This contradicts the assumption that $s$ is the smallest element in the cycle.

Therefore, as long as $\sigma \left(s\right)=\omega \left(s\right)$ , no non-trivial cycles can exist.

From the previous theorem, in which we proved that $\sigma \left(s\right)=\omega \left(s\right)$ for all $s\in {\mathbb{N}}^{+}$ , we can thus conclude that no non-trivial cycles exist in the Collatz dynamics.

Remark Since the equality $\sigma \left(s\right)=\omega \left(s\right)$ has now been proven for all $s\in {\mathbb{N}}^{+}$ , all previously established lemmas (e.g., Lemma 4.5, Lemma 4.6) are no longer restricted to $n<19478780533$ , but hold for all values of $n\in \mathbb{N}$ .

5. The Stopping Time Counting Function

5.1. Theoritical Approach

Definition 5.1. The Stopping Time Counting Function is an arithmetic function that, for every integer $n$ , gives the number of residue classes modulo $2^n$ of the starting numbers of Syracuse sequences with a stopping time equal to $n$ :

$z\left(n\right)=\left\{s<2^n|\sigma \left(s\right)=n\right\}$

In the following, we shall use the notation $z_n$ .

Mike Winkler [2] (2017) was the first mathematician to describe the stopping Time Counting Function. He stated that the number $z_r$ of residue classes modulo $2^{{\sigma }_r}$ for starting numbers $s$ with a finite stopping time $\sigma \left(s\right)={\sigma }_r$ , where ${\sigma }_r=\lfloor r{\log }_{2}3+1\rfloor$ , satisfies the following equation:

$z_r=\frac{\left(m+r-2\right)!}{m!\cdot \left(r-2\right)!}-{\displaystyle \sum }_{i=2}^{r-1}\left(\begin{array}{c}\lfloor \frac{3\left(r-i\right)+\delta }{2}\rfloor \\ r-i\end{array}\right)\cdot z_i,\text{with}m=\lfloor \left(r-1\right){\log }_{2}3-\left(r-1\right)\rfloor ,$ (11)

where $\delta$ can take different values modulo 3. However, Mike Winkler notes that estimating this value is complex and his work provides a computational code limited to the first 50 values of $z_r$ .

In this section, we propose an exact formulation of the stopping-time counting function by slightly modifying the approach suggested by Mike Winkler. Before presenting our formulation of this counting function, we introduce a set of useful properties of the Syracuse sequences.

In our work, instead of using $z_r$ , we use $z_{n\left(r\right)}=h_{n\left(r\right)}\left(n\left(r\right)\right)$ , where $n\left(r\right)=\lfloor r{\log }_{2}3+1\rfloor$ . This represents the number of modulo residue classes $2^{n\left(r\right)}$ for the starting numbers $s$ such that $\sigma \left(s\right)=n$ . In this section, we propose a new formulation of the Winkler formula that is independent of the parameter $\delta$ , allowing us to compute the exact values of $z_r$ for any $r$ . In Winkler’s original formula, $r$ denotes the number of odd integers in the Syracuse integer sequence up to ${\sigma }_r$ iterations. We introduce a new definition: $z_n$ , the number of modulo residue classes $2^n$ for Syracuse sequences with starting numbers $s$ such that $\sigma \left(s\right)=n$ . This new definition enables us to reformulate $z_n$ as follows.

But before presenting our formulation of the stopping Time Counting Function, we need to introduce a preliminary concept that is highly useful for understanding this formulation, the notion of sequence of transition of the coefficients, associated with a Syracuse sequence.

Definition 5.2. A transition sequence, associated with a Syracuse sequence starting from a positive integer $s$ , is a sequence consisting of the multiplicative coefficients of $s$ at each iteration: $\frac{3}{2}$ if the previous term is odd and $\frac{1}{2}$ otherwise. More formally, if $T_n\left(s\right)=\left\{T^k\left(s\right)|k\le n\right\}=\left\{s,T\left(s\right),\cdots ,T^n\left(s\right)\right\}$ is a finite Syracuse subsequence, the associated transition subsequence is defined as

$T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}$

where $t_i=\frac{3}{2}$ if $T^{i-1}\left(s\right)$ is odd, and $t_i=\frac{1}{2}$ if $T^{i-1}\left(s\right)$ else

Lemma 5.1. Given a Syracuse subsequence $T_n\left(s\right)=\left\{T^k\left(s\right)|k\le n\right\}=\left\{s,T\left(s\right),\cdots ,T^n\left(s\right)\right\}$ and its associated transition sequence $T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}$ , we can express $c_n\left(s\right)={\displaystyle {\sum }_{i=1}^r{3}^{r-i}{2}^{n-\left({\alpha }_i+\cdots +{{\alpha }^{\prime }}_r\left(n\right)\right)}}$ , presented in the diophantine equation (2), in terms of $t_i$ as follows:

$c_n\left(s\right)=\frac{2^n}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j.$

Proof. The proof is carried out by induction. Since we systematically start with an odd number—because if the first term of the sequence is even, we begin with a division by 2—then.

$c_1\left(s\right)=\frac{2^1}{3}{\displaystyle \sum }_{i=1}^{r=1}{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^1{t}_j=1.$

Now, suppose that the expression

$c_n\left(s\right)=\frac{2^n}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{l}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j$

holds for $n$ , and let us show that it also holds for $n+1$ .

We have two cases to consider:

The first case occurs when the transition sequence with $n+1$ elements is obtained by adding the term $t_{n+1}=\frac{1}{2}$ to $T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}$ . In this case, we have

$c_{n+1}\left(s\right)=c_n\left(s\right)=\frac{2^n}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j=\frac{2^{n+1}}{3}{\displaystyle \sum }_{i=1}^r\frac{1}{2}\cdot {\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j.$

As $t_{n+1}=\frac{1}{2}$ , then

$c_{n+1}\left(s\right)=\frac{2^{n+1}}{3}{\displaystyle \sum }_{i=1}^r{t}_{n+1}\cdot {\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j=\frac{2^{n+1}}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^{n+1}{t}_j$

The second case occurs when the transition sequence with $n+1$ elements is obtained by adding the term $t_{n+1}=\frac{3}{2}$ to $T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}$ . In this case, we have

$c_{n+1}\left(s\right)=3\cdot c_n\left(s\right)+2^n=3\cdot \frac{2^n}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j+2^n=\frac{2^{n+1}}{3}\cdot \left({\displaystyle \sum }_{i=1}^r\frac{3}{2}\cdot {\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j+\frac{3}{2}\right).$

As $t_{n+1}=\frac{3}{2}$ , then

In conclusion, we can say that $c_n\left(s\right)$ is fully defined by the terms $t_i$ of the transition sequence.

Lemma 5.2. Given three positive integers $n,r,c$ , the Diophantine equation

$2^{n}y-3^{r}s=c$

admits a unique solution for $\left(y,s\right)$ such that $y<3^r$ and $s<2^n$ .

Proof. By Bachet-Bézout’s theorem, since $2^n$ and $3^r$ are co-prime, the equation

$2^n{y}^{\prime }-3^r{s}^{\prime }=1$

admits infinitely many integer solutions. Among these, there exists a unique pair $\left(y^{\prime },s^{\prime }\right)$ such that:

$0\le y^{\prime }<3^r\text{and}0\le s^{\prime }<2^n.$

Now, consider the original equation:

$2^{n}y-3^{r}s=c.$

Multiplying the solution $\left(y^{\prime },s^{\prime }\right)$ by $c$ , we obtain a particular solution:

$y=c{y}^{\prime },s=c{s}^{\prime }.$

Since this may not satisfy the desired bounds, we introduce an integer $k$ such that:

$y=c{y}^{\prime }-k{3}^r,s=c{s}^{\prime }-k{2}^n.$

The appropriate choice of $k$ is given by:

$k=\lfloor \frac{c{y}^{\prime }}{3^r}\rfloor .$

This ensures:

$0\le y<3^r\text{and}0\le s<2^n.$

Since the construction of $y$ and $s$ depends uniquely on $c,n$ and $r$ , this solution is unique.

Consider the case $\sigma \left(s\right)=8$ , we use the same approach instead of checking all odd integers less than 2⁸. The solution $\left(s^{\prime },y^{\prime }\right)$ of the reduced Diophantine equation $2^8{y}^{\prime }-3^5{s}^{\prime }=1$ , using the Bachet-Bézout algorithm, is $\left(187,197\right)$ . The transition sequences $T{r}_8\left(s\right)$ satisfying (14) and their corresponding $c$ values are:

$T{r}_8\left(s_1\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2}\right\},c=251,$

$T{r}_8\left(s_2\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2},\frac{3}{2},\frac{1}{2}\right\},c=259,$

$T{r}_8\left(s_3\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2}\right\},c=211$ (highest trajectory before stopping time),

$T{r}_8\left(s_4\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{1}{2}\right\},c=319$ (lowest trajectory before stopping time),

$T{r}_8\left(s_5\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2}\right\},c=227,$

$T{r}_8\left(s_6\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{1}{2}\right\},c=283,$

$T{r}_8\left(s_7\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2}\right\},c=287.$

The corresponding solutions are:

For $c=251$ : $s_1=2^8\left(\frac{c{s^{\prime }}_1}{2^8}-\frac{c{y^{\prime }}_1}{3^5}\right)=39$ , $y_1=38$ .

For $c=259$ : $s_2=2^8\left(\frac{c{s^{\prime }}_2}{2^8}-\frac{c{y^{\prime }}_2}{3^5}\right)=79$ , $y_2=76$ .

For $c=211$ : $s_3=2^8\left(\frac{c{s^{\prime }}_3}{2^8}-\frac{c{y^{\prime }}_3}{3^5}\right)=95$ , $y_3=91$ .

For $c=319$ : $s_4=2^8\left(\frac{c{s^{\prime }}_4}{2^8}-\frac{c{y^{\prime }}_4}{3^5}\right)=123$ , $y_4=118$ .

For $c=227$ : $s_5=2^8\left(\frac{c{s^{\prime }}_5}{2^8}-\frac{c{y^{\prime }}_5}{3^5}\right)=175$ , $y_5=167$ .

For $c=283$ : $s_6=2^8\left(\frac{c{s^{\prime }}_6}{2^8}-\frac{c{y^{\prime }}_6}{3^5}\right)=199$ , $y_6=190$ .

For $c=287$ : $s_7=2^8\left(\frac{c{s^{\prime }}_7}{2^8}-\frac{c{y^{\prime }}_7}{3^5}\right)=219$ , $y_7=209$ .

Thus, we obtain the set of 7 integers modulo 2⁸ with stopping time $\sigma \left(s\right)=8$ : $\left\{39,79,95,123,175,199,219\right\}$ . We have efficiently determined these values without checking all 2⁸ integers, which is even more beneficial for larger $n$ .

Another example: Consider $n=16$ and the transition sequence $T{r}_{16}\left(s\right)=\left\{\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2}\right\}$ , which satisfies (14) for $n=16$ :

Using the Bachet-Bézout algorithm, we solve $2^{16}{y}^{″}-3^{10}{s}^{″}=1$ and find $\left(y^{\prime },s^{″}\right)=\left(52222,57959\right)$ . We then solve $2^{16}{y}^{\prime }-3^{10}{s}^{\prime }=c$ , where

$c=\frac{2^{16}}{3}{\displaystyle \sum }_{i=1}^8{\displaystyle \prod }_{j=i\text{if}{t}_j=\frac{3}{2}}^{16}{t}_j=131405.$

The final values are:

$y=c{y}^{\prime }-\lfloor \frac{c{y}^{\prime }}{3^{10}}\rfloor 3^{10}=29522\text{and}s=c{s}^{\prime }-\lfloor \frac{c{y}^{\prime }}{3^{10}}\rfloor 2^{16}=32763.$

We can check that $s=32763$ yields $T^{16}\left(s\right)=29522$ , confirming that $\sigma \left(s\right)=16$ .

Lemma 5.3. There exists a bijection between the set of Syracuse subsequences of length $n$ , $T_n\left(s\right)$ , and the set of transition sequences $T{r}_n\left(s\right)$ .

Proof. Given a positive integer $s$ , consider the subsequence generated by $s$ consisting of the first $n$ iterates, denoted by $T_n\left(s\right)$ . By construction, there exists a unique transition sequence $T{r}_n\left(s\right)$ which records the sequence of coefficients $t_i$ corresponding to the parity of each iterate.

Conversely, suppose we are given a transition sequence consisting of $r$ terms $t_i=\frac{3}{2}$ and $n-r$ terms $t_j=\frac{1}{2}$ . The value $c$ associated to this transition sequence is given by:

$c=\frac{2^n}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j.$

According to Lemma 5.2, there exists a unique integer $s<2^n$ satisfying the Diophantine equation:

$2^{n}y-3^{r}s=c.$

This $s$ uniquely generates a subsequence $T_n\left(s\right)$ whose associated transition sequence is exactly the given one. Therefore, the mapping is bijective.

Theorem 5.4. For every positive integer $n$ such that all positive integers $s<2^n$ with stopping time $\sigma \left(s\right)=n$ satisfy the condition $\sigma \left(s\right)=\omega \left(s\right)$ , then the number of residue classes modulo $2^n$ of integers $s$ such that $\sigma \left(s\right)=n$ is given by the following expression:

$z_n=h_n\left(n\right)=\left(\begin{array}{c}n\\ r\left(n\right)\end{array}\right)-{\displaystyle \sum }_{i=1}^{n-1}\left(\begin{array}{c}n-i\\ r-r\left(i\right)\end{array}\right)\cdot z_i$ (12)

with $z_1=1$ , and $n\left(i\right)=\lfloor i\cdot {\log }_2\left(3\right)+1\rfloor$ , for $i\in \mathbb{N}$ .

Proof. The main idea developed in this proof is to find the easiest way to count the number of positive integers $s<2^n$ , starting number of suracuse sequences, which have a stopping time $\sigma \left(s\right)=n$ .

Our proof of (6.4) relies on understanding the link between Syracuse sub-sequences $T_n\left(s\right)$ and their corresponding transition sequences $T{r}_n\left(s\right)$ . We have shown that there is a one-to-one correspondence between the set of sub-sequences $T_n\left(s\right)$ and the set of transition sequences $T{r}_n\left(s\right)$ . Afterward, we will demonstrate that it is easier to count the transition sequences corresponding to Syracuse sequences of starting number $s$ , such that $\sigma \left(s\right)=n$ .

For any integer $s$ , the corresponding sequence of transitions $T{r}_n\left(s\right)$ is associated by construction with a Syracuse sub-sequence $T_n\left(s\right)$ . The reverse is also true, which we will prove in the following. Our transition sequences are similar to parity vectors used in various studies of the Collatz problem.

Given a transition sequence $T{r}_n(.)$ , and thanks to the results of Lemmas 6.1, 6.2, and 6.3, we know that there is a unique solution to the following Diophantine equation:

$2^{n}y-3^{r}s=c,\text{where}c=c_n\left(s\right)={\displaystyle \sum }_{i=1}^r{3}^{r-i}{2}^{n-\left({\alpha }_i+\cdots +{{\alpha }^{\prime }}_r\left(n\right)\right)}=\frac{2^n}{3}{\displaystyle \sum }_{i=1}^r{\displaystyle \prod }_{\begin{array}{c}j=i\\ t_j=\frac{3}{2}\end{array}}^n{t}_j.$ (13)

This implies that for each integer $s$ , the starting number of a Syracuse sequence, there exists one and only one transition sequence, and conversely.

Now, we focus on the transition sequences $T{r}_n\left(s\right)$ for integers $s$ with $\sigma \left(s\right)=n$ . As we specified that we will consider the values of n such that $\sigma \left(s\right)=\omega \left(s\right)=n$ , it implies that We have to study and count all sequences of transitions $T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}$ satisfying:

${\displaystyle \prod }_{j=1}^n{t}_j<1\text{and}\text{for}\text{all}k<n,{\displaystyle \prod }_{j=1}^k{t}_j>1,\text{with}{t}_j\in \left\{\frac{1}{2},\frac{3}{2}\right\}.$ (14)

If $\sigma \left(s\right)=n$ , by definition: $T^n\left(s\right)=\frac{3^r}{2^n}s+c_n\left(s\right)<s<T^k\left(s\right)=\frac{3^{r\left(k\right)}}{2^k}s+c_k\left(s\right)$ for $k<n$ . Thanks to the main theorem by Lynn E. Garner [1] and Lemma 2.3, for all $\sigma \left(s\right)=n<19478780533$ , the stopping time $n$ corresponds to the first iterate where $\frac{3^{r\left(n\right)}}{2^n}<1$ , which has been extended to any integer n through Theorem 4.7. This implies:

${\displaystyle \prod }_{j=1}^n{t}_j=\frac{3^{r\left(n\right)}}{2^n}<1\text{and}\text{for}\text{all}k<n,{\displaystyle \prod }_{j=1}^k{t}_j=\frac{3^{r\left(k\right)}}{2^k}>1.$

Thus, for each transition sequence $T{r}_n\left(s\right)$ that satisfies these conditions, there is a unique solution $\left(s,y\right)$ to the Diophantine equation $2^{n}y-3^{r}s=c$ , where $c$ is defined in (13) and $r=\lfloor \frac{n}{{\log }_{2}3}\rfloor$ . Here, $y=T^n\left(s\right)<s<2^n$ , $y<3^r$ , and $\sigma \left(s\right)=n$ .

As stated in Lemma (4.5), if $s$ is a starting number such that $\sigma \left(s\right)=n$ , then the transition sequence $T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}$ contains exactly $r=\lfloor \frac{n}{{\log }_{2}3}\rfloor$ elements of $\frac{3}{2}$ and $n-r$ elements of $\frac{1}{2}$ , ensuring that ${\displaystyle {\prod }_{j=1}^n{t}_j}<1$ and ${\displaystyle {\prod }_{j=1}^i{t}_j}>1$ for all $i<n$ . The quantity $z_n$ is precisely the number of transition sequences $T{r}_n\left(s\right)$ that satisfy (14).

The number of combinations of $r$ elements of $\frac{3}{2}$ and $n-r$ elements of $\frac{1}{2}$ is $\left(\begin{array}{c}n\\ r\left(n\right)\end{array}\right)$ , where $r\left(n\right)=\lfloor \frac{n}{{\log }_2\left(3\right)}\rfloor$ .

We must subtract the number of Syracuse sequences with stopping times less than $n$ .

For all $i<n$ , the number of sequences of transition $T{r}_i\left(s\right)=\left\{t_1,\cdots ,t_i\right\}$ satisfying:

${\displaystyle \prod }_{j=1}^{j=i}{t}_j<1\text{and}{\displaystyle \prod }_{j=1}^{j=l}{t}_j>1\text{for}\text{all}l<i$

given by

$\left(\begin{array}{c}n-i\\ r\left(n\right)-r\left(i\right)\end{array}\right)z_i$

Thus, summing on all $0<i<n$ the following sum:

${\displaystyle \sum }_{i=1}^{r-1}\left(\begin{array}{c}n-i\\ r\left(n\right)-r\left(i\right)\end{array}\right)z_i$

This yields the final expression of the Stopping Time counting function available, for all $n<19478780533$ according to the main Garner’s theorem and lemma 4.1 and mre generally for all n according to our theorem 4.7:

$z_n=h_n\left(n\right)=\left(\begin{array}{c}n\\ r\left(n\right)\end{array}\right)-{\displaystyle \sum }_{i=1}^{n-1}\left(\begin{array}{c}n-i\\ r-r\left(i\right)\end{array}\right)\cdot z_i$

We have provided an exact formulation of the counting function for the set of integers $s$ in $Z/2^{n}Z$ that have a finite stopping time $\sigma \left(s\right)=n$ .

We compute below the first numbers of integers $s<2^n$ such that $\sigma \left(s\right)=n$ .

$z_1=\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)$

$z_2=\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_1=1$

$z_3=\left(\begin{array}{l}3\hfill \\ 1\hfill \end{array}\right)-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_2=0$

$z_4=\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_3=1$

$z_5=\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)-\left(\begin{array}{l}4\hfill \\ 3\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_4=2$

$z_6=\left(\begin{array}{l}6\hfill \\ 3\hfill \end{array}\right)-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}3\hfill \\ 1\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_5=0$

$z_7=\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_6=3$

$z_8=\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)-\left(\begin{array}{l}7\hfill \\ 5\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}4\hfill \\ 3\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_6-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_7=7$

$\begin{array}{c}{z}_9=\left(\begin{array}{l}9\hfill \\ 5\hfill \end{array}\right)-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}6\hfill \\ 3\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}3\hfill \\ 1\hfill \end{array}\right)\cdot z_6\\ -\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_8\\ =0\end{array}$

$\begin{array}{c}{z}_{10}=\left(\begin{array}{c}10\\ 6\end{array}\right)-\left(\begin{array}{l}9\hfill \\ 6\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_6\\ -\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_9\\ =12\end{array}$

$\begin{array}{c}{z}_{11}=\left(\begin{array}{c}11\\ 6\end{array}\right)-\left(\begin{array}{c}10\\ 6\end{array}\right)\cdot z_1-\left(\begin{array}{l}9\hfill \\ 5\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}8\hfill \\ 4\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}6\hfill \\ 3\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}5\hfill \\ 2\hfill \end{array}\right)\cdot z_6\\ -\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}3\hfill \\ 1\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}2\hfill \\ 0\hfill \end{array}\right)\cdot z_9-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_{10}\\ =0\end{array}$

$\begin{array}{c}{z}_{12}=\left(\begin{array}{c}12\\ 7\end{array}\right)-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_1-\left(\begin{array}{c}10\\ 6\end{array}\right)\cdot z_2-\left(\begin{array}{l}9\hfill \\ 5\hfill \end{array}\right)\cdot z_3-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}6\hfill \\ 3\hfill \end{array}\right)\cdot z_6\\ -\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}3\hfill \\ 1\hfill \end{array}\right)\cdot z_9-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_{10}-\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)\cdot z_{11}\\ =30\end{array}$

$\begin{array}{c}{z}_{13}=\left(\begin{array}{c}13\\ 8\end{array}\right)-\left(\begin{array}{c}12\\ 8\end{array}\right)\cdot z_1-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_2-\left(\begin{array}{c}10\\ 6\end{array}\right)\cdot z_3-\left(\begin{array}{l}9\hfill \\ 6\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_6\\ -\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_9-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_{10}-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_{11}-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_{12}\\ =85\end{array}$

We can see that this formulation of the Stopping time counting function give $z_n=0$ for the integers $n$ which cannot be a stopping time value. to stopping time, in other words, where $z_n=0$ .

Theorem 5.5. For every integer $n$ and if all integers $s<2^n$ such that σ(s) = n satisfy the condition $\sigma \left(s\right)=\omega \left(s\right)$ , then the number of residue classes modulo $2^n$ of integers $s$ such that $\sigma \left(s\right)=n$ is given by the following expression:

$z_{n\left(r\right)}=h_{n\left(r\right)}\left(n\left(r\right)\right)=\left(\begin{array}{c}n\left(r\right)\\ r\end{array}\right)-{\displaystyle \sum }_{i=0}^{r-1}\left(\begin{array}{c}n\left(r\right)-n\left(i\right)\\ r-i\end{array}\right)z_{n\left(i\right)}$ (14)

with $z_1=1$ , and $r\left(i\right)=\lfloor \frac{i}{{\log }_2\left(3\right)}\rfloor$ , for $i\in \mathbb{N}$ .

This formulation corresponds to a new indicial referential, the sum is done on the number of odd iterates and not on all iterates. The main difference is that this formulation only provides the value of $z_n$ for all $n$ which are a real stopping time. We detail in the following the expression of the first values of $z_n$ and observe that the coefficients of $z_n$ , where $n$ is a stopping time, are identical in both formulations of Theorems 6.4 and 6.5.

$z_1=1$

$z_2=\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_1=1$

$z_4=\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)-\left(\begin{array}{l}3\hfill \\ 1\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_2=2$

$z_5=\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)-\left(\begin{array}{l}4\hfill \\ 3\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_4=2$

$z_7=\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_5=3$

$z_8=\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)-\left(\begin{array}{l}7\hfill \\ 5\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}4\hfill \\ 3\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_7=7$

$z_{10}=\left(\begin{array}{c}10\\ 6\end{array}\right)-\left(\begin{array}{l}9\hfill \\ 6\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_8=12$

$\begin{array}{c}{z}_{12}=\left(\begin{array}{c}12\\ 7\end{array}\right)-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_1-\left(\begin{array}{c}10\\ 6\end{array}\right)\cdot z_2-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_7-\left(\begin{array}{l}4\hfill \\ 2\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_{10}\\ =30\end{array}$

$\begin{array}{c}{z}_{13}=\left(\begin{array}{c}13\\ 8\end{array}\right)-\left(\begin{array}{c}12\\ 8\end{array}\right)\cdot z_1-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_2-\left(\begin{array}{l}9\hfill \\ 6\hfill \end{array}\right)\cdot z_4-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_5-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_7\\ -\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_{10}-\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)\cdot z_{12}\\ =85\end{array}$

$\begin{array}{c}{z}_{15}=\left(\begin{array}{c}15\\ 9\end{array}\right)-\left(\begin{array}{c}14\\ 9\end{array}\right)\cdot z_1-\left(\begin{array}{c}13\\ 8\end{array}\right)\cdot z_2-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_4-\left(\begin{array}{c}10\\ 6\end{array}\right)\cdot z_5-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_7\\ -\left(\begin{array}{l}7\hfill \\ 4\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_{10}-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_{12}-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_{13}\\ =173\end{array}$

$\begin{array}{c}{z}_{16}=\left(\begin{array}{l}16\hfill \\ 10\hfill \end{array}\right)-\left(\begin{array}{l}15\hfill \\ 10\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{c}14\\ 9\end{array}\right)\cdot z_2-\left(\begin{array}{c}12\\ 8\end{array}\right)\cdot z_4-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_5-\left(\begin{array}{l}9\hfill \\ 6\hfill \end{array}\right)\cdot z_7\\ -\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_8-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_{10}-\left(\begin{array}{l}4\hfill \\ 3\hfill \end{array}\right)\cdot z_{12}-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_{13}-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_{15}\\ =476\end{array}$

$\begin{array}{c}{z}_{18}=\left(\begin{array}{l}18\hfill \\ 11\hfill \end{array}\right)-\left(\begin{array}{l}17\hfill \\ 11\hfill \end{array}\right)\cdot z_1-\left(\begin{array}{l}16\hfill \\ 10\hfill \end{array}\right)\cdot z_2-\left(\begin{array}{c}14\\ 9\end{array}\right)\cdot z_4-\left(\begin{array}{c}13\\ 8\end{array}\right)\cdot z_5-\left(\begin{array}{c}11\\ 7\end{array}\right)\cdot z_7\\ -\left(\begin{array}{c}10\\ 6\end{array}\right)\cdot z_8-\left(\begin{array}{l}8\hfill \\ 5\hfill \end{array}\right)\cdot z_{10}-\left(\begin{array}{l}6\hfill \\ 4\hfill \end{array}\right)\cdot z_{12}-\left(\begin{array}{l}5\hfill \\ 3\hfill \end{array}\right)\cdot z_{13}-\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)\cdot z_{15}-\left(\begin{array}{l}2\hfill \\ 1\hfill \end{array}\right)\cdot z_{16}\\ =961\end{array}$

5.2. Computational Results

We have applied (12) up to $n=76001$ (python code in Appendix B) and give in Table 2 the 60 first values of $z_n\left(r\right)$ . We have also verified the collatz conjecture for all positive integer below 2⁵⁰ and have also computed all histograms $H_n$ for all $n\le 50$ giving the counts of $h_n\left(p\right)$ and particularly the $h_n\left(n\right)$ the number of positive integer s lower than $2^n$ such that $\sigma \left(s\right)=n$ (python code in appendix A).

Table 2. First 60 values of the stopping time counting function.

$n$	$r\left(n\right)$	$z_n=h_n\left(n\right)$	$\frac{\pi \left(2^n\right)}{2^n}=1-\frac{S\left(n\right)}{2^n}$	$\frac{S\left(n\right)}{2^n}$
1	0	1	0.50000000	0.50000000
2	1	1	0.75000000	0.25000000
3	1	0	0.75000000	0.25000000
4	2	1	0.81250000	0.18750000
5	3	2	0.87500000	0.12500000
6	3	0	0.87500000	0.12500000
7	4	3	0.89843750	0.10156250
8	5	7	0.92578125	0.07421875
9	5	0	0.92578125	0.07421875
10	6	12	0.93750000	0.06250000
11	6	0	0.93750000	0.06250000
12	7	30	0.94482422	0.05517578
13	8	85	0.95520020	0.04479980
14	8	0	0.95520020	0.04479980
15	9	173	0.96047974	0.03952026
16	10	476	0.96774292	0.03225708
17	10	0	0.96774292	0.03225708
18	11	961	0.97140884	0.02859116
19	11	0	0.97140884	0.02859116
20	12	2652	0.97393799	0.02606201
21	13	8045	0.97777414	0.02222586
22	13	0	0.97777414	0.02222586
23	14	17,637	0.97987664	0.02012336
24	15	51,033	0.98291844	0.01708156
25	15	0	0.98291844	0.01708156
26	16	108,950	0.98454192	0.01545808
27	17	312,455	0.98686989	0.01313011
28	17	0	0.98686989	0.01313011
29	18	663,535	0.98810582	0.01189418
30	18	0	0.98810582	0.01189418
31	19	1,900,470	0.98899080	0.01100920
32	20	5,936,673	0.99037304	0.00962696
33	20	0	0.99037304	0.00962696
34	21	13,472,296	0.99115723	0.00884277
35	22	39,993,895	0.99232121	0.00767879
36	22	0	0.99232121	0.00767879
37	23	87,986,917	0.99296139	0.00703861
38	23	0	0.99296139	0.00703861
39	24	25,7978,502	0.99343065	0.00656935
40	25	820,236,724	0.99417666	0.00582334
41	25	0	0.99417666	0.00582334
42	26	1,899,474,678	0.99460855	0.00539145
43	27	5,723,030,586	0.99525918	0.00474082
44	27	0	0.99525918	0.00474082
45	28	12,809,477,536	0.99562325	0.00437675
46	29	38,036,848,410	0.99616378	0.00383622
47	29	0	0.99616378	0.00383622
48	30	84,141,805,077	0.99646271	0.00353729
49	30	0	0.99646271	0.00353729
50	31	248,369,601,964	0.99668331	0.00331669
51	32	794,919,136,728	0.99703633	0.00296367
52	32	0	0.99703633	0.00296367
53	33	1,857,112,329,035	0.99724251	0.00275749
54	34	5,636,545,892,795	0.99755540	0.00244460
55	34	0	0.99755540	0.00244460
56	35	1,273,2900,345,928	0.99773210	0.00226790
57	35	0	0.99773210	0.00226790
58	36	38,088,111,350,198	0.99786425	0.00213575
59	37	123,110,229,387,834	0.99807781	0.00192219
60	37	0	0.99807781	0.00192219

For $n=100$ , $\frac{S\left(n\right)}{2^n}\simeq 0.000225$ and $\theta \left(n\right)=\frac{{\log }_2\left(S\left(n\right)\right)}{n}\simeq 0.8788221262$ and $z_{100}=32053249939776775765443011$ .

For $n=405$ , $\frac{S\left(n\right)}{2^n}\simeq 9.68160440706356\text{E}-10$ and $\theta \left(n\right)=\frac{{\log }_2\left(S\left(n\right)\right)}{n}\simeq 0.9260641116$ and z₄₀₅ = 3,476,553,789,120,508,476,368,100,052,260,690,271,283,238,505,581,916,333,757,459,587,755,180,695,960,919,229,021,382,116,342,674,546,834,066,825,086.

For $n=76001$ , $\frac{S\left(n\right)}{2^n}\simeq 5.785339919\text{E}-1152$ and $\theta \left(n\right)=\frac{{\log }_2\left(S\left(n\right)\right)}{n}\simeq 0.949680546787772$ .

6. Asymptotic Density of Positive Integers with High Stopping Times

Thanks to (12), we have computed the values of the counting function $z_{n\left(r\right)}$ and of the density functions $\frac{\pi \left(2^n\right)}{2^n}$ , $\frac{S\left(n\right)}{2^n}$ up to $n=76001$ . The results presented in Figure 1 and Figure 2, which seems to confirm that $\theta \left(n\right)=\frac{{\log }_2\left(S\left(n\right)\right)}{n}$ tends to a constant value less than 1. A formal proof is provided below.

Figure 1. Function ${\log }_2\left(S\left(n\right)\right)$ .

Figure 2. Function $\theta \left(n\right)=\frac{{\log }_2\left(S\left(n\right)\right)}{n}$ .

These numerical results based on the application of the stopping time counting function illustrate that the above function asymptotically tends towards a constant which seems to be less than 0.95. We will formally confirm this result in the following theorem.

We aim to show that the density of integers $s\in \mathbb{N}$ whose stopping time satisfies $\sigma \left(s\right)\le n$ tends to 1 as $n\to \infty$ . This asymptotic behavior was first conjectured by Riho Terras [7] in 1976, and stronger forms were subsequently established by Jean-Paul Allouche [8] in 1978 and Yvan Korec [9] in 1994. In this work, we introduce a new approach based on the stopping-time counting function.

Theorem 6.1. As long as $\sigma \left(s\right)=\omega \left(s\right)$ for all $s<2^n$ such that $\sigma \left(s\right)=n$ , the percentage of residue classes mod $2^n$ of starting numbers $s$ such that $\sigma \left(s\right)>n$ , given by $\frac{S\left(n\right)}{2^n}$ , tends to 0 as $n$ approaches infinity. Moreover, there exists a constant $\theta <1$ such that $S\left(n\right)<2^{n\theta }$ for sufficiently large $n$ .

Proof. From (10) and Theoreme 4.7, we have

$S\left(n\right)=2^n\left(1-{\displaystyle \sum }_{r=1}^{r\left(n\right)}\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}\right)=2^n{\displaystyle \sum }_{r\left(n+1\right)}^{\infty }\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}.$

We seek an upper bound for the last term of the inequality above.

From (15), we have:

$z_{p\left(r\right)}=\left(\begin{array}{c}p\left(r\right)\\ r\end{array}\right)-{\displaystyle \sum }_{i=0}^{r-1}\left(\begin{array}{c}p\left(r\right)-p\left(i\right)\\ r-i\end{array}\right)\cdot z_{p\left(i\right)}\le \left(\begin{array}{c}p\left(r\right)\\ r\end{array}\right)$

Using the asymptotic Laplace approximation of the factorial, we have:

$n!~n^n{\text{e}}^{-n}\sqrt{2\pi n}\left(1+\frac{1}{12n}+\frac{1}{288n^2}-O\left(\frac{1}{n^3}\right)\right)$

We can derive an upper bound for $\left(\begin{array}{c}p\\ xp\end{array}\right)$ when $p$ is sufficiently large, $xp\in N$ , and $0<x<1$

$\left(\begin{array}{c}p\\ xp\end{array}\right)=\frac{p!}{\left(x\cdot p\right)!\cdot \left(p-x\cdot p\right)!},$

We substitute the three factorials with their asymptotic formula.

$\left(\begin{array}{c}p\\ xp\end{array}\right)\simeq \frac{\frac{p^p}{{\text{e}}^{-p}}\cdot \sqrt{2\text{Π}p}\cdot \left(1+\frac{1}{12p}+o\left(\frac{1}{p^2}\right)\right)}{\left(\frac{{\left(xp\right)}^{xp}}{{\text{e}}^{-xp}}\cdot \sqrt{2\pi xp}\cdot \left(1+\frac{1}{12xp}+o\left(\frac{1}{{\left(xp\right)}^2}\right)\right)\right)\cdot \left(\frac{{\left(\left(1-x\right)p\right)}^{\left(1-x\right)p}}{{\text{e}}^{\left(1-x\right)p}}\cdot \sqrt{2\pi \left(1-x\right)p}\cdot \left(1+\frac{1}{12\left(1-x\right)p}+o\left(\frac{1}{{\left(\left(1-x\right)p\right)}^2}\right)\right)\right)}$

Which can be significantly simplified to write:

$\left(\begin{array}{c}p\\ xp\end{array}\right)\simeq \frac{1}{\sqrt{2\pi x\left(1-x\right)p}}\cdot {\left(\frac{1}{x^x{\left(1-x\right)}^{1-x}}\right)}^p\cdot \left(1-\frac{A}{12p}+\frac{1}{2}\cdot {\left(\frac{A}{12p}\right)}^2+o\left(\frac{1}{p^3}\right)\right)$

with $A=\frac{1-x+x^2}{x\cdot \left(1-x\right)}$ . The last term $\left(1-\frac{A}{12p}+\frac{1}{2}\cdot {\left(\frac{A}{12p}\right)}^2+o\left(\frac{1}{p^3}\right)\right)$ is less than one for all $p$ . Finally, we can obtain the following upper bound;

$\left(\begin{array}{l}p\hfill \\ xp\hfill \end{array}\right)<a\cdot \frac{q^p}{\sqrt{p}}\text{where}a=\frac{1}{\sqrt{2\pi x\left(1-x\right)}}\text{and}q=\frac{1}{x^x{\left(1-x\right)}^{1-x}}\text{with}x=\frac{r}{p\left(r\right)}<\frac{\ln \left(2\right)}{\ln \left(3\right)}$

Effectively, since $p$ is a stopping time value and $r$ is the number of odd iterates, we have $r=\lfloor \frac{p}{{\log }_2\left(3\right)}\rfloor$ . Therefore, by definition of the floor function, it follows directly that $r<\frac{p}{{\text{log}}_2\left(3\right)}$ .

Moreover, if we study the variations of the following function which represent the main term of the above approximation of $\left(\begin{array}{c}p\\ xp\end{array}\right)$ :

$F_p\left(x\right)=\frac{1}{{\left(x^x{\left(1-x\right)}^{1-x}\right)}^p\sqrt{2\pi x\left(1-x\right)p}}$

As $F_p\left(x\right)=F_p\left(1-x\right)$ , this function is symmetric at $x=\frac{1}{2}$ and tends to $+\infty$ as $x\to 0$ or $x\to 1$ . There is a minimum at $x=\frac{1}{2}$ and $F$ is a strictly growing function between $\frac{1}{2}$ and 1. So we have:

$F_p\left(\frac{1}{2}\right)<F_p\left(\frac{r}{p\left(r\right)}\right)<F_p\left(\frac{\text{ln}\left(2\right)}{\text{ln}\left(3\right)}\right)$

which implies that

$z_{p\left(r\right)}<\left(\begin{array}{c}p\left(r\right)\\ r\end{array}\right)<a\frac{q^p}{\sqrt{p}}\text{where}a=\frac{1}{\sqrt{2\pi x\left(1-x\right)}}\text{and}q=\frac{1}{x^x{\left(1-x\right)}^{1-x}}\text{with}x=\frac{\text{ln}\left(2\right)}{\text{ln}\left(3\right)}$

We can give numerical values of these parameters: $x\simeq \frac{\text{log}\left(2\right)}{\text{log}\left(3\right)}\simeq 0.63093$ , $q\simeq 1.93181$ , and $a\simeq 0.82673$ .

And we finally obtain an upper bound of the density function:

$\frac{z_{p\left(r\right)}}{2^{p\left(r\right)}}<\frac{1}{2^p}\left(\begin{array}{c}p\\ r\end{array}\right)\simeq \frac{a}{\sqrt{p}}{\left(\frac{q}{2}\right)}^p\text{where}\frac{q}{2}\simeq 0.96591$ (16)

This result aligns with the upper bound discussed by Terence Tao [10] on his blog about the Collatz conjecture. Using (16), we derive an upper bound for (10):

$\frac{S\left(n\right)}{2^n}={\displaystyle \sum }_{i>r\left(n\right)}\frac{z_{p\left(i\right)}}{2^{p\left(i\right)}}<{\displaystyle \sum }_{j>n}\frac{z_j}{2^j}<{\displaystyle \sum }_{j>n}\frac{a}{\sqrt{j}}{\left(\frac{q}{2}\right)}^j<\frac{a}{\sqrt{n+1}}\cdot {\displaystyle \sum }_{j>n}\sqrt{\frac{n+1}{j}}{\left(\frac{q}{2}\right)}^j$

As $\sqrt{\frac{n+1}{j}}\le 1$ for all $j>n$ then:

$\frac{S\left(n\right)}{2^n}<\frac{a}{\sqrt{n+1}}\cdot {\displaystyle \sum }_{j>n}{\left(\frac{q}{2}\right)}^j=\frac{a}{\sqrt{n+1}}\cdot {\left(\frac{q}{2}\right)}^{n+1}{\displaystyle \sum }_{i\ge 0}{\left(\frac{q}{2}\right)}^j<\frac{C}{\sqrt{n+1}}{\left(\frac{q}{2}\right)}^{n+1}$

And finally

$\frac{S\left(n\right)}{2^n}<\frac{C}{\sqrt{n+1}}{\left(\frac{q}{2}\right)}^{n+1}\text{with}C=\frac{a}{1-q/2}\simeq 24.28$ (17)

We conclude that, as $\frac{S\left(n\right)}{2^n}>0$ and has an upperbound which tends to 0 when n tends to infinity, then:

$\underset{n\to \infty }{\text{lim}}\frac{S\left(n\right)}{2^n}=\underset{n\to \infty }{\text{lim}}\frac{C}{\sqrt{n+1}}{\left(\frac{q}{2}\right)}^{n+1}=0.$ (18)

Theorem 6.2. As long as $\sigma \left(s\right)=\omega \left(s\right)$ for all $s<2^n$ such that $\sigma \left(s\right)=n$ , there exists a constant $\theta <1$ such that $S\left(n\right)<2^{n\theta }$ for sufficiently large $n$ .

Proof. For sufficiently large $n$ , we are looking for a real number $0<\theta <1$ such that $S\left(n\right)<2^{n\theta }$ . According to the previous theorem and equation (17), we have the following bound:

$S\left(n\right)<\frac{C\cdot q^{n+1}}{2\sqrt{n+1}}.$

We seek $\theta$ satisfying:

$S\left(n\right)<\frac{C\cdot q^{n+1}}{2\sqrt{n+1}}<2^{n\cdot \theta }.$

Taking the base-2 logarithm of both sides of the two inequalities (which preserves the inequality since ${\text{log}}_2\left(x\right)$ is increasing), we are looking for $\theta$ which satisfy to:

${\log }_{2}S\left(n\right)<n\cdot {\log }_2\left(q\right)-\frac{{\log }_2\left(n+1\right)}{2}+{\log }_2\left(\frac{C\cdot q}{2}\right)<n\cdot \theta .$

Defining the arithmetic function:

$\theta \left(n\right)={\text{log}}_2\left(q\right)-\frac{{\text{log}}_2\left(n+1\right)}{2n}+\frac{{\text{log}}_2\left(\frac{C\cdot q}{2}\right)}{n},$

which is a monotonically increasing function for sufficiently large $n$ . It is clear that:

$\theta \left(n\right)\le {\text{log}}_2\left(q\right)\approx \mathrm{0.94996.}$

Since we have already verified numerically that $\theta \left(n\right)=\frac{{\text{log}}_2\left(S\left(n\right)\right)}{n}\approx 0.94968$ for $n=76001$ , it confirms the coherence of our estimation.

Therefore, for all $n>550$ , we can take:

$\theta ={\text{log}}_2\left(q\right)\approx 0.94996,$

such that the inequality $S\left(n\right)<2^{n\theta }$ holds, as supported by our computational results.

7. Highest and Lowest Trajectories before the Stopping Time Iterate

As we have seen in Section 3, the set of integers $s<2^n$ with a stopping time $\sigma \left(s\right)=n$ generates a set of trajectories of Syracuse sequences, from the starting number $s$ to the iterate at the stopping time. We will characterize the lowest and highest trajectories of this set. Specifically, we will show that the highest trajectory corresponds to the lowest value of $c=c_n\left(s\right)$ , as defined in (13), and the lowest trajectory corresponds to the highest value of $c$ .

Let $s$ be the starting number of a Syracuse sequence such that $\sigma \left(s\right)=n$ . We have seen that $\left(s,T^n\left(s\right)\right)$ is a solution of the Diophantine equation:

$2^n\cdot T^n\left(s\right)-3^r\cdot s=c_n\left(s\right),\text{where}r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor \text{and}c=c_n\left(s\right).$

We define:

$c_{n,\text{min}}=\underset{s<2^n,\sigma \left(s\right)=n}{\text{min}}{c}_n\left(s\right)\text{and}{c}_{n,\text{max}}=\underset{s<2^n,\sigma \left(s\right)=n}{\text{max}}{c}_n\left(s\right).$

First, we will derive the arithmetic function that gives $c_{n,\text{min}}$ as a function of $n$ . For each $n$ , the highest trajectory corresponding to $\sigma \left(s\right)=n$ is associated with a sequence of transitions $T{r}_n\left(s\right)$ , where the first $r$ terms are equal to $\frac{3}{2}$ and the last $n-r$ terms are equal to $\frac{1}{2}$ :

$T{r}_n\left(s\right)=\left\{t_1,\cdots ,t_n\right\}\text{where}{t}_i=\frac{3}{2}\text{for}1\le i\le r\text{and}{t}_i=\frac{1}{2}\text{for}r<i\le n.$

The Value of $c_n$ associated to the highest trajectory of the family of integer s such that $\sigma \left(s\right)=n$ is given by the following equation and we shall see in the next theorem that it corresponds to the minimum value of $c_n\left(s\right)$ :

$c_{n,\text{min}}={\displaystyle \sum }_{i=1}^r{3}^{\left(r-i\right)}\cdot 2^{\left(i-1\right)}=3^r-2^r.$ (19)

**Examples:**

1) For $\sigma \left(s\right)=7$ , the highest trajectory is obtained for $s=15$ , and the iterate at stopping time is $T^7\left(s\right)=10$ , which satisfies the Diophantine equation $2^7\cdot T^7\left(s\right)-3^4\cdot s=c$ with $c=3^4-2^4=65$ , the lowest value of $c$ .

2) For $\sigma \left(s\right)=8$ , the highest trajectory is obtained for $s=95$ , and the iterate at the stopping time is $T^8\left(s\right)=91$ , which satisfies the Diophantine equation $2^8\cdot T^8\left(s\right)-3^5\cdot s=c$ with $c=3^5-2^5=211$ , also the lowest value of $c$ .

To explicitly construct the lowest trajectory, we start from an integer $s<2^n$ such that $\sigma \left(s\right)=n$ , and look for a syracuse sequence corresponding to this trajectory. Like in a previous section, it appears more comfortable to use the transition sequence associated with the lowest syracuse sequence of stopping time equal to n. This transition sequence has to satisfy the following conditions:

$\text{for}\text{all}k<n,1<{\displaystyle \prod }_{j=1}^k{t}_j<2\text{or}\text{if}{\displaystyle \prod }_{j=1}^k{t}_j>2\text{then}{t}_{k+1}=\frac{1}{2}\text{and}{\displaystyle \prod }_{j=1}^n{t}_j<1$

Formalizing precisely this iterative construction, we find that the $r$ terms $t_j=\frac{3}{2}$ are exactly located:

$j=\left(i-1\right){\log }_2\left(3\right)+1,\text{for}1\le i\le r,\text{with}r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor$

Theorem 7.1. For all integers $s<2^n$ such that $\sigma \left(s\right)=n$ :

$c_{n,\text{max}}=\underset{s<2^n,\sigma \left(s\right)=n}{\text{max}}{c}_n\left(s\right)\text{exist}\text{and}{c}_{n,\text{max}}={\displaystyle \sum }_{i=1}^r{3}^{\left(r-i\right)}\cdot 2^{\lfloor \left(i-1\right){\text{log}}_2\left(3\right)\rfloor },\text{where}r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor .$ (20)

$c_{n,\text{min}}=\underset{s<2^n,\sigma \left(s\right)=n}{\text{min}}{c}_n\left(s\right)\text{exist}\text{and}{c}_{n,\text{min}}={\displaystyle \sum }_{i=1}^r{3}^{\left(r-i\right)}\cdot 2^{\left(i-1\right)}=3^r-2^r,\text{where}r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor .$ (21)

Proof. Any sequence of transitions corresponding to a Syracuse sequence starting from $s$ with $\sigma \left(s\right)=n$ contains $r$ terms equal to $\frac{3}{2}$ and $n-r$ terms equal to $\frac{1}{2}$ . It is easy to see that the highest trajectory corresponds to the sequence of transitions where $t_i=\frac{3}{2}$ for $i\le r$ . We are going to show that when we permute the two elements of this pattern $\frac{3}{2},\frac{1}{2}$ in a sequence of transition, keeping the stopping time unchanged, the value of $c_n\left(s\right)$ increases.

Consider two sequences of transitions with the same terms $t_i$ , except at positions $k$ and $k+1$ :

$T{r}_n\left(s_1\right)=\left\{t_i,1\le i\le n\right\}\text{with}{t}_k=\frac{3}{2}\text{and}{t}_{k+1}=\frac{1}{2},$

$T{r}_n\left(s_2\right)=\left\{t_i,1\le i\le n\right\}\text{with}{t}_k=\frac{1}{2}\text{and}{t}_{k+1}=\frac{3}{2}.$

Then:

$c_n\left(s_1\right)=\frac{2^n}{3}\left({\displaystyle \sum }_{i=1}^{k-1}{\displaystyle \prod }_{j=i\text{if}{t}_i=\frac{3}{2}}^n{t}_j+{\displaystyle \prod }_{j=k\text{as}{t}_k=\frac{3}{2}}^n{t}_j+{\displaystyle \sum }_{i=k+2}^n{\displaystyle \prod }_{j=i\text{if}{t}_i=\frac{3}{2}}^n{t}_j\right),$

$c_n\left(s_2\right)=\frac{2^n}{3}\left({\displaystyle \sum }_{i=1}^{k-1}{\displaystyle \prod }_{j=i\text{if}{t}_i=\frac{3}{2}}^n{t}_j+{\displaystyle \prod }_{j=k+1\text{as}{t}_{k+1}=\frac{3}{2}}^n{t}_j+{\displaystyle \sum }_{i=k+2}^n{\displaystyle \prod }_{j=i\text{if}{t}_i=\frac{3}{2}}^n{t}_j\right).$

The difference:

$c_n\left(s_2\right)-c_n\left(s_1\right)={\displaystyle \prod }_{j=k+1\text{as}{t}_{k+1}=\frac{3}{2}}^n{t}_j-{\displaystyle \prod }_{j=k\text{if}{t}_k=\frac{3}{2}}^n{t}_j=\frac{1}{2}{\displaystyle \prod }_{j=k+1\text{as}{t}_{k+1}=\frac{3}{2}}^n{t}_j>0,$

Which implies $c_n\left(s_2\right)>c_n\left(s_1\right)$ . This justifies that when we permute a pair $\left\{\frac{3}{2},\frac{1}{2}\right\}$ into $\left\{\frac{1}{2},\frac{3}{2}\right\}$ , the value of $c_n\left(s\right)$ increases. Since there are only a finite number of $s$ with $\sigma \left(s\right)=n$ , the maximum value $c_{n,\text{max}}$ is reached for a sequence defined as above. The highest trajectory, the r terms $\frac{3}{2}$ correspond to the r first terms of the sequence of transition and according to the above result provide the minimum value of $c_n\left(s\right)$ :

$c_{n,\text{min}}={\displaystyle \sum }_{i=1}^r{3}^{\left(r-i\right)}\cdot 2^{\left(i-1\right)}=3^r-2^r\text{where}r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor$

Starting from the sequence of transitions where the positions of the $i$ -th term $\frac{3}{2}$ are located at $\lfloor \left(i-1\right){\text{log}}_2\left(3\right)\rfloor +1$ , any permutation would result in a sequence with a stopping time lower than $n$ . And according to the above result provide the maximum value of $c_n\left(s\right)$ :

$c_{n,\text{max}}={\displaystyle \sum }_{i=1}^r{3}^{r-i}{2}^{\lfloor \left(i-1\right){\text{log}}_2\left(3\right)\rfloor }\text{where}r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor$

By construction, the lowest trajectory oscillates mainly between $s$ and $2s$ , and whenever an iterate at step $i<n$ exceeds $2s$ , the next iterate (at step $i+1$ ) is forced below $2s$ . If, in the associated transition sequence, we permute a pair $\left\{\frac{3}{2},\frac{1}{2}\right\}$ , the previous iterate would become less than s, which contradict the hypothesis that $\sigma \left(s\right)=n$ . In Table 3, we give the first values of $c_{n,\text{max}}$ .

Table 3. First values of c_n,max.

$n$	$c_{n,\text{max}}$	$n$	$c_{n,\text{max}}$
5	23	51	14,535,113,675,299,973
7	85	53	44,731,240,932,742,543
8	319	54	138,697,322,425,598,125
10	1085	56	425,099,166,531,535,367
12	3767	58	1,311,326,296,613,570,069
13	13,349	59	4,078,094,077,916,566,079
15	44,143	61	12,522,512,609,901,409,981
16	148,813	62	3,872,045,933,431,107,691
18	479,207	64	118,467,221,012,146,924,709
20	1,568,693	65	364,625,035,073,295,549,935
21	5,230,367	67	1,112,321,849,293,596,201,421
23	16,739,677	69	3,410,752,524,175,626,810,727
24	54,413,335	70	10,527,405,477,706,233,258,037
26	171,628,613	72	32,172,512,243,477,405,425,823
27	548,440,271	73	98,878,719,971,867,038,884,317
29	1,712,429,677	75	301,358,526,398,470,761,866,647
31	5,405,724,487	77	922,965,045,126,890,866,454,725
32	17,290,915,285	78	2,844,452,999,106,586,922,783,311
34	54,020,229,503	80	8,684,474,724,771,589,415,188,205
35	170,650,623,101	81	26,657,887,084,122,082,832,917,703
37	529,131,738,487	83	81,182,587,071,980,877,673,459,285
39	1,656,114,692,197	85	248,383,464,494,401,149,719,202,559
40	5,243,221,983,535	86	764,493,206,597,037,515,952,906,493
42	16,279,421,764,493	88	2,332,165,246,018,780,681,449,317,111
43	51,037,288,549,031	89	7,151,238,242,967,014,578,710,341,861
45	157,509,912,158,197	91	21,763,199,738,722,388,804,855,806,639
46	490,121,922,519,007	92	66,527,539,255,452,546,689,466,544,141
48	1,505,550,139,645,853	94	202,058,497,844,928,400,618,197,880,871
50	4,657,387,907,292,887	96	616,079,013,849,068,244,053,786,636,405

Lemma 7.2. $c_{n,\max }$ has an upper bound: $c_{n,\max }<r\cdot 3^{r-1}$

Proof. ach term in the above sum representing $c_{n,\text{max}}$ can be bounded above as follows:

$3^{r-i}{2}^{\lfloor \left(i-1\right){\log }_2\left(3\right)\rfloor }<3^{r-i}{2}^{\left(i-1\right){\log }_2\left(3\right)}=3^{r-i}{3}^{i-1}=3^{r-1}.$

Thus, $c_{n,\max }={\displaystyle \sum }_{i=1}^r{3}^{r-i}{2}^{\lfloor \left(i-1\right){\log }_2\left(3\right)\rfloor }<{\displaystyle \sum }_{i=1}^r{3}^{r-1}=r\cdot 3^{r-1}$ where $r=\lfloor \frac{n}{{\text{log}}_2\left(3\right)}\rfloor$

8. Conclusions

In this paper, we have established several important results regarding the link between stopping times and non-trivial cycles in Syracuse (Collatz) sequences:

1) We extended the work initiated by Lynn E. Garner (1981), who demonstrated that as long as the stopping time equals the coefficient stopping time, no non-trivial cycle can exist.

2) We revealed a particularly noteworthy property: two Syracuse sequences starting from integers $s$ and $2^n\cdot m+s$ exhibit exactly the same behavior up to the $n^{\text{th}}$ iterate.

3) Building on these initial findings, we proved rigorously that the stopping time always equals the coefficient stopping time. This result implies directly that non-trivial cycles cannot exist.

4) Furthermore, we provided an explicit formula for the stopping time counting function, giving the exact number $z_{n\left(r\right)}$ of positive integers $s<2^n$ with stopping time $\sigma \left(s\right)=n$ :

$z_n=\left(\begin{array}{c}n\\ r\left(n\right)\end{array}\right)-{\displaystyle \sum }_{i=1}^{n-1}\left(\begin{array}{c}n-i\\ r-r\left(i\right)\end{array}\right)\cdot z_i$

5) By combining these results, we demonstrated that the density of integers $s<2^n$ satisfying $\sigma \left(s\right)>n$ tends to zero as $n$ approaches infinity.

6) Lastly, we precisely characterized the Syracuse sequences corresponding to the highest and lowest trajectories associated with a given stopping time $\sigma \left(s\right)=n$ . We derived explicit arithmetic expressions for the corresponding parameters $c_{n,\text{min}}$ and $c_{n,\text{max}}$ .

These results collectively provide a deeper understanding of the intricate behavior and structure of Syracuse sequences, offering further insight into the validity and complexity of the Collatz conjecture.

Appendix

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Garner, L.E. (1981) On the Collatz 3n + 1 Algorithm. Proceedings of the American Mathematical Society, 82, 19-22.[CrossRef]
[2]	Winkler, M. (2017) New Results on the Stopping Time Behaviour of the Collatz 3x+1 Function. arXiv: 1504.00212. https://arxiv.org/abs/1504.00212
[3]	Barina, D. (2020) Convergence Verification of the Collatz Problem. The Journal of Supercomputing, 77, 2681-2688.[CrossRef]
[4]	e Silva, T. (1999) Maximum Excursion and Stopping Time Record-Holders for the Problem: Computational Results. Mathematics of Computation, 68, 371-384.[CrossRef]
[5]	Eliahou, S. (2011) Le problème 3n+1: Y a-t-il des cycles non triviaux? https://images-des-maths.pages.math.cnrs.fr/freeze/Le-probleme-3n-1-y-a-t-il-des-cycles-non-triviaux-III.html
[6]	Lagarias, J.C. (2011) The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society.
[7]	Terras, R. (1976) A Stopping Time Problem on the Positive Integers. Acta Arithmetica, 30, 241-252.[CrossRef]
[8]	Allouche, J.P. (1978) Sur la conjecture de ‘Syracuse-kakutani-collatz’. Séminaire de Théorie des Nombres de Bordeaux, 8, 1-16. http://eudml.org/doc/182044
[9]	Korec, Y. (1994) A Density Estimate for the 3x+1 Problem. Mathematica Slovaca, 44, 85-89. http://eudml.org/doc/32414
[10]	Tao, T. (2011) The Collatz Conjecture, Littlewood-Oxford Theory and Powers of 2 and 3. https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/