onezero

Introduction

Consider the following rule that maps a given positive integer n to another: if n is even, the next integer is n/2; if n is odd, the next integer is 3n+1. Starting at an arbitrary integer, we can repeatedly apply the rule to obtain a sequence of integers. For example: 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

It has been conjectured that all integers eventually yield a 1. The “Collatz problem”, also known as the “3x+1” problem, is to determine whether the conjecture is true. The conjecture has been verified by computer up to 5.6*10¹³. (See the table of contents at the sci.math FAQ and follow the link to “Unsolved Problems.”)

One day, Roddy Collins was showing me the Fractint package. Fractint is a package for generating images of fractals and fractal-like structures. Fractint has its own programming language, as well as a huge number of options for doing things like manipulating images and controlling parameters. The main operation in the programming language is to repeat a certain region of code until some termination condition is reached. The color or intensity at a given pixel corresponds to how many times the loop was iterated for the object that corresponds to the pixel.

This reminded me of the Collatz problem, and I wondered whether we could use Fractint to draw a picture of the Collatz problem. I thought it would be neat to use the same kind of spiral pattern that has sometimes been used to graphically display prime numbers:

 . . .  27  26  25
12  11  10   9  24
13   2   1   8  23
14   3   X   7  22
15   4   5   6  21
16  17  18  19  20

(The X in the above is meant to make the middle easy to spot.)

If we assign each spot a 0 if the number is composite, and a 1 if the number is prime, then we get:

 . . .   0   0   0
 0   1   0   0   0
 1   0   0   0   1
 0   1   X   1   0
 0   0   1   0   0
 0   1   0   1   0

This can be turned into an image by using, say, white for 0, and black for 1. Then we can look for patterns, taking advantage of the pattern recognition machinery in our eyes and brains.

We can do the same thing for the Collatz problem. Given an integer n, the point corresponding to n in the image has an intensity that is a logarithmic function of the number of steps until n‘s Collatz sequence reaches 1.

The Image

After some hacking in Fractint’s programming language, Roddy and I got Fractint to make the image we wanted. The image is a rectangle because the image was taken from a rectangular screen. The smallest dimension of the image is 480, so the central 480 by 480 square shows the “Collatz intensities” for the integers 1 to 480²-1=230399. I make no guarantees about the correctness of this image! Web browsers might scale it. Here’s the image.

Some structure is evident in the image. It might be interesting to try to relate this structure to the Collatz problem’s rule from which the image is derived. A 3-dimensional version of the image might also be interesting.

Fractint Code

Here is the Fractint code. (This code is for Fraction version 19.6 or later.)

Collatz() { ;
  ; Spiral showing number of iterations for Collatz
  ; termination.   For spiral info, see p99 of
  ; "Concrete Mathematics" by Graham, Patashnik,
  ; and Knuth (first edition).
  centerx = floor(real(scrnmax) / 2)
  centery = floor(imag(scrnmax) / 2)
  x = real(scrnpix) - centerx
  y = imag(scrnpix) - centery
  ax = abs(x), ay = abs(y)
  if (ax &gt ay)
     k = ax
  else
     k = ay
  endif
  s = (-1)^(x&lty)               ; sign
  z = 4*k*k + s * (2*k+x+y)      ; starting integer
  :
  if ((2*floor(z/2)) == z)
    z = z/2
  else
    z = 3*z+1
  endif
  z != 1
}

Related Web Pages

Abstract from Lagarias’s paper The 3x+1 problem and its Generalizations, The American Mathematical Monthly, Volume 92, 1985, 3-23.

Image Showing the Running Time of Euclid’s GCD Algorithm Using Color as a Function of X and Y

The Collatz Problem entry at Wikipedia

The Collatz Problem entry at MathWorld (includes some striking images)

Unsolved Mathematics Problems entry at MathWorld