The technology that you do not master, will master you.

A Bash Script To Demonstrate The Collatz Conjecture

Date/Time Permalink: 06/11/12 12:16:09 pm
Category: General

I suppose every hacker who reads Godel, Escher, Bach: An Eternal Golden Braid has the same problem: You can't read five pages without finding some new math or logic conjecture which you immediately have to stop and play with. Hey, it's kind of the whole point of the book! Being able to diddle out a quick Bash script to play with some sequence just makes it that much more interesting.

So, on page 400-402 of said work, the Collatz conjecture is introduced, also called "hailstone numbers". It's explained fully at that Wiki, but briefly you pick a number and apply the following rules indefinitely until you reach 1: If it's even, divide it by two, if it's odd, multiply it times 3 and add 1.

The conjecture is that every whole positive integer eventually reaches 1, albeit with considerable meandering along the path. The script:

#!/bin/bash

# Demonstrates the Collatz conjecture -
#     That any number will eventually boil down to 1
#     by following the formula of dividing it by 2 if
#     it is even and multiplying it by 3 and adding 1
#     if it is odd.

# http://en.wikipedia.org/wiki/Collatz_conjecture

if [ "$1" ]; then
  N=$1
else
  N=$RANDOM
fi

ORIG=$N

echo "Starting number: "$N
echo
echo $N

STEP=0

while [ "$N" -ne "1" ]
do
  if [ "$(($N % 2))" -eq "0" ]; then
    N=$(($N / 2))
  else
    N=$((($N * 3) + 1))
  fi
  echo $N
  STEP=$(($STEP + 1))
done

echo "The number $ORIG took $STEP steps."

exit 0

If you give it a numeric argument, it'll start with that; otherwise it will just use a Bash built-in $RANDOM number. You will note that there's no bounds-checking or error termination here, indicating that I have great faith in either the conjecture or the user's ability to press Ctrl-C. You can also type in a number so high that Bash can't handle it and causes a stack overflow, plunging it into negative numbers which never terminate (even if they make it low, they may loop -20, -10, -5, -14, -7, -20...). Bash can handle 64-bit integers, so logically you'd check for anything higher than 9,223,372,036,854,775,807. But there's a problem with that...

The problem is that 9,223,372,036,854,775,807 is odd, so of course it's going to multiply times 3 and add 1. And so is 9,223,372,036,854,775,805, so that's too high. And indeed, we know from the whole nature of hailstone sequences that they sometimes get much higher than their starting number before they terminate, so the script would have to check the bounds on whatever the highest number is that can't get higher in the sequence than the 64-bit limit... And proving that all numbers below N never get higher than X is a problem such that if we solved it, we might as well solve the conjecture - a feat for which Paul Erdos posted a $500 prize in his lifetime. Unclaimed.

So, yeah, I'm open for some critique on this one.

In fact, if any math geniuses drop by here, my uneducated guess regarding proving the Collatz conjecture: Has anybody thought of using a Sieve of Eratosthenes type method on this? For instance, we know that 2 terminates; since 2 terminates, all powers of 2 must also terminate. We know that 4 terminates, so all powers of 4 must also terminate. 3 terminates; does that mean that all powers of 3 must also terminate? That's not so obvious.

Yeah, I'm in over my head here.

Sorry, no solution to the Mu puzzle, keep looking...

Update Just found out that the always-intriguing Cliff Pickover has also posted about hailstone numbers.

Follow me on Twitter for an update every time this blog gets a post.
Stumble it Reddit this share on Facebook

suddenly the moon