Typically, Collatz (or the 3x+1 problem) only applies to integer values for x, but what about non-integer x values? It has been shown that the number of steps to 1 can be computed for some non-integers, but are there more non-integers that also work?

Initial observation:

It has previously been shown that Collatz can be applied to some non-integers, specifically some rational numbers that have a power of three in their denominator. Here we will examine a second technique that will allow for applying Collatz to a different set of non-integers.

Question:

Other than the previously mentioned non-integers, are there other non-integer values that Collatz can be applied to?

Background:

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}$$

which terminates when x_i=1. One common question is, how many steps from an initial x₀ to 1. Also, of those steps, how many are 3x+1 steps (m), and how many are x/2 steps (d)?

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

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

with a new terminating condition of x_i=2^d for some non-negative integer d, where lob(x_i) is the lowest order bit of x_i.

Derivation:

In each iteration of the division-free formulation of Collatz only x_i and its lowest order bit (i.e., lob(x_i)) are needed. Thus any number that has a lowest order bit should work. Since all even numbers have a lob>1, the standard and division-free recurrences can be combined as:

$$x_{i+1}\leftarrow \{\begin{array}{cc}3x_i+\mathrm{lob}\left(x_i\right)& \mathrm{lob}\left(x_i\right)\le 1\\ x_i/\text{2}& \mathrm{lob}\left(x_i\right)>1\end{array}$$

With this modification, the finishing criteria can be returned to x_i=1, as in standard Collatz.

For integer values this recurrence will produce the same sequence as standard Collatz. However with this minor change, the recurrence also works with some non-integers.

Computing d and m

Since lob(x_i) is no longer always an integer, w is also no longer always an integer. However, the value of m is still one less than the number of non-zero bits in w, and d is still the largest element of V.

Enumeration:

The table below shows the value of the first few non-integer bits. Similarly to how integers can be expressed as a sum of non-negative powers of 2, non-integers can also be expressed by including negative powers of 2.  Thus a portion of non-integers can be uniformly sampled by picking a step size that is a power of 2 less than 1.

Exponential	Fraction	Decimal	Binary
20	1/1	1.010	1.02
2-1	1/2	0.510	0.12
2-2	1/4	0.2510	0.012
2-3	1/8	0.12510	0.0012
2-4	1/16	0.062510	0.00012

A full enumeration is also possible, using a method similar to the enumeration of rational numbers, but that is beyond the scope of this exercise.

Discussion:

The first graph below shows the number of steps to 1 versus x₀, for this modified form of Collatz. The integers are highlighted as blue ‘x’s, while the non-integer x₀ values are shown in orange.  The second graph shows similar data over a larger range of x₀ values. In the first graph there are hints of an overlapping patterns of the integers and non-integers, while the pattern is more prominent in the second graph. The code to generate these graphs is available on github.

 

The next two graphs show the same data as the first two, but with the addition of x₀ values found by sampling w, shown in green.

Conclusion:

With a small modification to the standard Collatz recurrence, it is possible to apply it to any number that can be expressed as a sum of powers of 2.

Future Questions:

Can this be extended further? Can the elements of V be non-integers? Can m or d be non-integers?  Is it possible for x₀ to be an arbitrary real?