Wednesday, February 14, 2024

Experimental Results on the 3n+1 Conjecture

I. The Collatz Function as a Limit at Infinity

One of the reasons, which is not often discussed, for the convergence of the Collatz function[1] is that it relies upon indefinite division by fluctuating powers of two. In otherwords, if we are only allowed to divide an even number $n$ by $2^k$ for some maximal $k$ (regardless of whether said number is divisible by a greater power of two), the resulting sequence will diverge to infinity for most values of $n$.  More formally, we can represent the entire family of restricted Collatz functions as
\[ f_k(n) = \begin{cases} 3n+1, & n \equiv 1 \ (\text{mod} \ 2) \\ n-2, & n \equiv 0 \ (\text{mod} \ 2^{k+1}) \\ n/2, & \text{otherwise} \end{cases} \]
for $k \geq 1$. In the case where $n=3$ and $k=1$, the resulting divergent sequence is
\[ \{ f^i_1(3) \}_{i=0}^{\infty} = \{ 3,10,5,16,14,7,22,11,34,17,52,50,25, \ \ldots \ \} \ . \]
Given any odd argument greater than one, the iterations of this function always diverge. However, only a unique subset of the odd numbers generates the entire set of odds under repeated iteration. This subset corresponds with A045883 in OEIS[2], which has the formula
\[ \frac{(3n+1)2^n-(-1)^n}{9} \ . \]
     For $k>1$ there are increasingly more odd valued arguments which produce convergent cycles, assuming that none of the even numbers in the given sequence is divisible by $2^{k+1}$ (or the growth of the sequence falls below a certain bound). In this way, as $k$ approaches infinity the restricted function becomes equivalent to the original Collatz function.
     It would also prove interesting to see if these divergent sequences have some relation to infinite continued fractions, or nested radicals.

II. The Extended Problem

(i) A generalized Collatz function.

To settle for an exposition which only touches upon these restricted functions would be unsatisfactory at best. It was shown in the previous section how the Collatz function can be modified to produce divergent sequences, but there is a much more general function at work here. For any coprime pair of odd numbers $(a,b)$ , we define the generalized Collatz function $F$ such that
\[ F(z,n) = \begin{cases} a\cdot n \pm b, & n \equiv 1 \ (\text{mod} \ 2) \\ n/2, & n \equiv 0 \ (\text{mod} \ 2) \end{cases} \] where $z=a \pm bi$ (the use of complex numbers here is merely for notational convenience and has no further significance). The total number of coprime pairs $a,b \leq 2m-1$ is given by the formula
\[ -1+2\sum_{n=1}^m \sum_{k=1}^n \bigg\lfloor \frac{1}{\text{gcd}(2k-1, 2n-1)} \bigg\rfloor \]
which, when multiplied by two, accounts for all possible combinations including change of sign. A similar generalized Collatz function has been developed by Bouhamidi[3] who provides a thorough graph theoretic interpretation of the problem.
     Now that we have a definition of our function there is still another matter to discuss. Depending on the choice of coefficient and our initial argument, the generalized function will produce either divergent or convergent cycles. For $\text{Re}(z) > 3$ most arguments will produce divergent cycles under repeated iteration (unless $a\cdot n \pm b = 2^k$, as an example). In contrast, for $\text{Re}(z) \leq 3$ all arguments produce convergent cycles with $z=3+i$ being the only exceptional case that has a single fundamental cycle. Let us further examine the instance where $z=3+5i$. There are numerous trajectories of this function which never return to one, such as $\{ 19,62,31,98,49,152,76,38 \}$. We also have infinitely many arguments that do return to one, however. They are always numbers of the form
\[ n=\frac{2^{2k-1}-5}{3} \ . \]
This derivation can be adapted for arbitrary pairs $(a,b)$, but it is by no means comprehensive.

(ii) Singular cycles and conditional convergence.

Now we will address those values of $z$ that generate divergent sequences under repeated iteration, as well as a method for inducing them to converge. In the previous subsection we discussed how divergent cases can either avoid or return to unity, but here we will focus on how greater coefficients can form conditionally convergent cycles in general.
     Most arguments will produce divergent sequences with larger coefficients having a greater propensity for divergence. We will first expound on those limited instances which produce singular cycles, followed by a brief  discussion about the conditional convergence of the reduced generalized function.
     To begin with, any aforementioned pair $(a,b)$ such that $a\pm b=2^k$ automatically forms a cycle that converges to one. When both of these constants are positive, there are only a finite number of possible pairs ($2^{k-1}$ to be exact). When $b$ is negative, however, there are an infinite number of combinations for each $k\geq 1$. This is the first type of singular cycle. The second type involves cases where the coefficient $a=2^k-1$ and the cycle begins with $n=\pm b$. It should also be noted for $(a,b)=(3,p)$, where $p$ is an odd prime, that $n=p^k$ always ends in the cycle $\{p,4p,2p\}$. This does not hold for $a>3$.
     Now we will discuss our "method" which allows the convergence of any arbitrary argument for the generalized Collatz function. Regrettably, it requires experimental deduction of a reduction constant that is found by trial and error, with said constant being proportional to the initial argument.
     Let us begin by introducing the modified function $F_r$ and the latent sequence of odd numbers $\{\alpha_0, \alpha_1, \ ... \ \}$, where $r$ is the reduction constant.  When this constant is equal to zero our modified function is identical to the generalized Collatz function. As for the sequence of odd numbers, or alpha sequence, they satisfy the following relationship
\[ F_r^{s_0+\ldots +s_k}(z, \alpha_0) = \alpha_k \] where $\{s_0, s_1, \ ... \ \}$ is the iterative sequence over $\alpha_0$, and $s_0=0$ for all such sequences. This then implies that 
\[ F_r^{s_0+\ldots +s_k+1}(z,\alpha_0) = 2^{s_{k+1}}\alpha_{k+1} \ . \]
It should also be noted that the iterative sequence, as well as the alpha sequence, is dependent on the choice of reduction constant.
     Let us define the function more explicitly to see how the constant is applied:
\[ F_r^{s_0+\ldots +s_k}(z, \alpha_0) = \begin{cases} \text{Re}(z) \cdot \alpha_k + \text{Im}(z), & k \equiv 0 \ (\text{mod} \ r+1) \\ \alpha_k - 2(k - (r+1) \big\lfloor \frac{k}{r+1} \big\rfloor) + 1, & k \not \equiv 0 \ (\text{mod} \ r+1) \end{cases} \ . \]
Here we see that the argument is reduced in a regular manner after applying the first operation in the formula above. When the argument is even, the normal division operation is employed
\[ F_r^{k+1}(z,\alpha_0) = \frac{F_r^k(z,\alpha_0)}{2} \ \forall \ F_r^k(z,\alpha_0) \equiv 0 \ (\text{mod} \ 2) \ . \]
To give a more tangible demonstration of the function at work, let us consider an example that is experimentally known to converge. We have as our given parameters: $z=97+13i$, $\alpha_0=85$, and $r=3$. These generate the following sequence of operations
\[ \begin{matrix} 97\cdot 85+13 = 8258, \\ \\ \displaystyle\frac{8258}{2}=4129, \\ \\ 4129-1=4128, \\ \\ \displaystyle\frac{4128}{2^5}=129, \\ \\ 129-3=126, \\ \\ \displaystyle\frac{126}{2}=63, \\ \\ 63-5=58, \\ \\ \displaystyle\frac{58}{2}=29, \\ \\ 97\cdot 29+13=2826, \\ \\ \displaystyle\frac{2826}{2}=1413, \\ \\ 1413-1=1412, \\ \\ \displaystyle\frac{1412}{2^2}, \\ \\ 353-3=350, \\ \\ \displaystyle\frac{350}{2}=175, \\ \\ 175-5=170, \\ \\ \displaystyle\frac{170}{2}=85 \ . \end{matrix} \ . \]
This cycle also occurs for greater values of $\alpha_0$, such as $113$, with the same reduction constant as before.

III. Triangular Diagrams

(i) Hailstone triangles of rank $k$.

For the final section of our paper, we will discuss two families of numerical configurations the first of which we will refer to as hailstone triangles. The rank one case is derived from the consecutive sequence of odds $\{1,3,5, \ ... \ \}$ by applying the Collatz function $f$ to each odd in our list and then retaining any values
\[ \frac{f(2n-1)}{2} \equiv 1 \ (\text{mod} \ 2) \ . \]
This process is then repeated for the resulting list, and so on until it can be continued no further. As an example, the first three (rank one) triangles are as follows
\[ 1 \ , \]
\[ \begin{matrix} 1 & 3 & 5 \\ \ & 5 & \  \end{matrix} \ , \]
\[ \begin{matrix} 1 & 3 & 5 & 7 & 9 & 11 & 13 \\ \ & 5 & \ & 11 & \ & 17 & \ \\ \ & \ & \ & 17 & \ & \ & \ \end{matrix} \ . \]
     There are several integer sequences to unpack here, so for the sake of brevity we will focus only on the most pertinent ones. Each triangle has associated with it five unique values which are as follows: height, width, number of elements, mid-point, and max-point. The first three values are fairly self-explanatory, whereas the last two refer to the top and bottom element of the middle column of each triangle, respectively. The height $h(n)$ is simply $n$, and the width is $2^n-1$. The mid-point $\text{mid}(n)$ is equal to the width in this case, and the max-point $\text{max}(n)$ is given by $2\cdot 3^{n-1}-1$. Lastly, the number of elements $N(n)$ coincides with the second column in Euler's triangle (A000295 in OEIS)[4], i.e. $2^n-n-1$.
     Such results seem anticlimactic at first, however, we may further generalize this concept to rank $k$ triangles where the difference between consecutive elements in the top row of each figure is equal to $2^k$. There is a subtle difference in the construction of triangles of rank two or greater which reveals their hidden uniqueness. After applying the Collatz function, dividing out the $k$-th power of two, and retaining any odd factors from the first row, all subsequent rows are merely divided by two as was done for our rank one case. But before we can begin this process, we must first discuss the arithmetic progressions which form the top row in those figures of greater rank.
     The $j$-th term of the $k$-th arithmetic progression is given by the formula
\[ 2^k j + \frac{((-1)^{k-1}+3)2^{k-1}-1}{3} \]
for $j\geq 1$. When the Collatz function is applied to every other term in our  chosen progression, it yields an odd number multiplied by $2^k$. Now that we have defined said progressions, the next step is to further generalize our parameters from the rank one case.
     The first term of each progression coincides with the odd "Lichtenberg" numbers (entries A000975[5]/A002450[6] OEIS) such that every number occurs twice, i.e. $\{ 1,1,5,5,21,21, \ ... \ \}$. This sequence can be derived from the formula above by setting $j=1$. We can think of these as the seeds from which the separate ranks of triangles are constructed. They also represent the initial mid-point values that may be used to derive the other mid-points recursively. In order to derive these mid-points we invoke the following piecewise recurrence relation 
\[ \text{mid}_k(n+1) = \begin{cases} 2\cdot \text{mid}_k(n) + J_k, & k \equiv 1 \ (\text{mod} \ 2) \\ 4\cdot \text{mid}_k(n) + 2^k + 1, & k \equiv 0 \ (\text{mod} \ 2) \end{cases} \]
where $J_k$ is the $k$-th Jacobsthal number (A001045)[7]. The initial mid-points correspond with the formula 
\[ \text{mid}_k(1) = \frac{((-1)^{k-1} + 3)2^{k-1} -1 }{3} \ . \]
These do not always coincide with the initial max-point values. For odd ranked triangles the initial mid-point is equivalent to the initial max-point, but for triangles of even rank the initial max-point is equal to one. We can state this more explicitly as
\[ \text{max}_k(1) = \begin{cases} \text{mid}_k(1), & k \equiv 1 \ (\text{mod} \ 2) \\ 1, & k \equiv 0 \ (\text{mod} \ 2) \end{cases} \ . \]
In general for $n>1$ we have the expression
\[ \text{max}_k(n) = \begin{cases} 2\cdot 3^{n-1}-1, & k \equiv 1 \ (\text{mod} \ 2) \\ 2\cdot 3^{2n-2}-1, & k \equiv 0 \ (\text{mod} \ 2) \end{cases} \]
which is a novel result in its own right. These are listed under entry A048473 (OEIS)[8], and will be referred to as Syracuse numbers. We will return to this sequence in the next subsection.
     The last three generalized parameters are purely quantitative in nature. They include the height $h_k(n)$, the width $w_k(n)$, and the number of elements $N_k(n)$ in each figure. We can summarize them with the following expressions: 
\[ h_k(n) = \begin{cases} n, & k \equiv 1 \ (\text{mod} \ 2) \\ 2n, & k \equiv 0 \ (\text{mod} \ 2) \end{cases} \ , \]
\[ w_k(n) = \begin{cases} 2^n-1, & k \equiv 1 \ (\text{mod} \ 2) \\ \displaystyle\frac{4^n - 1}{3}, & k \equiv 0 \ (\text{mod} \ 2) \end{cases} \ , \]
and
\[ N_k(n) = \begin{cases} 2^{n+1}-n-2, & k \equiv 1 \ (\text{mod} \ 2) \\ \displaystyle\frac{2^{2n+1}-2}{3}, & k \equiv 0 \ (\text{mod} \ 2) \end{cases} \ . \]
Having established all of the necessary preliminaries we can now construct triangles of arbitrary rank for some fixed $n$ and $k$. To give an example let us consider the first two figures of rank four 
\[ \begin{matrix} 5 \\ 1 \end{matrix} \ \ \ , \ \ \ \begin{matrix} 5 & 21 & 37 & 53 & 69 \\ 1 & \ & 7 & \ & 13 \\ \ & \ & 11 & \ & \ \\ \ & \ & 17 & \ & \ \end{matrix} \]
and rank five
\[ 21 \ \ \ , \ \ \ \begin{matrix} 21 & 53 & 85 \\ \ & 5 & \ \end{matrix} \]
respectively. Here we clearly see that the structure of the triangles alternates according to the parity of the rank. Furthermore, they demonstrate that the cycles generated by the Collatz function follow a periodic spacing pattern which affects their overall length.

(ii) Syracuse arrays.

The sequence mentioned in the previous subsection which we dubbed "Syracuse numbers" will be the final focus of our paper. Their formula has already been elaborated, as well as the fact that they are the maximal elements of the hailstone triangles. What is not immediately evident, however, is how they can be used to construct more conventional triangular arrays that have a unique connection with the Collatz function.
     When we take the first $n$ terms of the Syracuse numbers and average each pair of consecutive elements, a new row of $n-1$ elements is formed underneath like so
\[ \begin{matrix} 1 & \ & 5 & \ & 17 & \ & 53 \\ \ & 3 & \ & 11 & \ & 35 & \ \\ \ & \ & 7 & \ & 23 & \ & \ \\ \ & \ & \ & 15 & \ & \ & \ \end{matrix} \]
yielding an enumerable sequence of arrays (such as $n=4$ in the example above). This can be described more explicitly using the formula
\[ T_{i+1,j} = \frac{T_{i,j}+T_{i,j+1}}{2} \] where $T_{i,j}$ is the $j$-th triangular element of the $i$-th row, and $T_{1,j}=2\cdot 3^{i-1}-1$. Another interesting property of these numbers is that when the Collatz function is applied to any element below the first row, it follows the right diagonal associated with said element, i.e. 
\[ f^2(T_{i,j}) = T_{i-1,j+1} \]
or 
\[ \frac{3\cdot T_{i,j} +1}{2}=T_{i-1,j+1} \ . \]
     Our concept can be further extended to higher order arrays which form a triangular prism in three dimensions. Each horizontal layer in this configuration is defined recursively by introducing a third parameter to our triangular elements
\[ T^{k+1}_{i,j} = 2(T^k_{i,j}+1) + T^k_{i,j+1} \] where $k$ is the layer in which the element occurs. Here is a visual example of how our previous array can be extended vertically
\[ \begin{matrix} 249 \\ \uparrow \\ \begin{matrix} 49 & \ & 149 \\ \ & 99 & \ \end{matrix} \\ \uparrow \\ \begin{matrix} 9 & \ & 29 & \ & 89 \\ \ & 19 & \ & 59 & \ \\ \ & \ & 39 & \ & \ \end{matrix} \\ \uparrow \\ \begin{matrix} 1 & \ & 5 & \ & 17 & \ & 53 \\ \ & 3 & \ & 11 & \ & 35 & \ \\ \ & \ & 7 & \ & 23 & \ & \ \\ \ & \ & \ & 15 & \ & \ & \ \end{matrix} \end{matrix} \ . \]
We can imagine these as being stacked on top of one another to form a right tetrahedral arrangement. Further note, when we apply the Collatz function twice to any element in the upper triangular layers it follows the corresponding right diagonal as it did before (or more explicitly $f^2(T_{i,j}^k)=T_{i-1,j+1}^k$).

REFERENCES

[1]  Weisstein Eric W. "Collatz problem." From Mathworld--a Wolfram web resource. (https://mathworld.wolfram.com/CollatzProblem.html)

[2]  "A045883." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A045883)

[3]  Bouhamidi, A. (2021). "On a General Syracuse Problem with Conjectures." 

[4]  "A000295." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A000295)

[5]  "A000975." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A000975)

[6]  "A002450." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A002450)

[7]  "A001045." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A001045)

[8]  "A048473." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A048473)



02-20240214 by JRWheat

Experimental Results on the 3n+1 Conjecture

I. The Collatz Function as a Limit at Infinity One of the reasons, which is not often discussed, for the convergence of the Collatz functi...