In the XKCD comic dated 3/4/2010, the Collatz Conjecture presents the following scenario:
Well I don’t know if your friends will stop calling your or not, but I was curious about what the graph would actually look like. The graph in the comic looks like it was created with Graphviz, one of my favorite programs!
So I wrote a quick bash script to generate the approrpiate links for graphviz to interpret:
#!/bin/bash
echo "digraph \"xkcd\" {"
for NUMBER in `seq 1 100`
do
if [ $[$NUMBER % 2] -eq 0 ]; then #We are even
let OUTPUT=$NUMBER/2
else #Odd
let OUTPUT=$NUMBER*3+1
fi
echo "$NUMBER -> $OUTPUT"
done
echo "}"
So what does it really look like? Here:
There are lots of straggling links. This is of course only because I went to 100. Why not 1000? It is a little big… click Here.
Turns out with even more numbers we end up with even more isolated links, no big super chain.
If you would like to run this code for yourself, first make sure you have the graphviz package installed in your linux system. Then copy that code above into a script, say called xkcd.sh. Then run like so:
./xkcd.sh | neato -Tpng | display
Adjust as necessary.
Cool.
Note about the “little big” image: please don’t use jpeg for such things! Jpeg is for pictures. Indexed (and B/W) images, are so much better served by PNG.
Hi Kyle,
Nice use of bash and graphviz. When I looked the the graph for the set {1…1000} ints, my first thought was that enough iterations may produce a fractal – and it appears so, though the function must be extended to include complex numbers, check it out at: http://www.nathanieljohnston.com/index.php/2009/06/the-collatz-conjecture-as-a-fractal/