Typically, Collatz (or the 3x+1 problem) only applies to integer values for x, but what about non-integer values?  Does Collatz even make sense for non-integers?  Find out below.

Initial observation:

The standard Collatz problem is as follows.

Starting from an integer x₀, find the next value x_i using the recurrence:

$$x_{i+1}\leftarrow \{\begin{array}{cc}3x_i+1& x_i\text{ is odd}\\ x_i/\text{2}& x_i\text{ is even}\end{array}$$

One common question is, how many steps does it take to get from an initial number x₀ to 1? Also, of those steps, how many were 3x+1 steps (m), and how many were x/2 steps (d),

Previously, it has been shown that division-free Collatz gives the same results for the number of steps, m, and d. The division-free recurrence being,

$$x_{i+1}\leftarrow & 3x_i+\mathrm{lob}\left(x_i\right)$$

with a new terminating condition of x_i=2^k for some integer k. Where lob(x_i) is the value of the lowest order bit in the binary encoding of x_i. In this formulation, the final value for x_i will be 2^d where d is the number of division steps in standard Collatz, and m is the number of times the division free recurrence was applied to get to 2^d.

Question:

Can the rules of Collatz be extended to non-integers?

Derivation:

By expanding the non-lob terms of the recurrence gives:

$$\begin{array}{ccc}{x}_i& \leftarrow & 3x_{i–1}+\mathrm{lob}\left(x_{i–1}\right)\\ & \leftarrow & 3(3x_{i–2}+\mathrm{lob}(x_{i–2}\left)\right)+\mathrm{lob}\left(x_{i–1}\right)\\ & \leftarrow & 9x_{i–2}+3\mathrm{lob}\left(x_{i–2}\right)+\mathrm{lob}\left(x_{i–1}\right)\\ & \leftarrow & 9(3x_{i–3}+\mathrm{lob}(x_{i–3}\left)\right)+3\mathrm{lob}\left(x_{i–2}\right)+\mathrm{lob}\left(x_{i–1}\right)\\ & \leftarrow & 27x_{i–3}+9\mathrm{lob}\left(x_{i–3}\right)+3\mathrm{lob}\left(x_{i–2}\right)+\mathrm{lob}\left(x_{i–1}\right)\\ & & ···\\ & \leftarrow & 3^k{x}_{i–k}+\sum _{j_{=}}^k{3}^{i–\mathrm{j}}\mathrm{lob}\left(x_{i–j}\right)\end{array}$$

By replacing the summation with y and setting i=m, we get the simpler expression:

$$x_i\leftarrow 3^k{x}_{i–k}+y$$

Since the stopping condition is x_i=2^d, at which point i=m, the expression will be:

$$2^d=3^m+y$$

Unfortunately, this expression doesn’t have any information about d, which is needed to compute the total steps to 1. Recalling that the terminating condition is that x_m=2^d, we can replace x_m with 2^d, and add an additional 2^d to both sides. With a bit of algebraic manipulation, z can be defined as follows, which can be used to recompute x₀.

$$z=y+2^d=2^{d+1}–3^m{x}_0$$

Setting aside how to compute y, solving this expression for x₀ gives:

$$x_0=\frac{2^d–y}{3^m}$$

which curiously has a power of 3 in the denominator.

Defining w and V

In the expansion of the recurrence above, it is clear that the lob bits for each iteration are critical to this computation. Therefore it is helpful to keep track of the lob bits, by defining additional value w and vector V, which can be computed from x₀ while applying the division-free recurrence. Let v_i ∈ V be the position of the lowest order bit in x_i, and w(x₀) be the sum of the lowest order bits over the computations of division-free Collatz from x₀ to 2^d. Thus the relationship between w and V is,

$$w=\sum _{j_{=}}^m{2}^{v_j}$$

As shown in the table below, the value of w, can be computed by summing over the lob(x_i) each iteration. For x₀=33 the sum of the lowest order bits is 281,397.

	Arithmetic Region (ARi)
i	8	7	6	5	4	3	2	1	0	xi	vi	lob(xi)
0						1	0	00	01	33	0	20
1						11	0	01	00	100	2	22
2					1	001	1	00		304	4	24
3				1	1	101	0			928	5	25
4			1	01	1	000				2816	8	28
5			100	01	0					8704	9	29
6		1	101	00						26624	11	211
7		101	000							81920	14	214
8	1	0000								262144	18	218
w	1	0001	001	01	1	001	1	01	01			281397

Computing m, and d from w and V

Since w and V are so closely related, how they define m and d are similarly related. The length of V is also the number of one bits in w, which is the value of m. Similarly, d is the last element of V (also log₂ hob(x_i)).

Computing z from V

To get z from V is the summation:

$$z=\sum _{j_{=}}^m(3^{m–j}·2^{v_j})$$

Recalling that w can be defined as a sum, there is a simple method to convert the bits in w to z, but getting w back from z is more complicated. This complication comes from the lack of predictability of lob(x_i).

Enumeration:

Since z, m, and d are easily computed from V or w, we can rewrite the equation for x₀ as

$$x_0=\frac{2^{d\left(w\right)+1}–z\left(V\right(w\left)\right)}{3^{m\left(w\right)}}$$

But what happens when an arbitrary value is used for w (i.e., not just a w computed from an integer x₀)? The equivalent V has a length, which is m, and the final and largest value in V is d.

Since x₀ (along with m and d) can be computed from z, and z can be easily computed from a V vector, then by enumerating possible values of w and therefore valid z values, should also enumerate possible values of x₀ that includes non-integers.

The first graph below is m+d (i.e., steps to 1 in standard Collatz) versus the resulting x₀. The integer values of x₀ are shown with blue ‘x’s, while orange dots are non-integer x₀ values computed directly from other w values. The second graph shows the same values over a wider range of x₀ values. The code to generate these graphs is available on github.

The next graph shows the relationship between x₀ and w. The final graph shows the same values over a wider range of x₀ and w values.

Conclusion:

Through some algebraic manipulation and the definition of some new variables, yes it is possible to extend a form of Collatz to certain non-integer values and compute the number of steps it would take to to reach 1 for those non-integers.

Future Questions:

Now that some non-integers have been found where the number of steps to 1 can be computed, are there any other forms of non-integers that also work?