# The 3x+1 Problem: Existence of Cycles Under Assumption of Distance Between Odd Values

Adrien Prost-Boucle

<figure><img src="image_1.png" /></figure>

## To cite this version:

Adrien Prost-Boucle. The 3x+1 Problem: Existence of Cycles Under Assumption of Distance Between Odd Values. 2018. hal-01784043v2

HAL Id: hal-01784043

https://hal.science/hal-01784043v2

Preprint submitted on 16 May 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# The 3x+1 Problem: Existence of Cycles
Under Assumption of Distance Between Odd Values

Adrien Prost-Boucle

adrien.prost-boucle@laposte.net

First version December 2015 - Last revision May 16, 2018

## Abstract

Existence of non-trivial cycles in the 3x + 1 sequence is still unknown. It has already been proven that the length of such cycles, if any exists, is at least 17 billion terms.

In this work, we show that an assumption of minimum distance between odd terms makes this minimum length much higher than this previous result. An efficient calculation technique is proposed to compute the minimum cycle length under such an assumption. This technique uses a previously-calculated cycle length and produces a potentially higher cycle length. This forms an iterative process that generates very high cycle lengths. But convergence of this iterative process is unknown.

## 1 Introduction

Let $U_0 \in \mathbb{N}, U_0 \ge 1$

The 3x + 1 sequence for $U_0$ as initial value is defined by:

$$U_{N+1} = \begin{cases} 3U_N + 1 & \text{if } U_N \text{ is odd} \\ U_N/2 & \text{if } U_N \text{ is even} \end{cases} \quad (1)$$

The conjecture states that for any positive integer $U_0$, the sequence will eventually reach the value 1 and the trivial cycle $1 \to 4 \to 2 \to 1$.

The problem is usually addressed by trying to find counterexamples or to tighten the constraints for such counterexamples:

* find a cycle different than the trivial one,

* find an initial value for which the sequence diverges, i.e. tends to infinity.

These works deal with existence of cycles and, more precisely, with the conditions under which cycles may or may not exist.

## 2 Minimum Cycle Length: What's Known

It is known that the minimum length of a non-trivial cycle, if any exists, is above 17 billion [5]. This limit was obtained the following way.

Let $(b_1, b_2, ..., b_P, c_1, c_2, ..., c_Q)$ be the set of values of a non-trivial cycle, where $P$ values are even (noted $b_i$) and $Q$ values are odd (noted $c_i$).

Apply the appropriate $3n + 1$ or $n/2$ transformation to these values. This gives the set:

$$(b_1/2, b_2/2, ..., b_P/2, 3c_1 + 1, 3c_2 + 1, ..., 3c_Q + 1)$$

The initial set and the new set contain the same values. Let's multiply the values in each set:
$$ \prod_{i=1}^{P} b_i \prod_{i=1}^{Q} c_i = \prod_{i=1}^{P} \frac{b_i}{2} \prod_{i=1}^{Q} (3c_i + 1) \qquad (2) $$

$$ 2^P = \prod_{i=1}^{Q} \left(3 + \frac{1}{c_i}\right) \qquad (3) $$

Let $m$ be the smallest odd value in the non-trivial cycle. Immediate lower and upper bounds are:

$$ \prod_{i=1}^{Q} 3 \le 2^P \le \prod_{i=1}^{Q} \left(3 + \frac{1}{m}\right) \qquad (4) $$

$$ 3^Q \le 2^P \le \left(3 + \frac{1}{m}\right)^Q \qquad (5) $$

$$ Q \log(3) \le P \log(2) \le Q \log \left(3 + \frac{1}{m}\right) \qquad (6) $$

$$ \frac{\log(3)}{\log(2)} \le \frac{P}{Q} \le \frac{\log\left(3 + \frac{1}{m}\right)}{\log(2)} \qquad (7) $$

Tests have already determined that $m > 4.54 \times 10^{18}$ [4][6]. The corresponding lower and upper bounds can be numerically calculated. These values are shown in Equation 8.

$$ \begin{aligned} \frac{\log(3)}{\log(2)} &= 1.5849625007211561814537389 \\ \frac{\log\left(3 + \frac{1}{m}\right)}{\log(2)} &= 1.5849625007211561815596636 \end{aligned} \qquad (8) $$

Now the idea is to find the closest *Farey pair* that contains both the lower and upper bounds. This can be done with a simple program. The obtained values are:

$$ \begin{aligned} \text{Farey, low} &= 1.584962500721156181431426806 \\ \frac{\log(3)}{\log(2)} &= 1.58496250072115618153738943 \\ \text{Farey, median} &= 1.584962500721156181455956187 \\ \frac{\log\left(3 + \frac{1}{m}\right)}{\log(2)} &= 1.584962500721156181559663689 \\ \text{Farey, up} &= 1.584962500721156181837818673 \end{aligned} \qquad (9) $$

The corresponding fractions are:

$$ \frac{9\,809\,721\,694}{6\,189\,245\,291} < \frac{P}{Q} < \frac{630\,138\,897}{397\,573\,379} \qquad (10) $$

So the most "economical" value for $P/Q$ is the median of the Farey interval:

$$ \frac{9\,809\,721\,694 + 630\,138\,897}{6\,189\,245\,291 + 397\,573\,379} = \frac{10\,439\,860\,591}{6\,586\,818\,670} \qquad (11) $$

And the minimum length for a non-trivial cycle is:

$$ P + Q \ge 10\,439\,860\,591 + 6\,586\,818\,670 = 17\,026\,679\,261 \qquad (12) $$

and that cycle has at least $Q = 6\,586\,818\,670$ odd terms.
Note: it is also very easy to verify a previous result [5]: the minimum length for a cycle whose minimum value is $2^{1000}$ is:

$$ 
\begin{aligned}
& 17223898570360623838998548995391166495 \\
& 399882592603233581973777962889089997304035223866014023925 \\
& 657945536860740172893628206893866847256040164553474790827
\end{aligned} 
\quad (13) 
$$

which is $1.7223 \times 10^{151}$, where the paper mentioned $3.45 \times 10^{150}$.

### 3 Introducing Distance Between Odd Values

In Equation 4 an approximation is done: the minimum value $m$ is used in place of each odd value.

The upper bound can be made more accurate by taking into account the fact that odd values are all different and obviously separated from each other by at least 2.

Let's note $p$ the minimum distance between any two odd values in a cycle. This leads to the following formula:

$$ 3^Q \le 2^P \le \prod_{i=0}^{Q-1} \left( 3 + \frac{1}{m + pi} \right) \quad (14) $$

$$ \frac{\log(3)}{\log(2)} \le \frac{P}{Q} \le \frac{1}{Q \log(2)} \log \prod_{i=0}^{Q-1} \left( 3 + \frac{1}{m + pi} \right) \quad (15) $$

The value of the upper bound can be calculated the naive, iterative way. For $m = 5.76 \times 10^{18}$ [6], $Q = 6586818670$ and $p = 2$ this computation takes 30 minutes to one hour using the FPFR library [2] on a modest personal processor. However, the resulting upper bound does not lead to a higher minimum cycle length (see in Equation 22 for data).

Computing time is also an issue. Indeed the conjecture is assumed to be true, so much higher values of $Q$ are to be considered. So this iterative multiplication technique is not really usable and a much faster technique is needed, is possible with a computing time less independent from $Q$, $m$ and $p$.

### 4 Calculation with the Gamma Function

Let's get back to Equation 15:

$$ \frac{\log(3)}{\log(2)} \le \frac{P}{Q} \le \frac{1}{Q \log(2)} \log \prod_{i=0}^{Q-1} \left( 3 + \frac{1}{m + pi} \right) $$

And let's focus on the upper bound and in particular on the log of the big product, noted $L(Q, m, p)$:

$$ L(Q, m, p) = \log \prod_{i=0}^{Q-1} \left( 3 + \frac{1}{m + pi} \right) = \log \prod_{i=0}^{Q-1} (3m + 1 + 3pi) - \log \prod_{i=0}^{Q-1} (m + pi) \quad (16) $$

According to Wikipedia [1], the product of terms of an arithmetic progression with common differences $d$ is:

$$ \prod_{i=1}^{n} a_i = d^n \frac{\Gamma(a_1/d + n)}{\Gamma(a_1/d)} \quad (17) $$

Hence:
$$
\begin{align}
L(Q, m, p) &= Q \log(3p) + \log\Gamma\left(\frac{3m+1}{3p} + Q\right) - \log\Gamma\left(\frac{3m+1}{3p}\right) \nonumber \\
&\quad - Q \log(p) - \log\Gamma\left(\frac{m}{p} + Q\right) + \log\Gamma\left(\frac{m}{p}\right) \tag{18} \\
&= Q \log(3) + \log\Gamma\left(\frac{3m+1}{3p} + Q\right) - \log\Gamma\left(\frac{3m+1}{3p}\right) \nonumber \\
&\quad - \log\Gamma\left(\frac{m}{p} + Q\right) + \log\Gamma\left(\frac{m}{p}\right) \nonumber
\end{align}
$$

This expression is interesting because the MPFR library provides an efficient function for computing the log of the Gamma function with arbitrary precision [3].

Tests show that this implementation gives the exact same results than the iterative computation of the iterative multiplication approach, but in a fraction of a second instead of a little hour for $Q = 6586818670$.

# 5 Getting Below the Farey Mediant

For convenience, let's note $U(Q, m, p)$ the upper bound of $P/Q$:

$$ \frac{\log(3)}{\log(2)} \le \frac{P}{Q} \le U(Q, m, p) \qquad (19) $$

$$ U(Q, m, p) = \frac{L(Q, m, p)}{Q \log(2)} \qquad (20) $$

The results are presented with the following values:

* $m = 5 \times 2^{60} = 5764607523034234880$ [4]

* $Q = 6586818670$

Here are the obtained values for $\log(3)/\log(2)$ and the different bounds at play:

Farey, low = 1.5849625007211561814314268062509723530038066478047428

$\log(3)/\log(2) = 1.5849625007211561814537389439478165087598144076924810$

$U(Q, m, 10^{12}) = 1.5849625007211561814542530720584209158104732038115609$

Farey, mediant = 1.5849625007211561814559561877236253112156797843047347

$U(Q, m, 10^{11}) = 1.5849625007211561814572048491868099136766952836725916$ (21)

$U(Q, m, 2) = 1.5849625007211561815371615090560087897406079401861865$

$\frac{\log(3 + \frac{1}{m})}{\log(2)} = 1.5849625007211561815371615091513299901632854912379459$

Farey, up = 1.5849625007211561818378186734680744306071861013611779

The exact value of $p$ that brings the upper bound of Equation 15 below the previously-obtained Farey mediant can be found by program. Considering only multiples of 2 because the distance between two odd values is always a multiple of 2, this exact value is $p = 174532627282 \approx 1.7453 \times 10^{11}$:
Farey, low = 1.5849625007211561814314268062509723530038066478047428

$log(3)/log(2) = 1.5849625007211561814537389439478165087598144076924810$

$U(Q, m, 174532627282) = 1.5849625007211561814559561877236061907119887283793972$

Farey, mediant = 1.5849625007211561814559561877236253112156797843047347

$U(Q, m, 174532627280) = 1.5849625007211561814559561877236268288964619964702012$

$$ \frac{\log\left(3 + \frac{1}{m}\right)}{\log(2)} = 1.5849625007211561815371615091513299901632854912379459 $$

Farey, up = 1.5849625007211561818378186734680744306071861013611779

(22)

Note that this exact distance value is of no real interest in this paper. In the rest of the paper, the value $p = 10^{12}$ is used.

# 6 Iterative Calculation of the Minimum Length

The direct consequence of getting below the Farey mediant is that a new, higher value for $Q$ is obtained. Hence the minimum cycle length gets higher.

And this process can be repeated: A higher value for $Q$ is injected in Equation 15, which leads to a narrower Farey pair. This gives an even higher value for $Q$, which can be injected again in Equation 15, etc.

The sequence of values for $Q$ is presented in Table 1. Note that the first value is the initialization with $p = 0$.

# 7 Conclusion

There is no sign that the proposed iterative process would stop at a particular value of $Q$. But if it does not converge, then no cycle exists under the assumption $p \ge 10^{12}$.

However this may just be another form of the $3x+1$ problem with similarly (or even more) difficult problems. Indeed the assumption $p \ge 10^{12}$ is way above what's known, and convergence of the proposed iterative process with $Q$ also have to be tackled.

# References

[1] Arithmetic progression - Product. http://en.wikipedia.org/wiki/Arithmetic_progression#Product.

[2] MPFR. http://www.mpfr.org.

[3] MPFR Special Functions. http://www.mpfr.org/mpfr-current/mpfr.html#Special-Functions.

[4] Tomás Oliveira e Silva. Computational verification of the $3x+1$ conjecture. https://web.archive.org/web/20130318045112/http://www.ieeta.pt/~tos/3x+1.html.

[5] Shalom Eliahou. The $3x+1$ problem: new lower bounds on nontrivial cycle lengths. Discrete Mathematics, 118(1-3):45-56, 1993.

[6] Jeffrey C. Lagarias. The Ultimate Challenge: The $3x+1$ Problem. 2010.
<table><caption>Table 1: Sequence of values of Q for $p = 10^{12}$</caption><thead><tr><th>Iteration</th><th>Minimum Q</th></tr></thead><tbody><tr><td>0</td><td>6 586 818 670</td></tr><tr><td>1</td><td>72 057 431 991</td></tr><tr><td>2</td><td>137 528 045 312</td></tr><tr><td>3</td><td>890 638 885 193</td></tr><tr><td>4</td><td>1 643 749 725 074</td></tr><tr><td>5</td><td>2 396 860 564 955</td></tr><tr><td>6</td><td>3 149 971 404 836</td></tr><tr><td>7</td><td>3 903 082 244 717</td></tr><tr><td>8</td><td>4 656 193 084 598</td></tr><tr><td>9</td><td>5 409 303 924 479</td></tr><tr><td>10</td><td>11 571 718 688 839</td></tr><tr><td>20</td><td>1 398 396 683 579 133</td></tr><tr><td>30</td><td>11 985 484 530 117 643</td></tr><tr><td>40</td><td>74 330 983 802 537 273</td></tr><tr><td>50</td><td>397 560 349 370 386 783</td></tr><tr><td>60</td><td>5 225 419 486 637 257 521 420 827</td></tr><tr><td>70</td><td>39 957 712 860 825 006 867 994 487</td></tr><tr><td>80</td><td>74 690 006 235 012 756 214 568 147</td></tr><tr><td>90</td><td>109 422 299 609 200 505 561 141 807</td></tr><tr><td>100</td><td>144 154 592 983 388 254 907 715 467</td></tr><tr><td>125</td><td>11 282 135 875 044 327 510 184 064 564 573</td></tr><tr><td>150</td><td>386 817 433 078 330 714 992 022 377 068 049 349</td></tr></tbody></table>