Introduction
The 3x+1 problem is one I find interesting as it is based on some rather simple arithmetic but generates some very interesting questions.
The 3x+1 equation appears to connect all the positive integers into a tree rooted on the cycle [4, 2, 1, 4]. No-one has been able to find any positive integers that aren't in this tree, even though all numbers up to about 10^[16] have been tested, or probably more by now, see the link below.
A full description of the problem and the current records for various properties of the equation can be found at http://www.ericr.nl/wondrous/index.html and www.cecm.sfu.ca/organics/papers/lagarias/.
The Algorithm
The 3x+1 algorithm maps every integer onto another different integer (no integer can be mapped onto itself).
If the starting integer 'x' is even the next value is 'x' divided by 2, otherwise it is three times 'x' plus 1. You can see this (implemented in javascript) in the "NextRaw" function in the code attached to this page.
To generate the sequence based on a particular number you take the result of this operation and feed it back into the equation until the result is '1'. For example, if we start with 29 and keep applying this function we get the sequence [29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Try it:
Most of the subsequent discussion on these pages involves the abbreviated sequence where only the odd numbers are displayed. If n¬1 and n¬2 are consecutive members of this odd sequence they they are related by the expression:
n2 = (3 × n1 + 1) / 2a.
Where 'a' is an integer (≥1), which will come in useful later when we look at creating equations that will identify the identity of any loops within this system.
See the "odd" sequence generated by
A-lists
When working with the odd sequences the algorithm becomes: n{RA}(3n+1)/2^a, which replaces the conditional part of the iteration with a new variable 'a'. The route taken by a number as it converges on 1 can be represented by a list of 'a' values.
See an example:
For a set of a‐values, [a¬1,a¬2,…,a¬n], we can define two integers, 'n' and 'm'. 'n' is simply the number of terms in the list and 'm' is the sum:
m=∑(a¬1,a¬2,…a¬n)
More interestingly, if we pick an arbitrary sequence of 'a', values we can use it to generate a loop in the more generic iteration
n{RA}(3n¬1+K)/2^a
where K=2^m-3^n,
For a set of 'n' a-values, [a¬1,a¬2,…,a¬n] we can calculate a seed value:
where S=3^[n-1]+(3^[n-2]*2^[a1])+(3^[n-3]*2^[a1+a2])+…+2^[a1+a2+...+a(n-1)]
Which we can then feed into the iteration to generate a loop.
Try it, enter some 'a' values:
If you use the default values in the interactive element above you will generate the cycle [19,31,49] in the 3x+5 system. There is another cycle in this system that can be generated using the A‐list [1,2,2]. In fact, when m=5 and n=3 there are 6 possible A-lists (shown with the associated values).
[1, 1, 3] = 19 [1, 2, 2] = 23 [1, 3, 1] = 31 [2, 2, 1] = 37 [3, 1, 1] = 49 [2, 1, 2] = 29
Examining these you can see that the loops are generated by cycling the members of these lists, so the six A‐lists generate 2 loops.
These lists are explored in detail on the A-lists page, where I will show that they can be used to prove that a systematic search for loops in the 3x+1 system is doomed to failure.
Another interesting consequence is that if you can find a solution for 2^m-3^n=1 you will find a loop in the 3x+1 system, for instance 2^2-3^1 gives the list [1] and the loop [1].
The calculation also works when K is negative, for instance the two examples where 2^m-3^n=−1, (1,1) and (3,2) lead to loops in the negative domain, [-1] and [-5,-7]. You can generate these using the interactive elements above with negative seeds.
Unfortunately Catalan's Conjecture, among other things, shows that there are no other solutions to 2^m-3^n=1, so that route is closed. That doesn't, though, prove that there aren't any other loops, it just rules out the most obvious route to finding them.
organisation
The remainder of this site concentrates on the odd numbers. This transformation can be made because every even number is a power of two times an odd number. Once we encounter an even number we can keep on dividing by two until we reach the root odd number. We can therefore represent the infinite set [n, 2n, 4n, 8n, ...] by just 'n'.
There are two main sections:
The first, called "Observations" discusses a number of empirical observations of the system (and related ones like 3x+5). It includes record holders for various properties (like residues the longest sequence) and illustrations of sections of the tree, such as this glide tree example.
Residues also have their own page where the structure of the residue distribution is analysed.
The second part called "Analysis" explores the possibility of identifying loops algorithmically by looking for solutions to particular equations.
There are also some Python code samples which can be used to generate the odd sequences and the colour information and vector lengths used to draw some of the diagrams found on this site.