The Collatz-O-Matic

Are you sick of having to work out the Collatz Sequence by hand? Run out of whiteboard space? Hand cramping up with all your scribbling? Then you need my latest project, the Collatz-O-Matic!:

thumb_IMG_2072_1024.jpg

Shown with LEDs spooled, ready for computation on the go

This came about because after the previous posts on Cellular Automata, I sent a link to Stephen Wolfram, he kindly emailed back and said he thought it was cool. However the email ended with: (emphasis mine)

P.S. If you’re into such things, you might enjoy http://www.wolframscience.com/nksonline/page-0895c-text

I think in all these years nobody has yet actually implemented this…

Darn it, that sounds like a challenge.

I had actually already planned out what my next project was going to be, but unfortunately my brain felt this was enough of a nifty concept to make me drop what I was doing and start sketching tag systems. After a brief dialog with my shoulder angels, I gave in.

A Post Tag System is a method of computing very similar to a Turing Machine. There’s an array of symbols, or a tape, or a queue, however you want to call it, and a simple series of operations are performed on it at each timestep.

My machine is set up to follow the Collatz conjecture, which we’ll describe shortly. Every step the following things occur:

  • 2 tags are deleted from the start of the tape
  • If the first symbol deleted was:
    • A – then write BC to the rear of the  tape
    • B – then write to the rear of the tape
    • C – then write AAA to the rear of the tape

That’s it. That simple behaviour is enough to implement the [modified] Collatz sequence below. (If the number is even, then divide by 2. If odd, then multiply by 3, add one, and divide by 2.  )

Collatz diagram v02.png

By the way, the Collatz conjecture is still an unsolved problem in mathematics. So far every positive integer tested flows to 1, but it’s not yet been formally proved that all positive integers will.

Back to the tag system! I started looking at systems with rolling balls, as Stephen Wolfram suggested. Hooking up a couple of servos to sort of sluice-gate the flow of balls from a set of hoppers is fairly doable. There are a number of ways to detect the different types of balls, but a colour sensor is probably easiest. I got some cedar spheres from the dollar store and started prototyping.

wooden balls 01.JPG

Computing in action.

Hmm… how many balls would I need? Based on wanting to calculate the Collatz sequence for each number 1 to 30, working out the maximum intermediate values for each… average ball size 23mm… let’s see…. length of the track is… Two hundred and twelve meters.

OK, perhaps a tad too ambitious for a quick project.

As an alternative strategy, I decided to use LED strip as the ‘tape’, and make a very simple interface with an arduino. Here’s how it works:

  • When the machine’s stopped, the A/B/C buttons add that symbol to the end of the tape.
  • If the tape holds only ‘A’s, ( no ‘B’s or ‘C’s), then update the numeric display at the bottom left to show the current number
  • Each step two symbols are deleted from the start of the tape, the corresponding rule lamp is lit up, and new symbols are added to the far end of the tape.
  • Clear button stops or resets the display, ‘Step’ runs one step of simulation forward (until the next number in the sequence is reached), and ‘Auto’ runs the sequence until it reaches 1.

thumb_IMG_2074_1024.jpg

Here’s the machine in action:

Fun fact, if you try and start from 27, then the machine will break! That’s because the values go up to 9,232 on the way to reaching 1. My (inefficient) code uses a byte per tag symbol, and the arduino only has ~2k of memory, so I run out of space long beforehand!

I put in some code to detect the tape running out, and here’s what it looks like after a few minutes of churning away:

thumb_IMG_2070_1024.jpg

Your modern electronics are no match for the might of the number 27.

Inside the machine is an Arduino Nano, some LEDs and switches, and a couple of meters of Adafruit Neopixels

internals.jpg

Not my finest work, but it should be reasonably sturdy

The files are up on Thingiverse here for anyone that wants to make their own:

http://www.thingiverse.com/thing:1810442

This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to The Collatz-O-Matic

  1. Pingback: The Collatz-O-Matic: a State Machine with Style! | Hackaday

  2. celticunion says:

    This wasn’t explained very well in the hack-a-day eMail, but I like whatever it is.

    Like

  3. Quick heads up – the link at the top of the page: My main site – has been taken over and is hosting malware. Please delete the link as you are doing zero service to your followers.

    My guess is that you let the domain name expire and it was taken over.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s