An NKS Approach to the 3n+1 Problem

Brenton Bostick
Wittenberg University

The 3n+1 problem defines a function T(n) such that if n is even, then T(n) is n/2, and if n is odd then T(n) is 3n+1. The question is: after enough applications of T, do all integers eventually iterate to 1?

A cellular automaton (CA) was built that computes iterations of the function T. The CA given in NKS has a few drawbacks that warrant a new approach: it operates in base 6, an unfamiliar base for many people, and it constantly moves to the right, which is a distracting side effect. However, there are advantages: its rule table is stated simply in one update rule and works in only 7 colors. It also computes all digits of any one iteration in parallel.

My CA works in base 2. It has 9 colors. It has a fixed “binary point” color that acts as an anchor. It takes 2 time steps to compute a bit for each iteration, but multiple bits are computed in parallel.

Visualizing the evolution of the CA has aided me in thinking about the problem as an algorithm rather than a simple function. Several results concerning the interplay of the bits of the iterates have emerged. A potential new approach to solving the problem “algorithmically” is also discussed.

Created by Mathematica  (April 20, 2004)