The 3x+1 Problem

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¹⁶ have been tested.

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

Updates

The 3x+1 equation

The 3x+1 equation maps every integer onto another different integer (no integer can be mapped onto itself). I prefer to express the mapping using the python script shown in the next box.


def next (x):
    if x % 2 == 0:
        return x / 2

    return 3 * x + 1

(You can download the Python interpreter from www.python.org or Activestate). This says that if the starting integer 'x' is even (the percent sign '%' is the modulo operator, which returns the remainder after division) the next value is 'x' divided by 2, otherwise it is three times 'x' plus 1.

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]

The script to generate this list looks like


def fullSequence(x):
    ret=[x]

    while x > 1:
        x = next (x)
        ret.append (x)

    return ret

In this code fragment 'ret' is a list that starts off just containing 'x'. As the calculation is repeated the new values are appended to the list until 'x' is 1. There is a link to the source code at the bottom of this page.

A-Lists

I define the A-Lists for the integers 'm' and 'n' as the sets of n integers [a₁, a₂, ..., a_n], (a_i > 0), where ∑(a₁, a₂, ..., a_n) = m. These lists can be used to generate the members of cycles in 3x+K systems, where K = 2^m−3ⁿ.

When m = 5 and n = 3 we get the following 6 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

In this example K is 5 and we get the loops [19,31,49,19] and [23,37,29,23].

The A-Lists page explores these lists and shows how they can be used to create powerful constraints on where any additional loops might be.

The (x-1)/4 Modification

This is an idea I've been working on but which hasn't yet been incorporated into the site. 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 4 times the previous one, plus 1. 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.

As we are now working exclusively with odd numbers we can convert back to a tree using all the integers by noting that all odd numbers are of the form 2k-1. Making this transformation, x -> (x+1)/2 gives us the tree shown in the next picture.

This tree is explored on its own page.

Site 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 and 5x+1). It includes record holders for various properties (like the longest sequence) and illustrations of sections of the tree.

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.