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)




Program Outline
Schedule
Logistics
Presentations
Gallery
Photo Scrapbook

NKS 2007
NKS 2006
NKS 2003