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

` `

When working with the odd sequences the algorithm becomes: n → (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, [a1, a2, ..., an], we can define two integers, 'n' and 'm'. 'n' is simply the number of terms in the list and 'm' is the sum:

m = ∑(a1, a2, ..., an)

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 → (3n1 + K) / 2a

where K=2^m-3^n,

For a set of 'n' a-values, [a1, a2, ..., an]. 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 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 2m−3n = 1 you will find a loop in the 3x + 1 system, for instance 22−31 gives the list [1] and the loop [1].

The calculation also works when K is negative, for instance the two examples where 2m−3n = −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,

The image on the left (below) shows the odd-tree, described on the "Observations" page. This is the 3x+1 tree after the even nodes have been collapsed.

In the diagram on the left two thirds of the odd nodes (those that aren't divisible by three) have an infinite number of immediate predecessors, each being one more than 4 times the previous one. All except the smallest are also of the form 8n+5. So, if we modify the 3x+1 equation slightly, so that numbers 'x' of the form 8n+5, map to (x-1)/4 = (2n+1) we get the tree on the right.

This tree no longer has nodes with infinite numbers of branches, instead each node has either one or two predecessors as shown in the following diagrams, which shows all odd numbers within 6 iterations of 1.

The colour scheme has been changed. Nodes of the form 8n+5 are coloured yellow, the remainder according to the value modulo 6. Every node has a yellow predecessor of the form 4n+1, so even though only 25% of numbers will be yellow they occupy a large percentage of any finite depth portion of the tree, about 60% I estimate. This tree is explored on its own page.

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 and 5x+1). 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.

(c) John Whitehouse 2011 - 2022